From 919d1e85f2cc17059f72db48c3bc38e0b524f6c0 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Fri, 5 Mar 2021 18:58:12 +0100 Subject: Add a context pointer to the rbtree key comparison Signed-off-by: David Oberhollenzer --- include/rbtree.h | 8 ++++++-- lib/common/hardlink.c | 3 ++- lib/util/rbtree.c | 6 +++--- tests/libutil/rbtree.c | 7 ++++--- 4 files changed, 15 insertions(+), 9 deletions(-) diff --git a/include/rbtree.h b/include/rbtree.h index bbba711..b1ddcd2 100644 --- a/include/rbtree.h +++ b/include/rbtree.h @@ -26,12 +26,15 @@ typedef struct rbtree_node_t { typedef struct rbtree_t { rbtree_node_t *root; - int (*key_compare)(const void *lhs, const void *hrs); + int (*key_compare)(const void *ctx, + const void *lhs, const void *hrs); size_t key_size; size_t key_size_padded; size_t value_size; + + void *key_context; } rbtree_t; static SQFS_INLINE void *rbtree_node_key(rbtree_node_t *n) @@ -45,7 +48,8 @@ static SQFS_INLINE void *rbtree_node_value(rbtree_node_t *n) } SQFS_INTERNAL int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, - int(*key_compare)(const void *, const void *)); + int(*key_compare)(const void *, const void *, + const void *)); SQFS_INTERNAL void rbtree_cleanup(rbtree_t *tree); diff --git a/lib/common/hardlink.c b/lib/common/hardlink.c index 63621a4..678a7a3 100644 --- a/lib/common/hardlink.c +++ b/lib/common/hardlink.c @@ -71,9 +71,10 @@ fail_insert: return -1; } -static int compare_inum(const void *lhs, const void *rhs) +static int compare_inum(const void *ctx, const void *lhs, const void *rhs) { sqfs_u32 l = *((sqfs_u32 *)lhs), r = *((sqfs_u32 *)rhs); + (void)ctx; return l < r ? -1 : (l > r ? 1 : 0); } diff --git a/lib/util/rbtree.c b/lib/util/rbtree.c index 873add8..d8f1305 100644 --- a/lib/util/rbtree.c +++ b/lib/util/rbtree.c @@ -80,7 +80,7 @@ static rbtree_node_t *subtree_insert(rbtree_t *tree, rbtree_node_t *root, if (root == NULL) return new; - if (tree->key_compare(new->data, root->data) < 0) { + if (tree->key_compare(tree->key_context, new->data, root->data) < 0) { root->left = subtree_insert(tree, root->left, new); } else { root->right = subtree_insert(tree, root->right, new); @@ -139,7 +139,7 @@ static rbtree_node_t *copy_node(const rbtree_t *t, const rbtree_node_t *n) } int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, - int(*key_compare)(const void *, const void *)) + int(*key_compare)(const void *, const void *, const void *)) { size_t diff, size; @@ -220,7 +220,7 @@ rbtree_node_t *rbtree_lookup(const rbtree_t *tree, const void *key) int ret; while (node != NULL) { - ret = tree->key_compare(key, node->data); + ret = tree->key_compare(tree->key_context, key, node->data); if (ret == 0) break; diff --git a/tests/libutil/rbtree.c b/tests/libutil/rbtree.c index 03c0025..25c9b61 100644 --- a/tests/libutil/rbtree.c +++ b/tests/libutil/rbtree.c @@ -9,8 +9,9 @@ #include "rbtree.h" #include "../test.h" -static int key_compare(const void *a, const void *b) +static int key_compare(const void *ctx, const void *a, const void *b) { + (void)ctx; return *((sqfs_s32 *)a) - *((sqfs_s32 *)b); } @@ -66,14 +67,14 @@ static void check_binary_tree_dfs(rbtree_node_t *n) if (n->left != NULL) { cmp = rbtree_node_key(n->left); - TEST_ASSERT(key_compare(cmp, key) < 0); + TEST_ASSERT(key_compare(NULL, cmp, key) < 0); check_binary_tree_dfs(n->left); } if (n->right != NULL) { cmp = rbtree_node_key(n->right); - TEST_ASSERT(key_compare(cmp, key) > 0); + TEST_ASSERT(key_compare(NULL, cmp, key) > 0); check_binary_tree_dfs(n->right); } -- cgit v1.2.3