* [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
@ 2025-04-17 16:52 Michael Niedermayer
2025-04-17 17:57 ` Nicolas George
2025-04-19 10:36 ` Leo Izen
0 siblings, 2 replies; 11+ messages in thread
From: Michael Niedermayer @ 2025-04-17 16:52 UTC (permalink / raw)
To: FFmpeg development discussions and patches
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=UTF-8, Size: 45573 bytes --]
AVL Tree based Map
compared to AVDictionary this has
* clone is O(n) instead of O(n²)
* copy is O(n*log n) instead of O(n²)
* O(log n) malloc() calls by default and O(1) if av_map_realloc() is used instead of O(n)
* get/add/delete is O(log n)
*
* You can add (if memory is realloced before) and remove entries while a iterator stays valid
* copy is atomic, a failure means the dst is unchanged
*
* there are restrictions on what compare function can be used on get depending on how the Map was created
* you can mix case sensitive and case insensitive compare with av_map_supercmp_*
* Supports binary objects, not just strings
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
libavutil/Makefile | 3 +
libavutil/map.c | 415 ++++++++++++++++++++++++++++++++++++++
libavutil/map.h | 270 +++++++++++++++++++++++++
libavutil/tests/map.c | 221 ++++++++++++++++++++
libavutil/tree.c | 6 +-
libavutil/tree_internal.h | 28 +++
tests/fate/libavutil.mak | 4 +
tests/ref/fate/map | 27 +++
8 files changed, 969 insertions(+), 5 deletions(-)
create mode 100644 libavutil/map.c
create mode 100644 libavutil/map.h
create mode 100644 libavutil/tests/map.c
create mode 100644 libavutil/tree_internal.h
create mode 100644 tests/ref/fate/map
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 9ef118016bb..3a92748a482 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -81,6 +81,7 @@ HEADERS = adler32.h \
replaygain.h \
ripemd.h \
samplefmt.h \
+ map.h \
sha.h \
sha512.h \
spherical.h \
@@ -173,6 +174,7 @@ OBJS = adler32.o \
rc4.o \
ripemd.o \
samplefmt.o \
+ map.o \
side_data.o \
sha.o \
sha512.o \
@@ -290,6 +292,7 @@ TESTPROGS = adler32 \
random_seed \
rational \
ripemd \
+ map \
sha \
sha512 \
side_data_array \
diff --git a/libavutil/map.c b/libavutil/map.c
new file mode 100644
index 00000000000..59b87a1f074
--- /dev/null
+++ b/libavutil/map.c
@@ -0,0 +1,415 @@
+/*
+ * Copyright (c) 2025 Michael Niedermayer
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <inttypes.h>
+#include <string.h>
+
+#include "avassert.h"
+#include "avstring.h"
+#include "error.h"
+#include "mem.h"
+#include "map.h"
+
+#include "tree_internal.h" // For improved readability with AVTreeNode, do NOT touch AVTreeNode internals
+
+typedef struct{
+ AVMapEntry map_entry;
+ uint8_t treenode_and_keyvalue[0];
+} AVMapInternalEntry;
+
+struct AVMap{
+#define CMP_MASK 31
+ AVMapCompareFunc cmp[27];
+ AVMapCopyFunc copy;
+ AVMapFreeFunc freef;
+ int count;
+ int deleted;
+ int next; ///< index of entry in root array after all used entries
+ unsigned internal_entries_len;
+ AVTreeNode *tree_root;
+ AVMapInternalEntry *internal_entries;
+};
+
+static uint8_t deleted_entry;
+
+static inline int internal_entry_len(AVMapInternalEntry *I) {
+ return (I->map_entry.keylen + I->map_entry.valuelen + sizeof (*I) + sizeof(AVTreeNode) - 1) / sizeof (*I) + 1;
+}
+
+static inline AVTreeNode * internal_treenode(const AVMapInternalEntry *I)
+{
+ return (AVTreeNode *)I->treenode_and_keyvalue;
+}
+
+static inline uint8_t * internal_key(AVMapInternalEntry *I)
+{
+ return I->treenode_and_keyvalue + sizeof(AVTreeNode);
+}
+
+static inline uint8_t * internal_value(AVMapInternalEntry *I)
+{
+ return I->treenode_and_keyvalue + sizeof(AVTreeNode) + I->map_entry.keylen;
+}
+
+static inline AVMapInternalEntry * keyvalue2internal(const uint8_t *keyvalue)
+{
+ return (AVMapInternalEntry*)(keyvalue - offsetof(AVMapInternalEntry, treenode_and_keyvalue) - sizeof(AVTreeNode));
+}
+
+int av_map_strcmp_keyvalue(const char *a, const char *b)
+{
+ int v = strcmp(a,b);
+ if(!v)
+ v = strcmp(a + strlen(a) + 1, b + strlen(a) + 1); // please optimize this dear compiler, we know the strlen after strcmp()
+ return v;
+}
+
+int av_map_supercmp_key(const char *a, const char *b)
+{
+ int v = av_strcasecmp(a,b);
+ if (!v)
+ v = strcmp(a,b);
+
+ return v;
+}
+
+int av_map_supercmp_keyvalue(const char *a, const char *b)
+{
+ int v = av_map_supercmp_key(a,b);
+ if (!v)
+ v = strcmp(a + strlen(a) + 1, b + strlen(a) + 1);
+
+ return v;
+}
+
+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->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 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[0], next_node, 2);
+ av_assert2(prev_keyvalue);
+ if (!next_node[1] || cmp(next_node[1], keyvalue))
+ return NULL;
+
+ keyvalue = next_node[1];
+ } else {
+ void *next_node[4] = { NULL, NULL, NULL, NULL };
+ keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, next_node, 4);
+ if (next_node[2]) // If we have a leftmost equal keyvalue, use it instead
+ keyvalue = next_node[2];
+ }
+
+ if (!keyvalue)
+ return NULL;
+
+ return &keyvalue2internal(keyvalue)->map_entry;
+}
+
+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)
+ return NULL;
+
+ return &keyvalue2internal(keyvalue)->map_entry;
+}
+
+static void update_pointers(AVMap *dst, AVMapInternalEntry *dst_internal_entries, const AVMapInternalEntry *src_internal_entries)
+{
+ AVTreeNode *src_tree_root = dst->tree_root;
+
+ if (src_tree_root) {
+ dst->tree_root = src_tree_root - internal_treenode(src_internal_entries) + internal_treenode(dst_internal_entries);
+ av_tree_move(dst->tree_root, src_tree_root, dst_internal_entries, src_internal_entries);
+ }
+
+ //TODO We could attempt to compact free space
+ for(int i = 0; i<dst->next; i++) {
+ if (dst_internal_entries[i].map_entry.key != &deleted_entry) {
+ dst_internal_entries[i].map_entry.key = internal_key (dst_internal_entries + i);
+ dst_internal_entries[i].map_entry.value = internal_value(dst_internal_entries + i);
+ }
+ i += internal_entry_len(dst_internal_entries + i) - 1;
+ }
+ dst->internal_entries = dst_internal_entries;
+}
+
+int av_map_realloc(AVMap *s, int extra_elements, int extra_space) {
+ int64_t advance = extra_elements + (extra_space + (int64_t)extra_elements*(sizeof(*s->internal_entries) + sizeof(AVTreeNode) - 1)) / sizeof(*s->internal_entries);
+
+ if (advance > (INT32_MAX - s->next) / sizeof(AVMapInternalEntry))
+ return AVERROR(ENOMEM);
+
+ AVMapInternalEntry *new_internal_entries = av_fast_realloc(s->internal_entries, &s->internal_entries_len, (s->next + advance) * sizeof(AVMapInternalEntry));
+
+ if (!new_internal_entries)
+ return AVERROR(ENOMEM);
+
+ if (new_internal_entries != s->internal_entries) {
+ update_pointers(s, new_internal_entries, s->internal_entries);
+ }
+ return advance;
+}
+
+int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int valuelen, int flags)
+{
+ av_assert2(keylen || valuelen); // patch welcome but how would the compare function compare a len=0 element without knowing it is a len 0 element
+
+ int advance = av_map_realloc(s, 1, keylen + valuelen);
+ if (advance < 0)
+ return advance;
+
+ AVMapEntry *entry = &s->internal_entries[s->next].map_entry;
+ AVTreeNode *next = internal_treenode(s->internal_entries + s->next);
+ memset(next, 0, sizeof(*next));
+ entry->keylen = keylen;
+ entry->valuelen= valuelen;
+ entry->key = internal_key (s->internal_entries + s->next);
+ entry->value = internal_value(s->internal_entries + s->next);
+ memcpy(entry->key , key , keylen);
+ memcpy(entry->value, value, valuelen);
+
+ 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, flags & ~CMP_MASK);
+ av_assert2(ret == 1);
+ elem = av_tree_insert(&s->tree_root, entry->key, s->cmp[0], &next);
+ av_assert2(elem == entry->key || !elem);
+ ret = 2;
+ } else
+ return 0; //entry already in the map
+ }
+ av_assert2(!next);
+ av_assert2(s->tree_root);
+ s->next += advance;
+ s->count++;
+
+ return ret;
+}
+
+int av_map_add_strings(AVMap *s, const char *key, const char *value, int flags)
+{
+ return av_map_add(s, key, strlen(key)+1, value, strlen(value)+1, 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[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
+ old_keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, NULL, 0);
+ if (!old_keyvalue)
+ return 0;
+
+ 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[0], &next);
+ if (!next)
+ return 0;
+ old_keyvalue = next->elem; //TODO add a API to av_tree() to return the elem of a AVTreeNode
+
+ }
+ AVMapInternalEntry *internal_entry = keyvalue2internal(old_keyvalue);
+ internal_entry->map_entry.key = &deleted_entry;
+
+ s->count--;
+ s->deleted++;
+
+ if ((flags & AV_MAP_ALLOW_REBUILD) && s->deleted > s->count) {
+ 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);
+ } else {
+ if (s->freef)
+ for (int i=0; i<s->count; i++)
+ s->freef(&s->internal_entries[i].map_entry);
+ av_freep(&s->internal_entries);
+ memcpy(s, news, sizeof(*s));
+ }
+ }
+ }
+
+ return 1;
+}
+
+const AVMapEntry *av_map_iterate(const AVMap *s,
+ const AVMapEntry *prev)
+{
+ AVMapInternalEntry *I;
+ if (prev) {
+ I = (AVMapInternalEntry*)((uint8_t*)prev - offsetof(AVMapInternalEntry, map_entry));
+ I += internal_entry_len(I);
+ } else {
+ I = s->internal_entries;
+ }
+ while (I < s->internal_entries + s->next && I->map_entry.key == &deleted_entry)
+ I += internal_entry_len(I);
+
+ if (I == s->internal_entries + s->next)
+ return NULL;
+
+ return &I->map_entry;
+}
+
+int av_map_count(const AVMap *s)
+{
+ return s->count;
+}
+
+void av_map_free(AVMap **sp)
+{
+ AVMap *s = *sp;
+
+ for (int i=0; i<s->count; i++) {
+ if (s->freef)
+ s->freef(&s->internal_entries[i].map_entry);
+ }
+ av_freep(&s->internal_entries);
+ s->next =
+ s->internal_entries_len =
+ s->count = 0;
+ av_freep(sp);
+}
+
+int av_map_copy(AVMap *dst, const AVMap *src)
+{
+ const AVMapEntry *t = NULL;
+ AVMap *bak = av_memdup(dst, sizeof(*dst));
+ if (!bak)
+ return AVERROR(ENOMEM);
+
+ AVMapInternalEntry *new_internal_entries = av_memdup(bak->internal_entries, bak->internal_entries_len);
+ AVMapInternalEntry *old_internal_entries = dst->internal_entries;
+
+ while ((t = av_map_iterate(src, t))) {
+ int ret = av_map_add(dst, t->key, t->keylen, t->value, t->valuelen, 0);
+
+ if (ret < 0) {
+ update_pointers(bak, new_internal_entries, old_internal_entries);
+ av_free(dst->internal_entries);
+ memcpy(dst, bak, sizeof(*dst));
+ return ret;
+ }
+ }
+
+ av_freep(&new_internal_entries);
+ av_free(bak);
+
+ return 0;
+}
+
+AVMap *av_map_clone(AVMap *s)
+{
+ AVMap *dst = av_memdup(s, sizeof(AVMap));
+
+ if (!dst)
+ return NULL;
+
+ dst->internal_entries = av_memdup(s->internal_entries, s->internal_entries_len);
+
+ if (!dst->internal_entries)
+ goto err;
+
+ update_pointers(dst, dst->internal_entries, s->internal_entries);
+
+ return dst;
+err:
+ if (dst) {
+ av_freep(&dst->internal_entries);
+ }
+ av_free(dst);
+ return NULL;
+}
diff --git a/libavutil/map.h b/libavutil/map.h
new file mode 100644
index 00000000000..03572960306
--- /dev/null
+++ b/libavutil/map.h
@@ -0,0 +1,270 @@
+/*
+ * Copyright (c) 2025 Michael Niedermayer
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * Public map API.
+ */
+
+#ifndef AVUTIL_MAP_H
+#define AVUTIL_MAP_H
+
+#include <stdint.h>
+
+#include "tree.h"
+
+/**
+ * compared to AVDictionary this has
+ * clone is O(n) instead of O(n²)
+ * copy is O(n*log n) instead of O(n²)
+ * O(log n) malloc() calls by default and O(1) if av_map_realloc() is used instead of O(n)
+ * get/add/delete is O(log n)
+ *
+ * You can add (if memory is realloced before) and remove entries while a iterator stays valid
+ * copy is atomic, a failure means the dst is unchanged
+ *
+ * there are restrictions on what compare function can be used on get depending on how the Map was created
+ * you can mix case sensitive and case insensitive compare with av_map_supercmp_*
+ * Supports binary objects, not just strings
+ */
+
+enum {
+//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 {
+ uint8_t *key;
+ uint8_t *value;
+ int keylen;
+ int valuelen;
+} AVMapEntry;
+
+typedef struct AVMap AVMap;
+typedef void (* AVMapFreeFunc)(AVMapEntry *c);
+typedef void (* AVMapCopyFunc)(AVMapEntry *dst, const AVMapEntry *src, size_t len);
+typedef int (* AVMapCompareFunc)(const void *keyvalue, const void *b);
+
+/**
+ * like strcmp() but compares concatenated keyvalues.
+ *
+ * A map initialized with this will allow duplicate keys as long as their values differ.
+ */
+int av_map_strcmp_keyvalue(const char *a, const char *b);
+
+/**
+ * like av_map_strcmp_keyvalue() but is compatible with av_strcasecmp() and av_map_supercmp_key.
+ *
+ * A map initialized with this will allow duplicate keys as long as their values differ.
+ */
+int av_map_supercmp_keyvalue(const char *a, const char *b);
+
+/**
+ * like strcmp() but is compatible with av_strcasecmp().
+ *
+ * A map initialized with this will not allow duplicate keys.
+ */
+int av_map_supercmp_key(const char *a, const char *b);
+
+
+/**
+ *
+ * @param keyvalue_cmp compare function, will be passed the key + value concatenated.
+ * it should form a strict total order on all elements you want to store. each key-value pair
+ * can only occur once. Though there can be multiple values for the same key. IF this function
+ * treats them as different.
+ *
+ * if the keyvalue_cmp is inconsistant, for example a < b && b < a, reading may still work as long
+ * as the function later used for reading treats all elements in the inconsistant subset as
+ * equal this is not supported or recommanded but rather documented for completeness. Deleting
+ * elements of such inconsistant subsets should not be expected to work.
+ *
+ * @param freef receives a AVMapEntry and should free any resources except the AVMapEntry->key/value pointer itself
+ * for flat structs like strings, this is simply NULL
+ *
+ * Key Value compaibility
+ * av_map_supercmp_keyvalue X!=x X!=x av_map_supercmp_key, av_strcasecmp, (trucated av_strcasecmp)
+ * av_map_supercmp_key X!=x av_strcasecmp, (trucated av_strcasecmp)
+ * av_strcasecmp X==x truncation
+ *
+ * av_map_strcmp_keyvalue X!=x X!=x strcmp, truncation
+ * strcmp X!=x truncation
+ *
+ *
+ */
+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 compare function to be added.
+ * cmp(a,b) must return 0 or be equal to the previously added compare function for (a,b), if it returns 0 it also must do so for all
+ * elements between a and b
+ *
+ * @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 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
+ *
+ * This can be used to avoid repeated memory reallocation.
+ *
+ * @param extra_elements number of new elements to be added
+ * @param extra_space sum of keylen and valuelen of all to be added elements
+ *
+ * @return <0 on error
+ */
+int av_map_realloc(AVMap *s, int extra_elements, int extra_space);
+
+/**
+ * Add the given entry into a AVMap.
+ *
+ * @param s Pointer AVMap struct.
+ * @param value Entry value to add to *s
+ * @param valuelen length of value
+ * @param flags 0, AV_MAP_ALLOW_REBUILD, AV_MAP_REPLACE
+ *
+ * @return 1 if the entry was added, 0 if it was already in the map, 2 if it was replaced
+ * otherwise an error code <0
+ */
+int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int valuelen, int flags);
+int av_map_add_strings(AVMap *s, const char *key, const char *value, int flags);
+
+/**
+ * Delete the given entry from a AVMap.
+ *
+ * @param s Pointer AVMap struct.
+ * @param keyvalue key or concatenated key+value
+ * @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 flags);
+
+/**
+ * Iterate over possibly multiple matching map entries.
+ *
+ * The returned entry must not be changed, or it will
+ * cause undefined behavior.
+ *
+ * @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
+ *
+ * @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 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 flags);
+
+/**
+ * Iterate over a map
+ *
+ * Iterates through all entries in the map.
+ *
+ * @warning If you call any function with AV_SET_ALLOW_REBUILD set, then the iterator is
+ * invalidated, and must not be used anymore. Otherwise av_map_add() (without realloc) and av_map_del()
+ * can saftely be called during iteration.
+ *
+ * Typical usage:
+ * @code
+ * const AVMapEntry *e = NULL;
+ * while ((e = av_map_iterate(m, e))) {
+ * // ...
+ * }
+ * @endcode
+ *
+ * @param s The map to iterate over
+ * @param prev Pointer to the previous AVMapEntry, NULL initially
+ *
+ * @retval AVMapEntry* The next element in the map
+ * @retval NULL No more elements in the map
+ */
+const AVMapEntry *av_map_iterate(const AVMap *s,
+ const AVMapEntry *prev);
+
+/**
+ * Get number of entries in map.
+ *
+ * @param s map
+ * @return number of entries in map
+ */
+int av_map_count(const AVMap *s);
+
+/**
+ * Free all the memory allocated for an AVMap struct
+ * and all values.
+ */
+void av_map_free(AVMap **s);
+
+AVMap *av_map_clone(AVMap *s);
+
+/**
+ * Copy entries from one AVMap struct into another.
+ *
+ * @param dst Pointer to a pointer to a AVMap struct to copy into. If *dst is NULL,
+ * this function will allocate a struct for you and put it in *dst
+ * @param src Pointer to the source AVMap struct to copy items from.
+ * @param flags Flags to use when setting entries in *dst
+ *
+ * @see when the initial dst map is empty use av_map_clone() as its faster
+ *
+ * @return 0 on success, negative AVERROR code on failure.
+ */
+
+int av_map_copy(AVMap *dst, const AVMap *src);
+
+#endif /* AVUTIL_MAP_H */
diff --git a/libavutil/tests/map.c b/libavutil/tests/map.c
new file mode 100644
index 00000000000..7705eb31a95
--- /dev/null
+++ b/libavutil/tests/map.c
@@ -0,0 +1,221 @@
+/*
+ * copyright (c) 2025 Michael Niedermayer
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <string.h>
+#include <stdio.h>
+
+#include "libavutil/avassert.h"
+#include "libavutil/avstring.h"
+#include "libavutil/mem.h"
+#include "libavutil/map.h"
+
+
+static void print_set(const AVMap *s)
+{
+ const AVMapEntry *t = NULL;
+ while ((t = av_map_iterate(s, t)))
+ printf("%s=%s %d,%d ", t->key, t->value, t->keylen, t->valuelen);
+ printf("\n");
+}
+
+int main(void)
+{
+ void *our_cmp[] = {
+ strcmp,
+ av_map_strcmp_keyvalue,
+ av_strcasecmp,
+ 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,
+ av_strcasecmp,
+ 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], 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_subflags[settype]);
+ av_assert0(e == NULL);
+
+ e = av_map_get(set, "foo", our_subflags[settype]);
+ av_assert0(e == NULL);
+
+ int ret = av_map_del(set, "foo", our_subflags[settype]);
+ av_assert0(ret == 0);
+
+ print_set(set);
+
+ printf("testing 1-set\n");
+
+ ret = av_map_add(set, "foo", 4, "bar", 4, 0);
+ av_assert0(ret == 1);
+
+ 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_subflags[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype == 1) {
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar"));
+ } else {
+ av_assert0(!strcmp(e->value, "bar"));
+ }
+
+ ret = av_map_add(set, "foo", 4, "bear", 5, AV_MAP_REPLACE);
+ av_assert0(ret == 2);
+
+ 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"));
+ } else {
+ av_assert0(!strcmp(e->value, "bear"));
+ }
+
+ 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_subflags[settype]);
+ if (settype == 1) {
+ av_assert0(!strcmp(e->key, "foo"));
+ av_assert0(!strcmp(e->value, "bear"));
+ } else {
+ av_assert0(e == NULL);
+ }
+
+ ret = av_map_del(set, "foo", our_subflags[settype]);
+ av_assert0(ret == 1);
+
+ 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"));
+ } else {
+ av_assert0(e == NULL);
+ }
+
+ ret = av_map_del(set, "foo", our_subflags[settype]);
+ av_assert0(ret == ((int[]){0,1,0})[settype]);
+
+
+ print_set(set);
+
+ printf("testing n-set\n");
+ unsigned r = 5;
+ int histogram[256] = {0};
+ for(int i=0; i<1000; i++) {
+ r = r*123 + 7;
+ unsigned char str[3] = {0};
+ str[0] = r;
+ ret = av_map_add(set, str, 2, str, 2 ,0);
+ if (i < 128) {
+ if (settype != 2) {
+ av_assert0(ret == 1);
+ } else {
+ av_assert0(ret == !histogram[av_toupper(str[0])]);
+ histogram[av_toupper(str[0])] = 1;
+ }
+ } else {
+ av_assert0(ret == 0);
+ }
+ printf("%d", ret);
+ }
+ printf("\n");
+
+ r = 5;
+ for(int i=0; i<1000; i++) {
+ r = r*123 + 7;
+ char str[3] = {0};
+ str[0] = r;
+
+ if (i == 51) {
+ AVMap *old = set;
+ set = av_map_clone(set);
+ av_map_del(old, str, 0);
+ av_map_free(&old);
+ }
+ if (i == 73) {
+ AVMap *old = set;
+ set = av_map_new(our_cmp[settype], our_flags[settype], NULL, NULL);
+ av_map_add_cmp_func(set, our_subcmp[settype], our_subflags[settype]);
+ ret = av_map_add_strings(set, "the key", "the value", 0);
+ av_map_copy(set, old);
+ av_map_del(old, str, 0);
+ av_map_free(&old);
+ }
+ e = av_map_get(set, str, our_subflags[settype]);
+ if (settype != 2) {
+ av_assert0(!strcmp(e->key, str));
+ av_assert0(!strcmp(e->value, str));
+ } else {
+ av_assert0(!av_strcasecmp(e->key, str));
+ av_assert0(!av_strcasecmp(e->value, str));
+ }
+ 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));
+ } else {
+ av_assert0(!av_strcasecmp(e->key, str));
+ av_assert0(!av_strcasecmp(e->value, str));
+ }
+ ret = av_map_add(set, str, 2, str, 2, 0);
+ av_assert0(ret == 0);
+
+ str[1]='x';
+
+ e = av_map_get(set, str, our_subflags[settype]);
+ av_assert0(e == NULL);
+ e = av_map_get_multiple(set, NULL, str, our_subflags[settype]);
+ av_assert0(e == NULL);
+ }
+ print_set(set);
+
+ av_map_free(&set);
+ av_assert0(!set);
+ }
+
+ return 0;
+}
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 708d4013f04..3007dc26d29 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -24,11 +24,7 @@
#include "mem.h"
#include "tree.h"
-typedef struct AVTreeNode {
- struct AVTreeNode *child[2];
- void *elem;
- int state;
-} AVTreeNode;
+#include "tree_internal.h"
const int av_tree_node_size = sizeof(AVTreeNode);
diff --git a/libavutil/tree_internal.h b/libavutil/tree_internal.h
new file mode 100644
index 00000000000..6207c321a8e
--- /dev/null
+++ b/libavutil/tree_internal.h
@@ -0,0 +1,28 @@
+/*
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_TREE_INTERNAL_H
+#define AVUTIL_TREE_INTERNAL_H
+
+typedef struct AVTreeNode {
+ struct AVTreeNode *child[2];
+ void *elem;
+ int state;
+} AVTreeNode;
+
+#endif /* AVUTIL_TREE_INTERNAL_H */
diff --git a/tests/fate/libavutil.mak b/tests/fate/libavutil.mak
index 6bf03b24386..b7df499a29c 100644
--- a/tests/fate/libavutil.mak
+++ b/tests/fate/libavutil.mak
@@ -74,6 +74,10 @@ FATE_LIBAVUTIL += fate-dict
fate-dict: libavutil/tests/dict$(EXESUF)
fate-dict: CMD = run libavutil/tests/dict$(EXESUF)
+FATE_LIBAVUTIL += fate-map
+fate-map: libavutil/tests/map$(EXESUF)
+fate-map: CMD = run libavutil/tests/map$(EXESUF)
+
FATE_LIBAVUTIL += fate-encryption-info
fate-encryption-info: libavutil/tests/encryption_info$(EXESUF)
fate-encryption-info: CMD = run libavutil/tests/encryption_info$(EXESUF)
diff --git a/tests/ref/fate/map b/tests/ref/fate/map
new file mode 100644
index 00000000000..6d1699ef4b7
--- /dev/null
+++ b/tests/ref/fate/map
@@ -0,0 +1,27 @@
+testing empty set
+
+testing 1-set
+
+testing n-set
+1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+the key=the value 8,10 n=n 2,2 á=á 2,2 "=" 2,2 ]=] 2,2 ¶=¶ 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 ‘=‘ 2,2 ²=² 2,2 = 2,2 Æ=Æ 2,2 )=) 2,2 º=º 2,2 e=e 2,2 Ž=Ž 2,2 A=A 2,2 B=B 2,2 ½=½ 2,2 Ö=Ö 2,2 Ù=Ù 2,2 J=J 2,2 •=• 2,2 ž=ž 2,2 ñ=ñ 2,2 Ò=Ò 2,2 í=í 2,2 æ=æ 2,2 ‰=‰ 2,2 Ú=Ú 2,2 Å=Å 2,2 ®=® 2,2 ¡=¡ 2,2 b=b 2,2 \x1d=\x1d 2,2 ö=ö 2,2 9=9 2,2 j=j 2,2 õ=õ 2,2 ¾=¾ 2,2 Q=Q 2,2 ò=ò 2,2 M=M 2,2 \x06=\x06 2,2 é=é 2,2 ú=ú 2,2 %=% 2,2 Î=Î 2,2 \x01=\x01 2,2 ‚=‚ 2,2 }=} 2,2 \x16=\x16 2,2 ™=™ 2,2 Š=Š 2,2 U=U 2,2 Þ=Þ 2,2 ±=± 2,2 \x12=\x12 2,2 = 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 …=… 2,2 î=î 2,2 a=a 2,2 ¢=¢ 2,2 Ý=Ý 2,2 6=6 2,2 ù=ù 2,2 ª=ª 2,2 µ=µ 2,2 þ=þ 2,2 \x11=\x11 2,2 2=2 2,2 \r=\r 2,2 F=F 2,2 ©=© 2,2 :=: 2,2 å=å 2,2 \x0e=\x0e 2,2 Á=Á 2,2 Â=Â 2,2 === 2,2 V=V 2,2 Y=Y 2,2 Ê=Ê 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 q=q 2,2 R=R 2,2 m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2 â=â 2,2 = 2,2 v=v 2,2 ¹=¹ 2,2 ê=ê 2,2 u=u 2,2 >=> 2,2 Ñ=Ñ 2,2 r=r 2,2 Í=Í 2,2 †=† 2,2 i=i 2,2 z=z 2,2 ¥=¥ 2,2 N=N 2,2 = 2,2 \x02=\x02 2,2 ý=ý 2,2 –=– 2,2 \x19=\x19 2,2
+=
+ 2,2 Õ=Õ 2,2 ^=^ 2,2 1=1 2,2 ’=’ 2,2 -=- 2,2 ¦=¦ 2,2 É=É 2,2 š=š 2,2 \x05=\x05 2,2
+testing empty set
+
+testing 1-set
+
+testing n-set
+1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+the key=the value 8,10 n=n 2,2 á=á 2,2 "=" 2,2 ]=] 2,2 ¶=¶ 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 ‘=‘ 2,2 ²=² 2,2 = 2,2 Æ=Æ 2,2 )=) 2,2 º=º 2,2 e=e 2,2 Ž=Ž 2,2 A=A 2,2 B=B 2,2 ½=½ 2,2 Ö=Ö 2,2 Ù=Ù 2,2 J=J 2,2 •=• 2,2 ž=ž 2,2 ñ=ñ 2,2 Ò=Ò 2,2 í=í 2,2 æ=æ 2,2 ‰=‰ 2,2 Ú=Ú 2,2 Å=Å 2,2 ®=® 2,2 ¡=¡ 2,2 b=b 2,2 \x1d=\x1d 2,2 ö=ö 2,2 9=9 2,2 j=j 2,2 õ=õ 2,2 ¾=¾ 2,2 Q=Q 2,2 ò=ò 2,2 M=M 2,2 \x06=\x06 2,2 é=é 2,2 ú=ú 2,2 %=% 2,2 Î=Î 2,2 \x01=\x01 2,2 ‚=‚ 2,2 }=} 2,2 \x16=\x16 2,2 ™=™ 2,2 Š=Š 2,2 U=U 2,2 Þ=Þ 2,2 ±=± 2,2 \x12=\x12 2,2 = 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 …=… 2,2 î=î 2,2 a=a 2,2 ¢=¢ 2,2 Ý=Ý 2,2 6=6 2,2 ù=ù 2,2 ª=ª 2,2 µ=µ 2,2 þ=þ 2,2 \x11=\x11 2,2 2=2 2,2 \r=\r 2,2 F=F 2,2 ©=© 2,2 :=: 2,2 å=å 2,2 \x0e=\x0e 2,2 Á=Á 2,2 Â=Â 2,2 === 2,2 V=V 2,2 Y=Y 2,2 Ê=Ê 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 q=q 2,2 R=R 2,2 m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2 â=â 2,2 = 2,2 v=v 2,2 ¹=¹ 2,2 ê=ê 2,2 u=u 2,2 >=> 2,2 Ñ=Ñ 2,2 r=r 2,2 Í=Í 2,2 †=† 2,2 i=i 2,2 z=z 2,2 ¥=¥ 2,2 N=N 2,2 = 2,2 \x02=\x02 2,2 ý=ý 2,2 –=– 2,2 \x19=\x19 2,2
+=
+ 2,2 Õ=Õ 2,2 ^=^ 2,2 1=1 2,2 ’=’ 2,2 -=- 2,2 ¦=¦ 2,2 É=É 2,2 š=š 2,2 \x05=\x05 2,2
+testing empty set
+
+testing 1-set
+
+testing n-set
+1111111111111111111111111111111111011101111111111111111111111111101111111111111111111011101001101111011011011001011111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+the key=the value 8,10 n=n 2,2 á=á 2,2 "=" 2,2 ]=] 2,2 ¶=¶ 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 ‘=‘ 2,2 ²=² 2,2 = 2,2 Æ=Æ 2,2 )=) 2,2 º=º 2,2 e=e 2,2 Ž=Ž 2,2 A=A 2,2 B=B 2,2 ½=½ 2,2 Ö=Ö 2,2 Ù=Ù 2,2 J=J 2,2 •=• 2,2 ž=ž 2,2 ñ=ñ 2,2 Ò=Ò 2,2 í=í 2,2 æ=æ 2,2 ‰=‰ 2,2 Ú=Ú 2,2 Å=Å 2,2 ®=® 2,2 ¡=¡ 2,2 \x1d=\x1d 2,2 ö=ö 2,2 9=9 2,2 õ=õ 2,2 ¾=¾ 2,2 Q=Q 2,2 ò=ò 2,2 M=M 2,2 \x06=\x06 2,2 é=é 2,2 ú=ú 2,2 %=% 2,2 Î=Î 2,2 \x01=\x01 2,2 ‚=‚ 2,2 }=} 2,2 \x16=\x16 2,2 ™=™ 2,2 Š=Š 2,2 U=U 2,2 Þ=Þ 2,2 ±=± 2,2 \x12=\x12 2,2 = 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 …=… 2,2 î=î 2,2 ¢=¢ 2,2 Ý=Ý 2,2 6=6 2,2 ù=ù 2,2 ª=ª 2,2 µ=µ 2,2 þ=þ 2,2 \x11=\x11 2,2 2=2 2,2 \r=\r 2,2 F=F 2,2 ©=© 2,2 :=: 2,2 å=å 2,2 \x0e=\x0e 2,2 Á=Á 2,2 Â=Â 2,2 === 2,2 V=V 2,2 Ê=Ê 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 R=R 2,2 = 2,2 Z=Z 2,2 .=. 2,2 !=! 2,2 â=â 2,2 = 2,2 ¹=¹ 2,2 ê=ê 2,2 >=> 2,2 Ñ=Ñ 2,2 Í=Í 2,2 †=† 2,2 ¥=¥ 2,2 = 2,2 \x02=\x02 2,2 ý=ý 2,2 –=– 2,2 \x19=\x19 2,2
+=
+ 2,2 Õ=Õ 2,2 ^=^ 2,2 1=1 2,2 ’=’ 2,2 -=- 2,2 ¦=¦ 2,2 É=É 2,2 š=š 2,2 \x05=\x05 2,2
--
2.49.0
[-- Attachment #2: Type: text/plain, Size: 251 bytes --]
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-17 16:52 [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap Michael Niedermayer
@ 2025-04-17 17:57 ` Nicolas George
2025-04-17 20:12 ` Michael Niedermayer
2025-04-19 10:36 ` Leo Izen
1 sibling, 1 reply; 11+ messages in thread
From: Nicolas George @ 2025-04-17 17:57 UTC (permalink / raw)
To: FFmpeg development discussions and patches
Michael Niedermayer (HE12025-04-17):
> +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->copy = copy;
> + s->freef = freef;
> +
> + av_map_add_cmp_func(s, cmp_keyvalue, cmp_flags);
> +
> + return s;
> +}
If you do not want to do the version where dynamic allocation can be
avoided, would you at least consider using _alloc() for this? It is only
to letters more, it is consistent with the rest of the API and it would
leave _new() available if somebody adds the lighter version.
I really do not understand why you do not want to do this: it is a very
useful low-hanging fruit, and it is quite elegant and fun to implement.
Alas, you did not reply to my last round of arguments.
> + * @param keyvalue_cmp compare function, will be passed the key + value concatenated.
Please no. Pass the key and the value separately to the compare
function.
> +/**
> + * 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 compare function to be added.
> + * cmp(a,b) must return 0 or be equal to the previously added compare function for (a,b), if it returns 0 it also must do so for all
> + * elements between a and b
> + *
> + * @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 cmp, int cmp_flags);
This whole thing with multiple compare functions makes the code quite
hard to understand. And not just the code: it makes the API itself hard
to understand.
I think the practical goal it server could be achieved in a simpler way.
If I understand correctly, it servers to allow the equivalent of
AV_DICT_IGNORE_SUFFIX and such. It would be simpler to have a flag to
av_map_find() to let it return the first key >= to the searched key.
Regards,
--
Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-17 17:57 ` Nicolas George
@ 2025-04-17 20:12 ` Michael Niedermayer
2025-04-18 14:46 ` Leo Izen
2025-04-19 13:03 ` Nicolas George
0 siblings, 2 replies; 11+ messages in thread
From: Michael Niedermayer @ 2025-04-17 20:12 UTC (permalink / raw)
To: FFmpeg development discussions and patches
[-- Attachment #1.1: Type: text/plain, Size: 5901 bytes --]
Hi
On Thu, Apr 17, 2025 at 07:57:46PM +0200, Nicolas George wrote:
> Michael Niedermayer (HE12025-04-17):
> > +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->copy = copy;
> > + s->freef = freef;
> > +
> > + av_map_add_cmp_func(s, cmp_keyvalue, cmp_flags);
> > +
> > + return s;
> > +}
>
> If you do not want to do the version where dynamic allocation can be
> avoided, would you at least consider using _alloc() for this? It is only
> to letters more, it is consistent with the rest of the API and it would
> leave _new() available if somebody adds the lighter version.
ok, i will change teh name
>
> I really do not understand why you do not want to do this: it is a very
> useful low-hanging fruit, and it is quite elegant and fun to implement.
You can implement an av_map_new() variant thats on the stack
if thats what you want to have / to use / to do
once the code is in git
or maybe i will do it but there are many more interresting things
> Alas, you did not reply to my last round of arguments.
yes, mails take alot of time to read and reply to.
>
> > + * @param keyvalue_cmp compare function, will be passed the key + value concatenated.
>
> Please no. Pass the key and the value separately to the compare
> function.
thats neither efficient nor does it fit the existing APIs.
The value is most of the time not used and when used it is known exactly
where it is. after a string compare of the key thats equal the value location is known
or with arbitrary binary data the compare function knows the size of the data.
Passing redudant pointers just wastes cpu cycles
also existing APIs from av_tree strcmp() av_strcasecmp() and so on none of
which take 4 pointers from which they would ignore 2.
>
> > +/**
> > + * 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 compare function to be added.
> > + * cmp(a,b) must return 0 or be equal to the previously added compare function for (a,b), if it returns 0 it also must do so for all
> > + * elements between a and b
> > + *
> > + * @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 cmp, int cmp_flags);
>
> This whole thing with multiple compare functions makes the code quite
> hard to understand. And not just the code: it makes the API itself hard
> to understand.
>
> I think the practical goal it server could be achieved in a simpler way.
>
> If I understand correctly, it servers to allow the equivalent of
> AV_DICT_IGNORE_SUFFIX and such. It would be simpler to have a flag to
> av_map_find() to let it return the first key >= to the searched key.
There is
AV_MAP_CMP_CASE_SENSITIVE
AV_MAP_CMP_CASE_INSENSITIVE
AV_MAP_CMP_KEY
AV_MAP_CMP_KEYVALUE
AV_MAP_CMP_TRUNCATED
AV_MAP_CMP_NON_TRUNCATED
and these are passed to av_map_get() no compare function.
the compare functions are needed purely for setup. And there
they are needed because of arbitrary data support. av_map cannot
know how to compare your data. (if its not strings)
but something like a av_map_find() that returns the closest
previous and next matching and mismatching entries is a good idea too.
But the existing code is much simpler:
AVMapEntry e = NULL;
while (e = av_map_get_multiple(set, e, "author", AV_MAP_CMP_CASE_INSENSITIVE | AV_MAP_CMP_KEY) {
printf("Tag key:%s value:%s\n", e->key, e->value);
}
vs:
/**
*
* @param surroundings these are the 2 closest non matching and 2 farthest matching entries
*/
const AVMapEntry *av_map_get_find(const AVMap *s, AVMapEntry *surroundings[4], const char *keyvalue, int flags);
you would probably need something like this:
(which is alot uglier and probably contains bugs)
AVMapEntry *e4[4] = {NULL};
AVMapEntry *e = av_map_find(set, e4, "author", AV_MAP_CMP_KEY); //We hope that "author" is the first in the ordering of case insensitive strings
if (e4[2]) // we compare just the key so we can have multiple matches and need to take the first not any
e = e4[2];
if (!e)
e = e4[1]; //if we have no exact match we start with the next non match which may be matching with case insensitive compare
while(e) {
if (!av_strcasecmp(e->key, "author")) {
printf("Tag key:%s value:%s\n", e->key, e->value);
} else {
break;
}
memset(e4, 0, sizeof(e4));
av_map_find(set, e4, e->key, 0);
e = e4[1];
}
Also the code above will just give wrong results with no warning if the compare
function the map is setup with is incompatible with
thx
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]
[-- Attachment #2: Type: text/plain, Size: 251 bytes --]
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-17 20:12 ` Michael Niedermayer
@ 2025-04-18 14:46 ` Leo Izen
2025-04-19 1:23 ` Michael Niedermayer
2025-04-19 13:03 ` Nicolas George
1 sibling, 1 reply; 11+ messages in thread
From: Leo Izen @ 2025-04-18 14:46 UTC (permalink / raw)
To: ffmpeg-devel
On 4/17/25 16:12, Michael Niedermayer wrote:
>>
>>> + * @param keyvalue_cmp compare function, will be passed the key + value concatenated.
>>
>> Please no. Pass the key and the value separately to the compare
>> function.
>
> thats neither efficient nor does it fit the existing APIs.
> The value is most of the time not used and when used it is known exactly
> where it is. after a string compare of the key thats equal the value location is known
> or with arbitrary binary data the compare function knows the size of the data.
> Passing redudant pointers just wastes cpu cycles
> also existing APIs from av_tree strcmp() av_strcasecmp() and so on none of
> which take 4 pointers from which they would ignore 2.
>
The problem is that passing the key and value pairs combined requires
you to concatenate them. Since AVMapEntry has two separate pointers *key
and *value, it doesn't make sense to concatenate them before comparison
rather than just pass the pointers as-is.
- Leo Izen (Traneptora)
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-18 14:46 ` Leo Izen
@ 2025-04-19 1:23 ` Michael Niedermayer
0 siblings, 0 replies; 11+ messages in thread
From: Michael Niedermayer @ 2025-04-19 1:23 UTC (permalink / raw)
To: FFmpeg development discussions and patches
[-- Attachment #1.1: Type: text/plain, Size: 1346 bytes --]
On Fri, Apr 18, 2025 at 10:46:42AM -0400, Leo Izen wrote:
> On 4/17/25 16:12, Michael Niedermayer wrote:
> > >
> > > > + * @param keyvalue_cmp compare function, will be passed the key + value concatenated.
> > >
> > > Please no. Pass the key and the value separately to the compare
> > > function.
> >
> > thats neither efficient nor does it fit the existing APIs.
> > The value is most of the time not used and when used it is known exactly
> > where it is. after a string compare of the key thats equal the value location is known
> > or with arbitrary binary data the compare function knows the size of the data.
> > Passing redudant pointers just wastes cpu cycles
> > also existing APIs from av_tree strcmp() av_strcasecmp() and so on none of
> > which take 4 pointers from which they would ignore 2.
> >
> The problem is that passing the key and value pairs combined requires you to
> concatenate them. Since AVMapEntry has two separate pointers *key and
> *value, it doesn't make sense to concatenate them before comparison
> rather than just pass the pointers as-is.
AVMapEntry.key and value are always concatenate already
thx
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Nations do behave wisely once they have exhausted all other alternatives.
-- Abba Eban
[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]
[-- Attachment #2: Type: text/plain, Size: 251 bytes --]
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-17 16:52 [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap Michael Niedermayer
2025-04-17 17:57 ` Nicolas George
@ 2025-04-19 10:36 ` Leo Izen
2025-04-19 14:39 ` Michael Niedermayer
1 sibling, 1 reply; 11+ messages in thread
From: Leo Izen @ 2025-04-19 10:36 UTC (permalink / raw)
To: ffmpeg-devel
On 4/17/25 12:52, Michael Niedermayer wrote:
> AVL Tree based Map
>
> compared to AVDictionary this has
> * clone is O(n) instead of O(n²)
> * copy is O(n*log n) instead of O(n²)
> * O(log n) malloc() calls by default and O(1) if av_map_realloc() is used instead of O(n)
> * get/add/delete is O(log n)
> *
> * You can add (if memory is realloced before) and remove entries while a iterator stays valid
> * copy is atomic, a failure means the dst is unchanged
> *
> * there are restrictions on what compare function can be used on get depending on how the Map was created
> * you can mix case sensitive and case insensitive compare with av_map_supercmp_*
> * Supports binary objects, not just strings
>
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---
> libavutil/Makefile | 3 +
> libavutil/map.c | 415 ++++++++++++++++++++++++++++++++++++++
> libavutil/map.h | 270 +++++++++++++++++++++++++
> libavutil/tests/map.c | 221 ++++++++++++++++++++
> libavutil/tree.c | 6 +-
> libavutil/tree_internal.h | 28 +++
> tests/fate/libavutil.mak | 4 +
> tests/ref/fate/map | 27 +++
> 8 files changed, 969 insertions(+), 5 deletions(-)
> create mode 100644 libavutil/map.c
> create mode 100644 libavutil/map.h
> create mode 100644 libavutil/tests/map.c
> create mode 100644 libavutil/tree_internal.h
> create mode 100644 tests/ref/fate/map
>
> diff --git a/libavutil/Makefile b/libavutil/Makefile
> index 9ef118016bb..3a92748a482 100644
> --- a/libavutil/Makefile
> +++ b/libavutil/Makefile
> @@ -81,6 +81,7 @@ HEADERS = adler32.h \
> replaygain.h \
> ripemd.h \
> samplefmt.h \
> + map.h \
> sha.h \
> sha512.h \
> spherical.h \
> @@ -173,6 +174,7 @@ OBJS = adler32.o \
> rc4.o \
> ripemd.o \
> samplefmt.o \
> + map.o \
> side_data.o \
> sha.o \
> sha512.o \
> @@ -290,6 +292,7 @@ TESTPROGS = adler32 \
> random_seed \
> rational \
> ripemd \
> + map \
> sha \
> sha512 \
> side_data_array \
> diff --git a/libavutil/map.c b/libavutil/map.c
> new file mode 100644
> index 00000000000..59b87a1f074
> --- /dev/null
> +++ b/libavutil/map.c
> @@ -0,0 +1,415 @@
> +/*
> + * Copyright (c) 2025 Michael Niedermayer
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <inttypes.h>
> +#include <string.h>
> +
> +#include "avassert.h"
> +#include "avstring.h"
> +#include "error.h"
> +#include "mem.h"
> +#include "map.h"
> +
> +#include "tree_internal.h" // For improved readability with AVTreeNode, do NOT touch AVTreeNode internals
> +
> +typedef struct{
> + AVMapEntry map_entry;
> + uint8_t treenode_and_keyvalue[0];
> +} AVMapInternalEntry;
> +
> +struct AVMap{
> +#define CMP_MASK 31
> + AVMapCompareFunc cmp[27];
> + AVMapCopyFunc copy;
> + AVMapFreeFunc freef;
> + int count;
> + int deleted;
> + int next; ///< index of entry in root array after all used entries
Indices into arrays and counts and the like should be size_t.
> + unsigned internal_entries_len;
> + AVTreeNode *tree_root;
> + AVMapInternalEntry *internal_entries;
> +};
> +
> +static uint8_t deleted_entry;
static const should allow the compiler to put it in a different section
if it wishes. You can still address it even then.
> +
> +static inline int internal_entry_len(AVMapInternalEntry *I) {
> + return (I->map_entry.keylen + I->map_entry.valuelen + sizeof (*I) + sizeof(AVTreeNode) - 1) / sizeof (*I) + 1;
> +}
> +
> +static inline AVTreeNode * internal_treenode(const AVMapInternalEntry *I)
> +{
> + return (AVTreeNode *)I->treenode_and_keyvalue;
> +}
> +
> +static inline uint8_t * internal_key(AVMapInternalEntry *I)
> +{
> + return I->treenode_and_keyvalue + sizeof(AVTreeNode);
> +}
> +
> +static inline uint8_t * internal_value(AVMapInternalEntry *I)
> +{
> + return I->treenode_and_keyvalue + sizeof(AVTreeNode) + I->map_entry.keylen;
> +}
> +
> +static inline AVMapInternalEntry * keyvalue2internal(const uint8_t *keyvalue)
> +{
> + return (AVMapInternalEntry*)(keyvalue - offsetof(AVMapInternalEntry, treenode_and_keyvalue) - sizeof(AVTreeNode));
> +}
> +
> +int av_map_strcmp_keyvalue(const char *a, const char *b)
> +{
> + int v = strcmp(a,b);
> + if(!v)
> + v = strcmp(a + strlen(a) + 1, b + strlen(a) + 1); // please optimize this dear compiler, we know the strlen after strcmp()
> + return v;
> +}
> +
> +int av_map_supercmp_key(const char *a, const char *b)
> +{
> + int v = av_strcasecmp(a,b);
> + if (!v)
> + v = strcmp(a,b);
> +
> + return v;
> +}
> +
> +int av_map_supercmp_keyvalue(const char *a, const char *b)
> +{
> + int v = av_map_supercmp_key(a,b);
> + if (!v)
> + v = strcmp(a + strlen(a) + 1, b + strlen(a) + 1);
> +
> + return v;
> +}
> +
> +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);
Need to check for cmp_flags >= 27U before indexing into the array. The
compiler may pull this array off the stack cause it's static const so
you risk hitting a dead page here.
> +
> + 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->copy = copy;
> + s->freef = freef;
> +
> + av_map_add_cmp_func(s, cmp_keyvalue, cmp_flags);
No check for return value. av_map_add_cmp_func can return
AVERROR(EINVAL) depending on cmp_flags.
> +
> + return s;
> +}
> +
> +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[0], next_node, 2);
> + av_assert2(prev_keyvalue);
> + if (!next_node[1] || cmp(next_node[1], keyvalue))
> + return NULL;
> +
> + keyvalue = next_node[1];
> + } else {
> + void *next_node[4] = { NULL, NULL, NULL, NULL };
> + keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, next_node, 4);
> + if (next_node[2]) // If we have a leftmost equal keyvalue, use it instead
> + keyvalue = next_node[2];
> + }
> +
> + if (!keyvalue)
> + return NULL;
> +
> + return &keyvalue2internal(keyvalue)->map_entry;
> +}
> +
> +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)
> + return NULL;
> +
> + return &keyvalue2internal(keyvalue)->map_entry;
> +}
> +
> +static void update_pointers(AVMap *dst, AVMapInternalEntry *dst_internal_entries, const AVMapInternalEntry *src_internal_entries)
> +{
> + AVTreeNode *src_tree_root = dst->tree_root;
> +
> + if (src_tree_root) {
> + dst->tree_root = src_tree_root - internal_treenode(src_internal_entries) + internal_treenode(dst_internal_entries);
> + av_tree_move(dst->tree_root, src_tree_root, dst_internal_entries, src_internal_entries);
> + }
> +
> + //TODO We could attempt to compact free space
> + for(int i = 0; i<dst->next; i++) {
> + if (dst_internal_entries[i].map_entry.key != &deleted_entry) {
> + dst_internal_entries[i].map_entry.key = internal_key (dst_internal_entries + i);
> + dst_internal_entries[i].map_entry.value = internal_value(dst_internal_entries + i);
> + }
> + i += internal_entry_len(dst_internal_entries + i) - 1;
> + }
> + dst->internal_entries = dst_internal_entries;
> +}
> +
> +int av_map_realloc(AVMap *s, int extra_elements, int extra_space) {
> + int64_t advance = extra_elements + (extra_space + (int64_t)extra_elements*(sizeof(*s->internal_entries) + sizeof(AVTreeNode) - 1)) / sizeof(*s->internal_entries);
> +
> + if (advance > (INT32_MAX - s->next) / sizeof(AVMapInternalEntry))
> + return AVERROR(ENOMEM);
> +
> + AVMapInternalEntry *new_internal_entries = av_fast_realloc(s->internal_entries, &s->internal_entries_len, (s->next + advance) * sizeof(AVMapInternalEntry));
> +
> + if (!new_internal_entries)
> + return AVERROR(ENOMEM);
> +
> + if (new_internal_entries != s->internal_entries) {
> + update_pointers(s, new_internal_entries, s->internal_entries);
> + }
Code style: remove {}
> + return advance;
> +}
> +
> +int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int valuelen, int flags)
> +{
> + av_assert2(keylen || valuelen); // patch welcome but how would the compare function compare a len=0 element without knowing it is a len 0 element
> +
This is a public function so we should be returning AVERROR(EINVAL) on
invalid input rather than asserting. Since a library user could do that.
> + int advance = av_map_realloc(s, 1, keylen + valuelen);
> + if (advance < 0)
> + return advance;
> +
> + AVMapEntry *entry = &s->internal_entries[s->next].map_entry;
> + AVTreeNode *next = internal_treenode(s->internal_entries + s->next);
> + memset(next, 0, sizeof(*next));
> + entry->keylen = keylen;
> + entry->valuelen= valuelen;
> + entry->key = internal_key (s->internal_entries + s->next);
> + entry->value = internal_value(s->internal_entries + s->next);
> + memcpy(entry->key , key , keylen);
> + memcpy(entry->value, value, valuelen);
> +
> + 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, flags & ~CMP_MASK);
> + av_assert2(ret == 1);
> + elem = av_tree_insert(&s->tree_root, entry->key, s->cmp[0], &next);
> + av_assert2(elem == entry->key || !elem);
> + ret = 2;
> + } else
> + return 0; //entry already in the map
> + }
> + av_assert2(!next);
> + av_assert2(s->tree_root);
> + s->next += advance;
> + s->count++;
> +
> + return ret;
> +}
> +
> +int av_map_add_strings(AVMap *s, const char *key, const char *value, int flags)
> +{
> + return av_map_add(s, key, strlen(key)+1, value, strlen(value)+1, 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[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
> + old_keyvalue = av_tree_find2(s->tree_root, keyvalue, cmp, NULL, 0);
> + if (!old_keyvalue)
> + return 0;
> +
> + 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[0], &next);
> + if (!next)
> + return 0;
> + old_keyvalue = next->elem; //TODO add a API to av_tree() to return the elem of a AVTreeNode
> +
> + }
> + AVMapInternalEntry *internal_entry = keyvalue2internal(old_keyvalue);
> + internal_entry->map_entry.key = &deleted_entry;
> +
> + s->count--;
> + s->deleted++;
> +
> + if ((flags & AV_MAP_ALLOW_REBUILD) && s->deleted > s->count) {
> + 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);
> + } else {
> + if (s->freef)
> + for (int i=0; i<s->count; i++)
> + s->freef(&s->internal_entries[i].map_entry);
> + av_freep(&s->internal_entries);
> + memcpy(s, news, sizeof(*s));
> + }
> + }
> + }
> +
> + return 1;
> +}
> +
> +const AVMapEntry *av_map_iterate(const AVMap *s,
> + const AVMapEntry *prev)
> +{
> + AVMapInternalEntry *I;
> + if (prev) {
> + I = (AVMapInternalEntry*)((uint8_t*)prev - offsetof(AVMapInternalEntry, map_entry));
> + I += internal_entry_len(I);
> + } else {
> + I = s->internal_entries;
> + }
> + while (I < s->internal_entries + s->next && I->map_entry.key == &deleted_entry)
> + I += internal_entry_len(I);
> +
> + if (I == s->internal_entries + s->next)
> + return NULL;
> +
> + return &I->map_entry;
> +}
> +
> +int av_map_count(const AVMap *s)
> +{
> + return s->count;
> +}
> +
> +void av_map_free(AVMap **sp)
> +{
> + AVMap *s = *sp;
> +
> + for (int i=0; i<s->count; i++) {
> + if (s->freef)
> + s->freef(&s->internal_entries[i].map_entry);
> + }
> + av_freep(&s->internal_entries);
> + s->next =
> + s->internal_entries_len =
> + s->count = 0;
> + av_freep(sp);
> +}
> +
> +int av_map_copy(AVMap *dst, const AVMap *src)
> +{
> + const AVMapEntry *t = NULL;
> + AVMap *bak = av_memdup(dst, sizeof(*dst));
> + if (!bak)
> + return AVERROR(ENOMEM);
> +
> + AVMapInternalEntry *new_internal_entries = av_memdup(bak->internal_entries, bak->internal_entries_len);
> + AVMapInternalEntry *old_internal_entries = dst->internal_entries;
We don't allow mixed delcarations and statements. Hoist the defintion
above if (!bak) and then put the assignment below it.
> +
> + while ((t = av_map_iterate(src, t))) {
> + int ret = av_map_add(dst, t->key, t->keylen, t->value, t->valuelen, 0);
> +
> + if (ret < 0) {
> + update_pointers(bak, new_internal_entries, old_internal_entries);
> + av_free(dst->internal_entries);
> + memcpy(dst, bak, sizeof(*dst));
> + return ret;
You leak bak here. Possibly new_internal_entries as well.
> + }
> + }
> +
> + av_freep(&new_internal_entries);
> + av_free(bak);
> +
> + return 0;
> +}
> +
> +AVMap *av_map_clone(AVMap *s)
> +{
> + AVMap *dst = av_memdup(s, sizeof(AVMap));
> +
> + if (!dst)
> + return NULL;
> +
> + dst->internal_entries = av_memdup(s->internal_entries, s->internal_entries_len);
> +
> + if (!dst->internal_entries)
> + goto err;
> +
> + update_pointers(dst, dst->internal_entries, s->internal_entries);
> +
> + return dst;
> +err:
> + if (dst) {
> + av_freep(&dst->internal_entries);
> + }
Code style: remove {}
> + av_free(dst);
> + return NULL;
> +}
> diff --git a/libavutil/map.h b/libavutil/map.h
> new file mode 100644
> index 00000000000..03572960306
> --- /dev/null
> +++ b/libavutil/map.h
> @@ -0,0 +1,270 @@
> +/*
> + * Copyright (c) 2025 Michael Niedermayer
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +/**
> + * @file
> + * Public map API.
> + */
> +
> +#ifndef AVUTIL_MAP_H
> +#define AVUTIL_MAP_H
> +
> +#include <stdint.h>
> +
> +#include "tree.h"
> +
> +/**
> + * compared to AVDictionary this has
> + * clone is O(n) instead of O(n²)
> + * copy is O(n*log n) instead of O(n²)
> + * O(log n) malloc() calls by default and O(1) if av_map_realloc() is used instead of O(n)
> + * get/add/delete is O(log n)
> + *
> + * You can add (if memory is realloced before) and remove entries while a iterator stays valid
> + * copy is atomic, a failure means the dst is unchanged
> + *
> + * there are restrictions on what compare function can be used on get depending on how the Map was created
> + * you can mix case sensitive and case insensitive compare with av_map_supercmp_*
> + * Supports binary objects, not just strings
> + */
> +
> +enum {
> +//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 {
> + uint8_t *key;
> + uint8_t *value;
Any particular reason to use unsigned char here rather than just char
when working with strings? Most string stuff expects signed char.
> + int keylen;
> + int valuelen;
size_t for lengths
> +} AVMapEntry;
> +
> +typedef struct AVMap AVMap;
> +typedef void (* AVMapFreeFunc)(AVMapEntry *c);
> +typedef void (* AVMapCopyFunc)(AVMapEntry *dst, const AVMapEntry *src, size_t len);
> +typedef int (* AVMapCompareFunc)(const void *keyvalue, const void *b);
> +
> +/**
> + * like strcmp() but compares concatenated keyvalues.
> + *
> + * A map initialized with this will allow duplicate keys as long as their values differ.
> + */
> +int av_map_strcmp_keyvalue(const char *a, const char *b);
> +
> +/**
> + * like av_map_strcmp_keyvalue() but is compatible with av_strcasecmp() and av_map_supercmp_key.
> + *
> + * A map initialized with this will allow duplicate keys as long as their values differ.
> + */
> +int av_map_supercmp_keyvalue(const char *a, const char *b);
> +
> +/**
> + * like strcmp() but is compatible with av_strcasecmp().
> + *
> + * A map initialized with this will not allow duplicate keys.
> + */
> +int av_map_supercmp_key(const char *a, const char *b);
I don't believe it's clear if and when a user should call these
functions or simply pass them by address. If so, we should use the
typedef, or at least reference it in the doc comment.
> +
> +
> +/**
> + *
> + * @param keyvalue_cmp compare function, will be passed the key + value concatenated.
> + * it should form a strict total order on all elements you want to store. each key-value pair
> + * can only occur once. Though there can be multiple values for the same key. IF this function
> + * treats them as different.
> + *
> + * if the keyvalue_cmp is inconsistant, for example a < b && b < a, reading may still work as long
> + * as the function later used for reading treats all elements in the inconsistant subset as
> + * equal this is not supported or recommanded but rather documented for completeness. Deleting
> + * elements of such inconsistant subsets should not be expected to work.
> + *
> + * @param freef receives a AVMapEntry and should free any resources except the AVMapEntry->key/value pointer itself
> + * for flat structs like strings, this is simply NULL
> + *
> + * Key Value compaibility
> + * av_map_supercmp_keyvalue X!=x X!=x av_map_supercmp_key, av_strcasecmp, (trucated av_strcasecmp)
> + * av_map_supercmp_key X!=x av_strcasecmp, (trucated av_strcasecmp)
> + * av_strcasecmp X==x truncation
> + *
> + * av_map_strcmp_keyvalue X!=x X!=x strcmp, truncation
> + * strcmp X!=x truncation
> + *
> + *
> + */
> +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 compare function to be added.
> + * cmp(a,b) must return 0 or be equal to the previously added compare function for (a,b), if it returns 0 it also must do so for all
> + * elements between a and b
> + *
> + * @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 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
> + *
> + * This can be used to avoid repeated memory reallocation.
> + *
> + * @param extra_elements number of new elements to be added
> + * @param extra_space sum of keylen and valuelen of all to be added elements
> + *
> + * @return <0 on error
> + */
> +int av_map_realloc(AVMap *s, int extra_elements, int extra_space);
> +
> +/**
> + * Add the given entry into a AVMap.
> + *
> + * @param s Pointer AVMap struct.
> + * @param value Entry value to add to *s
> + * @param valuelen length of value
> + * @param flags 0, AV_MAP_ALLOW_REBUILD, AV_MAP_REPLACE
> + *
> + * @return 1 if the entry was added, 0 if it was already in the map, 2 if it was replaced
> + * otherwise an error code <0
> + */
> +int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int valuelen, int flags);
> +int av_map_add_strings(AVMap *s, const char *key, const char *value, int flags);
> +
> +/**
> + * Delete the given entry from a AVMap.
> + *
> + * @param s Pointer AVMap struct.
> + * @param keyvalue key or concatenated key+value
> + * @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 flags);
> +
> +/**
> + * Iterate over possibly multiple matching map entries.
> + *
> + * The returned entry must not be changed, or it will
> + * cause undefined behavior.
> + *
> + * @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
> + *
> + * @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 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 flags);
> +
> +/**
> + * Iterate over a map
> + *
> + * Iterates through all entries in the map.
> + *
> + * @warning If you call any function with AV_SET_ALLOW_REBUILD set, then the iterator is
> + * invalidated, and must not be used anymore. Otherwise av_map_add() (without realloc) and av_map_del()
> + * can saftely be called during iteration.
> + *
> + * Typical usage:
> + * @code
> + * const AVMapEntry *e = NULL;
> + * while ((e = av_map_iterate(m, e))) {
> + * // ...
> + * }
> + * @endcode
> + *
> + * @param s The map to iterate over
> + * @param prev Pointer to the previous AVMapEntry, NULL initially
> + *
> + * @retval AVMapEntry* The next element in the map
> + * @retval NULL No more elements in the map
> + */
> +const AVMapEntry *av_map_iterate(const AVMap *s,
> + const AVMapEntry *prev);
> +
> +/**
> + * Get number of entries in map.
> + *
> + * @param s map
> + * @return number of entries in map
> + */
> +int av_map_count(const AVMap *s);
> +
> +/**
> + * Free all the memory allocated for an AVMap struct
> + * and all values.
> + */
> +void av_map_free(AVMap **s);
> +
> +AVMap *av_map_clone(AVMap *s);
> +
> +/**
> + * Copy entries from one AVMap struct into another.
> + *
> + * @param dst Pointer to a pointer to a AVMap struct to copy into. If *dst is NULL,
> + * this function will allocate a struct for you and put it in *dst
> + * @param src Pointer to the source AVMap struct to copy items from.
> + * @param flags Flags to use when setting entries in *dst
> + *
> + * @see when the initial dst map is empty use av_map_clone() as its faster
> + *
> + * @return 0 on success, negative AVERROR code on failure.
> + */
> +
> +int av_map_copy(AVMap *dst, const AVMap *src);
> +
> +#endif /* AVUTIL_MAP_H */
> diff --git a/libavutil/tests/map.c b/libavutil/tests/map.c
> new file mode 100644
> index 00000000000..7705eb31a95
> --- /dev/null
> +++ b/libavutil/tests/map.c
> @@ -0,0 +1,221 @@
> +/*
> + * copyright (c) 2025 Michael Niedermayer
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <string.h>
> +#include <stdio.h>
> +
> +#include "libavutil/avassert.h"
> +#include "libavutil/avstring.h"
> +#include "libavutil/mem.h"
> +#include "libavutil/map.h"
> +
> +
> +static void print_set(const AVMap *s)
> +{
> + const AVMapEntry *t = NULL;
> + while ((t = av_map_iterate(s, t)))
> + printf("%s=%s %d,%d ", t->key, t->value, t->keylen, t->valuelen);
> + printf("\n");
> +}
> +
> +int main(void)
> +{
> + void *our_cmp[] = {
> + strcmp,
> + av_map_strcmp_keyvalue,
> + av_strcasecmp,
> + 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,
> + av_strcasecmp,
> + 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], 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_subflags[settype]);
> + av_assert0(e == NULL);
> +
> + e = av_map_get(set, "foo", our_subflags[settype]);
> + av_assert0(e == NULL);
> +
> + int ret = av_map_del(set, "foo", our_subflags[settype]);
> + av_assert0(ret == 0);
> +
> + print_set(set);
> +
> + printf("testing 1-set\n");
> +
> + ret = av_map_add(set, "foo", 4, "bar", 4, 0);
> + av_assert0(ret == 1);
> +
> + 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_subflags[settype]);
> + av_assert0(!strcmp(e->key, "foo"));
> + if (settype == 1) {
> + av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar"));
> + } else {
> + av_assert0(!strcmp(e->value, "bar"));
> + }
> +
> + ret = av_map_add(set, "foo", 4, "bear", 5, AV_MAP_REPLACE);
> + av_assert0(ret == 2);
> +
> + 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"));
> + } else {
> + av_assert0(!strcmp(e->value, "bear"));
> + }
> +
> + 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_subflags[settype]);
> + if (settype == 1) {
> + av_assert0(!strcmp(e->key, "foo"));
> + av_assert0(!strcmp(e->value, "bear"));
> + } else {
> + av_assert0(e == NULL);
> + }
> +
> + ret = av_map_del(set, "foo", our_subflags[settype]);
> + av_assert0(ret == 1);
> +
> + 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"));
> + } else {
> + av_assert0(e == NULL);
> + }
> +
> + ret = av_map_del(set, "foo", our_subflags[settype]);
> + av_assert0(ret == ((int[]){0,1,0})[settype]);
> +
> +
> + print_set(set);
> +
> + printf("testing n-set\n");
> + unsigned r = 5;
> + int histogram[256] = {0};
> + for(int i=0; i<1000; i++) {
> + r = r*123 + 7;
> + unsigned char str[3] = {0};
> + str[0] = r;
> + ret = av_map_add(set, str, 2, str, 2 ,0);
> + if (i < 128) {
> + if (settype != 2) {
> + av_assert0(ret == 1);
> + } else {
> + av_assert0(ret == !histogram[av_toupper(str[0])]);
> + histogram[av_toupper(str[0])] = 1;
> + }
> + } else {
> + av_assert0(ret == 0);
> + }
> + printf("%d", ret);
> + }
> + printf("\n");
> +
> + r = 5;
> + for(int i=0; i<1000; i++) {
> + r = r*123 + 7;
> + char str[3] = {0};
> + str[0] = r;
> +
> + if (i == 51) {
> + AVMap *old = set;
> + set = av_map_clone(set);
> + av_map_del(old, str, 0);
> + av_map_free(&old);
> + }
> + if (i == 73) {
> + AVMap *old = set;
> + set = av_map_new(our_cmp[settype], our_flags[settype], NULL, NULL);
> + av_map_add_cmp_func(set, our_subcmp[settype], our_subflags[settype]);
> + ret = av_map_add_strings(set, "the key", "the value", 0);
> + av_map_copy(set, old);
> + av_map_del(old, str, 0);
> + av_map_free(&old);
> + }
> + e = av_map_get(set, str, our_subflags[settype]);
> + if (settype != 2) {
> + av_assert0(!strcmp(e->key, str));
> + av_assert0(!strcmp(e->value, str));
> + } else {
> + av_assert0(!av_strcasecmp(e->key, str));
> + av_assert0(!av_strcasecmp(e->value, str));
> + }
> + 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));
> + } else {
> + av_assert0(!av_strcasecmp(e->key, str));
> + av_assert0(!av_strcasecmp(e->value, str));
> + }
> + ret = av_map_add(set, str, 2, str, 2, 0);
> + av_assert0(ret == 0);
> +
> + str[1]='x';
> +
> + e = av_map_get(set, str, our_subflags[settype]);
> + av_assert0(e == NULL);
> + e = av_map_get_multiple(set, NULL, str, our_subflags[settype]);
> + av_assert0(e == NULL);
> + }
> + print_set(set);
> +
> + av_map_free(&set);
> + av_assert0(!set);
> + }
> +
> + return 0;
> +}
> diff --git a/libavutil/tree.c b/libavutil/tree.c
> index 708d4013f04..3007dc26d29 100644
> --- a/libavutil/tree.c
> +++ b/libavutil/tree.c
> @@ -24,11 +24,7 @@
> #include "mem.h"
> #include "tree.h"
>
> -typedef struct AVTreeNode {
> - struct AVTreeNode *child[2];
> - void *elem;
> - int state;
> -} AVTreeNode;
> +#include "tree_internal.h"
>
> const int av_tree_node_size = sizeof(AVTreeNode);
>
> diff --git a/libavutil/tree_internal.h b/libavutil/tree_internal.h
> new file mode 100644
> index 00000000000..6207c321a8e
> --- /dev/null
> +++ b/libavutil/tree_internal.h
> @@ -0,0 +1,28 @@
> +/*
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#ifndef AVUTIL_TREE_INTERNAL_H
> +#define AVUTIL_TREE_INTERNAL_H
> +
> +typedef struct AVTreeNode {
> + struct AVTreeNode *child[2];
> + void *elem;
> + int state;
> +} AVTreeNode;
> +
> +#endif /* AVUTIL_TREE_INTERNAL_H */
> diff --git a/tests/fate/libavutil.mak b/tests/fate/libavutil.mak
> index 6bf03b24386..b7df499a29c 100644
> --- a/tests/fate/libavutil.mak
> +++ b/tests/fate/libavutil.mak
> @@ -74,6 +74,10 @@ FATE_LIBAVUTIL += fate-dict
> fate-dict: libavutil/tests/dict$(EXESUF)
> fate-dict: CMD = run libavutil/tests/dict$(EXESUF)
>
> +FATE_LIBAVUTIL += fate-map
> +fate-map: libavutil/tests/map$(EXESUF)
> +fate-map: CMD = run libavutil/tests/map$(EXESUF)
> +
> FATE_LIBAVUTIL += fate-encryption-info
> fate-encryption-info: libavutil/tests/encryption_info$(EXESUF)
> fate-encryption-info: CMD = run libavutil/tests/encryption_info$(EXESUF)
> diff --git a/tests/ref/fate/map b/tests/ref/fate/map
> new file mode 100644
> index 00000000000..6d1699ef4b7
> --- /dev/null
> +++ b/tests/ref/fate/map
> @@ -0,0 +1,27 @@
> +testing empty set
> +
> +testing 1-set
> +
> +testing n-set
> +1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
> +the key=the value 8,10 n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2 �=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 b=b 2,2 \x1d=\x1d 2,2 �=� 2,2 9=9 2,2 j=j 2,2 �=� 2,2 �=� 2,2 Q=Q 2,2 �=� 2,2 M=M 2,2 \x06=\x06 2,2 �=� 2,2 �=� 2,2 %=% 2,2 �=� 2,2 \x01=\x01 2,2 �=� 2,2 }=} 2,2 \x16=\x16 2,2 �=� 2,2 �=� 2,2 U=U 2,2 �=� 2,2 �=� 2,2 \x12=\x12 2,2 �=� 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 �=� 2,2 �=� 2,2 a=a 2,2 �=� 2,2 �=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x11=\x11 2,2 2=2 2,2
> =
> 2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 \x0e=\x0e 2,2 �=� 2,2 �=� 2,2 === 2,2 V=V 2,2 Y=Y 2,2 �=� 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 q=q 2,2 R=R 2,2 m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2 �=� 2,2 �=� 2,2 v=v 2,2 �=� 2,2 �=� 2,2 u=u 2,2 >=> 2,2 �=� 2,2 r=r 2,2 �=� 2,2 �=� 2,2 i=i 2,2 z=z 2,2 �=� 2,2 N=N 2,2 �=� 2,2 \x02=\x02 2,2 �=� 2,2 �=� 2,2 \x19=\x19 2,2
> +=
> + 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x05=\x05 2,2
This may just be my email client messing up, but many of these appear to
be nonprintable. I don't know why.
> +testing empty set
> +
> +testing 1-set
> +
> +testing n-set
> +1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
> +the key=the value 8,10 n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2 �=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 b=b 2,2 \x1d=\x1d 2,2 �=� 2,2 9=9 2,2 j=j 2,2 �=� 2,2 �=� 2,2 Q=Q 2,2 �=� 2,2 M=M 2,2 \x06=\x06 2,2 �=� 2,2 �=� 2,2 %=% 2,2 �=� 2,2 \x01=\x01 2,2 �=� 2,2 }=} 2,2 \x16=\x16 2,2 �=� 2,2 �=� 2,2 U=U 2,2 �=� 2,2 �=� 2,2 \x12=\x12 2,2 �=� 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 �=� 2,2 �=� 2,2 a=a 2,2 �=� 2,2 �=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x11=\x11 2,2 2=2 2,2
> =
> 2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 \x0e=\x0e 2,2 �=� 2,2 �=� 2,2 === 2,2 V=V 2,2 Y=Y 2,2 �=� 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 q=q 2,2 R=R 2,2 m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2 �=� 2,2 �=� 2,2 v=v 2,2 �=� 2,2 �=� 2,2 u=u 2,2 >=> 2,2 �=� 2,2 r=r 2,2 �=� 2,2 �=� 2,2 i=i 2,2 z=z 2,2 �=� 2,2 N=N 2,2 �=� 2,2 \x02=\x02 2,2 �=� 2,2 �=� 2,2 \x19=\x19 2,2
> +=
> + 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x05=\x05 2,2
> +testing empty set
> +
> +testing 1-set
> +
> +testing n-set
> +1111111111111111111111111111111111011101111111111111111111111111101111111111111111111011101001101111011011011001011111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
> +the key=the value 8,10 n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2 �=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x1d=\x1d 2,2 �=� 2,2 9=9 2,2 �=� 2,2 �=� 2,2 Q=Q 2,2 �=� 2,2 M=M 2,2 \x06=\x06 2,2 �=� 2,2 �=� 2,2 %=% 2,2 �=� 2,2 \x01=\x01 2,2 �=� 2,2 }=} 2,2 \x16=\x16 2,2 �=� 2,2 �=� 2,2 U=U 2,2 �=� 2,2 �=� 2,2 \x12=\x12 2,2 �=� 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x11=\x11 2,2 2=2 2,2
> =
> 2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 \x0e=\x0e 2,2 �=� 2,2 �=� 2,2 === 2,2 V=V 2,2 �=� 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 R=R 2,2 = 2,2 Z=Z 2,2 .=. 2,2 !=! 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 >=> 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x02=\x02 2,2 �=� 2,2 �=� 2,2 \x19=\x19 2,2
> +=
> + 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x05=\x05 2,2
>
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
Leo Izen (Traneptora)
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-17 20:12 ` Michael Niedermayer
2025-04-18 14:46 ` Leo Izen
@ 2025-04-19 13:03 ` Nicolas George
2025-04-19 16:23 ` Michael Niedermayer
1 sibling, 1 reply; 11+ messages in thread
From: Nicolas George @ 2025-04-19 13:03 UTC (permalink / raw)
To: FFmpeg development discussions and patches
Michael Niedermayer (HE12025-04-17):
> ok, i will change teh name
Thanks.
> You can implement an av_map_new() variant thats on the stack
> if thats what you want to have / to use / to do
> once the code is in git
> or maybe i will do it but there are many more interresting things
I have checked, it can be done after the fact. (I am surprised you do
not consider this interesting).
> yes, mails take alot of time to read and reply to.
Sorry, I had assumed you would have replied before posting an updated
version because that is what I would have done.
Summary of the rest of the message:
- Keep the core API simple:
- no duplicated values;
- one compare function set once and for all at creation time.
- Implement extra features as utility functions on top of the core API.
> thats neither efficient nor does it fit the existing APIs.
> The value is most of the time not used and when used it is known exactly
> where it is. after a string compare of the key thats equal the value location is known
> or with arbitrary binary data the compare function knows the size of the data.
> also existing APIs from av_tree strcmp() av_strcasecmp() and so on none of
> which take 4 pointers from which they would ignore 2.
The more I think on if, the more I think this idea of giving the value
to the compare function is a bad idea. It is a break of abstraction,
unlike most other dictionaries API. The concatenation bit is kind of
exposing the specifics of the implementation.
IIUC, the point is to use it to allow multiple values with the same key.
But it also introduces de-duplication that might not be wanted.
In retrospect, I think shoehorning duplicated keys into AVDictionary was
a bad idea, and imitating that here is compounding the bad idea status.
If API-users want multiple values with de-dupliction like that, it is
simpler to do on their side by making the value part of the key, and
using dummy values:
"x" => "first" | "x:first" => ""
"x" => "second" | "x:second" => ""
"y" => "other" | "y:other" => ""
Callers can choose the best delimiters for their needs.
If API-users want multiple values without de-duplication, better treat
the value itself as an array/list somehow. If the code does not treat \0
as special in the value, we can do a lot of things like easily.
We can offer utility functions to support these patterns if that happens
to be useful. It is better than having these minor features affect the
design of the data structure.
> Passing redudant pointers just wastes cpu cycles
Does it make a non-negligible difference? Because when it comes to extra
pointers, there is more: real compare function might need a global
argument to determine their behavior: strcoll_l() and its third argument
for example.
If the extra pointer does make a significant difference, I have a
solution too. It requires a flags argument to the creation function
would help.
> the compare functions are needed purely for setup. And there
> they are needed because of arbitrary data support. av_map cannot
> know how to compare your data. (if its not strings)
Of course, we need to be able to set the compare function. My point it:
singular: ONE compare function for the whole map, set at creation and
never changed afterwards.
> But the existing code is much simpler:
>
> AVMapEntry e = NULL;
> while (e = av_map_get_multiple(set, e, "author", AV_MAP_CMP_CASE_INSENSITIVE | AV_MAP_CMP_KEY) {
> printf("Tag key:%s value:%s\n", e->key, e->value);
> }
That could be done as an utility function wrapping the “vs” code below I
snipped. It is better than letting this complicate the core API.
> Also the code above will just give wrong results with no warning if the compare
> function the map is setup with is incompatible with
I think you forgot the end of the sentence.
Reading more carefully, the business with the multiple compare function
makes even less sense to me:
>>> + * it must form a strict total order on all elements you want to store.
>>> + * @param cmp compatible compare function that comapres key or keyvalues
There is only order compatible with a total order is itself. As is, the
documentation says all the compare functions must return the exact same
thing, but that cannot be what it means.
Regards,
--
Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-19 10:36 ` Leo Izen
@ 2025-04-19 14:39 ` Michael Niedermayer
0 siblings, 0 replies; 11+ messages in thread
From: Michael Niedermayer @ 2025-04-19 14:39 UTC (permalink / raw)
To: FFmpeg development discussions and patches
[-- Attachment #1.1: Type: text/plain, Size: 9874 bytes --]
Hi Leo
On Sat, Apr 19, 2025 at 06:36:56AM -0400, Leo Izen wrote:
> On 4/17/25 12:52, Michael Niedermayer wrote:
[...]
> > +typedef struct{
> > + AVMapEntry map_entry;
> > + uint8_t treenode_and_keyvalue[0];
> > +} AVMapInternalEntry;
> > +
> > +struct AVMap{
> > +#define CMP_MASK 31
> > + AVMapCompareFunc cmp[27];
> > + AVMapCopyFunc copy;
> > + AVMapFreeFunc freef;
> > + int count;
> > + int deleted;
> > + int next; ///< index of entry in root array after all used entries
>
> Indices into arrays and counts and the like should be size_t.
I guess AVMap will be one of the first parts of FFmpeg doing that
git grep 'int count' | wc
354 2493 27289
git grep 'size_t count' | wc
2 8 97
git grep 'int [a-zA-Z_]*index' | wc
1279 7735 94963
git grep 'size_t [a-zA-Z_]*index' | wc
29 118 1888
also we use av_fast_realloc() which doesnt use size_t
and av_map_realloc() must return a signed value to allow error codes so it will use int64_t not size_t
>
> > + unsigned internal_entries_len;
> > + AVTreeNode *tree_root;
> > + AVMapInternalEntry *internal_entries;
> > +};
> > +
> > +static uint8_t deleted_entry;
>
> static const should allow the compiler to put it in a different section if
> it wishes. You can still address it even then.
I dont want to put it in a different section. Its value should be available
with a minimum of computation.
[...]
> > +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);
>
> Need to check for cmp_flags >= 27U before indexing into the array. The
ok
> compiler may pull this array off the stack cause it's static const so you
> risk hitting a dead page here.
printf("A"+5) also might hit a dead page, the user is not supposed to input
invalid data, and theres no gurantee that passing invalid data will not crash
[...]
> > +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->copy = copy;
> > + s->freef = freef;
> > +
> > + av_map_add_cmp_func(s, cmp_keyvalue, cmp_flags);
>
> No check for return value. av_map_add_cmp_func can return AVERROR(EINVAL)
> depending on cmp_flags.
indeed, i missed that, good find
[...]
> > + return advance;
> > +}
> > +
> > +int av_map_add(AVMap *s, const char *key, int keylen, const char *value, int valuelen, int flags)
> > +{
> > + av_assert2(keylen || valuelen); // patch welcome but how would the compare function compare a len=0 element without knowing it is a len 0 element
> > +
>
> This is a public function so we should be returning AVERROR(EINVAL) on
> invalid input rather than asserting. Since a library user could do that.
Its a speed relevent function
testing for the caller to do something stupid is not its job
The assert helps the user to find such a mistake
[...]
> > +int av_map_copy(AVMap *dst, const AVMap *src)
> > +{
> > + const AVMapEntry *t = NULL;
> > + AVMap *bak = av_memdup(dst, sizeof(*dst));
> > + if (!bak)
> > + return AVERROR(ENOMEM);
> > +
> > + AVMapInternalEntry *new_internal_entries = av_memdup(bak->internal_entries, bak->internal_entries_len);
> > + AVMapInternalEntry *old_internal_entries = dst->internal_entries;
>
> We don't allow mixed delcarations and statements. Hoist the defintion above
> if (!bak) and then put the assignment below it.
commit 890b8da1ce27fd365eaffefc7efcbadae9f01f2a
configure: Allow mixing declarations and statements
>
> > +
> > + while ((t = av_map_iterate(src, t))) {
> > + int ret = av_map_add(dst, t->key, t->keylen, t->value, t->valuelen, 0);
> > +
> > + if (ret < 0) {
> > + update_pointers(bak, new_internal_entries, old_internal_entries);
> > + av_free(dst->internal_entries);
> > + memcpy(dst, bak, sizeof(*dst));
> > + return ret;
>
> You leak bak here. Possibly new_internal_entries as well.
fixed
[...]
> > +typedef struct AVMapEntry {
> > + uint8_t *key;
> > + uint8_t *value;
>
> Any particular reason to use unsigned char here rather than just char when
> working with strings? Most string stuff expects signed char.
changed to char*
AVMap is not limited to strings
>
> > + int keylen;
> > + int valuelen;
>
> size_t for lengths
>
> > +} AVMapEntry;
> > +
> > +typedef struct AVMap AVMap;
> > +typedef void (* AVMapFreeFunc)(AVMapEntry *c);
> > +typedef void (* AVMapCopyFunc)(AVMapEntry *dst, const AVMapEntry *src, size_t len);
> > +typedef int (* AVMapCompareFunc)(const void *keyvalue, const void *b);
> > +
> > +/**
> > + * like strcmp() but compares concatenated keyvalues.
> > + *
> > + * A map initialized with this will allow duplicate keys as long as their values differ.
> > + */
> > +int av_map_strcmp_keyvalue(const char *a, const char *b);
> > +
> > +/**
> > + * like av_map_strcmp_keyvalue() but is compatible with av_strcasecmp() and av_map_supercmp_key.
> > + *
> > + * A map initialized with this will allow duplicate keys as long as their values differ.
> > + */
> > +int av_map_supercmp_keyvalue(const char *a, const char *b);
> > +
> > +/**
> > + * like strcmp() but is compatible with av_strcasecmp().
> > + *
> > + * A map initialized with this will not allow duplicate keys.
> > + */
> > +int av_map_supercmp_key(const char *a, const char *b);
>
>
> I don't believe it's clear if and when a user should call these functions or
> simply pass them by address. If so, we should use the typedef, or at least
> reference it in the doc comment.
the user can do whatever she wants with them
av_map_alloc() refers to them already
maybe we should simplify init to not require this at all, iam still thinking about that
[...]
> > index 00000000000..6d1699ef4b7
> > --- /dev/null
> > +++ b/tests/ref/fate/map
> > @@ -0,0 +1,27 @@
> > +testing empty set
> > +
> > +testing 1-set
> > +
> > +testing n-set
> > +1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
> > +the key=the value 8,10 n=n 2,2 �=� 2,2 "=" 2,2 ]=] 2,2 �=� 2,2 y=y 2,2 *=* 2,2 5=5 2,2 ~=~ 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 )=) 2,2 �=� 2,2 e=e 2,2 �=� 2,2 A=A 2,2 B=B 2,2 �=� 2,2 �=� 2,2 �=� 2,2 J=J 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 b=b 2,2 \x1d=\x1d 2,2 �=� 2,2 9=9 2,2 j=j 2,2 �=� 2,2 �=� 2,2 Q=Q 2,2 �=� 2,2 M=M 2,2 \x06=\x06 2,2 �=� 2,2 �=� 2,2 %=% 2,2 �=� 2,2 \x01=\x01 2,2 �=� 2,2 }=} 2,2 \x16=\x16 2,2 �=� 2,2 �=� 2,2 U=U 2,2 �=� 2,2 �=� 2,2 \x12=\x12 2,2 �=� 2,2 &=& 2,2 I=I 2,2 \x1a=\x1a 2,2 �=� 2,2 �=� 2,2 a=a 2,2 �=� 2,2 �=� 2,2 6=6 2,2 �=� 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x11=\x11 2,2 2=2 2,2
> > =
> > 2,2 F=F 2,2 �=� 2,2 :=: 2,2 �=� 2,2 \x0e=\x0e 2,2 �=� 2,2 �=� 2,2 === 2,2 V=V 2,2 Y=Y 2,2 �=� 2,2 \x15=\x15 2,2 \x1e=\x1e 2,2 q=q 2,2 R=R 2,2 m=m 2,2 f=f 2,2 = 2,2 Z=Z 2,2 E=E 2,2 .=. 2,2 !=! 2,2 �=� 2,2 �=� 2,2 v=v 2,2 �=� 2,2 �=� 2,2 u=u 2,2 >=> 2,2 �=� 2,2 r=r 2,2 �=� 2,2 �=� 2,2 i=i 2,2 z=z 2,2 �=� 2,2 N=N 2,2 �=� 2,2 \x02=\x02 2,2 �=� 2,2 �=� 2,2 \x19=\x19 2,2
> > +=
> > + 2,2 �=� 2,2 ^=^ 2,2 1=1 2,2 �=� 2,2 -=- 2,2 �=� 2,2 �=� 2,2 �=� 2,2 \x05=\x05 2,2
>
>
> This may just be my email client messing up, but many of these appear to be
> nonprintable. I don't know why.
Testing that covers non printable chars
thanks for the review
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
The educated differ from the uneducated as much as the living from the
dead. -- Aristotle
[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]
[-- Attachment #2: Type: text/plain, Size: 251 bytes --]
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-19 13:03 ` Nicolas George
@ 2025-04-19 16:23 ` Michael Niedermayer
2025-04-19 17:23 ` Nicolas George
0 siblings, 1 reply; 11+ messages in thread
From: Michael Niedermayer @ 2025-04-19 16:23 UTC (permalink / raw)
To: FFmpeg development discussions and patches
[-- Attachment #1.1: Type: text/plain, Size: 7639 bytes --]
Hi
On Sat, Apr 19, 2025 at 03:03:16PM +0200, Nicolas George wrote:
> Michael Niedermayer (HE12025-04-17):
> > ok, i will change teh name
>
> Thanks.
>
> > You can implement an av_map_new() variant thats on the stack
> > if thats what you want to have / to use / to do
> > once the code is in git
> > or maybe i will do it but there are many more interresting things
>
> I have checked, it can be done after the fact. (I am surprised you do
> not consider this interesting).
There are too many interresting things. Its interresting but not
interresting enough. Also its easy to add later
>
> > yes, mails take alot of time to read and reply to.
>
> Sorry, I had assumed you would have replied before posting an updated
> version because that is what I would have done.
>
>
> Summary of the rest of the message:
>
> - Keep the core API simple:
>
> - no duplicated values;
>
> - one compare function set once and for all at creation time.
>
> - Implement extra features as utility functions on top of the core API.
>
>
> > thats neither efficient nor does it fit the existing APIs.
> > The value is most of the time not used and when used it is known exactly
> > where it is. after a string compare of the key thats equal the value location is known
> > or with arbitrary binary data the compare function knows the size of the data.
> > also existing APIs from av_tree strcmp() av_strcasecmp() and so on none of
> > which take 4 pointers from which they would ignore 2.
>
> The more I think on if, the more I think this idea of giving the value
> to the compare function is a bad idea. It is a break of abstraction,
> unlike most other dictionaries API. The concatenation bit is kind of
> exposing the specifics of the implementation.
>
> IIUC, the point is to use it to allow multiple values with the same key.
> But it also introduces de-duplication that might not be wanted.
>
[...]
>
> If API-users want multiple values with de-dupliction like that, it is
> simpler to do on their side by making the value part of the key, and
> using dummy values:
>
> "x" => "first" | "x:first" => ""
> "x" => "second" | "x:second" => ""
> "y" => "other" | "y:other" => ""
>
> Callers can choose the best delimiters for their needs.
>
> If API-users want multiple values without de-duplication, better treat
> the value itself as an array/list somehow. If the code does not treat \0
> as special in the value, we can do a lot of things like easily.
>
> We can offer utility functions to support these patterns if that happens
> to be useful. It is better than having these minor features affect the
> design of the data structure.
I dont know what you are trying to acomplish here.
The key-value part is a fundamental part of the design and it leads to
multiple advantages.
it makes the code simpler, faster and enables several features that
otherwise would be messy/complex
Also I have no interrest nor time for working on someone elses design
maybe if that design would convince me but this one does not.
I think you should resubmit AVWriter and work on it. I think most people
will respect your design choices unless there are really good technical
reasons to do something differently.
The same way I also expect you to respect my choice in AVMap unless theres
really something better
>
> > Passing redudant pointers just wastes cpu cycles
>
> Does it make a non-negligible difference? Because when it comes to extra
> pointers, there is more: real compare function might need a global
> argument to determine their behavior: strcoll_l() and its third argument
> for example.
>
> If the extra pointer does make a significant difference, I have a
> solution too. It requires a flags argument to the creation function
> would help.
There is no need for a "user context" pointer in the core API because the user
specified key is always passed in the first argument of the compare function.
A struct {Context *c, char *key} can be passed in that if someone really ever
needs this, noone needed this till now it seems.
>
> > the compare functions are needed purely for setup. And there
> > they are needed because of arbitrary data support. av_map cannot
> > know how to compare your data. (if its not strings)
>
> Of course, we need to be able to set the compare function. My point it:
> singular: ONE compare function for the whole map, set at creation and
> never changed afterwards.
>
> > But the existing code is much simpler:
> >
> > AVMapEntry e = NULL;
> > while (e = av_map_get_multiple(set, e, "author", AV_MAP_CMP_CASE_INSENSITIVE | AV_MAP_CMP_KEY) {
> > printf("Tag key:%s value:%s\n", e->key, e->value);
> > }
>
> That could be done as an utility function wrapping the “vs” code below I
> snipped. It is better than letting this complicate the core API.
>
> > Also the code above will just give wrong results with no warning if the compare
> > function the map is setup with is incompatible with
>
> I think you forgot the end of the sentence.
>
> Reading more carefully, the business with the multiple compare function
> makes even less sense to me:
>
> >>> + * it must form a strict total order on all elements you want to store.
>
> >>> + * @param cmp compatible compare function that comapres key or keyvalues
>
> There is only order compatible with a total order is itself. As is, the
> documentation says all the compare functions must return the exact same
> thing, but that cannot be what it means.
* @param cmp compare function to be added.
* cmp(a,b) must return 0 or be equal to the previously added compare function for (a,b), if it returns 0 it also must do so for all
* elements between a and b
You are the mathematican, my terminology is likely off by at least a bit if not more
an example:
if the map is initialized with:
int av_map_supercmp_key(const char *a, const char *b){
int v = av_strcasecmp(a,b);
if (!v)
v = strcmp(a,b);
return v;
}
then av_strcasecmp() is compatible
this allows finding both case sensitive and case insensitve matches.
In code that allows both these with the same map.
AVMapEntry e = NULL;
while (e = av_map_get_multiple(set, e, "author", AV_MAP_CMP_CASE_INSENSITIVE | AV_MAP_CMP_KEY) {
printf("Tag key:%s value:%s\n", e->key, e->value);
}
AVMapEntry e = NULL;
while (e = av_map_get_multiple(set, e, "author", AV_MAP_CMP_CASE_SENSITIVE | AV_MAP_CMP_KEY) {
printf("Tag key:%s value:%s\n", e->key, e->value);
}
Basically by chaining increasingly specific compare functions in code
(like av_strcasecmp and strcmp in the example)
it is later possible to stop before all functions are run and have
wider matches (like case insensitve in the example)
Of course for adding elements, always the same and most specific function
is used so everything is always ordered the same way. Its only the
find/get stuff that can use these other functions
But all this really is under the hood and the user doesnt need to know
the user just asks for case insensitve and gets it as long as the av_map
was settup in a way that allows it.
thx
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]
[-- Attachment #2: Type: text/plain, Size: 251 bytes --]
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-19 16:23 ` Michael Niedermayer
@ 2025-04-19 17:23 ` Nicolas George
2025-04-19 17:36 ` Nicolas George
0 siblings, 1 reply; 11+ messages in thread
From: Nicolas George @ 2025-04-19 17:23 UTC (permalink / raw)
To: FFmpeg development discussions and patches
Michael Niedermayer (HE12025-04-19):
> I dont know what you are trying to acomplish here.
I am trying to help make this API as good as possible before it becomes
public and cannot be changed. I am nowhere as good as you in many areas,
but I think I can say that architecture, and in particular API design,
is the thing I am especially good at.
> The key-value part is a fundamental part of the design and it leads to
> multiple advantages.
> it makes the code simpler, faster and enables several features that
> otherwise would be messy/complex
>
> Also I have no interrest nor time for working on someone elses design
> maybe if that design would convince me but this one does not.
I am not trying to impose my own design. In fact, I think would have
mostly done the same as you
> I think you should resubmit AVWriter and work on it. I think most people
> will respect your design choices unless there are really good technical
> reasons to do something differently.
> The same way I also expect you to respect my choice in AVMap unless theres
> really something better
I am precisely trying to steer a small part of the design towards
something better. You already changed your mind once about the compare
functions, can you not take two steps back, look at it and just consider
changing your mind a second time.
> There is no need for a "user context" pointer in the core API because the user
> specified key is always passed in the first argument of the compare function.
> A struct {Context *c, char *key} can be passed in that if someone really ever
> needs this, noone needed this till now it seems.
There is a need for a user context to the compare function if you want
to have a dictionary in German and a dictionary in French, because the
rules for alphabetical order are slightly different.
But that can be added later.
> You are the mathematican, my terminology is likely off by at least a bit if not more
Sorry for the nitpicking. Math expresses things slightly differently, so
there is no single word to express it in the case of 3-valued compare
functions. You can call it either “partial order” or “total preorder”,
but get rid of the word “strict”.
> Basically by chaining increasingly specific compare functions in code
> (like av_strcasecmp and strcmp in the example)
> it is later possible to stop before all functions are run and have
> wider matches (like case insensitve in the example)
>
> Of course for adding elements, always the same and most specific function
> is used so everything is always ordered the same way. Its only the
> find/get stuff that can use these other functions
That makes sense.
> But all this really is under the hood and the user doesnt need to know
> the user just asks for case insensitve and gets it as long as the av_map
> was settup in a way that allows it.
The user needs to understand that if they want to make a map of their
own type and need to provide the compare function.
Let me make you a promise: if you can write an introduction to the API
(as all non-trivial APIs should have) that makes other major developers
say “that was clear”, I will leave the matter alone.
But as is, I still think this is needlessly complex.
Regards,
--
Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
2025-04-19 17:23 ` Nicolas George
@ 2025-04-19 17:36 ` Nicolas George
0 siblings, 0 replies; 11+ messages in thread
From: Nicolas George @ 2025-04-19 17:36 UTC (permalink / raw)
To: FFmpeg development discussions and patches
Nicolas George (HE12025-04-19):
> Let me make you a promise: if you can write an introduction to the API
> (as all non-trivial APIs should have) that makes other major developers
> say “that was clear”, I will leave the matter alone.
… which does not mean I demand you do that. You can probably convince me
otherwise if your design is indeed the best.
Regards,
--
Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2025-04-19 17:36 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-04-17 16:52 [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap Michael Niedermayer
2025-04-17 17:57 ` Nicolas George
2025-04-17 20:12 ` Michael Niedermayer
2025-04-18 14:46 ` Leo Izen
2025-04-19 1:23 ` Michael Niedermayer
2025-04-19 13:03 ` Nicolas George
2025-04-19 16:23 ` Michael Niedermayer
2025-04-19 17:23 ` Nicolas George
2025-04-19 17:36 ` Nicolas George
2025-04-19 10:36 ` Leo Izen
2025-04-19 14:39 ` Michael Niedermayer
Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
This inbox may be cloned and mirrored by anyone:
git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \
ffmpegdev@gitmailbox.com
public-inbox-index ffmpegdev
Example config snippet for mirrors.
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git