[FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
Michael Niedermayer
michael at niedermayer.cc
Thu Apr 17 19:52:41 EEST 2025
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 at 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 = 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 = 2,2 é=é 2,2 ú=ú 2,2 %=% 2,2 Î=Î 2,2 = 2,2 ‚=‚ 2,2 }=} 2,2 = 2,2 ™=™ 2,2 Š=Š 2,2 U=U 2,2 Þ=Þ 2,2 ±=± 2,2 = 2,2 = 2,2 &=& 2,2 I=I 2,2 = 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 = 2,2 2=2 2,2
=
2,2 F=F 2,2 ©=© 2,2 :=: 2,2 å=å 2,2 = 2,2 Á=Á 2,2 Â=Â 2,2 === 2,2 V=V 2,2 Y=Y 2,2 Ê=Ê 2,2 = 2,2 = 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 = 2,2 ý=ý 2,2 –=– 2,2 = 2,2
+=
+ 2,2 Õ=Õ 2,2 ^=^ 2,2 1=1 2,2 ’=’ 2,2 -=- 2,2 ¦=¦ 2,2 É=É 2,2 š=š 2,2 = 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 = 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 = 2,2 é=é 2,2 ú=ú 2,2 %=% 2,2 Î=Î 2,2 = 2,2 ‚=‚ 2,2 }=} 2,2 = 2,2 ™=™ 2,2 Š=Š 2,2 U=U 2,2 Þ=Þ 2,2 ±=± 2,2 = 2,2 = 2,2 &=& 2,2 I=I 2,2 = 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 = 2,2 2=2 2,2
=
2,2 F=F 2,2 ©=© 2,2 :=: 2,2 å=å 2,2 = 2,2 Á=Á 2,2 Â=Â 2,2 === 2,2 V=V 2,2 Y=Y 2,2 Ê=Ê 2,2 = 2,2 = 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 = 2,2 ý=ý 2,2 –=– 2,2 = 2,2
+=
+ 2,2 Õ=Õ 2,2 ^=^ 2,2 1=1 2,2 ’=’ 2,2 -=- 2,2 ¦=¦ 2,2 É=É 2,2 š=š 2,2 = 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 = 2,2 ö=ö 2,2 9=9 2,2 õ=õ 2,2 ¾=¾ 2,2 Q=Q 2,2 ò=ò 2,2 M=M 2,2 = 2,2 é=é 2,2 ú=ú 2,2 %=% 2,2 Î=Î 2,2 = 2,2 ‚=‚ 2,2 }=} 2,2 = 2,2 ™=™ 2,2 Š=Š 2,2 U=U 2,2 Þ=Þ 2,2 ±=± 2,2 = 2,2 = 2,2 &=& 2,2 I=I 2,2 = 2,2 …=… 2,2 î=î 2,2 ¢=¢ 2,2 Ý=Ý 2,2 6=6 2,2 ù=ù 2,2 ª=ª 2,2 µ=µ 2,2 þ=þ 2,2 = 2,2 2=2 2,2
=
2,2 F=F 2,2 ©=© 2,2 :=: 2,2 å=å 2,2 = 2,2 Á=Á 2,2 Â=Â 2,2 === 2,2 V=V 2,2 Ê=Ê 2,2 = 2,2 = 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 = 2,2 ý=ý 2,2 –=– 2,2 = 2,2
+=
+ 2,2 Õ=Õ 2,2 ^=^ 2,2 1=1 2,2 ’=’ 2,2 -=- 2,2 ¦=¦ 2,2 É=É 2,2 š=š 2,2 = 2,2
--
2.49.0
More information about the ffmpeg-devel
mailing list