From 7c0c900e329faf456e2b7e1a017a197ef7839c5d Mon Sep 17 00:00:00 2001 From: Sebastian Harl Date: Fri, 11 Jul 2014 08:06:45 +0200 Subject: [PATCH] avltree: Always compare objects by name. We don't need a custom compare function (for now) and correctly passing in a const string when comparing based on objects is annoying to get right. --- src/include/utils/avltree.h | 23 +++++++++-------------- src/utils/avltree.c | 15 +++++---------- t/unit/utils/avltree_test.c | 21 ++++++++++----------- 3 files changed, 24 insertions(+), 35 deletions(-) diff --git a/src/include/utils/avltree.h b/src/include/utils/avltree.h index 7e70758..28efbdf 100644 --- a/src/include/utils/avltree.h +++ b/src/include/utils/avltree.h @@ -47,13 +47,10 @@ typedef struct sdb_avltree_iter sdb_avltree_iter_t; /* * sdb_avltree_create: - * Creates an AVL tree. Insert and lookup operations will use the specified - * compare function to determine the location of an object in the tree. If no - * function has been specified, it defaults to sdb_object_cmp_by_name, that - * is, objects will be compared by their names. + * Creates an AVL tree. Objects will be compared by their names. */ sdb_avltree_t * -sdb_avltree_create(sdb_object_cmp_cb cmp); +sdb_avltree_create(void); /* * sdb_avltree_destroy: @@ -73,10 +70,9 @@ sdb_avltree_clear(sdb_avltree_t *tree); /* * sdb_avltree_insert: - * Insert a new node into the tree (using the tree's compare function to find - * the right location). Each object must be unique (based on the compare - * function). This operation may change the structure of the tree by - * rebalancing subtrees which no longer comply with the rules of AVL. + * Insert a new node into the tree. Each object must be unique. This operation + * may change the structure of the tree by rebalancing subtrees which no + * longer comply with the rules of AVL. * * Returns: * - 0 on success @@ -87,22 +83,21 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj); /* * sdb_avltree_lookup: - * Lookup an object from a tree. The object matching the specified reference - * object (using the tree's compare function) will be returned. + * Lookup an object from a tree by name. * * Returns: * - the requested object * - NULL if no such object exists */ sdb_object_t * -sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref); +sdb_avltree_lookup(sdb_avltree_t *tree, const char *name); /* * sdb_avltree_get_iter, sdb_avltree_iter_has_next, sdb_avltree_iter_get_next, * sdb_avltree_iter_destroy: * Iterate through all nodes of the tree. The iterator will start at the - * smallest element (based on the tree's compare function) and then iterate - * through the sorted sequence of all nodes. + * smallest element (based on the name) and then iterate through the sorted + * sequence of all nodes. * * sdb_avltree_iter_get_next returns NULL if there is no next element. */ diff --git a/src/utils/avltree.c b/src/utils/avltree.c index 56bc57d..7397a34 100644 --- a/src/utils/avltree.c +++ b/src/utils/avltree.c @@ -36,6 +36,7 @@ #include #include +#include #include /* @@ -66,8 +67,6 @@ struct node { struct sdb_avltree { pthread_rwlock_t lock; - sdb_object_cmp_cb cmp; - node_t *root; size_t size; }; @@ -260,7 +259,7 @@ rebalance(sdb_avltree_t *tree, node_t *n) */ sdb_avltree_t * -sdb_avltree_create(sdb_object_cmp_cb cmp) +sdb_avltree_create(void) { sdb_avltree_t *tree; @@ -268,11 +267,7 @@ sdb_avltree_create(sdb_object_cmp_cb cmp) if (! tree) return NULL; - if (! cmp) - cmp = sdb_object_cmp_by_name; - pthread_rwlock_init(&tree->lock, /* attr = */ NULL); - tree->cmp = cmp; tree->root = NULL; tree->size = 0; @@ -331,7 +326,7 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj) while (42) { assert(parent); - diff = tree->cmp(obj, parent->obj); + diff = strcasecmp(obj->name, parent->obj->name); if (! diff) { node_destroy(n); pthread_rwlock_unlock(&tree->lock); @@ -363,7 +358,7 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj) } /* sdb_avltree_insert */ sdb_object_t * -sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref) +sdb_avltree_lookup(sdb_avltree_t *tree, const char *name) { node_t *n; @@ -372,7 +367,7 @@ sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref) n = tree->root; while (n) { - int diff = tree->cmp(n->obj, ref); + int diff = strcasecmp(n->obj->name, name); if (! diff) { sdb_object_ref(n->obj); diff --git a/t/unit/utils/avltree_test.c b/t/unit/utils/avltree_test.c index 3526e41..4f6933a 100644 --- a/t/unit/utils/avltree_test.c +++ b/t/unit/utils/avltree_test.c @@ -35,7 +35,7 @@ static sdb_avltree_t *tree; static void setup(void) { - tree = sdb_avltree_create(NULL); + tree = sdb_avltree_create(); fail_unless(tree != NULL, "sdb_avltree_create() = NULL; expected AVL-tree object"); } /* setup */ @@ -162,27 +162,26 @@ START_TEST(test_lookup) populate(); for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) { - sdb_object_t ref = SDB_OBJECT_STATIC(test_data[i].name); sdb_object_t *obj; - obj = sdb_avltree_lookup(tree, &ref); + obj = sdb_avltree_lookup(tree, test_data[i].name); fail_unless(obj != NULL, - "sdb_avltree_lookup(, <%s>) = NULL; " - "expected: ", ref.name); + "sdb_avltree_lookup(, %s) = NULL; " + "expected: ", test_data[i].name); fail_unless(obj == &test_data[i], - "sdb_avltree_lookup(, <%s>) = %p (%s); " - "expected: %p, (%s)", ref.name, obj, obj->name, + "sdb_avltree_lookup(, %s) = %p (%s); " + "expected: %p, (%s)", test_data[i].name, obj, obj->name, &test_data[i], test_data[i].name); } for (i = 0; i < SDB_STATIC_ARRAY_LEN(unused_names); ++i) { - sdb_object_t ref = SDB_OBJECT_STATIC(unused_names[i]); sdb_object_t *obj; - obj = sdb_avltree_lookup(tree, &ref); + obj = sdb_avltree_lookup(tree, unused_names[i]); fail_unless(obj == NULL, - "sdb_avltree_lookup(, <%s> = %p (%s); " - "expected: NULL", ref.name, obj, obj ? obj->name : ""); + "sdb_avltree_lookup(, %s) = %p (%s); " + "expected: NULL", unused_names[i], + obj, obj ? obj->name : ""); } } END_TEST -- 2.30.2