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 A89854CF2E
for <ffmpegdev@gitmailbox.com>; Tue, 15 Apr 2025 18:14:45 +0000 (UTC)
Received: from [127.0.1.1] (localhost [127.0.0.1])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 3529E68055D;
Tue, 15 Apr 2025 21:14:41 +0300 (EEST)
Received: from relay4-d.mail.gandi.net (relay4-d.mail.gandi.net
[217.70.183.196])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 0334E687A81
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 21:14:34 +0300 (EEST)
Received: by mail.gandi.net (Postfix) with ESMTPSA id 01280433EE
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 18:14:33 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc;
s=gm1; t=1744740874;
h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
to:to:cc:mime-version:mime-version:
content-transfer-encoding:content-transfer-encoding;
bh=6HK3CD9kbpZYp9D8vZ1FZc0ppt5tnAxR2UnOF1QcJqU=;
b=Vky9N6MKCqQcGRKxURYTA4XnRCo1Ly97ckNQJrDBNL+g9jrcszoNlIJQUO2ubdVbxmlxGB
JerAb0x1YRCn3CD/EU8bp5PLe56/4xNul66IwTJ2kwwMvUhFsNssBuvXM3GtQhU1P0uLZa
y6eO2GgUp4nihzw2OoFImevf7F5UhC/NeqYztsEcsRPjvPBFt5MzYPg3OLeJqW7M7T0Ir1
UoXU+bLiHSWLOBVcoStFW4xt14XZllmDn0CXqFRND22VF/Wj5VHIUhxXXUx9bYGBO4RWlM
7DRjTy8/8FhgFQ2zllyJrUTMzgR6HP1EulIQT8dQE5CrHppWHhNDlUukSATWtA==
From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Date: Tue, 15 Apr 2025 20:14:28 +0200
Message-ID: <20250415181433.530161-1-michael@niedermayer.cc>
X-Mailer: git-send-email 2.49.0
MIME-Version: 1.0
X-GND-State: clean
X-GND-Score: -70
X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvvdegudelucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhephffvufffkffoggfgsedtkeertdertddtnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpefhledvvdehgfettdefueevtdeifffhkeeljeetjeeugfelgfffieduheevvefgvdenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg
X-GND-Sasl: michael@niedermayer.cc
Subject: [FFmpeg-devel] [PATCH v2 1/6] avutil/tree: av_tree_find2() to also
find the first and last elements comparing equal
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: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: ffmpeg-devel-bounces@ffmpeg.org
Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org>
Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250415181433.530161-1-michael@niedermayer.cc/>
List-Archive: <https://master.gitmailbox.com/ffmpegdev/>
List-Post: <mailto:ffmpegdev@gitmailbox.com>
This patch also improves the worst case of O(n) (with n equal elements) to O(log n)
This may be used by AVDictionary2 And AVSet for iterating over identical
keys
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
libavutil/tree.c | 34 +++++++++++++++++++++++++++++-----
libavutil/tree.h | 6 ++++++
2 files changed, 35 insertions(+), 5 deletions(-)
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 7b57b2d39a7..9f58a3f3d49 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -18,6 +18,7 @@
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
+#include "avassert.h"
#include "error.h"
#include "log.h"
#include "mem.h"
@@ -36,19 +37,36 @@ struct AVTreeNode *av_tree_node_alloc(void)
return av_mallocz(sizeof(struct AVTreeNode));
}
-void *av_tree_find(const AVTreeNode *t, void *key,
- int (*cmp)(const void *key, const void *b), void *next[2])
+static void tree_find_next(const AVTreeNode *t, const void *key,
+ int (*cmp)(const void *key, const void *b), void *next[4], int nextlen, int direction)
+{
+ if (t) {
+ unsigned int v = cmp(key, t->elem);
+ if (v) {
+ next[direction] = t->elem;
+ av_assert2((v >> 31) == direction);
+ tree_find_next(t->child[!direction], key, cmp, next, nextlen, direction);
+ } else {
+ if (nextlen >= 4)
+ next[2+direction] = t->elem;
+ tree_find_next(t->child[direction], key, cmp, next, nextlen, direction);
+ }
+ }
+}
+
+void *av_tree_find2(const AVTreeNode *t, const void *key,
+ int (*cmp)(const void *key, const void *b), void *next[4], int nextlen)
{
if (t) {
unsigned int v = cmp(key, t->elem);
if (v) {
if (next)
next[v >> 31] = t->elem;
- return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next);
+ return av_tree_find2(t->child[(v >> 31) ^ 1], key, cmp, next, nextlen);
} else {
if (next) {
- av_tree_find(t->child[0], key, cmp, next);
- av_tree_find(t->child[1], key, cmp, next);
+ tree_find_next(t->child[0], key, cmp, next, nextlen, 0);
+ tree_find_next(t->child[1], key, cmp, next, nextlen, 1);
}
return t->elem;
}
@@ -56,6 +74,12 @@ void *av_tree_find(const AVTreeNode *t, void *key,
return NULL;
}
+void *av_tree_find(const AVTreeNode *t, void *key,
+ int (*cmp)(const void *key, const void *b), void *next[2])
+{
+ return av_tree_find2(t, key, cmp, next, 2);
+}
+
void *av_tree_insert(AVTreeNode **tp, void *key,
int (*cmp)(const void *key, const void *b), AVTreeNode **next)
{
diff --git a/libavutil/tree.h b/libavutil/tree.h
index bbb8fbb1262..6bafd47e593 100644
--- a/libavutil/tree.h
+++ b/libavutil/tree.h
@@ -55,6 +55,9 @@ struct AVTreeNode *av_tree_node_alloc(void);
* @param next If next is not NULL, then next[0] will contain the previous
* element and next[1] the next element. If either does not exist,
* then the corresponding entry in next is unchanged.
+ * if nextlen is 4 then next[2] will contain the first element comparing
+ * equal that is smaller than the returned. Similarly next[3] will
+ * contain the last element comparing equal that is larger than the returned
* @param cmp compare function used to compare elements in the tree,
* API identical to that of Standard C's qsort
* It is guaranteed that the first and only the first argument to cmp()
@@ -63,6 +66,9 @@ struct AVTreeNode *av_tree_node_alloc(void);
* @return An element with cmp(key, elem) == 0 or NULL if no such element
* exists in the tree.
*/
+void *av_tree_find2(const struct AVTreeNode *root, const void *key,
+ int (*cmp)(const void *key, const void *b), void *next[4], int nextlen);
+
void *av_tree_find(const struct AVTreeNode *root, void *key,
int (*cmp)(const void *key, const void *b), void *next[2]);
--
2.49.0
_______________________________________________
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".