From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <ffmpeg-devel-bounces@ffmpeg.org>
Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100])
by master.gitmailbox.com (Postfix) with ESMTPS id 9E2CF4CF2E
for <ffmpegdev@gitmailbox.com>; Tue, 15 Apr 2025 18:15:34 +0000 (UTC)
Received: from [127.0.1.1] (localhost [127.0.0.1])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 35D92687A81;
Tue, 15 Apr 2025 21:14:47 +0300 (EEST)
Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net
[217.70.183.201])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 6D089687D2C
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 21:14:38 +0300 (EEST)
Received: by mail.gandi.net (Postfix) with ESMTPSA id BC88043423
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 18:14:37 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc;
s=gm1; t=1744740878;
h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
to:to:cc:mime-version:mime-version:content-type:content-type:
content-transfer-encoding:content-transfer-encoding:
in-reply-to:in-reply-to:references:references;
bh=lqdXVV8Wot6+oaQCsIWchOb4pepsq02irVuw7XNvJ8s=;
b=SCrqXe11/29Bp7udv9XhxnRhVmBf898oMka4A6EObBM2rxMKe4EOeiAvGDKmC/swuqrMmn
g4VK4x/joPtkTOGgSrahA4GGxJDusn3g6dll6Usk+qBS4a9atOWiFyfxy5xaKyGAfjbF7p
uAjFBDYFxwdw8E97qqrxqxBXra7iQK75w97cOk2+iK8Er29FcVojhHX5kIKs/Lq1zp60FA
N9DyK5e/sn4qRA7vRnIeJjh/fdSZELBisb93teg4/GJ7coZvlPtM/NeC9UNP7rVFoolG3c
yTPkonIge2Djd4DiR5aGH+mpMyLC/apsDk0MFq/RH+MMJ5D0ib/vGR3cBl4N2Q==
From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Date: Tue, 15 Apr 2025 20:14:32 +0200
Message-ID: <20250415181433.530161-5-michael@niedermayer.cc>
X-Mailer: git-send-email 2.49.0
In-Reply-To: <20250415181433.530161-1-michael@niedermayer.cc>
References: <20250415181433.530161-1-michael@niedermayer.cc>
MIME-Version: 1.0
X-GND-State: clean
X-GND-Score: -70
X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvvdegudekucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhephffvufffkffojghfgggtgfesthhqredtredtjeenucfhrhhomhepofhitghhrggvlhcupfhivgguvghrmhgrhigvrhcuoehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgeqnecuggftrfgrthhtvghrnhephfeufeeltdehgeehiedvveelkeevgeeftdfgueeivdegfeejgfdvhfevheegiefhnecukfhppeeguddrieeirdeijedruddufeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeeguddrieeirdeijedruddufedphhgvlhhopehlohgtrghlhhhoshhtpdhmrghilhhfrhhomhepmhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtpdhnsggprhgtphhtthhopedupdhrtghpthhtohepfhhfmhhpvghgqdguvghvvghlsehffhhmphgvghdrohhrgh
X-GND-Sasl: michael@niedermayer.cc
Subject: [FFmpeg-devel] [PATCH v2 5/6] libavutil: Add AVMap
X-BeenThere: ffmpeg-devel@ffmpeg.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: FFmpeg development discussions and patches <ffmpeg-devel.ffmpeg.org>
List-Unsubscribe: <https://ffmpeg.org/mailman/options/ffmpeg-devel>,
<mailto:ffmpeg-devel-request@ffmpeg.org?subject=unsubscribe>
List-Archive: <https://ffmpeg.org/pipermail/ffmpeg-devel>
List-Post: <mailto:ffmpeg-devel@ffmpeg.org>
List-Help: <mailto:ffmpeg-devel-request@ffmpeg.org?subject=help>
List-Subscribe: <https://ffmpeg.org/mailman/listinfo/ffmpeg-devel>,
<mailto:ffmpeg-devel-request@ffmpeg.org?subject=subscribe>
Reply-To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Content-Type: multipart/mixed; boundary="===============3952890375959664844=="
Errors-To: ffmpeg-devel-bounces@ffmpeg.org
Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org>
Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250415181433.530161-5-michael@niedermayer.cc/>
List-Archive: <https://master.gitmailbox.com/ffmpegdev/>
List-Post: <mailto:ffmpegdev@gitmailbox.com>
--===============3952890375959664844==
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
AVL Tree based Map
compared to AVDictionary this has
* clone is O(n) instead of O(n=C2=B2)
* copy is O(n*log n) instead of O(n=C2=B2)
* 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 i=
terator stays valid
* copy is atomic, a failure means the dst is unchanged
*
* there are restrictions on what compare function can be used on get depen=
ding on how the Map was created
* you can mix case sensitive and case insensitive compare with av_map_supe=
rcmp_*
* Supports binary objects, not just strings
Still somewhat work in progress, help more welcome than complaints ;)
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
libavutil/Makefile | 3 +
libavutil/map.c | 359 ++++++++++++++++++++++++++++++++++++++
libavutil/map.h | 230 ++++++++++++++++++++++++
libavutil/tests/map.c | 190 ++++++++++++++++++++
libavutil/tree.c | 6 +-
libavutil/tree_internal.h | 28 +++
tests/fate/libavutil.mak | 4 +
tests/ref/fate/map | 27 +++
8 files changed, 842 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 =3D adler32.h =
\
replaygain.h \
ripemd.h \
samplefmt.h \
+ map.h \
sha.h \
sha512.h \
spherical.h \
@@ -173,6 +174,7 @@ OBJS =3D adler32.o =
\
rc4.o \
ripemd.o \
samplefmt.o \
+ map.o \
side_data.o \
sha.o \
sha512.o \
@@ -290,6 +292,7 @@ TESTPROGS =3D 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..00dd5a1bd39
--- /dev/null
+++ b/libavutil/map.c
@@ -0,0 +1,359 @@
+/*
+ * 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-130=
1 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{
+ AVMapCompareFunc cmp_keyvalue;
+ AVMapCopyFunc copy;
+ AVMapFreeFunc freef;
+ int count;
+ int deleted;
+ int next; ///< index of entry in root array after al=
l 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) + si=
zeof(AVTreeNode) - 1) / sizeof (*I) + 1;
+}
+
+static inline AVTreeNode * internal_treenode(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.ke=
ylen;
+}
+
+static inline AVMapInternalEntry * keyvalue2internal(const uint8_t *keyval=
ue)
+{
+ return (AVMapInternalEntry*)(keyvalue - offsetof(AVMapInternalEntry, t=
reenode_and_keyvalue) - sizeof(AVTreeNode));
+}
+
+int av_map_strcmp_keyvalue(const char *a, const char *b)
+{
+ int v =3D strcmp(a,b);
+ if(!v)
+ v =3D strcmp(a + strlen(a) + 1, b + strlen(a) + 1); // please opti=
mize this dear compiler, we know the strlen after strcmp()
+ return v;
+}
+
+int av_map_supercmp_key(const char *a, const char *b)
+{
+ int v =3D av_strcasecmp(a,b);
+ if (!v)
+ v =3D strcmp(a,b);
+
+ return v;
+}
+
+int av_map_supercmp_keyvalue(const char *a, const char *b)
+{
+ int v =3D av_map_supercmp_key(a,b);
+ if (!v)
+ v =3D strcmp(a + strlen(a) + 1, b + strlen(a) + 1);
+
+ return v;
+}
+
+AVMap *av_map_new(AVMapCompareFunc cmp_keyvalue, AVMapCopyFunc copy, AVMap=
FreeFunc freef)
+{
+ AVMap *s =3D av_mallocz(sizeof(*s));
+ if (!s)
+ return NULL;
+
+ s->cmp_keyvalue =3D cmp_keyvalue;
+ s->copy =3D copy;
+ s->freef =3D freef;
+
+ return s;
+}
+
+const AVMapEntry *av_map_get_multiple(const AVMap *s, const AVMapEntry *pr=
ev, const char *keyvalue, int (*cmp)(const void *keyvalue, const void *b))
+{
+ if (prev) {
+ void *next_node[2] =3D { NULL, NULL };
+ void *prev_keyvalue =3D av_tree_find2(s->tree_root, prev->key, s->=
cmp_keyvalue, next_node, 2);
+ av_assert2(prev_keyvalue);
+ if (!next_node[1] || cmp(next_node[1], keyvalue))
+ return NULL;
+
+ keyvalue =3D next_node[1];
+ } else {
+ void *next_node[4] =3D { NULL, NULL, NULL, NULL };
+ keyvalue =3D 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 =3D next_node[2];
+ }
+
+ if (!keyvalue)
+ return NULL;
+
+ return &keyvalue2internal(keyvalue)->map_entry;
+}
+
+const AVMapEntry *av_map_get(const AVMap *s, const char *keyvalue, int (*c=
mp)(const void *keyvalue, const void *b))
+{
+ keyvalue =3D av_tree_find2(s->tree_root, keyvalue, cmp, NULL, 0);
+
+ if (!keyvalue)
+ return NULL;
+
+ return &keyvalue2internal(keyvalue)->map_entry;
+}
+
+int av_map_realloc(AVMap *s, int extra_elements, int extra_space) {
+ int64_t advance =3D extra_elements + (extra_space + (int64_t)extra_ele=
ments*(sizeof(*s->internal_entries) + sizeof(AVTreeNode) - 1)) / sizeof(*s-=
>internal_entries);
+
+ if (advance > (INT32_MAX - s->next) / sizeof(AVMapInternalEntry))
+ return AVERROR(ENOMEM);
+
+ AVMapInternalEntry *new_root =3D av_fast_realloc(s->internal_entries, =
&s->internal_entries_len, (s->next + advance) * sizeof(AVMapInternalEntry));
+
+ if (!new_root)
+ return AVERROR(ENOMEM);
+
+ if (new_root !=3D s->internal_entries) {
+ if (s->tree_root) {
+ AVTreeNode *new_tree_root =3D s->tree_root - internal_treenode=
(s->internal_entries) + internal_treenode(new_root);
+ av_tree_move(new_tree_root, s->tree_root, new_root, s->interna=
l_entries);
+ s->tree_root =3D new_tree_root;
+ }
+
+ for(int i =3D 0; i<s->next; i++) {
+ if (new_root[i].map_entry.key !=3D &deleted_entry) {
+ new_root[i].map_entry.key =3D internal_key (new_root + =
i);
+ new_root[i].map_entry.value =3D internal_value(new_root + =
i);
+ }
+ i +=3D internal_entry_len(new_root + i) - 1;
+ }
+ s->internal_entries =3D new_root;
+ }
+ return advance;
+}
+
+int av_map_add(AVMap *s, const char *key, int keylen, const char *value, i=
nt valuelen, int flags)
+{
+ av_assert2(keylen || valuelen); // patch welcome but how would the com=
pare function compare a len=3D0 element without knowing it is a len 0 eleme=
nt
+
+ int advance =3D av_map_realloc(s, 1, keylen + valuelen);
+ if (advance < 0)
+ return advance;
+
+ AVMapEntry *entry =3D &s->internal_entries[s->next].map_entry;
+ AVTreeNode *next =3D internal_treenode(s->internal_entries + s->next);
+ memset(next, 0, sizeof(*next));
+ entry->keylen =3D keylen;
+ entry->valuelen=3D valuelen;
+ entry->key =3D internal_key (s->internal_entries + s->next);
+ entry->value =3D internal_value(s->internal_entries + s->next);
+ memcpy(entry->key , key , keylen);
+ memcpy(entry->value, value, valuelen);
+
+ void *elem =3D av_tree_insert(&s->tree_root, entry->key, s->cmp_keyval=
ue, &next);
+ int ret =3D 1;
+ if (elem !=3D entry->key && elem) {
+ av_assert2(next);
+ //we assume that new entries are more common than replacements
+ if (flags & AV_MAP_REPLACE) {
+ ret =3D av_map_del(s, entry->key, s->cmp_keyvalue, flags);
+ av_assert2(ret =3D=3D 1);
+ elem =3D av_tree_insert(&s->tree_root, entry->key, s->cmp_keyv=
alue, &next);
+ av_assert2(elem =3D=3D entry->key || !elem);
+ ret =3D 2;
+ } else
+ return 0; //entry already in the map
+ }
+ av_assert2(!next);
+ av_assert2(s->tree_root);
+ s->next +=3D advance;
+ s->count++;
+
+ return ret;
+}
+
+int av_map_del(AVMap *s, const char *keyvalue, int (*cmp)(const void *keyv=
alue, const void *b), int flags)
+{
+ uint8_t *old_keyvalue;
+ AVTreeNode *next =3D NULL;
+
+ if (cmp !=3D s->cmp_keyvalue) {
+ // The user asks us to remove a entry with a compare function diff=
erent from the one used to build the map
+ // we need to do 2 calls here, first with the users compare to fin=
d the entry she wants to remove
+ // and then to remove it while maintaining the correct order withi=
n the map
+ old_keyvalue =3D 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_keyvalue, &next=
);
+ av_assert2(next);
+ } else {
+ av_tree_insert(&s->tree_root, (char*)keyvalue, s->cmp_keyvalue, &n=
ext);
+ if (!next)
+ return 0;
+ old_keyvalue =3D next->elem; //TODO add a API to av_tree() to retu=
rn the elem of a AVTreeNode
+
+ }
+ AVMapInternalEntry *internal_entry =3D keyvalue2internal(old_keyvalue);
+ internal_entry->map_entry.key =3D &deleted_entry;
+
+ s->count--;
+ s->deleted++;
+
+ if ((flags & AV_MAP_ALLOW_REBUILD) && s->deleted > s->count) {
+ AVMap *news =3D av_map_new(s->cmp_keyvalue, s->copy, s->freef);
+ if(news) {
+ int ret =3D av_map_copy(news, s);
+ if (ret < 0) {
+ av_map_free(&news);
+ } else {
+ if (s->freef)
+ for (int i=3D0; 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 =3D (AVMapInternalEntry*)((uint8_t*)prev - offsetof(AVMapInterna=
lEntry, map_entry));
+ I +=3D internal_entry_len(I);
+ } else {
+ I =3D s->internal_entries;
+ }
+ while (I < s->internal_entries + s->next && I->map_entry.key =3D=3D &d=
eleted_entry)
+ I +=3D internal_entry_len(I);
+
+ if (I =3D=3D 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 =3D *sp;
+
+ for (int i=3D0; i<s->count; i++) {
+ if (s->freef)
+ s->freef(&s->internal_entries[i].map_entry);
+ }
+ av_freep(&s->internal_entries);
+ s->next =3D
+ s->internal_entries_len =3D
+ s->count =3D 0;
+ av_freep(sp);
+}
+
+int av_map_copy(AVMap *dst, const AVMap *src)
+{
+ const AVMapEntry *t =3D NULL;
+ AVMap *bak =3D av_memdup(dst, sizeof(*dst));
+ if (!bak)
+ return AVERROR(ENOMEM);
+ bak->internal_entries =3D av_memdup(bak->internal_entries, bak->intern=
al_entries_len);
+
+ while ((t =3D av_map_iterate(src, t))) {
+ int ret =3D av_map_add(dst, t->key, t->keylen, t->value, t->valuel=
en, 0);
+
+ if (ret < 0) {
+ av_free(dst->internal_entries);
+ memcpy(dst, bak, sizeof(*dst));
+ return ret;
+ }
+ }
+ av_freep(&bak->internal_entries);
+ av_free(bak);
+
+ return 0;
+}
+
+AVMap *av_map_clone(AVMap *s)
+{
+ AVMap *dst =3D av_memdup(s, sizeof(AVMap));
+
+ if (!dst)
+ return NULL;
+
+ dst->internal_entries =3D av_memdup(s->internal_entries, s->internal_e=
ntries_len);
+
+ if (!dst->internal_entries)
+ goto err;
+
+ if (s->tree_root) {
+ dst->tree_root =3D s->tree_root - internal_treenode(s->internal_en=
tries) + internal_treenode(dst->internal_entries);
+ av_tree_move(dst->tree_root, s->tree_root, dst->internal_entries, =
s->internal_entries);
+ }
+
+ //TODO We could attempt to compact free space
+ for(int i =3D 0; i<s->next; i++) {
+ if (dst->internal_entries[i].map_entry.key !=3D &deleted_entry) {
+ dst->internal_entries[i].map_entry.key =3D internal_key (ds=
t->internal_entries + i);
+ dst->internal_entries[i].map_entry.value =3D internal_value(ds=
t->internal_entries + i);
+ }
+ i +=3D internal_entry_len(dst->internal_entries + i) - 1;
+ }
+
+ 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..0c660260017
--- /dev/null
+++ b/libavutil/map.h
@@ -0,0 +1,230 @@
+/*
+ * 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-130=
1 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=C2=B2)
+ * copy is O(n*log n) instead of O(n=C2=B2)
+ * 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 depe=
nding on how the Map was created
+ * you can mix case sensitive and case insensitive compare with av_map_sup=
ercmp_*
+ * Supports binary objects, not just strings
+ */
+
+enum {
+ AV_MAP_ALLOW_REBUILD =3D 1, ///< when removing entries rebuild the =
map to reduce memory consumption, note, this invalidates previously retriev=
ed elements and iterate state.
+ AV_MAP_REPLACE =3D 2, ///< 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, siz=
e_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() an=
d 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 co=
ncatenated.
+ * it must form a strict total order on all elements y=
ou want to store. each key-value pair
+ * can only occur once. Though there can be multiple v=
alues for the same key. IF this function
+ * treats them as different.
+ *
+ * @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!=3Dx X!=3Dx av_map_supercmp_key, av_st=
rcasecmp, (trucated av_strcasecmp)
+ * av_map_supercmp_key X!=3Dx av_strcasecmp, (trucated av_=
strcasecmp)
+ * av_strcasecmp X=3D=3Dx truncation
+ *
+ * av_map_strcmp_keyvalue X!=3Dx X!=3Dx strcmp, truncation
+ * strcmp X!=3Dx truncation
+ *
+ *
+ */
+AVMap *av_map_new(AVMapCompareFunc keyvalue_cmp, AVMapCopyFunc clone, AVMa=
pFreeFunc freef);
+
+/**
+ * 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 ele=
ments
+ *
+ * @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 m=
ap, 2 if it was replaced
+ * otherwise an error code <0
+ */
+int av_map_add(AVMap *s, const char *key, int keylen, const char *value, i=
nt valuelen, int flags);
+
+/**
+ * Delete the given entry from a AVMap.
+ *
+ * @param s Pointer AVMap struct.
+ * @param keyvalue key or concatenated key+value
+ * @param cmp compatible compare function that comapres key or keyva=
lues
+ * @param flags AV_MAP_ALLOW_REBUILD or 0
+ *
+ * @return 1 if the entry was deleted, 0 if it was not found in t=
he map
+ * otherwise an error code <0
+ */
+int av_map_del(AVMap *s, const char *keyvalue, int (*cmp)(const void *keyv=
alue, const void *b), 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
+ * @param cmp compare function, this will be passed keyvalue and the con=
catenated key+value
+ * it must form a total order on all elements, that is a key =
can occur more than once.
+ * But cmp2 must be a refinement of the cmp order, any disagr=
eement of the 2 compares
+ * must be by cmp returning equal. If this only reads the key=
part of keyvalue
+ * then keyvalue can be just a key
+ *
+ * @return Found entry or NULL in case no matching entry was found in=
the dictionary
+ */
+const AVMapEntry *av_map_get_multiple(const AVMap *s, const AVMapEntry *pr=
ev, const char *keyvalue, int (*cmp)(const void *keyvalue, const void *b));
+
+/**
+ * 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 (*c=
mp)(const void *keyvalue, const void *b));
+
+/**
+ * Iterate over a map
+ *
+ * Iterates through all entries in the map.
+ *
+ * @warning If you call any function with AV_SET_ALLOW_REBUILD set, then t=
he iterator is
+ * invalidated, and must not be used anymore. Otherwise av_map_add() (with=
out realloc) and av_map_del()
+ * can saftely be called during iteration.
+ *
+ * Typical usage:
+ * @code
+ * const AVMapEntry *e =3D NULL;
+ * while ((e =3D 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 *d=
st 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..38f0a153e68
--- /dev/null
+++ b/libavutil/tests/map.c
@@ -0,0 +1,190 @@
+/*
+ * 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-130=
1 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 =3D NULL;
+ while ((t =3D av_map_iterate(s, t)))
+ printf("%s=3D%s %d,%d ", t->key, t->value, t->keylen, t->valuele=
n);
+ printf("\n");
+}
+
+int main(void)
+{
+ void *our_cmp[] =3D {
+ strcmp,
+ av_map_strcmp_keyvalue,
+ av_strcasecmp,
+ av_map_supercmp_keyvalue,
+ av_map_supercmp_keyvalue,
+ };
+ void *our_subcmp[] =3D {
+ strcmp,
+ strcmp,
+ av_strcasecmp,
+ av_map_supercmp_key,
+ av_strcasecmp,
+ };
+
+ for (int settype=3D0; settype<3; settype++) {
+ AVMap *set =3D av_map_new(our_cmp[settype], NULL, NULL);
+
+ printf("testing empty set\n");
+
+ const AVMapEntry *e =3D av_map_get(set, "foo", our_subcmp[settype]=
);
+ av_assert0(e =3D=3D NULL);
+
+ e =3D av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(e =3D=3D NULL);
+
+ int ret =3D av_map_del(set, "foo", our_subcmp[settype], 0);
+ av_assert0(ret =3D=3D 0);
+
+ print_set(set);
+
+ printf("testing 1-set\n");
+
+ ret =3D av_map_add(set, "foo", 4, "bar", 4, 0);
+ av_assert0(ret =3D=3D 1);
+
+ ret =3D av_map_add(set, "foo", 4, "bear", 5, 0);
+ av_assert0(ret =3D=3D ((int[]){0,1,0})[settype]);
+
+ e =3D av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype =3D=3D 1) {
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar=
"));
+ } else {
+ av_assert0(!strcmp(e->value, "bar"));
+ }
+
+ ret =3D av_map_add(set, "foo", 4, "bear", 5, AV_MAP_REPLACE);
+ av_assert0(ret =3D=3D 2);
+
+ e =3D av_map_get(set, "foo", our_subcmp[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype =3D=3D 1) {
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar=
"));
+ } else {
+ av_assert0(!strcmp(e->value, "bear"));
+ }
+
+ e =3D av_map_get_multiple(set, NULL, "foo", our_subcmp[settype]);
+ av_assert0(!strcmp(e->key, "foo"));
+ if (settype =3D=3D 1) {
+ av_assert0(!strcmp(e->value, "bar"));
+ } else {
+ av_assert0(!strcmp(e->value, "bear"));
+ }
+ e =3D av_map_get_multiple(set, e, "foo", our_subcmp[settype]);
+ if (settype =3D=3D 1) {
+ av_assert0(!strcmp(e->key, "foo"));
+ av_assert0(!strcmp(e->value, "bear"));
+ } else {
+ av_assert0(e =3D=3D NULL);
+ }
+
+ ret =3D av_map_del(set, "foo", our_subcmp[settype], 0);
+ av_assert0(ret =3D=3D 1);
+
+ e =3D av_map_get(set, "foo", our_subcmp[settype]);
+ if (settype =3D=3D 1) {
+ av_assert0(!strcmp(e->key, "foo"));
+ av_assert0(!strcmp(e->value, "bear") || !strcmp(e->value, "bar=
"));
+ } else {
+ av_assert0(e =3D=3D NULL);
+ }
+
+ ret =3D av_map_del(set, "foo", our_subcmp[settype], 0);
+ av_assert0(ret =3D=3D ((int[]){0,1,0})[settype]);
+
+
+ print_set(set);
+
+ printf("testing n-set\n");
+ unsigned r =3D 5;
+ int histogram[256] =3D {0};
+ for(int i=3D0; i<1000; i++) {
+ r =3D r*123 + 7;
+ unsigned char str[3] =3D {0};
+ str[0] =3D r;
+ ret =3D av_map_add(set, str, 2, str, 2 ,0);
+ if (i < 128) {
+ if (settype !=3D 2) {
+ av_assert0(ret =3D=3D 1);
+ } else {
+ av_assert0(ret =3D=3D !histogram[av_toupper(str[0])]);
+ histogram[av_toupper(str[0])] =3D 1;
+ }
+ } else {
+ av_assert0(ret =3D=3D 0);
+ }
+ printf("%d", ret);
+ }
+ printf("\n");
+
+ r =3D 5;
+ for(int i=3D0; i<1000; i++) {
+ r =3D r*123 + 7;
+ char str[3] =3D {0};
+ str[0] =3D r;
+ e =3D av_map_get(set, str, our_subcmp[settype]);
+ if (settype !=3D 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 =3D av_map_get_multiple(set, NULL, str, our_subcmp[settype]);
+ if (settype !=3D 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 =3D av_map_add(set, str, 2, str, 2, 0);
+ av_assert0(ret =3D=3D 0);
+
+ str[1]=3D'x';
+
+ e =3D av_map_get(set, str, our_subcmp[settype]);
+ av_assert0(e =3D=3D NULL);
+ e =3D av_map_get_multiple(set, NULL, str, our_subcmp[settype]);
+ av_assert0(e =3D=3D NULL);
+ }
+ print_set(set);
+
+ av_map_free(&set);
+ av_assert0(!set);
+ }
+
+ return 0;
+}
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 09c55f6752d..5cffab4563c 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -24,11 +24,7 @@
#include "mem.h"
#include "tree.h"
=20
-typedef struct AVTreeNode {
- struct AVTreeNode *child[2];
- void *elem;
- int state;
-} AVTreeNode;
+#include "tree_internal.h"
=20
const int av_tree_node_size =3D sizeof(AVTreeNode);
=20
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-130=
1 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 +=3D fate-dict
fate-dict: libavutil/tests/dict$(EXESUF)
fate-dict: CMD =3D run libavutil/tests/dict$(EXESUF)
=20
+FATE_LIBAVUTIL +=3D fate-map
+fate-map: libavutil/tests/map$(EXESUF)
+fate-map: CMD =3D run libavutil/tests/map$(EXESUF)
+
FATE_LIBAVUTIL +=3D fate-encryption-info
fate-encryption-info: libavutil/tests/encryption_info$(EXESUF)
fate-encryption-info: CMD =3D run libavutil/tests/encryption_info$(EXESUF)
diff --git a/tests/ref/fate/map b/tests/ref/fate/map
new file mode 100644
index 00000000000..3333052a9f8
--- /dev/null
+++ b/tests/ref/fate/map
@@ -0,0 +1,27 @@
+testing empty set
+
+testing 1-set
+
+testing n-set
+11111111111111111111111111111111111111111111111111111111111111111111111111=
111111111111111111111111111111111111111111111111111111000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
00000000000000000000000000
+n=3Dn 2,2 =E1=3D=E1 2,2 "=3D" 2,2 ]=3D] 2,2 =B6=3D=B6 2,2 y=3Dy =
2,2 *=3D* 2,2 5=3D5 2,2 ~=3D~ 2,2 =91=3D=91 2,2 =B2=3D=B2 2,2 =
=8D=3D=8D 2,2 =C6=3D=C6 2,2 )=3D) 2,2 =BA=3D=BA 2,2 e=3De 2,2 =8E=
=3D=8E 2,2 A=3DA 2,2 B=3DB 2,2 =BD=3D=BD 2,2 =D6=3D=D6 2,2 =D9=3D=
=D9 2,2 J=3DJ 2,2 =95=3D=95 2,2 =9E=3D=9E 2,2 =F1=3D=F1 2,2 =D2=
=3D=D2 2,2 =ED=3D=ED 2,2 =E6=3D=E6 2,2 =89=3D=89 2,2 =DA=3D=DA 2,2 =
=C5=3D=C5 2,2 =AE=3D=AE 2,2 =A1=3D=A1 2,2 b=3Db 2,2 =1D=3D=1D 2,2=
=F6=3D=F6 2,2 9=3D9 2,2 j=3Dj 2,2 =F5=3D=F5 2,2 =BE=3D=BE 2,2 =
Q=3DQ 2,2 =F2=3D=F2 2,2 M=3DM 2,2 =06=3D=06 2,2 =E9=3D=E9 2,2 =FA=
=3D=FA 2,2 %=3D% 2,2 =CE=3D=CE 2,2 =01=3D=01 2,2 =82=3D=82 2,2 }=
=3D} 2,2 =16=3D=16 2,2 =99=3D=99 2,2 =8A=3D=8A 2,2 U=3DU 2,2 =DE=
=3D=DE 2,2 =B1=3D=B1 2,2 =12=3D=12 2,2 =AD=3D=AD 2,2 &=3D& 2,2 I=
=3DI 2,2 =1A=3D=1A 2,2 =85=3D=85 2,2 =EE=3D=EE 2,2 a=3Da 2,2 =A2=
=3D=A2 2,2 =DD=3D=DD 2,2 6=3D6 2,2 =F9=3D=F9 2,2 =AA=3D=AA 2,2 =
=B5=3D=B5 2,2 =FE=3D=FE 2,2 =11=3D=11 2,2 2=3D2 2,2 =0D=3D=0D 2,2 =
F=3DF 2,2 =A9=3D=A9 2,2 :=3D: 2,2 =E5=3D=E5 2,2 =0E=3D=0E 2,2 =
=C1=3D=C1 2,2 =C2=3D=C2 2,2 =3D=3D=3D 2,2 V=3DV 2,2 Y=3DY 2,2 =CA=
=3D=CA 2,2 =15=3D=15 2,2 =1E=3D=1E 2,2 q=3Dq 2,2 R=3DR 2,2 m=3Dm =
2,2 f=3Df 2,2 =3D 2,2 Z=3DZ 2,2 E=3DE 2,2 .=3D. 2,2 !=3D! 2,2=
=E2=3D=E2 2,2 =9D=3D=9D 2,2 v=3Dv 2,2 =B9=3D=B9 2,2 =EA=3D=EA 2,=
2 u=3Du 2,2 >=3D> 2,2 =D1=3D=D1 2,2 r=3Dr 2,2 =CD=3D=CD 2,2 =86=
=3D=86 2,2 i=3Di 2,2 z=3Dz 2,2 =A5=3D=A5 2,2 N=3DN 2,2 =81=3D=81 =
2,2 =02=3D=02 2,2 =FD=3D=FD 2,2 =96=3D=96 2,2 =19=3D=19 2,2=20=20=20
+=3D
+ 2,2 =D5=3D=D5 2,2 ^=3D^ 2,2 1=3D1 2,2 =92=3D=92 2,2 -=3D- 2,2 =
=A6=3D=A6 2,2 =C9=3D=C9 2,2 =9A=3D=9A 2,2 =05=3D=05 2,2=20=20=20
+testing empty set
+
+testing 1-set
+
+testing n-set
+11111111111111111111111111111111111111111111111111111111111111111111111111=
111111111111111111111111111111111111111111111111111111000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
00000000000000000000000000
+n=3Dn 2,2 =E1=3D=E1 2,2 "=3D" 2,2 ]=3D] 2,2 =B6=3D=B6 2,2 y=3Dy =
2,2 *=3D* 2,2 5=3D5 2,2 ~=3D~ 2,2 =91=3D=91 2,2 =B2=3D=B2 2,2 =
=8D=3D=8D 2,2 =C6=3D=C6 2,2 )=3D) 2,2 =BA=3D=BA 2,2 e=3De 2,2 =8E=
=3D=8E 2,2 A=3DA 2,2 B=3DB 2,2 =BD=3D=BD 2,2 =D6=3D=D6 2,2 =D9=3D=
=D9 2,2 J=3DJ 2,2 =95=3D=95 2,2 =9E=3D=9E 2,2 =F1=3D=F1 2,2 =D2=
=3D=D2 2,2 =ED=3D=ED 2,2 =E6=3D=E6 2,2 =89=3D=89 2,2 =DA=3D=DA 2,2 =
=C5=3D=C5 2,2 =AE=3D=AE 2,2 =A1=3D=A1 2,2 b=3Db 2,2 =1D=3D=1D 2,2=
=F6=3D=F6 2,2 9=3D9 2,2 j=3Dj 2,2 =F5=3D=F5 2,2 =BE=3D=BE 2,2 =
Q=3DQ 2,2 =F2=3D=F2 2,2 M=3DM 2,2 =06=3D=06 2,2 =E9=3D=E9 2,2 =FA=
=3D=FA 2,2 %=3D% 2,2 =CE=3D=CE 2,2 =01=3D=01 2,2 =82=3D=82 2,2 }=
=3D} 2,2 =16=3D=16 2,2 =99=3D=99 2,2 =8A=3D=8A 2,2 U=3DU 2,2 =DE=
=3D=DE 2,2 =B1=3D=B1 2,2 =12=3D=12 2,2 =AD=3D=AD 2,2 &=3D& 2,2 I=
=3DI 2,2 =1A=3D=1A 2,2 =85=3D=85 2,2 =EE=3D=EE 2,2 a=3Da 2,2 =A2=
=3D=A2 2,2 =DD=3D=DD 2,2 6=3D6 2,2 =F9=3D=F9 2,2 =AA=3D=AA 2,2 =
=B5=3D=B5 2,2 =FE=3D=FE 2,2 =11=3D=11 2,2 2=3D2 2,2 =0D=3D=0D 2,2 =
F=3DF 2,2 =A9=3D=A9 2,2 :=3D: 2,2 =E5=3D=E5 2,2 =0E=3D=0E 2,2 =
=C1=3D=C1 2,2 =C2=3D=C2 2,2 =3D=3D=3D 2,2 V=3DV 2,2 Y=3DY 2,2 =CA=
=3D=CA 2,2 =15=3D=15 2,2 =1E=3D=1E 2,2 q=3Dq 2,2 R=3DR 2,2 m=3Dm =
2,2 f=3Df 2,2 =3D 2,2 Z=3DZ 2,2 E=3DE 2,2 .=3D. 2,2 !=3D! 2,2=
=E2=3D=E2 2,2 =9D=3D=9D 2,2 v=3Dv 2,2 =B9=3D=B9 2,2 =EA=3D=EA 2,=
2 u=3Du 2,2 >=3D> 2,2 =D1=3D=D1 2,2 r=3Dr 2,2 =CD=3D=CD 2,2 =86=
=3D=86 2,2 i=3Di 2,2 z=3Dz 2,2 =A5=3D=A5 2,2 N=3DN 2,2 =81=3D=81 =
2,2 =02=3D=02 2,2 =FD=3D=FD 2,2 =96=3D=96 2,2 =19=3D=19 2,2=20=20=20
+=3D
+ 2,2 =D5=3D=D5 2,2 ^=3D^ 2,2 1=3D1 2,2 =92=3D=92 2,2 -=3D- 2,2 =
=A6=3D=A6 2,2 =C9=3D=C9 2,2 =9A=3D=9A 2,2 =05=3D=05 2,2=20=20=20
+testing empty set
+
+testing 1-set
+
+testing n-set
+11111111111111111111111111111111110111011111111111111111111111111011111111=
111111111110111010011011110110110110010111111111111111000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
00000000000000000000000000
+n=3Dn 2,2 =E1=3D=E1 2,2 "=3D" 2,2 ]=3D] 2,2 =B6=3D=B6 2,2 y=3Dy =
2,2 *=3D* 2,2 5=3D5 2,2 ~=3D~ 2,2 =91=3D=91 2,2 =B2=3D=B2 2,2 =
=8D=3D=8D 2,2 =C6=3D=C6 2,2 )=3D) 2,2 =BA=3D=BA 2,2 e=3De 2,2 =8E=
=3D=8E 2,2 A=3DA 2,2 B=3DB 2,2 =BD=3D=BD 2,2 =D6=3D=D6 2,2 =D9=3D=
=D9 2,2 J=3DJ 2,2 =95=3D=95 2,2 =9E=3D=9E 2,2 =F1=3D=F1 2,2 =D2=
=3D=D2 2,2 =ED=3D=ED 2,2 =E6=3D=E6 2,2 =89=3D=89 2,2 =DA=3D=DA 2,2 =
=C5=3D=C5 2,2 =AE=3D=AE 2,2 =A1=3D=A1 2,2 =1D=3D=1D 2,2 =F6=3D=F6=
2,2 9=3D9 2,2 =F5=3D=F5 2,2 =BE=3D=BE 2,2 Q=3DQ 2,2 =F2=3D=F2 2,=
2 M=3DM 2,2 =06=3D=06 2,2 =E9=3D=E9 2,2 =FA=3D=FA 2,2 %=3D% 2,2 =
=CE=3D=CE 2,2 =01=3D=01 2,2 =82=3D=82 2,2 }=3D} 2,2 =16=3D=16 2,2 =
=99=3D=99 2,2 =8A=3D=8A 2,2 U=3DU 2,2 =DE=3D=DE 2,2 =B1=3D=B1 2,2=
=12=3D=12 2,2 =AD=3D=AD 2,2 &=3D& 2,2 I=3DI 2,2 =1A=3D=1A 2,2 =
=85=3D=85 2,2 =EE=3D=EE 2,2 =A2=3D=A2 2,2 =DD=3D=DD 2,2 6=3D6 2,2 =
=F9=3D=F9 2,2 =AA=3D=AA 2,2 =B5=3D=B5 2,2 =FE=3D=FE 2,2 =11=3D=11 =
2,2 2=3D2 2,2 =0D=3D=0D 2,2 F=3DF 2,2 =A9=3D=A9 2,2 :=3D: 2,2 =
=E5=3D=E5 2,2 =0E=3D=0E 2,2 =C1=3D=C1 2,2 =C2=3D=C2 2,2 =3D=3D=3D 2=
,2 V=3DV 2,2 =CA=3D=CA 2,2 =15=3D=15 2,2 =1E=3D=1E 2,2 R=3DR 2,2 =
=3D 2,2 Z=3DZ 2,2 .=3D. 2,2 !=3D! 2,2 =E2=3D=E2 2,2 =9D=3D=9D=
2,2 =B9=3D=B9 2,2 =EA=3D=EA 2,2 >=3D> 2,2 =D1=3D=D1 2,2 =CD=3D=
=CD 2,2 =86=3D=86 2,2 =A5=3D=A5 2,2 =81=3D=81 2,2 =02=3D=02 2,2 =
=FD=3D=FD 2,2 =96=3D=96 2,2 =19=3D=19 2,2=20=20=20
+=3D
+ 2,2 =D5=3D=D5 2,2 ^=3D^ 2,2 1=3D1 2,2 =92=3D=92 2,2 -=3D- 2,2 =
=A6=3D=A6 2,2 =C9=3D=C9 2,2 =9A=3D=9A 2,2 =05=3D=05 2,2=20=20=20
--=20
2.49.0
--===============3952890375959664844==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
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".
--===============3952890375959664844==--