From 4a307afc0bddeba03e26d2d6d284b3f96f80a931 Mon Sep 17 00:00:00 2001 From: Sebastian Harl Date: Tue, 8 Jul 2014 19:51:07 +0200 Subject: [PATCH] utils avltree: Started implementation of an AVL tree. So far, it's just an unbalanced binary tree, though ;-) --- src/Makefile.am | 2 + src/include/utils/avltree.h | 83 ++++++++++ src/utils/avltree.c | 308 ++++++++++++++++++++++++++++++++++++ t/Makefile.am | 1 + t/unit/libsysdb_test.c | 1 + t/unit/libsysdb_test.h | 4 + t/unit/utils/avltree_test.c | 194 +++++++++++++++++++++++ 7 files changed, 593 insertions(+) create mode 100644 src/include/utils/avltree.h create mode 100644 src/utils/avltree.c create mode 100644 t/unit/utils/avltree_test.c diff --git a/src/Makefile.am b/src/Makefile.am index 705b7e4..0130d42 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -30,6 +30,7 @@ pkgfeinclude_HEADERS = \ include/frontend/sock.h pkgutilsincludedir = $(pkgincludedir)/utils pkgutilsinclude_HEADERS = \ + include/utils/avltree.h \ include/utils/channel.h \ include/utils/dbi.h \ include/utils/error.h \ @@ -77,6 +78,7 @@ libsysdb_la_SOURCES = \ frontend/sock.c include/frontend/sock.h \ frontend/session.c \ frontend/query.c \ + utils/avltree.c include/utils/avltree.h \ utils/channel.c include/utils/channel.h \ utils/error.c include/utils/error.h \ utils/llist.c include/utils/llist.h \ diff --git a/src/include/utils/avltree.h b/src/include/utils/avltree.h new file mode 100644 index 0000000..b3eec42 --- /dev/null +++ b/src/include/utils/avltree.h @@ -0,0 +1,83 @@ +/* + * SysDB - src/include/utils/avltree.h + * Copyright (C) 2014 Sebastian 'tokkee' Harl + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef SDB_UTILS_AVLTREE_H +#define SDB_UTILS_AVLTREE_H 1 + +#include "core/object.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* + * An AVL tree implements Adelson-Velskii and Landis' self-balancing search + * tree. It supports search, insert, and delete operations in average and + * worst-case time-complexity O(log n). + * + * XXX: self-balancing is not implemented yet + */ +struct sdb_avltree; +typedef struct sdb_avltree sdb_avltree_t; + +struct sdb_avltree_iter; +typedef struct sdb_avltree_iter sdb_avltree_iter_t; + +sdb_avltree_t * +sdb_avltree_create(sdb_object_cmp_cb cmp); + +void +sdb_avltree_destroy(sdb_avltree_t *tree); + +void +sdb_avltree_clear(sdb_avltree_t *tree); + +int +sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj); + +sdb_avltree_iter_t * +sdb_avltree_get_iter(sdb_avltree_t *tree); + +void +sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter); + +_Bool +sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter); +sdb_object_t * +sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter); + +size_t +sdb_avltree_size(sdb_avltree_t *tree); + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ! SDB_UTILS_AVLTREE_H */ + +/* vim: set tw=78 sw=4 ts=4 noexpandtab : */ + diff --git a/src/utils/avltree.c b/src/utils/avltree.c new file mode 100644 index 0000000..95c004d --- /dev/null +++ b/src/utils/avltree.c @@ -0,0 +1,308 @@ +/* + * SysDB - src/utils/avltree.c + * Copyright (C) 2014 Sebastian 'tokkee' Harl + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif /* HAVE_CONFIG_H */ + +#include "utils/avltree.h" + +#include + +#include + +/* + * private data types + */ + +struct node; +typedef struct node node_t; + +struct node { + sdb_object_t *obj; + + node_t *parent; + node_t *left; + node_t *right; +}; + +struct sdb_avltree { + pthread_rwlock_t lock; + + sdb_object_cmp_cb cmp; + + node_t *root; + size_t size; +}; + +struct sdb_avltree_iter { + sdb_avltree_t *tree; + node_t *node; +}; + +/* + * private helper functions + */ + +static void +node_destroy(node_t *n) +{ + sdb_object_deref(n->obj); + n->obj = NULL; + n->parent = n->left = n->right = NULL; + free(n); +} /* node_destroy */ + +static node_t * +node_create(sdb_object_t *obj) +{ + node_t *n = malloc(sizeof(*n)); + if (! n) + return NULL; + + sdb_object_ref(obj); + n->obj = obj; + n->parent = n->left = n->right = NULL; + return n; +} /* node_create */ + +static node_t * +node_next(node_t *n) +{ + node_t *next; + + if (! n) + return NULL; + + /* descend into the right tree */ + if (n->right) { + next = n->right; + while (next->left) + next = next->left; + return next; + } + + /* visit the parent if we're in its left tree */ + if (n->parent && (n->parent->left == n)) + return n->parent; + + /* find the parent of the sibling sub-tree on the right */ + next = n->parent; + next = NULL; + while (n->parent && (n->parent->right == n)) { + n = n->parent; + next = n; + } + if (next) + next = next->parent; + return next; +} /* node_next */ + +static void +tree_clear(sdb_avltree_t *tree) +{ + node_t *n; + + n = tree->root; + while (n) { + node_t *tmp = node_next(n); + + node_destroy(n); + n = tmp; + } + + tree->root = NULL; + tree->size = 0; +} /* tree_clear */ + +/* + * public API + */ + +sdb_avltree_t * +sdb_avltree_create(sdb_object_cmp_cb cmp) +{ + sdb_avltree_t *tree; + + tree = malloc(sizeof(*tree)); + 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; + return tree; +} /* sdb_avltree_create */ + +void +sdb_avltree_destroy(sdb_avltree_t *tree) +{ + if (! tree) + return; + + pthread_rwlock_wrlock(&tree->lock); + tree_clear(tree); + pthread_rwlock_unlock(&tree->lock); + pthread_rwlock_destroy(&tree->lock); + free(tree); +} /* sdb_avltree_destroy */ + +void +sdb_avltree_clear(sdb_avltree_t *tree) +{ + if (! tree) + return; + + pthread_rwlock_wrlock(&tree->lock); + tree_clear(tree); + pthread_rwlock_unlock(&tree->lock); +} /* sdb_avltree_clear */ + +int +sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj) +{ + node_t *parent; + node_t *n; + + int diff = -1; + + if (! tree) + return -1; + + n = node_create(obj); + if (! n) + return -1; + + parent = tree->root; + while (parent) { + diff = tree->cmp(obj, parent->obj); + if (! diff) { + node_destroy(n); + return -1; + } + + if (diff < 0) { + if (! parent->left) { + parent->left = n; + break; + } + parent = parent->left; + } + else { + if (! parent->right) { + parent->right = n; + break; + } + parent = parent->right; + } + } + + if (! parent) { + /* new root */ + if (diff < 0) + n->right = tree->root; + else + n->left = tree->root; + tree->root = n; + } + + n->parent = parent; + ++tree->size; + + /* XXX: rebalance */ + return 0; +} /* sdb_avltree_insert */ + +sdb_avltree_iter_t * +sdb_avltree_get_iter(sdb_avltree_t *tree) +{ + sdb_avltree_iter_t *iter; + + if (! tree) + return NULL; + + iter = malloc(sizeof(*iter)); + if (! iter) + return NULL; + + pthread_rwlock_rdlock(&tree->lock); + + iter->tree = tree; + iter->node = tree->root->left; + while (iter->node && iter->node->left) + iter->node = iter->node->left; + + pthread_rwlock_unlock(&tree->lock); + return iter; +} /* sdb_avltree_get_iter */ + +void +sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter) +{ + if (! iter) + return; + + iter->tree = NULL; + iter->node = NULL; + free(iter); +} /* sdb_avltree_iter_destroy */ + +_Bool +sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter) +{ + if (! iter) + return 0; + + return iter->node != NULL; +} /* sdb_avltree_iter_has_next */ + +sdb_object_t * +sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter) +{ + node_t *n; + + if (! iter) + return NULL; + + n = iter->node; + iter->node = node_next(iter->node); + return n ? n->obj : NULL; +} /* sdb_avltree_iter_get_next */ + +size_t +sdb_avltree_size(sdb_avltree_t *tree) +{ + return tree ? tree->size : 0; +} /* sdb_avltree_size */ + +/* vim: set tw=78 sw=4 ts=4 noexpandtab : */ + diff --git a/t/Makefile.am b/t/Makefile.am index 5de153f..c5560e9 100644 --- a/t/Makefile.am +++ b/t/Makefile.am @@ -34,6 +34,7 @@ unit_libsysdb_test_SOURCES = \ unit/frontend/connection_test.c \ unit/frontend/parser_test.c \ unit/frontend/sock_test.c \ + unit/utils/avltree_test.c \ unit/utils/channel_test.c \ unit/utils/dbi_test.c \ unit/utils/llist_test.c \ diff --git a/t/unit/libsysdb_test.c b/t/unit/libsysdb_test.c index d2e0667..dbda23c 100644 --- a/t/unit/libsysdb_test.c +++ b/t/unit/libsysdb_test.c @@ -50,6 +50,7 @@ main(void) { fe_conn_suite, NULL }, { fe_parser_suite, NULL }, { fe_sock_suite, NULL }, + { util_avltree_suite, NULL }, { util_channel_suite, NULL }, { util_dbi_suite, NULL }, { util_llist_suite, NULL }, diff --git a/t/unit/libsysdb_test.h b/t/unit/libsysdb_test.h index de04d50..861623f 100644 --- a/t/unit/libsysdb_test.h +++ b/t/unit/libsysdb_test.h @@ -91,6 +91,10 @@ fe_parser_suite(void); Suite * fe_sock_suite(void); +/* t/utils/avltree_test */ +Suite * +util_avltree_suite(void); + /* t/utils/channel_test */ Suite * util_channel_suite(void); diff --git a/t/unit/utils/avltree_test.c b/t/unit/utils/avltree_test.c new file mode 100644 index 0000000..d978eff --- /dev/null +++ b/t/unit/utils/avltree_test.c @@ -0,0 +1,194 @@ +/* + * SysDB - t/unit/utils/avltree_test.c + * Copyright (C) 2015 Sebastian 'tokkee' Harl + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "utils/avltree.h" +#include "libsysdb_test.h" + +#include + +static sdb_avltree_t *tree; + +static void +setup(void) +{ + tree = sdb_avltree_create(NULL); + fail_unless(tree != NULL, + "sdb_avltree_create() = NULL; expected AVL-tree object"); +} /* setup */ + +static void +teardown(void) +{ + sdb_avltree_destroy(tree); + tree = NULL; +} /* teardown */ + +/* 'a' - 'k' */ +static sdb_object_t test_data[] = { + SSTRING_OBJ("d"), + SSTRING_OBJ("f"), + SSTRING_OBJ("e"), + SSTRING_OBJ("b"), + SSTRING_OBJ("a"), + SSTRING_OBJ("c"), + SSTRING_OBJ("g"), + SSTRING_OBJ("h"), + SSTRING_OBJ("i"), + SSTRING_OBJ("j"), + SSTRING_OBJ("k"), +}; + +static void +populate(void) +{ + size_t i; + for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) + sdb_avltree_insert(tree, &test_data[i]); +} /* populate */ + +START_TEST(test_null) +{ + sdb_object_t o1 = SSTRING_OBJ("obj"); + sdb_object_t *o2; + sdb_avltree_iter_t *iter; + int check; + + /* all functions should work even when passed null values */ + sdb_avltree_destroy(NULL); + sdb_avltree_clear(NULL); + + check = sdb_avltree_insert(NULL, NULL); + fail_unless(check < 0, + "sdb_avltree_insert(NULL, NULL) = %d; expected: <0", check); + check = sdb_avltree_insert(NULL, &o1); + fail_unless(check < 0, + "sdb_avltree_insert(NULL, ) = %d; expected: <0", check); + fail_unless(o1.ref_cnt == 1, + "sdb_avltree_insert(NULL, ) incremented ref-cnt"); + /* it's acceptable to insert NULL */ + + iter = sdb_avltree_get_iter(NULL); + fail_unless(iter == NULL, + "sdb_avltree_get_iter(NULL) = %p; expected: NULL", iter); + + check = sdb_avltree_iter_has_next(NULL) != 0; + fail_unless(check == 0, + "sdb_avltree_iter_has_next(NULL) = %d; expected: 0", check); + o2 = sdb_avltree_iter_get_next(NULL); + fail_unless(o2 == NULL, + "sdb_avltree_iter_get_next(NULL) = %p; expected: NULL", o2); + + sdb_avltree_iter_destroy(NULL); + + check = (int)sdb_avltree_size(NULL); + fail_unless(check == 0, + "sdb_avltree_size(NULL) = %d; expected: 0", check); +} +END_TEST + +START_TEST(test_insert) +{ + size_t i; + + for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) { + int check; + + check = sdb_avltree_insert(tree, &test_data[i]); + fail_unless(check == 0, + "sdb_avltree_insert(, <%s>) = %d; expected: 0", + test_data[i].name, check); + + check = (int)sdb_avltree_size(tree); + fail_unless(check == (int)i + 1, + "sdb_avltree_size() = %d; expected: %zu", + check, i + 1); + } +} +END_TEST + +START_TEST(test_iter) +{ + sdb_avltree_iter_t *iter; + sdb_object_t *obj; + + size_t check, i; + + populate(); + check = sdb_avltree_size(tree); + fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data), + "INTERNAL ERROR: AVL tree size (after populate) = %zu; " + "expected: %zu", check, SDB_STATIC_ARRAY_LEN(test_data)); + + iter = sdb_avltree_get_iter(tree); + fail_unless(iter != NULL, + "sdb_avltree_get_iter() = NULL; expected: "); + + for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) { + char expected_name[] = { (char)('a' + (int)i), '\0' }; + + _Bool c = sdb_avltree_iter_has_next(iter); + fail_unless(c, "sdb_avltree_iter_has_next() = false; " + "expected: true", i); + + obj = sdb_avltree_iter_get_next(iter); + fail_unless(obj != NULL, + "sdb_avltree_iter_get_next() = NULL; " + "expected: ", i); + fail_unless(!strcmp(obj->name, expected_name), + "sdb_avltree_iter[%zu] = %s; expected: %s", + i, obj->name, expected_name); + } + + check = sdb_avltree_iter_has_next(iter) != 0; + fail_unless(check == 0, "sdb_avltree_iter_has_next() = true; " + "expected: false"); + obj = sdb_avltree_iter_get_next(iter); + fail_unless(obj == NULL, + "sdb_avltree_iter_get_next() = ; expected: NULL"); + + sdb_avltree_iter_destroy(iter); +} +END_TEST + +Suite * +util_avltree_suite(void) +{ + Suite *s = suite_create("utils::avltree"); + TCase *tc; + + tc = tcase_create("core"); + tcase_add_checked_fixture(tc, setup, teardown); + tcase_add_test(tc, test_null); + tcase_add_test(tc, test_insert); + tcase_add_test(tc, test_iter); + suite_add_tcase(s, tc); + + return s; +} /* util_avltree_suite */ + +/* vim: set tw=78 sw=4 ts=4 noexpandtab : */ + -- 2.30.2