[FFmpeg-devel] [PATCH] avutil/map: replace passing Compare functions by flags
Michael Niedermayer
michael at niedermayer.cc
Wed Apr 16 23:12:08 EEST 2025
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 <michael at 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
More information about the ffmpeg-devel
mailing list