From 02db0ae8ff83a42913b1b4224ccd8377f5fc5323 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Fri, 5 Mar 2021 17:41:53 +0100 Subject: Add a copy function to the rb-tree implementation If we use the rb-tree in libsquashfs objects, we need to be able top copy an entire tree as part of the object. Signed-off-by: David Oberhollenzer --- lib/util/rbtree.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+) (limited to 'lib') diff --git a/lib/util/rbtree.c b/lib/util/rbtree.c index 4e96435..873add8 100644 --- a/lib/util/rbtree.c +++ b/lib/util/rbtree.c @@ -105,6 +105,39 @@ static rbtree_node_t *mknode(const rbtree_t *t, const void *key, const void *val return node; } +static rbtree_node_t *copy_node(const rbtree_t *t, const rbtree_node_t *n) +{ + rbtree_node_t *out; + + out = calloc(1, sizeof(*out) + t->key_size_padded + t->value_size); + if (out == NULL) + return NULL; + + memcpy(out, n, sizeof(*n) + t->key_size_padded + t->value_size); + out->left = NULL; + out->right = NULL; + + if (n->left != NULL) { + out->left = copy_node(t, n->left); + + if (out->left == NULL) { + destroy_nodes_dfs(out); + return NULL; + } + } + + if (n->right != NULL) { + out->right = copy_node(t, n->right); + + if (out->right == NULL) { + destroy_nodes_dfs(out); + return NULL; + } + } + + return out; +} + int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, int(*key_compare)(const void *, const void *)) { @@ -146,6 +179,23 @@ int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, return 0; } +int rbtree_copy(const rbtree_t *tree, rbtree_t *out) +{ + memcpy(out, tree, sizeof(*out)); + out->root = NULL; + + if (tree->root != NULL) { + out->root = copy_node(tree, tree->root); + + if (out->root == NULL) { + memset(out, 0, sizeof(*out)); + return SQFS_ERROR_ALLOC; + } + } + + return 0; +} + void rbtree_cleanup(rbtree_t *tree) { destroy_nodes_dfs(tree->root); -- cgit v1.2.3