aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-03-05 18:58:12 +0100
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-03-06 22:08:36 +0100
commit919d1e85f2cc17059f72db48c3bc38e0b524f6c0 (patch)
treecac9b227ee4edac72b7c850370c23cbcf68d3d93
parent02db0ae8ff83a42913b1b4224ccd8377f5fc5323 (diff)
Add a context pointer to the rbtree key comparison
Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>
-rw-r--r--include/rbtree.h8
-rw-r--r--lib/common/hardlink.c3
-rw-r--r--lib/util/rbtree.c6
-rw-r--r--tests/libutil/rbtree.c7
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);
}