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 11EFF4CDA9
for <ffmpegdev@gitmailbox.com>; Mon, 14 Apr 2025 11:05:51 +0000 (UTC)
Received: from [127.0.1.1] (localhost [127.0.0.1])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 1C9F7687CAD;
Mon, 14 Apr 2025 14:05:26 +0300 (EEST)
Received: from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net
[217.70.183.195])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 857B4687C59
for <ffmpeg-devel@ffmpeg.org>; Mon, 14 Apr 2025 14:05:19 +0300 (EEST)
Received: by mail.gandi.net (Postfix) with ESMTPSA id BDBE71FCE7
for <ffmpeg-devel@ffmpeg.org>; Mon, 14 Apr 2025 11:05:18 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc;
s=gm1; t=1744628719;
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=G0XyUKYwutk0sk7kyqc29EP0UpXH1tLjSqRvcepRfhw=;
b=BvJ2dbEew72+3hTVO1v8QkEjKbqvA+jGCYJleoxl/iawV/XxBhElWK/8ANa9iuncaYfCdX
M7WV7YCqJwY+JhvZqzawJMiJY16yv6fm1OVeZ3g8qYVr/+mXos7vT7A/VKCefq0zP7Clj8
JuyPQfllsu/zkN8W5QP0cYRHBIFCgs/AAXbog9NCy9q9zBreMMn+Y5YOBVIIOrl/W9/Sfm
KFeCAsOeRgb1th1Eb69UC1ORBFGa3PUVai3xU4r07u7+VU/uWz+pvoGIqBZHJKmQeucQ+w
Wu0aTPqojN7YtHJXU6YIOkdIaM4pwgEB7IZDyTxa4jFRhluIY4uMXdWfbMpjUQ==
From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Date: Mon, 14 Apr 2025 13:05:15 +0200
Message-ID: <20250414110515.893360-3-michael@niedermayer.cc>
X-Mailer: git-send-email 2.49.0
In-Reply-To: <20250414110515.893360-1-michael@niedermayer.cc>
References: <20250414110515.893360-1-michael@niedermayer.cc>
MIME-Version: 1.0
X-GND-State: clean
X-GND-Score: -70
X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvvddtfeekucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhephffvufffkffojghfgggtgfesthhqredtredtjeenucfhrhhomhepofhitghhrggvlhcupfhivgguvghrmhgrhigvrhcuoehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgeqnecuggftrfgrthhtvghrnhephfeufeeltdehgeehiedvveelkeevgeeftdfgueeivdegfeejgfdvhfevheegiefhnecukfhppeeguddrieeirdeijedruddufeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeeguddrieeirdeijedruddufedphhgvlhhopehlohgtrghlhhhoshhtpdhmrghilhhfrhhomhepmhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtpdhnsggprhgtphhtthhopedupdhrtghpthhtohepfhhfmhhpvghgqdguvghvvghlsehffhhmphgvghdrohhrgh
X-GND-Sasl: michael@niedermayer.cc
Subject: [FFmpeg-devel] [PATCH 3/3] libavutil: Add AVSet
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="===============4608412060691016975=="
Errors-To: ffmpeg-devel-bounces@ffmpeg.org
Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org>
Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250414110515.893360-3-michael@niedermayer.cc/>
List-Archive: <https://master.gitmailbox.com/ffmpegdev/>
List-Post: <mailto:ffmpegdev@gitmailbox.com>
--===============4608412060691016975==
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
AVL Tree based set
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)
* malloc() calls are O(log n) instead of O(n)
* get/add/delete is O(log n)
*
* You can add and remove entries while a iterator stays valid
* copy is atomic, a failure means the dst is unchanged
*
* one cannot randomly change the compare function because the set is order=
ed by it, for example a set is either case sensitive or not
This may become the base for AVDictionary2 ... maybe
Still somewhat work in progress, help more welcome than complaints ;)
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
libavutil/Makefile | 3 +
libavutil/set.c | 269 ++++++++++++++++++++++++++++++++++++++
libavutil/set.h | 173 ++++++++++++++++++++++++
libavutil/tests/set.c | 109 +++++++++++++++
libavutil/tree.c | 6 +-
libavutil/tree_internal.h | 28 ++++
tests/fate/libavutil.mak | 4 +
tests/ref/fate/set | 8 ++
8 files changed, 595 insertions(+), 5 deletions(-)
create mode 100644 libavutil/set.c
create mode 100644 libavutil/set.h
create mode 100644 libavutil/tests/set.c
create mode 100644 libavutil/tree_internal.h
create mode 100644 tests/ref/fate/set
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 9ef118016bb..3ba3b908bc2 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -81,6 +81,7 @@ HEADERS =3D adler32.h =
\
replaygain.h \
ripemd.h \
samplefmt.h \
+ set.h \
sha.h \
sha512.h \
spherical.h \
@@ -173,6 +174,7 @@ OBJS =3D adler32.o =
\
rc4.o \
ripemd.o \
samplefmt.o \
+ set.o \
side_data.o \
sha.o \
sha512.o \
@@ -290,6 +292,7 @@ TESTPROGS =3D adler32 =
\
random_seed \
rational \
ripemd \
+ set \
sha \
sha512 \
side_data_array \
diff --git a/libavutil/set.c b/libavutil/set.c
new file mode 100644
index 00000000000..f9f7437b3de
--- /dev/null
+++ b/libavutil/set.c
@@ -0,0 +1,269 @@
+/*
+ * 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 "error.h"
+#include "mem.h"
+#include "set.h"
+
+#include "tree_internal.h" // For improved readability with AVTreeNode, do=
NOT touch AVTreeNode internals
+
+typedef struct{
+ AVTreeNode node; // tree node, NOTE this may not correspond to =
this set entry due to rotations
+ AVSetEntry set_entry;
+ uint8_t value[0];
+} AVSetInternalEntry;
+
+struct AVSet{
+ AVSetCompareFunc cmp;
+ AVSetCopyFunc copy;
+ AVSetFreeFunc freef;
+ int count;
+ int deleted;
+ int next; ///< index of entry in root array after al=
l used entries
+ unsigned array_len;
+ AVTreeNode *tree_root;
+ AVSetInternalEntry *root;
+};
+
+static uint8_t deleted_entry;
+
+static inline int internal_entry_len(AVSetInternalEntry *I) {
+ return (I->set_entry.len + sizeof (*I) - 1) / sizeof (*I) + 1;
+}
+
+AVSet *av_set_new(AVSetCompareFunc cmp, AVSetCopyFunc copy, AVSetFreeFunc =
freef)
+{
+ AVSet *s =3D av_mallocz(sizeof(*s));
+ if (!s)
+ return NULL;
+
+ s->cmp =3D cmp;
+ s->copy =3D copy;
+ s->freef =3D freef;
+
+ return s;
+}
+
+AVSetEntry *av_set_get(const AVSet *s, const AVSetEntry *prev, const char =
*value, int (*cmp)(const void *key, const void *b))
+{
+ if (cmp) {
+ if (prev && cmp) {
+ void *next_node[2] =3D { NULL, NULL };
+ void *prev_value =3D av_tree_find2(s->tree_root, prev->value, =
s->cmp, next_node, 2);
+ av_assert2(prev_value);
+ if (!next_node[1] || cmp(next_node[1], value))
+ return NULL;
+
+ value =3D next_node[1];
+ } else {
+ void *next_node[4] =3D { NULL, NULL, NULL, NULL };
+ value =3D av_tree_find2(s->tree_root, value, cmp, next_node, 4=
);
+ if (next_node[2]) // If we have a leftmost equal value, use it=
instead
+ value =3D next_node[2];
+ }
+ } else {
+ //we cannot have multiple matches with the cmp used for building a=
set as we could not have added these
+ value =3D av_tree_find2(s->tree_root, value, s->cmp, NULL, 0);
+ }
+
+ if (!value)
+ return NULL;
+
+ return &((AVSetInternalEntry*)(value - offsetof(AVSetInternalEntry, va=
lue)))->set_entry;
+}
+
+int av_set_add(AVSet *s, const char *value, int len, int flags)
+{
+ int advance =3D 1 + (len + sizeof(*s->root) - 1) / sizeof(*s->root);
+ AVSetInternalEntry *new_root =3D av_fast_realloc(s->root, &s->array_le=
n, (s->next + advance) * sizeof(AVSetInternalEntry));
+
+ av_assert2(value && len); // patch welcome but how would the compare f=
unction compare a len=3D0 element without knowing it is a len 0 element
+
+ if (!new_root)
+ return AVERROR(ENOMEM);
+
+ if (new_root !=3D s->root) {
+ if (s->tree_root) {
+ AVTreeNode *new_tree_root =3D s->tree_root - &s->root->node + =
&new_root->node;
+ av_tree_move(new_tree_root, s->tree_root, new_root, s->root);
+ s->tree_root =3D new_tree_root;
+ }
+
+ for(int i =3D 0; i<s->next; i++) {
+ if (new_root[i].set_entry.value !=3D &deleted_entry)
+ new_root[i].set_entry.value =3D new_root[i].value;
+ i +=3D internal_entry_len(new_root + i) - 1;
+ }
+ s->root =3D new_root;
+ }
+
+ AVSetEntry *entry =3D &new_root[s->next].set_entry;
+ memset(&new_root[s->next].node, 0, sizeof(new_root[s->next].node));
+ entry->value =3D new_root[s->next].value;
+ entry->len =3D len;
+ memcpy(entry->value, value, len);
+
+ AVTreeNode *next =3D &new_root[s->next].node;
+ void *elem =3D av_tree_insert(&s->tree_root, entry->value, s->cmp, &ne=
xt);
+ if (elem !=3D entry->value && elem) {
+ av_assert2(next);
+ return 0; //entry already in the set
+ }
+ av_assert2(!next);
+ av_assert2(s->tree_root);
+ s->next +=3D advance;
+ s->count++;
+
+ return 1;
+}
+
+int av_set_del(AVSet *s, const char *value, int len, int flags)
+{
+ uint8_t *old_value =3D av_tree_find2(s->tree_root, value, s->cmp, NULL=
, 0);
+ if (!old_value)
+ return 0;
+
+ AVTreeNode *next =3D NULL;
+ void *elem =3D av_tree_insert(&s->tree_root, value, s->cmp, &next);
+ av_assert2(next);
+
+ AVSetInternalEntry *internal_entry =3D (AVSetInternalEntry *)((uint8_t=
*)old_value - offsetof(AVSetInternalEntry, value));
+ internal_entry->set_entry.value =3D &deleted_entry;
+
+ s->count--;
+ s->deleted++;
+
+ if ((flags & AV_SET_ALLOW_REBUILD) && s->deleted > s->count) {
+ AVSet *news =3D av_set_new(s->cmp, s->copy, s->freef);
+ if(news) {
+ int ret =3D av_set_copy(news, s);
+ if (ret < 0) {
+ av_set_free(&news);
+ } else {
+ if (s->freef)
+ for (int i=3D0; i<s->count; i++)
+ s->freef(&s->root[i].set_entry);
+ av_freep(&s->root);
+ memcpy(s, news, sizeof(*s));
+ }
+ }
+ }
+
+ return 1;
+}
+
+const AVSetEntry *av_set_iterate(const AVSet *s,
+ const AVSetEntry *prev)
+{
+ AVSetInternalEntry *I;
+ if (prev) {
+ I =3D (AVSetInternalEntry*)((uint8_t*)prev - offsetof(AVSetInterna=
lEntry, set_entry));
+ I +=3D internal_entry_len(I);
+ } else {
+ I =3D s->root;
+ }
+ while (I < s->root + s->next && I->set_entry.value =3D=3D &deleted_ent=
ry)
+ I +=3D internal_entry_len(I);
+
+ if (I =3D=3D s->root + s->next)
+ return NULL;
+
+ return &I->set_entry;
+}
+
+int av_set_count(const AVSet *s)
+{
+ return s->count;
+}
+
+void av_set_free(AVSet **sp)
+{
+ AVSet *s =3D *sp;
+
+ for (int i=3D0; i<s->count; i++) {
+ if (s->freef)
+ s->freef(&s->root[i].set_entry);
+ }
+ av_freep(&s->root);
+ s->next =3D
+ s->array_len =3D
+ s->count =3D 0;
+ av_freep(sp);
+}
+
+int av_set_copy(AVSet *dst, const AVSet *src)
+{
+ const AVSetEntry *t =3D NULL;
+ AVSet *bak =3D av_memdup(dst, sizeof(*dst));
+ if (!bak)
+ return AVERROR(ENOMEM);
+ bak->root =3D av_memdup(bak->root, bak->array_len);
+
+ while ((t =3D av_set_iterate(src, t))) {
+ int ret =3D av_set_add(dst, t->value, t->len, 0);
+
+ if (ret < 0) {
+ av_free(dst->root);
+ memcpy(dst, bak, sizeof(*dst));
+ return ret;
+ }
+ }
+ av_freep(&bak->root);
+ av_free(bak);
+
+ return 0;
+}
+
+AVSet *av_set_clone(AVSet *s)
+{
+ AVSet *dst =3D av_memdup(s, sizeof(AVSet));
+
+ if (!dst)
+ return NULL;
+
+ dst->root =3D av_memdup(s->root, s->array_len);
+
+ if (!dst->root)
+ goto err;
+
+ if (s->tree_root) {
+ dst->tree_root =3D s->tree_root - &s->root->node + &dst->root->nod=
e;
+ av_tree_move(dst->tree_root, s->tree_root, dst->root, s->root);
+ }
+
+ //TODO We could attempt to compact free space
+ for(int i =3D 0; i<s->next; i++) {
+ if (dst->root[i].set_entry.value !=3D deleted_entry)
+ dst->root[i].set_entry.value =3D dst->root[i].value;
+ i +=3D internal_entry_len(dst->root + i) - 1;
+ }
+
+ return dst;
+err:
+ if (dst) {
+ av_freep(&dst->root);
+ }
+ av_free(dst);
+ return NULL;
+}
diff --git a/libavutil/set.h b/libavutil/set.h
new file mode 100644
index 00000000000..193499a4ab1
--- /dev/null
+++ b/libavutil/set.h
@@ -0,0 +1,173 @@
+/*
+ * 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 set API.
+ */
+
+#ifndef AVUTIL_SET_H
+#define AVUTIL_SET_H
+
+#include <stdint.h>
+
+#include "tree.h"
+
+/**
+ * Compared to AVDictionary
+ * clone is O(n) instead of O(n=C2=B2)
+ * copy is O(n*log n) instead of O(n=C2=B2)
+ * malloc() calls are O(log n) instead of O(n)
+ * get/add/delete is O(log n)
+ *
+ * You can add and remove entries while a iterator stays valid
+ * copy is atomic, a failure means the dst is unchanged
+ *
+ * one cannot randomly change the compare function because the set is orde=
red by it, for example a set is either case sensitive or not
+ */
+
+
+enum {
+ AV_SET_ALLOW_REBUILD =3D 1 ///< when removing entries rebuild the se=
t to reduce memory consumption, note, this invalidates previously retrieved=
elements and iterate state.
+};
+
+
+typedef struct AVSetEntry {
+ int len;
+ uint8_t *value;
+} AVSetEntry;
+
+typedef struct AVSet AVSet;
+typedef void (* AVSetFreeFunc)(AVSetEntry *c);
+typedef void (* AVSetCopyFunc)(AVSetEntry *dst, const AVSetEntry *src, siz=
e_t len);
+typedef int (* AVSetCompareFunc)(const void *key, const void *b);
+
+/**
+ *
+ * @param freef receives a AVSetEntry and should free any resources except=
the AVSetEntry->value pointer itself
+ * for flat structs like strings, this is simply NULL
+ *
+ */
+AVSet *av_set_new(AVSetCompareFunc compare, AVSetCopyFunc clone, AVSetFree=
Func freef);
+
+/**
+ * Add the given entry into a AVSet.
+ *
+ * @param s Pointer AVSet struct.
+ * @param value Entry value to add to *s
+ * @param valuelen length of value
+ *
+ * @return 1 if the entry was added, 0 if it was already in the s=
et
+ * otherwise an error code <0
+ */
+int av_set_add(AVSet *s, const char *value, int valuelen, int flags);
+
+/**
+ * Delete the given entry from a AVSet.
+ *
+ * @param s Pointer AVSet struct.
+ * @param value Entry value to delete from *s
+ * @param valuelen length of value
+ * @param flags can be set to AV_SET_ALLOW_REBUILD or 0
+ *
+ * @return 1 if the entry was deleted, 0 if it was not found in t=
he set
+ * otherwise an error code <0
+ */
+int av_set_del(AVSet *s, const char *value, int valuelen, int flags);
+
+/**
+ * Get a matching set entry.
+ *
+ * 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 value Matching value
+ * @param cmp A compatible comparission function. That is, this function=
can return 0
+ * for a consecutive subset of elements where the cmp functio=
n used for the set
+ * did not return 0.
+ * An example of such a function is one comparing only a pref=
ix of string.
+ * An anti-example: would be a case insensitive compare when =
the set was setup
+ * with case sensitive one.
+ *
+ * @return Found entry or NULL in case no matching entry was found in=
the dictionary
+ */
+
+AVSetEntry *av_set_get(const AVSet *s, const AVSetEntry *prev, const char =
*value, int (*cmp)(const void *key, const void *b));
+
+/**
+ * Iterate over a set
+ *
+ * Iterates through all entries in the set.
+ *
+ * @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_set_add() and a=
v_set_del()
+ * can saftely be called during iteration.
+ *
+ * Typical usage:
+ * @code
+ * const AVSetEntry *e =3D NULL;
+ * while ((e =3D av_set_iterate(m, e))) {
+ * // ...
+ * }
+ * @endcode
+ *
+ * @param s The set to iterate over
+ * @param prev Pointer to the previous AVSetEntry, NULL initially
+ *
+ * @retval AVSetEntry* The next element in the set
+ * @retval NULL No more elements in the set
+ */
+const AVSetEntry *av_set_iterate(const AVSet *s,
+ const AVSetEntry *prev);
+
+/**
+ * Get number of entries in set.
+ *
+ * @param s set
+ * @return number of entries in set
+ */
+int av_set_count(const AVSet *s);
+
+/**
+ * Free all the memory allocated for an AVSet struct
+ * and all values.
+ */
+void av_set_free(AVSet **s);
+
+AVSet *av_set_clone(AVSet *s);
+
+/**
+ * Copy entries from one AVSet struct into another.
+ *
+ * @param dst Pointer to a pointer to a AVSet 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 AVSet struct to copy items from.
+ * @param flags Flags to use when setting entries in *dst
+ *
+ * @see when the initial dst set is empty use av_set_clone() as its faster
+ *
+ * @return 0 on success, negative AVERROR code on failure.
+ */
+
+int av_set_copy(AVSet *dst, const AVSet *src);
+
+#endif /* AVUTIL_SET_H */
diff --git a/libavutil/tests/set.c b/libavutil/tests/set.c
new file mode 100644
index 00000000000..fbe68512bc7
--- /dev/null
+++ b/libavutil/tests/set.c
@@ -0,0 +1,109 @@
+/*
+ * 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/mem.h"
+
+#include "libavutil/set.h"
+
+static void print_set(const AVSet *s)
+{
+ const AVSetEntry *t =3D NULL;
+ while ((t =3D av_set_iterate(s, t)))
+ printf("%s %d ", t->value, t->len);
+ printf("\n");
+}
+
+int main(void)
+{
+ AVSet *set =3D av_set_new(strcmp, NULL, NULL);
+
+ printf("testing empty set\n");
+
+ AVSetEntry *e =3D av_set_get(set, NULL, "foo", NULL);
+ av_assert0(e =3D=3D NULL);
+
+ e =3D av_set_get(set, NULL, "foo", strcmp);
+ av_assert0(e =3D=3D NULL);
+
+ int ret =3D av_set_del(set, "foo", 4, 0);
+ av_assert0(ret =3D=3D 0);
+
+ print_set(set);
+
+ printf("testing 1-set\n");
+
+ ret =3D av_set_add(set, "foo", 4, 0);
+ av_assert0(ret =3D=3D 1);
+
+ ret =3D av_set_add(set, "foo", 4, 0);
+ av_assert0(ret =3D=3D 0);
+
+ e =3D av_set_get(set, NULL, "foo", NULL);
+ av_assert0(!strcmp(e->value, "foo"));
+
+ e =3D av_set_get(set, NULL, "foo", strcmp);
+ av_assert0(!strcmp(e->value, "foo"));
+
+ ret =3D av_set_del(set, "foo", 4, 0);
+ av_assert0(ret =3D=3D 1);
+
+ print_set(set);
+
+ printf("testing n-set\n");
+ unsigned r =3D 5;
+ for(int i=3D0; i<1000; i++) {
+ r =3D r*123 + 7;
+ char str[3] =3D {0};
+ str[0] =3D r;
+ ret =3D av_set_add(set, str , 2, 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_set_get(set, NULL, str, NULL);
+ av_assert0(!strcmp(e->value, str));
+ e =3D av_set_get(set, NULL, str, strcmp);
+ av_assert0(!strcmp(e->value, str));
+ ret =3D av_set_add(set, str , 2, 0);
+ av_assert0(ret =3D=3D 0);
+
+ str[1]=3D"x";
+
+ e =3D av_set_get(set, NULL, str, NULL);
+ av_assert0(e =3D=3D NULL);
+ e =3D av_set_get(set, NULL, str, strcmp);
+ av_assert0(e =3D=3D NULL);
+ }
+ print_set(set);
+
+ av_set_free(&set);
+ av_assert0(!set);
+
+ return 0;
+}
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 4aaaa4f7af3..fbfb87e3561 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..3583492054f 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-set
+fate-set: libavutil/tests/set$(EXESUF)
+fate-set: CMD =3D run libavutil/tests/set$(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/set b/tests/ref/fate/set
new file mode 100644
index 00000000000..76f9dbbbbed
--- /dev/null
+++ b/tests/ref/fate/set
@@ -0,0 +1,8 @@
+testing empty set
+
+testing 1-set
+
+testing n-set
+11111111111111111111111111111111111111111111111111111111111111111111111111=
111111111111111111111111111111111111111111111111111111000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
00000000000000000000000000
+n 2 =E1 2 " 2 ] 2 =B6 2 y 2 * 2 5 2 ~ 2 =91 2 =B2 2 =
=8D 2 =C6 2 ) 2 =BA 2 e 2 =8E 2 A 2 B 2 =BD 2 =D6 2 =D9=
2 J 2 =95 2 =9E 2 =F1 2 =D2 2 =ED 2 =E6 2 =89 2 =DA 2 =
=C5 2 =AE 2 =A1 2 b 2 =1D 2 =F6 2 9 2 j 2 =F5 2 =BE 2 Q=
2 =F2 2 M 2 =06 2 =E9 2 =FA 2 % 2 =CE 2 =01 2 =82 2 } =
2 =16 2 =99 2 =8A 2 U 2 =DE 2 =B1 2 =12 2 =AD 2 & 2 I 2=
=1A 2 =85 2 =EE 2 a 2 =A2 2 =DD 2 6 2 =F9 2 =AA 2 =B5 =
2 =FE 2 =11 2 2 2 =0D 2 F 2 =A9 2 : 2 =E5 2 =0E 2 =C1 2=
=C2 2 =3D 2 V 2 Y 2 =CA 2 =15 2 =1E 2 q 2 R 2 m 2 f =
2 2 Z 2 E 2 . 2 ! 2 =E2 2 =9D 2 v 2 =B9 2 =EA 2 u 2=
> 2 =D1 2 r 2 =CD 2 =86 2 i 2 z 2 =A5 2 N 2 =81 2 =
=02 2 =FD 2 =96 2 =19 2=20=20=20
+ 2 =D5 2 ^ 2 1 2 =92 2 - 2 =A6 2 =C9 2 =9A 2 =05 2=20=20=
=20
--=20
2.49.0
--===============4608412060691016975==
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".
--===============4608412060691016975==--