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

[Michael Niedermayer]

Hi Nicolas

On Mon, Apr 21, 2025 at 05:01:19PM +0200, Nicolas George wrote:
> Michael Niedermayer (HE12025-04-20):
> >					  theres no real reason
> > to hurry here
> 
> (This is me applauding.)
> 
> >		except that i seem to keep workig on it when
> > people ask for some non trivial changes/improvments :)
> 
> As long as you have fun.
> 
> > 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.
> > + *
> > + * ---------- 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
> 
> Maybe insist: “If the same (key, value) pair is added multiple times, it
> will be returned only once when iterating and removing it once will
> completely remove it.”
> 
> And that raises the question: should this API not also allow entries
> with multiplicity?

you can have some map where each element maps to an integer, where
that integer represents a "count"


> 
> Also: what happens if:
> 
> AVMap *map = av_map_alloc(av_map_strcmp_keyvalue, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEY, NULL, NULL);
> AVMap *map = av_map_alloc(strcmp, AV_MAP_CMP_CASE_SENSITIVE + AV_MAP_CMP_KEYVALUE, NULL, NULL);
> 
> (I swapped the compare functions)?

crash probably, but technically, undefined behavior


[...]

> > + *
> > + *
> > + * ----------- Adding entries -----------------
> > + *
> > + * av_map_add_strings(map, "cat", "neko", 0); // add new entry or do nothing
> > + *
> > + * 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
> 
> (It seems you sentence got interrup)
> 

> If I did “av_map_add("animal\0cat", 11, "neko", 5, 0)”, how can I del or
> get it?

depends on the compare function, the map was setup with.
If you created your own function that works with double or tripple zero
terminated strings. This will work perfectly fine.

Otherwise if you mix the passed object and the function so they are
not compatible then you get undefined behavior

same with qsort() or printf() or AVDictionary


> 
> > + *
> > + *
> > + * ----------- 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
> 
> This is crucial: how? (This is redundant with my next remark.)
> 
> > + *
> > + *
> > + * ----------- 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
> 
> Code examples needed. For example: a map where key = name, value = phone
> number, with AV_MAP_CMP_KEYVALUE. How do we set it up to allow
> case-insensitive lookups and name only lookups, and name only
> case-insensitive lookups?

The phone numbers i have seen are not affected by case sensitivity.
So case sensitivity only matters for the name (which is in key)

This should work:

AVMap *map = av_map_alloc(av_map_supercmp_keyvalue, AV_MAP_CMP_KEYVALUE + AV_MAP_CMP_CASE_SENSITIVE, NULL, NULL);
av_map_add_cmp_func(map,       av_map_supercmp_key, AV_MAP_CMP_KEY      + AV_MAP_CMP_CASE_SENSITIVE);
av_map_add_cmp_func(map,             av_strcasecmp, AV_MAP_CMP_KEY      + AV_MAP_CMP_CASE_INSENSITIVE);

But the point you seem to try to raise, is correct,
not every combination is possible

thx

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The worst form of inequality is to try to make unequal things equal.
-- Aristotle
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20250423/0ed12dff/attachment.sig>