AVL Tree based Map
compared to AVDictionary this has
* clone is O(n) instead of O(n²)
* copy is O(n*log n) instead of O(n²)
* O(log n) malloc() calls by default and O(1) if av_map_realloc() is used
instead of O(n)
* get/add/delete is O(log n)
*
* You can add (if memory is realloced before) and remove entries while a
iterator stays valid
* copy is atomic, a failure means the dst is unchanged
*
* there are restrictions on what compare function can be used on get depending
on how the Map was created
* you can mix case sensitive and case insensitive compare with
av_map_supercmp_*
* Supports binary objects, not just strings
Still somewhat work in progress, help more welcome than complaints ;)
Signed-off-by: Michael Niedermayer <mich...@niedermayer.cc>
---
libavutil/Makefile | 3 +
libavutil/map.c | 359 ++++++++++++++++++++++++++++++++++++++
libavutil/map.h | 230 ++++++++++++++++++++++++
libavutil/tests/map.c | 190 ++++++++++++++++++++
libavutil/tree.c | 6 +-
libavutil/tree_internal.h | 28 +++
tests/fate/libavutil.mak | 4 +
tests/ref/fate/map | 27 +++
8 files changed, 842 insertions(+), 5 deletions(-)
create mode 100644 libavutil/map.c
create mode 100644 libavutil/map.h
create mode 100644 libavutil/tests/map.c
create mode 100644 libavutil/tree_internal.h
create mode 100644 tests/ref/fate/map
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 9ef118016bb..3a92748a482 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -81,6 +81,7 @@ HEADERS = adler32.h
\
replaygain.h \
ripemd.h \
samplefmt.h \
+ map.h \
sha.h \
sha512.h \
spherical.h \
@@ -173,6 +174,7 @@ OBJS = adler32.o
\
rc4.o \
ripemd.o \
samplefmt.o \
+ map.o \
side_data.o \
sha.o \
sha512.o \
@@ -290,6 +292,7 @@ TESTPROGS = adler32
\
random_seed \
rational \
ripemd \
+ map \
sha \
sha512 \
side_data_array \
diff --git a/libavutil/map.c b/libavutil/map.c
new file mode 100644
index 00000000000..00dd5a1bd39
--- /dev/null
+++ b/libavutil/map.c
@@ -0,0 +1,359 @@
+/*
+ * Copyright (c) 2025 Michael Niedermayer
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <inttypes.h>
+#include <string.h>
+
+#include "avassert.h"
+#include "avstring.h"
+#include "error.h"
+#include "mem.h"
+#include "map.h"
+
+#include "tree_internal.h" // For improved readability with AVTreeNode, do NOT
touch AVTreeNode internals
+
+typedef struct{
+ AVMapEntry map_entry;
+ uint8_t treenode_and_keyvalue[0];
+} AVMapInternalEntry;
+
+struct AVMap{
+ AVMapCompareFunc cmp_keyvalue;
+ AVMapCopyFunc copy;
+ AVMapFreeFunc freef;
+ int count;
+ int deleted;
+ int next; ///< index of entry in root array after all
used entries
+ unsigned internal_entries_len;
+ AVTreeNode *tree_root;
+ AVMapInternalEntry *internal_entries;
+};
+
+static uint8_t deleted_entry;
+
+static inline int internal_entry_len(AVMapInternalEntry *I) {
+ return (I->map_entry.keylen + I->map_entry.valuelen + sizeof (*I) +
sizeof(AVTreeNode) - 1) / sizeof (*I) + 1;
+}
+
+static inline AVTreeNode * internal_treenode(AVMapInternalEntry *I)
+{
+ return (AVTreeNode *)I->treenode_and_keyvalue;
+}
+
+static inline uint8_t * internal_key(AVMapInternalEntry *I)
+{
+ return I->treenode_and_keyvalue + sizeof(AVTreeNode);
+}
+
+static inline uint8_t * internal_value(AVMapInternalEntry *I)
+{
+ return I->treenode_and_keyvalue + sizeof(AVTreeNode) + I->map_entry.keylen;
+}
+
+static inline AVMapInternalEntry * keyvalue2internal(const uint8_t *keyvalue)
+{
+ return (AVMapInternalEntry*)(keyvalue - offsetof(AVMapInternalEntry,
treenode_and_keyvalue) - sizeof(AVTreeNode));
+}
+
+int av_map_strcmp_keyvalue(const char *a, const char *b)
+{
+ int v = strcmp(a,b);
+ if(!v)
+ v = strcmp(a + strlen(a) + 1, b + strlen(a) + 1); // please optimize
this dear compiler, we know the strlen after strcmp()
+ return v;
+}
+
+int av_map_supercmp_key(const char *a, const char *b)
+{
+ int v = av_strcasecmp(a,b);
+ if (!v)
+ v = strcmp(a,b);
+
+ return v;
+}
+
+int av_map_supercmp_keyvalue(const char *a, const char *b)
+{
+ int v = av_map_supercmp_key(a,b);
+ if (!v)
+ v = strcmp(a + strlen(a) + 1, b + strlen(a) + 1);
+
+ return v;
+}
+
+AVMap *av_map_new(AVMapCompareFunc cmp_keyvalue, AVMapCopyFunc copy,
AVMapFreeFunc freef)
+{
+ AVMap *s = av_mallocz(sizeof(*s));
+ if (!s)
+ return NULL;
+
+ s->cmp_keyvalue = cmp_keyvalue;
+ s->copy = copy;
+ s->freef = freef;
+
+ return s;
+}
+
+const AVMapEntry *av_map_get_multiple(const AVMap *s, const AVMapEntry *prev,
const char *keyvalue, int (*cmp)(const void *keyvalue, const void *b))
+{
+ if (prev) {
+ void *next_node[2] = { NULL, NULL };
+ void *prev_keyvalue = av_tree_find2(s->tree_root, prev->key,
s->cmp_keyvalue, next_node, 2);
+ av_assert2(prev_keyvalue);
+ if (!next_node[1] || cmp(next_node[1], keyvalue))
+ return NULL;
+
+ keyvalue = next_node[1];
+ } else {
+ void *next_node[4] = { NULL, NULL, NULL, NULL };
+ keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, next_node, 4);
+ if (next_node[2]) // If we have a leftmost equal keyvalue, use it
instead
+ keyvalue = next_node[2];
+ }
+
+ if (!keyvalue)
+ return NULL;
+
+ return &keyvalue2internal(keyvalue)->map_entry;
+}
+
+const AVMapEntry *av_map_get(const AVMap *s, const char *keyvalue, int
(*cmp)(const void *keyvalue, const void *b))
+{
+ keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, NULL, 0);
+
+ if (!keyvalue)
+ return NULL;
+
+ return &keyvalue2internal(keyvalue)->map_entry;
+}
+
+int av_map_realloc(AVMap *s, int extra_elements, int extra_space) {
+ int64_t advance = extra_elements + (extra_space +
(int64_t)extra_elements*(sizeof(*s->internal_entries) + sizeof(AVTreeNode) -
1)) / sizeof(*s->internal_entries);
+
+ if (advance > (INT32_MAX - s->next) / sizeof(AVMapInternalEntry))
+ return AVERROR(ENOMEM);
+
+ AVMapInternalEntry *new_root = av_fast_realloc(s->internal_entries,
&s->internal_entries_len, (s->next + advance) * sizeof(AVMapInternalEntry));
+
+ if (!new_root)
+ return AVERROR(ENOMEM);
+
+ if (new_root != s->internal_entries) {
+ if (s->tree_root) {
+ AVTreeNode *new_tree_root = s->tree_root -
internal_treenode(s->internal_entries) + internal_treenode(new_root);
+ av_tree_move(new_tree_root, s->tree_root, new_root,
s->internal_entries);
+ s->tree_root = new_tree_root;
+ }
+
+ for(int i = 0; i<s->next; i++) {
+ if (new_root[i].map_entry.key != &deleted_entry) {
+ new_root[i].map_entry.key = internal_key (new_root + i);
+ new_root[i].map_entry.value = internal_value(new_root + i);
+ }
+ i += internal_entry_len(new_root + i) - 1;
+ }
+ s->internal_entries = new_root;
+ }
+ return advance;
+}
+
+int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int
valuelen, int flags)
+{
+ av_assert2(keylen || valuelen); // patch welcome but how would the compare
function compare a len=0 element without knowing it is a len 0 element
+
+ int advance = av_map_realloc(s, 1, keylen + valuelen);
+ if (advance < 0)
+ return advance;
+
+ AVMapEntry *entry = &s->internal_entries[s->next].map_entry;
+ AVTreeNode *next = internal_treenode(s->internal_entries + s->next);
+ memset(next, 0, sizeof(*next));
+ entry->keylen = keylen;
+ entry->valuelen= valuelen;
+ entry->key = internal_key (s->internal_entries + s->next);
+ entry->value = internal_value(s->internal_entries + s->next);
+ memcpy(entry->key , key , keylen);
+ memcpy(entry->value, value, valuelen);
+
+ void *elem = av_tree_insert(&s->tree_root, entry->key, s->cmp_keyvalue,
&next);
+ int ret = 1;
+ if (elem != entry->key && elem) {
+ av_assert2(next);
+ //we assume that new entries are more common than replacements
+ if (flags & AV_MAP_REPLACE) {
+ ret = av_map_del(s, entry->key, s->cmp_keyvalue, flags);
+ av_assert2(ret == 1);
+ elem = av_tree_insert(&s->tree_root, entry->key, s->cmp_keyvalue,
&next);
+ av_assert2(elem == entry->key || !elem);
+ ret = 2;
+ } else
+ return 0; //entry already in the map
+ }
+ av_assert2(!next);
+ av_assert2(s->tree_root);
+ s->next += advance;
+ s->count++;
+
+ return ret;
+}
+
+int av_map_del(AVMap *s, const char *keyvalue, int (*cmp)(const void
*keyvalue, const void *b), int flags)
+{
+ uint8_t *old_keyvalue;
+ AVTreeNode *next = NULL;
+
+ if (cmp != s->cmp_keyvalue) {
+ // The user asks us to remove a entry with a compare function
different from the one used to build the map
+ // we need to do 2 calls here, first with the users compare to find
the entry she wants to remove
+ // and then to remove it while maintaining the correct order within
the map
+ old_keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, NULL, 0);
+ if (!old_keyvalue)
+ return 0;
+
+ av_tree_insert(&s->tree_root, old_keyvalue, s->cmp_keyvalue, &next);
+ av_assert2(next);
+ } else {
+ av_tree_insert(&s->tree_root, (char*)keyvalue, s->cmp_keyvalue, &next);
+ if (!next)
+ return 0;
+ old_keyvalue = next->elem; //TODO add a API to av_tree() to return the
elem of a AVTreeNode
+
+ }
+ AVMapInternalEntry *internal_entry = keyvalue2internal(old_keyvalue);
+ internal_entry->map_entry.key = &deleted_entry;
+
+ s->count--;
+ s->deleted++;
+
+ if ((flags & AV_MAP_ALLOW_REBUILD) && s->deleted > s->count) {
+ AVMap *news = av_map_new(s->cmp_keyvalue, s->copy, s->freef);
+ if(news) {
+ int ret = av_map_copy(news, s);
+ if (ret < 0) {
+ av_map_free(&news);
+ } else {
+ if (s->freef)
+ for (int i=0; i<s->count; i++)
+ s->freef(&s->internal_entries[i].map_entry);
+ av_freep(&s->internal_entries);
+ memcpy(s, news, sizeof(*s));
+ }
+ }
+ }
+
+ return 1;
+}
+
+const AVMapEntry *av_map_iterate(const AVMap *s,
+ const AVMapEntry *prev)
+{
+ AVMapInternalEntry *I;
+ if (prev) {
+ I = (AVMapInternalEntry*)((uint8_t*)prev -
offsetof(AVMapInternalEntry, map_entry));
+ I += internal_entry_len(I);
+ } else {
+ I = s->internal_entries;
+ }
+ while (I < s->internal_entries + s->next && I->map_entry.key ==
&deleted_entry)
+ I += internal_entry_len(I);
+
+ if (I == s->internal_entries + s->next)
+ return NULL;
+
+ return &I->map_entry;
+}
+
+int av_map_count(const AVMap *s)
+{
+ return s->count;
+}
+
+void av_map_free(AVMap **sp)
+{
+ AVMap *s = *sp;
+
+ for (int i=0; i<s->count; i++) {
+ if (s->freef)
+ s->freef(&s->internal_entries[i].map_entry);
+ }
+ av_freep(&s->internal_entries);
+ s->next =
+ s->internal_entries_len =
+ s->count = 0;
+ av_freep(sp);
+}
+
+int av_map_copy(AVMap *dst, const AVMap *src)
+{
+ const AVMapEntry *t = NULL;
+ AVMap *bak = av_memdup(dst, sizeof(*dst));
+ if (!bak)
+ return AVERROR(ENOMEM);
+ bak->internal_entries = av_memdup(bak->internal_entries,
bak->internal_entries_len);
+
+ while ((t = av_map_iterate(src, t))) {
+ int ret = av_map_add(dst, t->key, t->keylen, t->value, t->valuelen, 0);
+
+ if (ret < 0) {
+ av_free(dst->internal_entries);
+ memcpy(dst, bak, sizeof(*dst));
+ return ret;
+ }
+ }
+ av_freep(&bak->internal_entries);
+ av_free(bak);
+
+ return 0;
+}
+
+AVMap *av_map_clone(AVMap *s)
+{
+ AVMap *dst = av_memdup(s, sizeof(AVMap));
+
+ if (!dst)
+ return NULL;
+
+ dst->internal_entries = av_memdup(s->internal_entries,
s->internal_entries_len);
+
+ if (!dst->internal_entries)
+ goto err;
+
+ if (s->tree_root) {
+ dst->tree_root = s->tree_root - internal_treenode(s->internal_entries)
+ internal_treenode(dst->internal_entries);
+ av_tree_move(dst->tree_root, s->tree_root, dst->internal_entries,
s->internal_entries);
+ }
+
+ //TODO We could attempt to compact free space
+ for(int i = 0; i<s->next; i++) {
+ if (dst->internal_entries[i].map_entry.key != &deleted_entry) {
+ dst->internal_entries[i].map_entry.key = internal_key
(dst->internal_entries + i);
+ dst->internal_entries[i].map_entry.value =
internal_value(dst->internal_entries + i);
+ }
+ i += internal_entry_len(dst->internal_entries + i) - 1;
+ }
+
+ return dst;
+err:
+ if (dst) {
+ av_freep(&dst->internal_entries);
+ }
+ av_free(dst);
+ return NULL;
+}
diff --git a/libavutil/map.h b/libavutil/map.h
new file mode 100644
index 00000000000..0c660260017
--- /dev/null
+++ b/libavutil/map.h
@@ -0,0 +1,230 @@
+/*
+ * Copyright (c) 2025 Michael Niedermayer
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * Public map API.
+ */
+
+#ifndef AVUTIL_MAP_H
+#define AVUTIL_MAP_H
+
+#include <stdint.h>
+
+#include "tree.h"
+
+/**
+ * compared to AVDictionary this has
+ * clone is O(n) instead of O(n²)
+ * copy is O(n*log n) instead of O(n²)
+ * O(log n) malloc() calls by default and O(1) if av_map_realloc() is used
instead of O(n)
+ * get/add/delete is O(log n)
+ *
+ * You can add (if memory is realloced before) and remove entries while a
iterator stays valid
+ * copy is atomic, a failure means the dst is unchanged
+ *
+ * there are restrictions on what compare function can be used on get
depending on how the Map was created
+ * you can mix case sensitive and case insensitive compare with
av_map_supercmp_*
+ * Supports binary objects, not just strings
+ */
+
+enum {
+ AV_MAP_ALLOW_REBUILD = 1, ///< when removing entries rebuild the map to
reduce memory consumption, note, this invalidates previously retrieved elements
and iterate state.
+ AV_MAP_REPLACE = 2, ///< replace keyvalue if already in the map
+};
+
+typedef struct AVMapEntry {
+ uint8_t *key;
+ uint8_t *value;
+ int keylen;
+ int valuelen;
+} AVMapEntry;
+
+typedef struct AVMap AVMap;
+typedef void (* AVMapFreeFunc)(AVMapEntry *c);
+typedef void (* AVMapCopyFunc)(AVMapEntry *dst, const AVMapEntry *src, size_t
len);
+typedef int (* AVMapCompareFunc)(const void *keyvalue, const void *b);
+
+/**
+ * like strcmp() but compares concatenated keyvalues.
+ *
+ * A map initialized with this will allow duplicate keys as long as their
values differ.
+ */
+int av_map_strcmp_keyvalue(const char *a, const char *b);
+
+/**
+ * like av_map_strcmp_keyvalue() but is compatible with av_strcasecmp() and
av_map_supercmp_key.
+ *
+ * A map initialized with this will allow duplicate keys as long as their
values differ.
+ */
+int av_map_supercmp_keyvalue(const char *a, const char *b);
+
+/**
+ * like strcmp() but is compatible with av_strcasecmp().
+ *
+ * A map initialized with this will not allow duplicate keys.
+ */
+int av_map_supercmp_key(const char *a, const char *b);
+
+
+/**
+ *
+ * @param keyvalue_cmp compare function, will be passed the key + value
concatenated.
+ * it must form a strict total order on all elements you
want to store. each key-value pair
+ * can only occur once. Though there can be multiple
values for the same key. IF this function
+ * treats them as different.
+ *
+ * @param freef receives a AVMapEntry and should free any resources except the
AVMapEntry->key/value pointer itself
+ * for flat structs like strings, this is simply NULL
+ *
+ * Key Value compaibility
+ * av_map_supercmp_keyvalue X!=x X!=x av_map_supercmp_key,
av_strcasecmp, (trucated av_strcasecmp)
+ * av_map_supercmp_key X!=x av_strcasecmp, (trucated
av_strcasecmp)
+ * av_strcasecmp X==x truncation
+ *
+ * av_map_strcmp_keyvalue X!=x X!=x strcmp, truncation
+ * strcmp X!=x truncation
+ *
+ *
+ */
+AVMap *av_map_new(AVMapCompareFunc keyvalue_cmp, AVMapCopyFunc clone,
AVMapFreeFunc freef);
+
+/**
+ * realloc internal space to accomodate the specified new elements
+ *
+ * This can be used to avoid repeated memory reallocation.
+ *
+ * @param extra_elements number of new elements to be added
+ * @param extra_space sum of keylen and valuelen of all to be added elements
+ *
+ * @return <0 on error
+ */
+int av_map_realloc(AVMap *s, int extra_elements, int extra_space);
+
+/**
+ * Add the given entry into a AVMap.
+ *
+ * @param s Pointer AVMap struct.
+ * @param value Entry value to add to *s
+ * @param valuelen length of value
+ * @param flags 0, AV_MAP_ALLOW_REBUILD, AV_MAP_REPLACE
+ *
+ * @return 1 if the entry was added, 0 if it was already in the map,
2 if it was replaced
+ * otherwise an error code <0
+ */
+int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int
valuelen, int flags);
+
+/**
+ * Delete the given entry from a AVMap.
+ *
+ * @param s Pointer AVMap struct.
+ * @param keyvalue key or concatenated key+value
+ * @param cmp compatible compare function that comapres key or keyvalues
+ * @param flags AV_MAP_ALLOW_REBUILD or 0
+ *
+ * @return 1 if the entry was deleted, 0 if it was not found in the
map
+ * otherwise an error code <0
+ */
+int av_map_del(AVMap *s, const char *keyvalue, int (*cmp)(const void
*keyvalue, const void *b), int flags);
+
+/**
+ * Iterate over possibly multiple matching map entries.
+ *
+ * The returned entry must not be changed, or it will
+ * cause undefined behavior.
+ *
+ * @param prev Set to the previous matching element to find the next.
+ * If set to NULL the first matching element is returned.
+ * @param keyvalue Matching key or key + value
+ * @param cmp compare function, this will be passed keyvalue and the
concatenated key+value
+ * it must form a total order on all elements, that is a key can
occur more than once.
+ * But cmp2 must be a refinement of the cmp order, any
disagreement of the 2 compares
+ * must be by cmp returning equal. If this only reads the key
part of keyvalue
+ * then keyvalue can be just a key
+ *
+ * @return Found entry or NULL in case no matching entry was found in the
dictionary
+ */
+const AVMapEntry *av_map_get_multiple(const AVMap *s, const AVMapEntry *prev,
const char *keyvalue, int (*cmp)(const void *keyvalue, const void *b));
+
+/**
+ * Like av_map_get_multiple() but only returns one matching entry
+ *
+ * The returned entry cannot be used as initial prev entry for
av_map_get_multiple()
+ */
+const AVMapEntry *av_map_get(const AVMap *s, const char *keyvalue, int
(*cmp)(const void *keyvalue, const void *b));
+
+/**
+ * Iterate over a map
+ *
+ * Iterates through all entries in the map.
+ *
+ * @warning If you call any function with AV_SET_ALLOW_REBUILD set, then the
iterator is
+ * invalidated, and must not be used anymore. Otherwise av_map_add() (without
realloc) and av_map_del()
+ * can saftely be called during iteration.
+ *
+ * Typical usage:
+ * @code
+ * const AVMapEntry *e = NULL;
+ * while ((e = av_map_iterate(m, e))) {
+ * // ...
+ * }
+ * @endcode
+ *
+ * @param s The map to iterate over
+ * @param prev Pointer to the previous AVMapEntry, NULL initially
+ *
+ * @retval AVMapEntry* The next element in the map
+ * @retval NULL No more elements in the map
+ */
+const AVMapEntry *av_map_iterate(const AVMap *s,
+ const AVMapEntry *prev);
+
+/**
+ * Get number of entries in map.
+ *
+ * @param s map
+ * @return number of entries in map
+ */
+int av_map_count(const AVMap *s);
+
+/**
+ * Free all the memory allocated for an AVMap struct
+ * and all values.
+ */
+void av_map_free(AVMap **s);
+
+AVMap *av_map_clone(AVMap *s);
+
+/**
+ * Copy entries from one AVMap struct into another.
+ *
+ * @param dst Pointer to a pointer to a AVMap struct to copy into. If *dst
is NULL,
+ * this function will allocate a struct for you and put it in *dst
+ * @param src Pointer to the source AVMap struct to copy items from.
+ * @param flags Flags to use when setting entries in *dst
+ *
+ * @see when the initial dst map is empty use av_map_clone() as its faster
+ *
+ * @return 0 on success, negative AVERROR code on failure.
+ */
+
+int av_map_copy(AVMap *dst, const AVMap *src);
+
+#endif /* AVUTIL_MAP_H */
diff --git a/libavutil/tests/map.c b/libavutil/tests/map.c
new file mode 100644
index 00000000000..38f0a153e68
--- /dev/null
+++ b/libavutil/tests/map.c
@@ -0,0 +1,190 @@
+/*
+ * copyright (c) 2025 Michael Niedermayer
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <string.h>
+#include <stdio.h>
+
+#include "libavutil/avassert.h"
+#include "libavutil/avstring.h"
+#include "libavutil/mem.h"
+#include "libavutil/map.h"
+
+
+static void print_set(const AVMap *s)
+{
+ const AVMapEntry *t = NULL;
+ while ((t = av_map_iterate(s, t)))
+ printf("%s=%s %d,%d ", t->key, t->value, t->keylen, t->valuelen);
+ printf("\n");
+}
+
+int main(void)
+{
+ void *our_cmp[] = {
+ strcmp,
+ av_map_strcmp_keyvalue,
+ av_strcasecmp,
+ av_map_supercmp_keyvalue,
+ av_map_supercmp_keyvalue,
+ };
+ void *our_subcmp[] = {
+ strcmp,
+ strcmp,
+ av_strcasecmp,
+ av_map_supercmp_key,
+ av_strcasecmp,
+ };
+
+ for (int settype=0; settype<3; settype++) {
+ AVMap *set = av_map_new(our_cmp[settype], NULL, NULL);
+
+ printf("testing empty set\n");
+
+ const AVMapEntry *e = av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(e == NULL);
+
+ e = av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(e == NULL);
+
+ int ret = av_map_del(set, "foo", our_subcmp[settype], 0);
+ av_assert0(ret == 0);
+
+ print_set(set);
+
+ printf("testing 1-set\n");
+
+ ret = av_map_add(set, "foo", 4, "bar", 4, 0);
+ av_assert0(ret == 1);
+
+ ret = av_map_add(set, "foo", 4, "bear", 5, 0);
+ av_assert0(ret == ((int[]){0,1,0})[settype]);
+
+ e = av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype == 1) {
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar"));
+ } else {
+ av_assert0(!strcmp(e->value, "bar"));
+ }
+
+ ret = av_map_add(set, "foo", 4, "bear", 5, AV_MAP_REPLACE);
+ av_assert0(ret == 2);
+
+ e = av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype == 1) {
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar"));
+ } else {
+ av_assert0(!strcmp(e->value, "bear"));
+ }
+
+ e = av_map_get_multiple(set, NULL, "foo", our_subcmp[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype == 1) {
+ av_assert0(!strcmp(e->value, "bar"));
+ } else {
+ av_assert0(!strcmp(e->value, "bear"));
+ }
+ e = av_map_get_multiple(set, e, "foo", our_subcmp[settype]);
+ if (settype == 1) {
+ av_assert0(!strcmp(e->key, "foo"));
+ av_assert0(!strcmp(e->value, "bear"));
+ } else {
+ av_assert0(e == NULL);
+ }
+
+ ret = av_map_del(set, "foo", our_subcmp[settype], 0);
+ av_assert0(ret == 1);
+
+ e = av_map_get(set, "foo", our_subcmp[settype]);
+ if (settype == 1) {
+ av_assert0(!strcmp(e->key, "foo"));
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar"));
+ } else {
+ av_assert0(e == NULL);
+ }
+
+ ret = av_map_del(set, "foo", our_subcmp[settype], 0);
+ av_assert0(ret == ((int[]){0,1,0})[settype]);
+
+
+ print_set(set);
+
+ printf("testing n-set\n");
+ unsigned r = 5;
+ int histogram[256] = {0};
+ for(int i=0; i<1000; i++) {
+ r = r*123 + 7;
+ unsigned char str[3] = {0};
+ str[0] = r;
+ ret = av_map_add(set, str, 2, str, 2 ,0);
+ if (i < 128) {
+ if (settype != 2) {
+ av_assert0(ret == 1);
+ } else {
+ av_assert0(ret == !histogram[av_toupper(str[0])]);
+ histogram[av_toupper(str[0])] = 1;
+ }
+ } else {
+ av_assert0(ret == 0);
+ }
+ printf("%d", ret);
+ }
+ printf("\n");
+
+ r = 5;
+ for(int i=0; i<1000; i++) {
+ r = r*123 + 7;
+ char str[3] = {0};
+ str[0] = r;
+ e = av_map_get(set, str, our_subcmp[settype]);
+ if (settype != 2) {
+ av_assert0(!strcmp(e->key, str));
+ av_assert0(!strcmp(e->value, str));
+ } else {
+ av_assert0(!av_strcasecmp(e->key, str));
+ av_assert0(!av_strcasecmp(e->value, str));
+ }
+ e = av_map_get_multiple(set, NULL, str, our_subcmp[settype]);
+ if (settype != 2) {
+ av_assert0(!strcmp(e->key, str));
+ av_assert0(!strcmp(e->value, str));
+ } else {
+ av_assert0(!av_strcasecmp(e->key, str));
+ av_assert0(!av_strcasecmp(e->value, str));
+ }
+ ret = av_map_add(set, str, 2, str, 2, 0);
+ av_assert0(ret == 0);
+
+ str[1]='x';
+
+ e = av_map_get(set, str, our_subcmp[settype]);
+ av_assert0(e == NULL);
+ e = av_map_get_multiple(set, NULL, str, our_subcmp[settype]);
+ av_assert0(e == NULL);
+ }
+ print_set(set);
+
+ av_map_free(&set);
+ av_assert0(!set);
+ }
+
+ return 0;
+}
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 09c55f6752d..5cffab4563c 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -24,11 +24,7 @@
#include "mem.h"
#include "tree.h"
-typedef struct AVTreeNode {
- struct AVTreeNode *child[2];
- void *elem;
- int state;
-} AVTreeNode;
+#include "tree_internal.h"
const int av_tree_node_size = sizeof(AVTreeNode);
diff --git a/libavutil/tree_internal.h b/libavutil/tree_internal.h
new file mode 100644
index 00000000000..6207c321a8e
--- /dev/null
+++ b/libavutil/tree_internal.h
@@ -0,0 +1,28 @@
+/*
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_TREE_INTERNAL_H
+#define AVUTIL_TREE_INTERNAL_H
+
+typedef struct AVTreeNode {
+ struct AVTreeNode *child[2];
+ void *elem;
+ int state;
+} AVTreeNode;
+
+#endif /* AVUTIL_TREE_INTERNAL_H */
diff --git a/tests/fate/libavutil.mak b/tests/fate/libavutil.mak
index 6bf03b24386..b7df499a29c 100644
--- a/tests/fate/libavutil.mak
+++ b/tests/fate/libavutil.mak
@@ -74,6 +74,10 @@ FATE_LIBAVUTIL += fate-dict
fate-dict: libavutil/tests/dict$(EXESUF)
fate-dict: CMD = run libavutil/tests/dict$(EXESUF)
+FATE_LIBAVUTIL += fate-map
+fate-map: libavutil/tests/map$(EXESUF)
+fate-map: CMD = run libavutil/tests/map$(EXESUF)
+
FATE_LIBAVUTIL += fate-encryption-info
fate-encryption-info: libavutil/tests/encryption_info$(EXESUF)
fate-encryption-info: CMD = run libavutil/tests/encryption_info$(EXESUF)
diff --git a/tests/ref/fate/map b/tests/ref/fate/map
new file mode 100644
index 00000000000..3333052a9f8
--- /dev/null
+++ b/tests/ref/fate/map
@@ -0,0 +1,27 @@
+testing empty set
+
+testing 1-set
+
+testing n-set
+1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2
~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2
�=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2
�=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2
�=� 2,2 �=� 2,2 b=b 2,2 = 2,2 �=� 2,2 9=9 2,2 j=j 2,2 �=� 2,2
�=� 2,2 Q=Q 2,2 �=� 2,2 M=M 2,2 = 2,2 �=� 2,2 �=� 2,2 %=% 2,2
�=� 2,2 = 2,2 �=� 2,2 }=} 2,2 = 2,2 �=� 2,2 �=� 2,2 U=U 2,2
�=� 2,2 �=� 2,2 = 2,2 �=� 2,2 &=& 2,2 I=I 2,2 = 2,2 �=� 2,2
�=� 2,2 a=a 2,2 �=� 2,2 �=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2
�=� 2,2 = 2,2 2=2 2,2
=
2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 = 2,2 �=� 2,2 �=� 2,2
=== 2,2 V=V 2,2 Y=Y 2,2 �=� 2,2 = 2,2 = 2,2 q=q 2,2 R=R 2,2
m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2
�=� 2,2 �=� 2,2 v=v 2,2 �=� 2,2 �=� 2,2 u=u 2,2 >=> 2,2 �=� 2,2
r=r 2,2 �=� 2,2 �=� 2,2 i=i 2,2 z=z 2,2 �=� 2,2 N=N 2,2 �=� 2,2
= 2,2 �=� 2,2 �=� 2,2 = 2,2
+=
+ 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2
�=� 2,2 = 2,2
+testing empty set
+
+testing 1-set
+
+testing n-set
+1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2
~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2
�=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2
�=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2
�=� 2,2 �=� 2,2 b=b 2,2 = 2,2 �=� 2,2 9=9 2,2 j=j 2,2 �=� 2,2
�=� 2,2 Q=Q 2,2 �=� 2,2 M=M 2,2 = 2,2 �=� 2,2 �=� 2,2 %=% 2,2
�=� 2,2 = 2,2 �=� 2,2 }=} 2,2 = 2,2 �=� 2,2 �=� 2,2 U=U 2,2
�=� 2,2 �=� 2,2 = 2,2 �=� 2,2 &=& 2,2 I=I 2,2 = 2,2 �=� 2,2
�=� 2,2 a=a 2,2 �=� 2,2 �=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2
�=� 2,2 = 2,2 2=2 2,2
=
2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 = 2,2 �=� 2,2 �=� 2,2
=== 2,2 V=V 2,2 Y=Y 2,2 �=� 2,2 = 2,2 = 2,2 q=q 2,2 R=R 2,2
m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2
�=� 2,2 �=� 2,2 v=v 2,2 �=� 2,2 �=� 2,2 u=u 2,2 >=> 2,2 �=� 2,2
r=r 2,2 �=� 2,2 �=� 2,2 i=i 2,2 z=z 2,2 �=� 2,2 N=N 2,2 �=� 2,2
= 2,2 �=� 2,2 �=� 2,2 = 2,2
+=
+ 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2
�=� 2,2 = 2,2
+testing empty set
+
+testing 1-set
+
+testing n-set
+1111111111111111111111111111111111011101111111111111111111111111101111111111111111111011101001101111011011011001011111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2
~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2
�=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2
�=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2
�=� 2,2 �=� 2,2 = 2,2 �=� 2,2 9=9 2,2 �=� 2,2 �=� 2,2 Q=Q 2,2
�=� 2,2 M=M 2,2 = 2,2 �=� 2,2 �=� 2,2 %=% 2,2 �=� 2,2 = 2,2
�=� 2,2 }=} 2,2 = 2,2 �=� 2,2 �=� 2,2 U=U 2,2 �=� 2,2 �=� 2,2
= 2,2 �=� 2,2 &=& 2,2 I=I 2,2 = 2,2 �=� 2,2 �=� 2,2 �=� 2,2
�=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 = 2,2 2=2 2,2
=
2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 = 2,2 �=� 2,2 �=� 2,2
=== 2,2 V=V 2,2 �=� 2,2 = 2,2 = 2,2 R=R 2,2 = 2,2
Z=Z 2,2 .=. 2,2 !=! 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 >=> 2,2
�=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 = 2,2 �=� 2,2 �=� 2,2
= 2,2
+=
+ 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2
�=� 2,2 = 2,2
--
2.49.0
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-requ...@ffmpeg.org with subject "unsubscribe".
