From 0b1fce762dca88659b3103783e8852cb7265823e Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sat, 22 Feb 2020 01:09:33 +0100 Subject: Add a very simple red-black tree implementation Signed-off-by: David Oberhollenzer --- include/rbtree.h | 63 +++++++++++++++++ lib/util/Makemodule.am | 1 + lib/util/rbtree.c | 181 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 245 insertions(+) create mode 100644 include/rbtree.h create mode 100644 lib/util/rbtree.c diff --git a/include/rbtree.h b/include/rbtree.h new file mode 100644 index 0000000..7fe1752 --- /dev/null +++ b/include/rbtree.h @@ -0,0 +1,63 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * rbtree.h + * + * Copyright (C) 2019 David Oberhollenzer + */ +#ifndef SQFS_RBTREE_H +#define SQFS_RBTREE_H + +#include "config.h" +#include "sqfs/predef.h" +#include "compat.h" + +#include + +typedef struct rbtree_node_t { + struct rbtree_node_t *left; + struct rbtree_node_t *right; + sqfs_u32 value_offset; + sqfs_u32 is_red : 1; + sqfs_u32 pad0 : 31; + + sqfs_u8 data[]; +} rbtree_node_t; + +typedef struct rbtree_t { + rbtree_node_t *root; + + int (*key_compare)(const void *lhs, const void *hrs); + + size_t key_size; + size_t key_size_padded; + + size_t value_size; +} rbtree_t; + +static SQFS_INLINE void *rbtree_node_key(rbtree_node_t *n) +{ + return n->data; +} + +static SQFS_INLINE void *rbtree_node_value(rbtree_node_t *n) +{ + return n->data + n->value_offset; +} + +SQFS_INTERNAL int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, + int(*key_compare)(const void *, const void *)); + +SQFS_INTERNAL void rbtree_cleanup(rbtree_t *tree); + +SQFS_INTERNAL int rbtree_insert(rbtree_t *tree, const void *key, + const void *value); + +SQFS_INTERNAL rbtree_node_t *rbtree_lookup(const rbtree_t *tree, + const void *key); + +#ifdef __cplusplus +} +#endif + +#endif /* TOOLS_RBTREE_H */ + diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am index f5a5680..87f3495 100644 --- a/lib/util/Makemodule.am +++ b/lib/util/Makemodule.am @@ -1,5 +1,6 @@ libutil_a_SOURCES = include/util.h include/str_table.h libutil_a_SOURCES += lib/util/str_table.c lib/util/alloc.c +libutil_a_SOURCES += lib/util/rbtree.c include/rbtree.h libutil_a_CFLAGS = $(AM_CFLAGS) libutil_a_CPPFLAGS = $(AM_CPPFLAGS) diff --git a/lib/util/rbtree.c b/lib/util/rbtree.c new file mode 100644 index 0000000..4e96435 --- /dev/null +++ b/lib/util/rbtree.c @@ -0,0 +1,181 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * rbtree.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "sqfs/error.h" +#include "rbtree.h" + +#include +#include + +#define IS_RED(n) ((n) && (n)->is_red) + +static void destroy_nodes_dfs(rbtree_node_t *n) +{ + rbtree_node_t *l, *r; + + if (n != NULL) { + l = n->left; + r = n->right; + free(n); + destroy_nodes_dfs(l); + destroy_nodes_dfs(r); + } +} + +static void flip_colors(rbtree_node_t *n) +{ + n->is_red = !n->is_red; + n->left->is_red = !n->left->is_red; + n->right->is_red = !n->right->is_red; +} + +static rbtree_node_t *rotate_right(rbtree_node_t *n) +{ + rbtree_node_t *x; + + x = n->left; + n->left = x->right; + x->right = n; + + x->is_red = x->right->is_red; + x->right->is_red = 1; + return x; +} + +static rbtree_node_t *rotate_left(rbtree_node_t *n) +{ + rbtree_node_t *x; + + x = n->right; + n->right = x->left; + x->left = n; + + x->is_red = x->left->is_red; + x->left->is_red = 1; + return x; +} + +static rbtree_node_t *subtree_balance(rbtree_node_t *n) +{ + if (IS_RED(n->right) && !IS_RED(n->left)) + n = rotate_left(n); + + if (IS_RED(n->left) && IS_RED(n->left->left)) + n = rotate_right(n); + + if (IS_RED(n->left) && IS_RED(n->right)) + flip_colors(n); + + return n; +} + +static rbtree_node_t *subtree_insert(rbtree_t *tree, rbtree_node_t *root, + rbtree_node_t *new) +{ + if (root == NULL) + return new; + + if (tree->key_compare(new->data, root->data) < 0) { + root->left = subtree_insert(tree, root->left, new); + } else { + root->right = subtree_insert(tree, root->right, new); + } + + return subtree_balance(root); +} + +static rbtree_node_t *mknode(const rbtree_t *t, const void *key, const void *value) +{ + rbtree_node_t *node; + + node = calloc(1, sizeof(*node) + t->key_size_padded + t->value_size); + if (node == NULL) + return NULL; + + node->value_offset = t->key_size_padded; + node->is_red = 1; + + memcpy(node->data, key, t->key_size); + memcpy(node->data + t->key_size_padded, value, t->value_size); + return node; +} + +int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, + int(*key_compare)(const void *, const void *)) +{ + size_t diff, size; + + memset(tree, 0, sizeof(*tree)); + tree->key_compare = key_compare; + tree->key_size = keysize; + tree->key_size_padded = keysize; + tree->value_size = valuesize; + + /* make sure the value always has pointer alignment */ + diff = keysize % sizeof(void *); + + if (diff != 0) { + diff = sizeof(void *) - diff; + + if (SZ_ADD_OV(tree->key_size_padded, diff, + &tree->key_size_padded)) { + return SQFS_ERROR_OVERFLOW; + } + } + + /* make sure the node can store the offset */ + if (sizeof(size_t) > sizeof(sqfs_u32)) { + if (tree->key_size_padded > 0x0FFFFFFFFUL) + return SQFS_ERROR_OVERFLOW; + } + + /* make sure the nodes fit in memory */ + size = sizeof(rbtree_node_t); + + if (SZ_ADD_OV(size, tree->key_size_padded, &size)) + return SQFS_ERROR_OVERFLOW; + + if (SZ_ADD_OV(size, tree->value_size, &size)) + return SQFS_ERROR_OVERFLOW; + + return 0; +} + +void rbtree_cleanup(rbtree_t *tree) +{ + destroy_nodes_dfs(tree->root); + memset(tree, 0, sizeof(*tree)); +} + +int rbtree_insert(rbtree_t *tree, const void *key, const void *value) +{ + rbtree_node_t *node = mknode(tree, key, value); + + if (node == NULL) + return SQFS_ERROR_ALLOC; + + tree->root = subtree_insert(tree, tree->root, node); + tree->root->is_red = 0; + return 0; +} + +rbtree_node_t *rbtree_lookup(const rbtree_t *tree, const void *key) +{ + rbtree_node_t *node = tree->root; + int ret; + + while (node != NULL) { + ret = tree->key_compare(key, node->data); + if (ret == 0) + break; + + node = ret < 0 ? node->left : node->right; + } + + return node; +} -- cgit v1.2.3