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 877624CF34
for <ffmpegdev@gitmailbox.com>; Tue, 15 Apr 2025 18:14:57 +0000 (UTC)
Received: from [127.0.1.1] (localhost [127.0.0.1])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 6FDC8687D31;
Tue, 15 Apr 2025 21:14:43 +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 E5DF468055D
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 21:14:35 +0300 (EEST)
Received: by mail.gandi.net (Postfix) with ESMTPSA id 2B9A04341A
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 18:14:34 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc;
s=gm1; t=1744740875;
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:
in-reply-to:in-reply-to:references:references;
bh=z1znmJc91RX9m8gUTvGzRrLTXQOqQLE5bNoBllOGJaw=;
b=lnqRoZVjeVgA0osXfBf+vRzdQJiiWzmE5NA7L0W1e4Fe0/Tj3plDTbbTflA2QX7cZdcX/Y
8vzkQ/8QOKvPbh/QgG8qvfqUyPZKOqTPn3DzLEpVtttgbJ7G3RKAQ2aAO8Rrg4CICAo2fm
wjIA0DngBAcTLrglUI9puKAxgHewtRSR6JgvYGnnODg93B7RCLmfwr5DBDQfQtr7y3koAe
uZ3960BqmdTQSGSM3RusNWPrxyqJaa32ZuTRdODfAu76cakXa6G17iZHNICPd3QEmeHxA1
ahrSFt89r8zs7L4mrqamAsCBHLSjiAgwINjgI2ovArRDMJuiULRLlky3tHSo+g==
From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Date: Tue, 15 Apr 2025 20:14:29 +0200
Message-ID: <20250415181433.530161-2-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: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvvdegudekucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhephffvufffkffojghfggfgsedtkeertdertddtnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpedvgfefudeijeetieejkefgfffhtdeludeuffdvfeelieevjeetvedufeetfeejfeenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg
X-GND-Sasl: michael@niedermayer.cc
Subject: [FFmpeg-devel] [PATCH v2 2/6] avutil/tree: Add av_tree_move
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-2-michael@niedermayer.cc/>
List-Archive: <https://master.gitmailbox.com/ffmpegdev/>
List-Post: <mailto:ffmpegdev@gitmailbox.com>
This will allow storing a tree in a flat array and reallocating it
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
libavutil/tree.c | 15 +++++++++++++++
libavutil/tree.h | 11 +++++++++++
2 files changed, 26 insertions(+)
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 9f58a3f3d49..455a447bf11 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -190,3 +190,18 @@ void av_tree_enumerate(AVTreeNode *t, void *opaque,
av_tree_enumerate(t->child[1], opaque, cmp, enu);
}
}
+
+void av_tree_move(struct AVTreeNode *t, struct AVTreeNode *old, void *elem, void *old_elem)
+{
+ if (t->child[0]) {
+ av_tree_move(t->child[0] - old + t, t->child[0], elem, old_elem);
+ t->child[0] = t->child[0] - old + t;
+ }
+ if (t->child[1]) {
+ av_tree_move(t->child[1] - old + t, t->child[1], elem, old_elem);
+ t->child[1] = t->child[1] - old + t;
+ }
+
+ if (t->elem && elem != old_elem)
+ t->elem = (uint8_t*)t->elem - (uint8_t*)old_elem + (uint8_t*)elem;
+}
diff --git a/libavutil/tree.h b/libavutil/tree.h
index 6bafd47e593..10895e39578 100644
--- a/libavutil/tree.h
+++ b/libavutil/tree.h
@@ -136,6 +136,17 @@ void av_tree_enumerate(struct AVTreeNode *t, void *opaque,
int (*cmp)(void *opaque, void *elem),
int (*enu)(void *opaque, void *elem));
+/**
+ * Updates the tree in case the tree has been moved.
+ * This is needed for example when all tree nodes are in an array that is reallocated
+ *
+ * @param root the root of the tree to update
+ * @param old the old root on which internal pointers are still based
+ * @param elem the array that contains all elements after the move
+ * @param old the old element array
+ */
+void av_tree_move(struct AVTreeNode *root, struct AVTreeNode *old, void *elem, void *old_elem);
+
/**
* @}
*/
--
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".