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

[Marton Balint]

On Wed, 23 Apr 2025, Michael Niedermayer wrote:

> Hi
>
> On Mon, Apr 21, 2025 at 09:55:33PM +0200, Marton Balint wrote:
>>
>>
>> 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?
>
> Yes.
> In how far a "automatic" replacement is possible iam not sure
>
>
>> 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...
>
> What do you mean by "keeps key insertion order" ?
> this isnt documented, or is it ?
> In fact i dont think thats supposed to be guranteed by AVDictionary
>
> I think the order coming out of av_map_iterate() will match the
> order elements where added.
> Is that what you meant ?

Yes, exactly. Admittedly not documented behaviour... Another thing is that 
this does not support AV_DICT_MULTIKEY if the same value is used multiple 
times. I am just saying that we should document these fundamental 
differences to avoid any suprises...

>
>
>
>>
>>> + *
>>> + * ---------- 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.
>
> yes, we can flip the default around if people prefer
> I really picked this solely because i felt negated flags with "DONT" in their
> name are suboptimal design
>
>
>>
>> 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.
>
> like i said i dont like the "DONT" flag, i think we should avoid such names
> in new designs. Maybe AV_MAP_PRESERVE would be an alternative ?

Flag names should be easy to understand and remember, I don't really mind 
if it is is negated. And "dont overwrite" or "no overwrite" is the most 
expressive IMHO.

>
> av_map_set_strings() implies setting a key to a value. When this in reality is
> more flexibl, depending on flags and setup

But if it depends on flags if "add" or "set" make more sense, then I'd 
rather keep set, considering the primary goal for this is being the 
dictionary replacement...

>
>
>>
>>> + *
>>> + * 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?
>
> it depends on the flags (which select the compare function)
> In fact it can be an arbitrary struct instead of a string, if the compare
> function  during setup compares the specific struct.
>
> av_map_del(map, "cat\0katze", AV_MAP_CMP_KEYVALUE);
> av_map_del(map, "cat", AV_MAP_CMP_KEY);
>
>
>>
>> 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.
>
> about "const char *", we could use a typedef or struct or something
>
> completely droping keyvalue from public API is not an option because
> AVMapEntry always provides you with a keyvalue already and requiring
> to copy it on every use is dumb.

But AVMapEntry has separete key and value pointers, even sizes, so I am 
not sure where you need to copy.

Regards,
Marton