[FFmpeg-devel] [PATCH] avutil/map: [WIP] Introduction

[Marton Balint]

On Sun, 20 Apr 2025, Michael Niedermayer wrote:

> Note, help is welcome.
> Time i spend on this, i cannot spend on other things
>
> Note2: i intend to push AVMap after the release unless the release
> ends up delayed alot for other reasons, theres no real reason
> to hurry here except that i seem to keep workig on it when
> people ask for some non trivial changes/improvments :)
> so dont ask, send patch yourself if its not a trivial change :))
>
> Signed-off-by: Michael Niedermayer <michael at niedermayer.cc>
> ---
> libavutil/map.h | 86 +++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 86 insertions(+)
>
> diff --git a/libavutil/map.h b/libavutil/map.h
> index 8211a05ec8d..0d3f7eab9ac 100644
> --- a/libavutil/map.h
> +++ b/libavutil/map.h
> @@ -31,6 +31,92 @@
> #include "tree.h"
> 
> /**
> + * @file
> + *
> + * AVMap is a simple and fast key -> value map.

Is this intended to be an AVDictionary replacement? Because as far as I 
remember AVDictionary keeps key insertion order, and we even rely on this 
behaviour sometimes, so an ordered-by-compare-function list is likely not 
going to work as an instant drop-in replacement...

> + *
> + * ---------- Creating AVMaps ------------------
> + *
> + * AVMap *map = av_map_alloc(strcmp, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEY, NULL, NULL);
> + *
> + * This creates a case sensitve string based map using strcmp(). It will not allow
> + * multiple entries with the same key.
> + * or
> + *
> + * AVMap *map = av_map_alloc(av_map_strcmp_keyvalue, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEYVALUE, NULL, NULL);
> + *
> + * This is like the previous, but it will allow multiple entries with the same key
> + * the difference here is that the compare function compares the value too when
> + * the key is equal.
> + * All entries in a map must always be different. So by comparing the value
> + * too we can have multiple entries with the same key
> + *
> + * The remaining 2 pointers in av_map_alloc() are for a function copying an element
> + * and one for freeing it. That is only needed for complex objects, not for strings.
> + *
> + *
> + * ----------- Adding entries -----------------
> + *
> + * av_map_add_strings(map, "cat", "neko", 0); // add new entry or do nothing

What "or do nothing" means here? That it will not overwrite a key by 
default? This is a different semantics than AVDictionary, where you need 
to explicitly set DONT_OVERWRITE flag for such.

I think we should use function names and flags similar to what we have in 
AVDictionary. Like av_map_set_strings() instead of av_map_add_strings(), 
or AV_MAP_DONT_OVERWRITE. So our users won't have to use different 
mindset for similar stuff.

> + *
> + * av_map_add_strings(map, "cat", "neko", AV_MAP_REPLACE); // add new entry or replace existing
> + *
> + *
> + * ----------- Removing entries -----------------
> + *
> + * Removing entries does by default not rebuild the map. That is, while access will always
> + * be O(log n) when n becomes smaller, memory consumption will not decrease until
> + * AV_SET_ALLOW_REBUILD is used. Note if you use AV_SET_ALLOW_REBUILD, all previously
> + * returned elements become invalid.
> + *
> + * av_map_del(map, "cat", 0); // remove one entry matching "the key"
> + *
> + * av_map_del(map, "cat", AV_SET_ALLOW_REBUILD); // remove one entry matching "the key" and rebuild the map to re

Do you specify a key, or a concatenated key + \0 + value? Or you can 
specify both?

In general I believe the public API should not use const char * for 
keyvalue types, that would be very fragile. A string constant is 
not a valid concatenated keyvalue for example, and the compiler will not 
catch such isses. Therefore public functions should always use separate 
key and separate value parameters.

> + *
> + *
> + * ----------- Retrieving an entry --------------
> + *
> + * AVMapEntry *e = av_map_get(map, "cat", AV_MAP_CMP_KEY); //Find an entry with the key = "cat"
> + *
> + * AVMapEntry *e = av_map_get(map, "cat", AV_MAP_CMP_KEY+AV_MAP_CMP_CASE_INSENSITIVE); //Find an entry with the key = "cat", "Cat", "cAt", ...
> + * // this will only work if one of the set compare functions is case insensitive
> + *
> + *
> + * ----------- Iterating over all elements ------
> + *
> + * const AVMapEntry *t = NULL;
> + * while ((t = av_map_iterate(s, t)))
> + *     printf("%s=%s %zu,%zu   ", t->key, t->value, t->keylen, t->valuelen);
> + *
> + *
> + * ----------- copying all elements of a mep into another map
> + *
> + * av_map_copy(dst, src);
> + *
> + *
> + * ----------- freeing a map ---------------------
> + *
> + * av_map_free(&map);
> + *
> + *
> + * ----------- multiple compare function in a single map -----------
> + *
> + * Each map has a primary compare function, which is used for ordering elements.
> + * Additional (compatible) compare functions can be added with av_map_add_cmp_func()
> + *
> + * What "compaibility" means here is that every added function returns the same value
> + * as the primary function or 0.
> + *
> + * An example, Imagine we have "cat", "dog", "Dog", "fox"
> + * a function that treats "dog" and "Dog" as equal is compatible to this ordering
> + * OTOH
> + * if we have have strcmp() as primary function we would order like this:
> + * "Dog", "cat", "dog", "fox"
> + * and here we could not treat "dog" and "Dog" as equal, and thus case insensitive
> + * compare would not be possible
> + *
> + * ----------- compared to AVDictionary -----------
> + *
>  * compared to AVDictionary this has
>  * clone is O(n) instead of O(n²)
>  * copy is O(n*log n) instead of O(n²)

You should also mention the differences (e.g. ordering).

Thanks,
Marton