From: Leo Izen <leo.izen@gmail.com>
To: ffmpeg-devel@ffmpeg.org
Subject: Re: [FFmpeg-devel] [PATCH v3] libavutil: Add AVMap
Date: Sat, 19 Apr 2025 06:36:56 -0400
Message-ID: <ef669c75-c548-4a04-8dca-147e59f67c08@gmail.com> (raw)
In-Reply-To: <20250417165241.3266643-1-michael@niedermayer.cc>
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".
next prev parent reply other threads:[~2025-04-19 10:37 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-04-17 16:52 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 [this message]
2025-04-19 14:39 ` Michael Niedermayer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ef669c75-c548-4a04-8dca-147e59f67c08@gmail.com \
--to=leo.izen@gmail.com \
--cc=ffmpeg-devel@ffmpeg.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
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