[FFmpeg-devel] [PATCH v2 2/6] avutil/tree: Add av_tree_move

[Michael Niedermayer]

This will allow storing a tree in a flat array and reallocating it

Signed-off-by: Michael Niedermayer <michael at 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