summaryrefslogtreecommitdiff
path: root/lib/util
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-03-05 17:41:53 +0100
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-03-06 22:08:36 +0100
commit02db0ae8ff83a42913b1b4224ccd8377f5fc5323 (patch)
tree27d8454d8d8033d33a58a852864cd6450df22709 /lib/util
parent378db7c6ab1336ce99136118a9b66901630ffc85 (diff)
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 <david.oberhollenzer@sigma-star.at>
Diffstat (limited to 'lib/util')
-rw-r--r--lib/util/rbtree.c50
1 files changed, 50 insertions, 0 deletions
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);