> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-boun...@ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Mittwoch, 16. April 2025 22:12
> To: FFmpeg development discussions and patches <ffmpeg-
> de...@ffmpeg.org>
> Subject: [FFmpeg-devel] [PATCH] avutil/map: replace passing Compare
> functions by flags
>
> This makes the API much more robust because if you receive a map
> from some other module you no longer need to know which
> compare function is correct for it
> Instead you just specify what you need, like
> AV_MAP_CMP_CASE_SENSITIVE or AV_MAP_CMP_CASE_INSENSITIVE or 0 if you
> dont care
> and the code will either do what you asked for or cleanly fail if its
> unable to
> previously it would just give you a wrong result sometimes
>
> Signed-off-by: Michael Niedermayer <mich...@niedermayer.cc>
> ---
> libavutil/map.c | 80 +++++++++++++++++++++++++++++++++++-------
> -
> libavutil/map.h | 53 +++++++++++++++++++++-------
> libavutil/tests/map.c | 45 ++++++++++++++++--------
> 3 files changed, 137 insertions(+), 41 deletions(-)
>
> diff --git a/libavutil/map.c b/libavutil/map.c
> index 00dd5a1bd39..950473c2c45 100644
> --- a/libavutil/map.c
> +++ b/libavutil/map.c
> @@ -35,7 +35,8 @@ typedef struct{
> } AVMapInternalEntry;
>
> struct AVMap{
> - AVMapCompareFunc cmp_keyvalue;
> +#define CMP_MASK 31
> + AVMapCompareFunc cmp[27];
> AVMapCopyFunc copy;
> AVMapFreeFunc freef;
> int count;
> @@ -98,24 +99,71 @@ int av_map_supercmp_keyvalue(const char *a, const
> char *b)
> return v;
> }
>
> -AVMap *av_map_new(AVMapCompareFunc cmp_keyvalue, AVMapCopyFunc copy,
> AVMapFreeFunc freef)
> +int av_map_add_cmp_func(AVMap *m, AVMapCompareFunc cmp, int
> cmp_flags)
> +{
> + static const uint8_t sensitivity[27][3] = {
> + {0,0, 0},{1,0, 0},{2,0, 0}, {0,3, 0},{1,3, 0},{2,3, 0}, {0,6,
> 0},{1,6, 0},{2,6, 0},
> + {0,0, 9},{1,0, 9},{2,0, 9}, {0,3, 9},{1,3, 9},{2,3, 9}, {0,6,
> 9},{1,6, 9},{2,6, 9},
> + {0,0,18},{1,0,18},{2,0,18}, {0,3,18},{1,3,18},{2,3,18},
> {0,6,18},{1,6,18},{2,6,18},};
> + int case_sensitive = sensitivity[cmp_flags][0];
> + int keyvalue_sensitive = sensitivity[cmp_flags][1];
> + int truncated_sensitive = sensitivity[cmp_flags][2];
> +
> + if (!keyvalue_sensitive || !truncated_sensitive || cmp_flags >=
> 27U)
> + return AVERROR(EINVAL);
> +
> + av_assert1(case_sensitive + keyvalue_sensitive +
> truncated_sensitive == cmp_flags);
> +
> + if ( case_sensitive == AV_MAP_CMP_CASE_SENSITIVE && m-
> >cmp[keyvalue_sensitive + AV_MAP_CMP_CASE_INSENSITIVE])
> + return AVERROR(EINVAL);
> + if ( keyvalue_sensitive == AV_MAP_CMP_KEYVALUE && m-
> >cmp[AV_MAP_CMP_KEY])
> + return AVERROR(EINVAL);
> + if (truncated_sensitive == AV_MAP_CMP_NON_TRUNCATED && m-
> >cmp[keyvalue_sensitive + AV_MAP_CMP_TRUNCATED])
> + return AVERROR(EINVAL);
> +
> + //max functions is KV NT CS -> KV NT CI -> KV T CI (CI/T is about
> value only) -> K NT CS -> K NT CI -> K T CI
> + //missing is KV T CS and K T CS, with them we can have KV NT CS -
> > KV T CS -> K NT CS -> K T CS
> +
> + for (int i=0; i<8; i++) {
> + int flags = 0;
> + if (i&1) flags += case_sensitive;
> + if (i&2) flags += keyvalue_sensitive;
> + if (i&4) flags += truncated_sensitive;
> +
> + if (!m->cmp[flags])
> + m->cmp[flags] = cmp;
> + }
> + return 0;
> +}
> +
> +int av_map_is_cmp_flags_supported(AVMap *m, int cmp_flags)
> +{
> + if (cmp_flags >= 27U)
> + return AVERROR(EINVAL);
> + return !!m->cmp[cmp_flags];
> +}
> +
> +AVMap *av_map_new(AVMapCompareFunc cmp_keyvalue, int cmp_flags,
> 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;
>
> + av_map_add_cmp_func(s, cmp_keyvalue, cmp_flags);
> +
> 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))
> +const AVMapEntry *av_map_get_multiple(const AVMap *s, const
> AVMapEntry *prev, const char *keyvalue, int flags)
> {
> + AVMapCompareFunc cmp = s->cmp[flags & CMP_MASK];
> +
> 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);
> + void *prev_keyvalue = av_tree_find2(s->tree_root, prev->key,
> s->cmp[0], next_node, 2);
> av_assert2(prev_keyvalue);
> if (!next_node[1] || cmp(next_node[1], keyvalue))
> return NULL;
> @@ -134,8 +182,10 @@ const AVMapEntry *av_map_get_multiple(const AVMap
> *s, const AVMapEntry *prev, co
> return &keyvalue2internal(keyvalue)->map_entry;
> }
>
> -const AVMapEntry *av_map_get(const AVMap *s, const char *keyvalue,
> int (*cmp)(const void *keyvalue, const void *b))
> +const AVMapEntry *av_map_get(const AVMap *s, const char *keyvalue,
> int flags)
> {
> + AVMapCompareFunc cmp = s->cmp[flags & CMP_MASK];
> +
> keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, NULL, 0);
>
> if (!keyvalue)
> @@ -192,15 +242,15 @@ int av_map_add(AVMap *s, const char *key, int
> keylen, const char *value, int val
> memcpy(entry->key , key , keylen);
> memcpy(entry->value, value, valuelen);
>
> - void *elem = av_tree_insert(&s->tree_root, entry->key, s-
> >cmp_keyvalue, &next);
> + void *elem = av_tree_insert(&s->tree_root, entry->key, s->cmp[0],
> &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);
> + ret = av_map_del(s, entry->key, flags & ~CMP_MASK);
> av_assert2(ret == 1);
> - elem = av_tree_insert(&s->tree_root, entry->key, s-
> >cmp_keyvalue, &next);
> + elem = av_tree_insert(&s->tree_root, entry->key, s-
> >cmp[0], &next);
> av_assert2(elem == entry->key || !elem);
> ret = 2;
> } else
> @@ -214,12 +264,13 @@ int av_map_add(AVMap *s, const char *key, int
> keylen, const char *value, int val
> return ret;
> }
>
> -int av_map_del(AVMap *s, const char *keyvalue, int (*cmp)(const void
> *keyvalue, const void *b), int flags)
> +int av_map_del(AVMap *s, const char *keyvalue, int flags)
> {
> uint8_t *old_keyvalue;
> AVTreeNode *next = NULL;
> + AVMapCompareFunc cmp = s->cmp[flags & CMP_MASK];
>
> - if (cmp != s->cmp_keyvalue) {
> + if (cmp != s->cmp[0]) {
> // 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
> @@ -227,10 +278,10 @@ int av_map_del(AVMap *s, const char *keyvalue,
> int (*cmp)(const void *keyvalue,
> if (!old_keyvalue)
> return 0;
>
> - av_tree_insert(&s->tree_root, old_keyvalue, s->cmp_keyvalue,
> &next);
> + av_tree_insert(&s->tree_root, old_keyvalue, s->cmp[0],
> &next);
> av_assert2(next);
> } else {
> - av_tree_insert(&s->tree_root, (char*)keyvalue, s-
> >cmp_keyvalue, &next);
> + av_tree_insert(&s->tree_root, (char*)keyvalue, s->cmp[0],
> &next);
> if (!next)
> return 0;
> old_keyvalue = next->elem; //TODO add a API to av_tree() to
> return the elem of a AVTreeNode
> @@ -243,8 +294,9 @@ int av_map_del(AVMap *s, const char *keyvalue, int
> (*cmp)(const void *keyvalue,
> s->deleted++;
>
> if ((flags & AV_MAP_ALLOW_REBUILD) && s->deleted > s->count) {
> - AVMap *news = av_map_new(s->cmp_keyvalue, s->copy, s->freef);
> + AVMap *news = av_map_new(s->cmp[0], AV_MAP_CMP_KEYVALUE +
> AV_MAP_CMP_NON_TRUNCATED, s->copy, s->freef);
> if(news) {
> + memcpy(news->cmp, s->cmp, sizeof(news->cmp));
> int ret = av_map_copy(news, s);
> if (ret < 0) {
> av_map_free(&news);
> diff --git a/libavutil/map.h b/libavutil/map.h
> index 0c660260017..10f541cc5ba 100644
> --- a/libavutil/map.h
> +++ b/libavutil/map.h
> @@ -46,8 +46,17 @@
> */
>
> 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
> +//use + not | to combine these flags
> + AV_MAP_CMP_CASE_SENSITIVE = 1,
> + AV_MAP_CMP_CASE_INSENSITIVE = 2,
> + AV_MAP_CMP_KEY = 3,
> + AV_MAP_CMP_KEYVALUE = 6,
> + AV_MAP_CMP_TRUNCATED = 9,
> + AV_MAP_CMP_NON_TRUNCATED = 18,
> +
> + AV_MAP_ALLOW_REBUILD = 256, ///< when removing entries
> rebuild the map to reduce memory consumption, note, this invalidates
> previously retrieved elements and iterate state.
> + AV_MAP_REPLACE = 512, ///< replace keyvalue if
> already in the map
> +
> };
>
> typedef struct AVMapEntry {
> @@ -104,7 +113,33 @@ int av_map_supercmp_key(const char *a, const char
> *b);
> *
> *
> */
> -AVMap *av_map_new(AVMapCompareFunc keyvalue_cmp, AVMapCopyFunc clone,
> AVMapFreeFunc freef);
> +AVMap *av_map_new(AVMapCompareFunc keyvalue_cmp, int cmp_flags,
> AVMapCopyFunc clone, AVMapFreeFunc freef);
> +
> +
> +/**
> + * Add a compatible compare function to the map.
> + * The function will later be selected by using AV_MAP_CMP_* flags
> + *
> + * Functions must be added from most specific to least specific, that
> is if a AVMap is build
> + * with a case insensitive compare no case sensitive compare
> functions can be added. This is
> + * to avoid building non functional AVMaps.
> + *
> + * @see av_map_new
> + *
> + * @param cmp_flags a combination of AV_MAP_CMP_*, note key/keyvalue
> and truncated vs non truncated
> + * are mandatory to be specified
> + *
> + * @return a negative error code if the cmp_flags are illegal or
> unsupported for this AVMap
> + * If you know your flags are valid, then you dont need to
> check the return
> + */
> +int av_map_add_cmp_func(AVMap *m, AVMapCompareFunc keyvalue_cmp, int
> cmp_flags);
> +
> +/**
> + *
> + * @return 1 if the provided AV_MAP_CMP_* flag combination is
> supported by this map.
> + * 0 otherwise
> + */
> +int av_map_is_cmp_flags_supported(AVMap *m, int cmp_flags);
>
> /**
> * realloc internal space to accomodate the specified new elements
> @@ -136,13 +171,12 @@ int av_map_add(AVMap *s, const char *key, int
> keylen, const char *value, int val
> *
> * @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);
> +int av_map_del(AVMap *s, const char *keyvalue, int flags);
>
> /**
> * Iterate over possibly multiple matching map entries.
> @@ -153,22 +187,17 @@ int av_map_del(AVMap *s, const char *keyvalue,
> int (*cmp)(const void *keyvalue,
> * @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));
> +const AVMapEntry *av_map_get_multiple(const AVMap *s, const
> AVMapEntry *prev, const char *keyvalue, int flags);
>
> /**
> * 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));
> +const AVMapEntry *av_map_get(const AVMap *s, const char *keyvalue,
> int flags);
>
> /**
> * Iterate over a map
> diff --git a/libavutil/tests/map.c b/libavutil/tests/map.c
> index 90950769f98..1e3f80a42af 100644
> --- a/libavutil/tests/map.c
> +++ b/libavutil/tests/map.c
> @@ -47,6 +47,13 @@ int main(void)
> av_map_supercmp_keyvalue,
> av_map_supercmp_keyvalue,
> };
> + int our_flags[] = {
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEY,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEYVALUE,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_INSENSITIVE +
> AV_MAP_CMP_KEY,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEYVALUE,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEYVALUE,
> + };
> void *our_subcmp[] = {
> strcmp,
> strcmp,
> @@ -54,19 +61,27 @@ int main(void)
> av_map_supercmp_key,
> av_strcasecmp,
> };
> + int our_subflags[] = {
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEY,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEY,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_INSENSITIVE +
> AV_MAP_CMP_KEY,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_SENSITIVE +
> AV_MAP_CMP_KEY,
> + AV_MAP_CMP_NON_TRUNCATED + AV_MAP_CMP_CASE_INSENSITIVE +
> AV_MAP_CMP_KEY,
> + };
>
> for (int settype=0; settype<3; settype++) {
> - AVMap *set = av_map_new(our_cmp[settype], NULL, NULL);
> + AVMap *set = av_map_new(our_cmp[settype], our_flags[settype],
> NULL, NULL);
> + av_map_add_cmp_func(set, our_subcmp[settype],
> our_subflags[settype]);
>
> printf("testing empty set\n");
>
> - const AVMapEntry *e = av_map_get(set, "foo",
> our_subcmp[settype]);
> + const AVMapEntry *e = av_map_get(set, "foo",
> our_subflags[settype]);
> av_assert0(e == NULL);
>
> - e = av_map_get(set, "foo", our_subcmp[settype]);
> + e = av_map_get(set, "foo", our_subflags[settype]);
> av_assert0(e == NULL);
>
> - int ret = av_map_del(set, "foo", our_subcmp[settype], 0);
> + int ret = av_map_del(set, "foo", our_subflags[settype]);
> av_assert0(ret == 0);
>
> print_set(set);
> @@ -79,7 +94,7 @@ int main(void)
> 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]);
> + e = av_map_get(set, "foo", our_subflags[settype]);
> av_assert0(!strcmp(e->key, "foo"));
> if (settype == 1) {
> av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value,
> "bar"));
> @@ -90,7 +105,7 @@ int main(void)
> 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]);
> + e = av_map_get(set, "foo", our_subflags[settype]);
> av_assert0(!strcmp(e->key, "foo"));
> if (settype == 1) {
> av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value,
> "bar"));
> @@ -98,14 +113,14 @@ int main(void)
> av_assert0(!strcmp(e->value, "bear"));
> }
>
> - e = av_map_get_multiple(set, NULL, "foo",
> our_subcmp[settype]);
> + e = av_map_get_multiple(set, NULL, "foo",
> our_subflags[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]);
> + e = av_map_get_multiple(set, e, "foo",
> our_subflags[settype]);
> if (settype == 1) {
> av_assert0(!strcmp(e->key, "foo"));
> av_assert0(!strcmp(e->value, "bear"));
> @@ -113,10 +128,10 @@ int main(void)
> av_assert0(e == NULL);
> }
>
> - ret = av_map_del(set, "foo", our_subcmp[settype], 0);
> + ret = av_map_del(set, "foo", our_subflags[settype]);
> av_assert0(ret == 1);
>
> - e = av_map_get(set, "foo", our_subcmp[settype]);
> + e = av_map_get(set, "foo", our_subflags[settype]);
> if (settype == 1) {
> av_assert0(!strcmp(e->key, "foo"));
> av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value,
> "bar"));
> @@ -124,7 +139,7 @@ int main(void)
> av_assert0(e == NULL);
> }
>
> - ret = av_map_del(set, "foo", our_subcmp[settype], 0);
> + ret = av_map_del(set, "foo", our_subflags[settype]);
> av_assert0(ret == ((int[]){0,1,0})[settype]);
>
>
> @@ -157,7 +172,7 @@ int main(void)
> r = r*123 + 7;
> char str[3] = {0};
> str[0] = r;
> - e = av_map_get(set, str, our_subcmp[settype]);
> + e = av_map_get(set, str, our_subflags[settype]);
> if (settype != 2) {
> av_assert0(!strcmp(e->key, str));
> av_assert0(!strcmp(e->value, str));
> @@ -165,7 +180,7 @@ int main(void)
> 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]);
> + e = av_map_get_multiple(set, NULL, str,
> our_subflags[settype]);
> if (settype != 2) {
> av_assert0(!strcmp(e->key, str));
> av_assert0(!strcmp(e->value, str));
> @@ -178,9 +193,9 @@ int main(void)
>
> str[1]='x';
>
> - e = av_map_get(set, str, our_subcmp[settype]);
> + e = av_map_get(set, str, our_subflags[settype]);
> av_assert0(e == NULL);
> - e = av_map_get_multiple(set, NULL, str,
> our_subcmp[settype]);
> + e = av_map_get_multiple(set, NULL, str,
> our_subflags[settype]);
> av_assert0(e == NULL);
> }
> print_set(set);
> --
> 2.49.0
>
> _______________________________________________
That's a good change, because it was in fact confusing.
Another confusing part of the API is the need for specifying the
lengths of key and value - and I finally figured out why it
didn't retrieve any elements: those values need to be strlen + 1
I think the final API should not require any length params
(or at least it should have a function that doesn't need it)
Best,
sw
_______________________________________________
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".
