From 244e834e4d971f81b93ccd79fbf93c1f7eb38d73 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 2 Jul 2020 20:52:05 +0200 Subject: [PATCH] avltree: Return errno values; unify argument handling. --- src/utils/avltree/avltree.c | 99 ++++++++++++++++++-------------- src/utils/avltree/avltree.h | 17 ++++-- src/utils/avltree/avltree_test.c | 2 +- 3 files changed, 70 insertions(+), 48 deletions(-) diff --git a/src/utils/avltree/avltree.c b/src/utils/avltree/avltree.c index af6efed95..728a1309d 100644 --- a/src/utils/avltree/avltree.c +++ b/src/utils/avltree/avltree.c @@ -25,6 +25,8 @@ **/ #include +#include +#include #include #include "utils/avltree/avltree.h" @@ -324,7 +326,7 @@ static c_avl_node_t *c_avl_node_prev(c_avl_node_t *n) { return r; } /* c_avl_node_t *c_avl_node_prev */ -static int _remove(c_avl_tree_t *t, c_avl_node_t *n) { +static void _remove(c_avl_tree_t *t, c_avl_node_t *n) { assert((t != NULL) && (n != NULL)); if ((n->left != NULL) && (n->right != NULL)) { @@ -408,8 +410,6 @@ static int _remove(c_avl_tree_t *t, c_avl_node_t *n) { } else { assert(0); } - - return 0; } /* void *_remove */ /* @@ -444,7 +444,7 @@ int c_avl_insert(c_avl_tree_t *t, void *key, void *value) { int cmp; if ((new = malloc(sizeof(*new))) == NULL) - return -1; + return ENOMEM; new->key = key; new->value = value; @@ -464,7 +464,7 @@ int c_avl_insert(c_avl_tree_t *t, void *key, void *value) { cmp = t->compare(nptr->key, new->key); if (cmp == 0) { free_node(new); - return 1; + return EEXIST; } else if (cmp < 0) { /* nptr < new */ if (nptr->right == NULL) { @@ -495,24 +495,23 @@ int c_avl_insert(c_avl_tree_t *t, void *key, void *value) { } /* int c_avl_insert */ int c_avl_remove(c_avl_tree_t *t, const void *key, void **rkey, void **rvalue) { - c_avl_node_t *n; - int status; - - assert(t != NULL); + if ((t == NULL) || (key == NULL)) { + return EINVAL; + } - n = search(t, key); + c_avl_node_t *n = search(t, key); if (n == NULL) - return -1; + return ENOENT; if (rkey != NULL) *rkey = n->key; if (rvalue != NULL) *rvalue = n->value; - status = _remove(t, n); + _remove(t, n); verify_tree(t->root); --t->size; - return status; + return 0; } /* void *c_avl_remove */ int c_avl_get(c_avl_tree_t *t, const void *key, void **value) { @@ -522,7 +521,7 @@ int c_avl_get(c_avl_tree_t *t, const void *key, void **value) { n = search(t, key); if (n == NULL) - return -1; + return ENOENT; if (value != NULL) *value = n->value; @@ -531,17 +530,15 @@ int c_avl_get(c_avl_tree_t *t, const void *key, void **value) { } int c_avl_pick(c_avl_tree_t *t, void **key, void **value) { - c_avl_node_t *n; - c_avl_node_t *p; - - assert(t != NULL); + if ((t == NULL) || ((key == NULL) && (value == NULL))) { + return EINVAL; + } - if ((key == NULL) || (value == NULL)) - return -1; - if (t->root == NULL) - return -1; + if (t->root == NULL) { + return EOF; + } - n = t->root; + c_avl_node_t *n = t->root; while ((n->left != NULL) || (n->right != NULL)) { if (n->left == NULL) { n = n->right; @@ -557,7 +554,7 @@ int c_avl_pick(c_avl_tree_t *t, void **key, void **value) { n = n->right; } - p = n->parent; + c_avl_node_t *p = n->parent; if (p == NULL) t->root = NULL; else if (p->left == n) @@ -565,8 +562,12 @@ int c_avl_pick(c_avl_tree_t *t, void **key, void **value) { else p->right = NULL; - *key = n->key; - *value = n->value; + if (key != NULL) { + *key = n->key; + } + if (value != NULL) { + *value = n->value; + } free_node(n); --t->size; @@ -578,8 +579,10 @@ int c_avl_pick(c_avl_tree_t *t, void **key, void **value) { c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t) { c_avl_iterator_t *iter; - if (t == NULL) + if (t == NULL) { + errno = EINVAL; return NULL; + } iter = calloc(1, sizeof(*iter)); if (iter == NULL) @@ -590,11 +593,11 @@ c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t) { } /* c_avl_iterator_t *c_avl_get_iterator */ int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value) { - c_avl_node_t *n; - - if ((iter == NULL) || (key == NULL) || (value == NULL)) - return -1; + if ((iter == NULL) || ((key == NULL) && (value == NULL))) { + return EINVAL; + } + c_avl_node_t *n = NULL; if (iter->node == NULL) { for (n = iter->tree->root; n != NULL; n = n->left) if (n->left == NULL) @@ -604,22 +607,27 @@ int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value) { n = c_avl_node_next(iter->node); } - if (n == NULL) - return -1; + if (n == NULL) { + return EOF; + } iter->node = n; - *key = n->key; - *value = n->value; + if (key != NULL) { + *key = n->key; + } + if (value != NULL) { + *value = n->value; + } return 0; } /* int c_avl_iterator_next */ int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) { - c_avl_node_t *n; - - if ((iter == NULL) || (key == NULL) || (value == NULL)) - return -1; + if ((iter == NULL) || ((key == NULL) && (value == NULL))) { + return EINVAL; + } + c_avl_node_t *n = NULL; if (iter->node == NULL) { for (n = iter->tree->root; n != NULL; n = n->right) if (n->right == NULL) @@ -629,12 +637,17 @@ int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) { n = c_avl_node_prev(iter->node); } - if (n == NULL) - return -1; + if (n == NULL) { + return EOF; + } iter->node = n; - *key = n->key; - *value = n->value; + if (key != NULL) { + *key = n->key; + } + if (value != NULL) { + *value = n->value; + } return 0; } /* int c_avl_iterator_prev */ diff --git a/src/utils/avltree/avltree.h b/src/utils/avltree/avltree.h index 3f52b9314..6d49ff7ed 100644 --- a/src/utils/avltree/avltree.h +++ b/src/utils/avltree/avltree.h @@ -137,17 +137,26 @@ int c_avl_get(c_avl_tree_t *t, const void *key, void **value); * * PARAMETERS * `t' AVL-tree to get the value from. - * `key' Pointer to a pointer in which to store the key. - * `value' Pointer to a pointer in which to store the value. + * `key' Pointer to a pointer in which to store the key. Either key or + * value, but not both, may be NULL. + * `value' Pointer to a pointer in which to store the value. Either key or + * value, but not both, may be NULL. * * RETURN VALUE - * Zero upon success or non-zero if the tree is empty or key or value is - * NULL. + * Zero upon success. EOF if the tree is empty. EINVAL if t or key are NULL. */ int c_avl_pick(c_avl_tree_t *t, void **key, void **value); c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t); + +/* c_avl_iterator_next returns the next key/value in the tree. Either key or + * value, but not both, may be NULL. Returns zero on success or EOF if there are + * no more nodes in the tree. */ int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value); + +/* c_avl_iterator_prev returns the previous key/value in the tree. Either key or + * value, but not both, may be NULL. Returns zero on success or EOF if there are + * no more nodes in the tree. */ int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value); void c_avl_iterator_destroy(c_avl_iterator_t *iter); diff --git a/src/utils/avltree/avltree_test.c b/src/utils/avltree/avltree_test.c index 8cbcb13ce..2221dbacc 100644 --- a/src/utils/avltree/avltree_test.c +++ b/src/utils/avltree/avltree_test.c @@ -92,7 +92,7 @@ DEF_TEST(success) { /* Key already exists. */ for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) - EXPECT_EQ_INT(1, c_avl_insert(t, cases[i].key, cases[i].value)); + EXPECT_EQ_INT(EEXIST, c_avl_insert(t, cases[i].key, cases[i].value)); /* get */ for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) { -- 2.47.2