From a6428c51f8544ca92870eb573f8a7bc7d1e16d19 Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Thu, 3 Jul 2008 15:37:38 +0300 Subject: [PATCH] Added SILC Tree API, a generic binary search tree interface So far it supports only AVL tree but support for other types of trees can be added easily. --- doc/runtime.in/manual.html.in | 1 + lib/silcutil/Makefile.ad | 7 +- lib/silcutil/silcavltree.c | 438 +++++++++++++++++++++++++++++ lib/silcutil/silcruntime.h.in | 1 + lib/silcutil/silctree.h | 427 ++++++++++++++++++++++++++++ lib/silcutil/silctree_i.h | 64 +++++ lib/silcutil/tests/Makefile.am | 4 +- lib/silcutil/tests/test_silctree.c | 122 ++++++++ 8 files changed, 1060 insertions(+), 4 deletions(-) create mode 100644 lib/silcutil/silcavltree.c create mode 100644 lib/silcutil/silctree.h create mode 100644 lib/silcutil/silctree_i.h create mode 100644 lib/silcutil/tests/test_silctree.c diff --git a/doc/runtime.in/manual.html.in b/doc/runtime.in/manual.html.in index f1e474ed..bc0bdcbd 100644 --- a/doc/runtime.in/manual.html.in +++ b/doc/runtime.in/manual.html.in @@ -75,6 +75,7 @@ of the Toolkit always delivers the latest version of this reference manual.
  • Global Variable Interface
  • Hash Table Interface
  • List Interface +
  • Binary Search Tree Interface
  • Logging Interface
  • Memory Interface
  • Memory Pool Interface diff --git a/lib/silcutil/Makefile.ad b/lib/silcutil/Makefile.ad index 2d565d81..a3898ffb 100644 --- a/lib/silcutil/Makefile.ad +++ b/lib/silcutil/Makefile.ad @@ -70,7 +70,8 @@ libsilcutil_la_SOURCES = \ silcglobal.c \ silcbufferstream.c \ silclocalnetstream.c \ - silcxml.c + silcxml.c \ + silcavltree.c include_HEADERS = \ $(SILC_DIST_HEADER) \ @@ -128,7 +129,9 @@ include_HEADERS = \ silcdir.h \ silcbufferstream.h \ silclocalnetstream.h \ - silcxml.h + silcxml.h \ + silctree.h \ + silctree_i.h SILC_EXTRA_DIST = diff --git a/lib/silcutil/silcavltree.c b/lib/silcutil/silcavltree.c new file mode 100644 index 00000000..cef09195 --- /dev/null +++ b/lib/silcutil/silcavltree.c @@ -0,0 +1,438 @@ +/* + + silcavltree.c + + Author: Pekka Riikonen + + Copyright (C) 2008 Pekka Riikonen + + 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. + 3. The name of the author may not be used to endorse or promote + products derived from this software without specific prior written + permission. + + THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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. + +*/ + +/* AVL Tree. This code is based on code in libdict package. I am putting + all changes under the same license, that is the revised BSD license. The + original code is copyright by Farooq Mela. + + Main differences are that this implementation does not use a separate + node context but the user provided entry itself is the node in the tree, + thus avoiding issues like memory allocation, cleanup, etc., and making + the interface more generic. This interface does not allocate any + memory. This implementation also supports duplicates by adding them to + a simple list. */ + +#include + +/************************ Static utility functions **************************/ + +/* Rotate left + + / / + B D + / \ / \ + A D ==> B E + / \ / \ + C E A C +*/ + +static int silc_avl_tree_rot_left(SilcTree *tree, SilcTreeHeader *h) +{ + SilcTreeHeader *right, *parent; + int hc; + + SILC_ASSERT(h); + SILC_ASSERT(h->right); + + right = h->right; + h->right = right->left; + if (right->left) + right->left->parent = h; + + parent = h->parent; + right->parent = parent; + + if (parent) { + if (parent->left == h) + parent->left = right; + else + parent->right = right; + } else { + tree->root = right; + } + + right->left = h; + h->parent = right; + + hc = right->t != 0; + h->t -= 1 + SILC_MAX(right->t, 0); + right->t -= 1 - SILC_MIN(h->t, 0); + + return hc; +} + +/* Rotate right + + / / + D B + / \ / \ + B E ==> A D + / \ / \ + A C C E +*/ + +static int silc_avl_tree_rot_right(SilcTree *tree, SilcTreeHeader *h) +{ + SilcTreeHeader *left, *parent; + int hc; + + SILC_ASSERT(h); + SILC_ASSERT(h->left); + + left = h->left; + h->left = left->right; + if (left->right) + left->right->parent = h; + + parent = h->parent; + left->parent = parent; + + if (parent) { + if (parent->left == h) + parent->left = left; + else + parent->right = left; + } else { + tree->root = left; + } + + left->right = h; + h->parent = left; + + hc = left->t != 0; + h->t += 1 - SILC_MIN(left->t, 0); + left->t += 1 + SILC_MAX(h->t, 0); + + return hc; +} + +/****************************** Public API **********************************/ + +/* Find entry */ + +void *silc_avl_tree_find(SilcTree *tree, void *entry, + SilcTreeCompare compare, void *context) +{ + SilcTreeHeader *h; + SilcTreeCompare cmp = compare ? compare : tree->compare; + void *cmp_context = compare ? context : tree->context; + int ret; + + SILC_LOG_DEBUG(("AVL tree %p, find %p", tree, entry)); + + h = tree->root; + while (h) { + ret = cmp(entry, SILC_TREE_GET_ENTRY(tree, h), cmp_context); + if (!ret) { + SILC_LOG_DEBUG(("Found %p", SILC_TREE_GET_ENTRY(tree, h))); + return SILC_TREE_GET_ENTRY(tree, h); + } + h = ret > 0 ? h->right : h->left; + } + + SILC_LOG_DEBUG(("Not found")); + silc_set_errno(SILC_ERR_NOT_FOUND); + return NULL; +} + +/* Insert entry to tree */ + +SilcBool silc_avl_tree_add(SilcTree *tree, void *entry) +{ + SilcTreeHeader *h, *parent = NULL, *q = NULL; + int ret = 0; + + SILC_LOG_DEBUG(("AVL tree %p, adding %p", tree, entry)); + + /* If tree is empty, add to root */ + if (!tree->root) { + h = SILC_TREE_GET_HEADER(tree, entry); + h->parent = h->left = h->right = h->dup = NULL; + h->t = 0; + tree->root = h; + + SILC_LOG_DEBUG(("Entry %p added as root", entry)); + + SILC_ASSERT(!tree->count); + tree->count = 1; + return TRUE; + } + + /* Find the spot to add the new entry */ + h = tree->root; + while (h) { + /* Same entry context must not be in tree */ + if (entry == SILC_TREE_GET_ENTRY(tree, h)) { + silc_set_errno(SILC_ERR_ALREADY_EXISTS); + return FALSE; + } + + ret = tree->compare(entry, SILC_TREE_GET_ENTRY(tree, h), tree->context); + if (!tree->duplicates && ret == 0) { + silc_set_errno(SILC_ERR_ALREADY_EXISTS); + return FALSE; + } + + /* Duplicate entry, add to list */ + if (ret == 0) { + q = SILC_TREE_GET_HEADER(tree, entry); + q->duplicate = TRUE; + q->parent = h; + if (h->dup) + h->dup->parent = q; + q->dup = h->dup; + h->dup = q; + SILC_LOG_DEBUG(("Entry %p is duplicate to %p", entry, + SILC_TREE_GET_ENTRY(tree, h))); + tree->count++; + return TRUE; + } + + parent = h; + if (parent->t) + q = parent; + h = ret > 0 ? h->right : h->left; + } + + /* Update parent */ + h = SILC_TREE_GET_HEADER(tree, entry); + if (ret < 0) + parent->left = h; + else + parent->right = h; + + SILC_LOG_DEBUG(("Entry %p added, parent %p", entry, + SILC_TREE_GET_ENTRY(tree, parent))); + + /* Update the new entry */ + h->parent = parent; + h->left = h->right = h->dup = NULL; + h->t = 0; + + /* Balance */ + while (parent != q) { + parent->t = (parent->right == h) * 2 - 1; + h = parent; + parent = h->parent; + } + + if (q) { + if (q->left == h) { + if (--q->t == (-2)) { + if (q->left->t > 0) + silc_avl_tree_rot_left(tree, q->left); + silc_avl_tree_rot_right(tree, q); + } + } else { + if (++q->t == 2) { + if (q->right->t < 0) + silc_avl_tree_rot_right(tree, q->right); + silc_avl_tree_rot_left(tree, q); + } + } + } + + tree->count++; + return TRUE; +} + +/* Delete entry from tree */ + +SilcBool silc_avl_tree_del(SilcTree *tree, void *entry) +{ + SilcTreeHeader *h, *q, *out, *parent = NULL, tmp; + int left; + + SILC_LOG_DEBUG(("AVL tree %p, delete %p", tree, entry)); + + if (!tree->root || !entry) { + silc_set_errno(SILC_ERR_INVALID_ARGUMENT); + return FALSE; + } + + /* Unless the incoming entry is already the one to be deleted find it + from the tree first. */ + q = h = SILC_TREE_GET_HEADER(tree, entry); + if (!h->parent && !h->left && !h->right && !h->t) { + entry = silc_avl_tree_find(tree, entry, NULL, NULL); + if (!entry) + return FALSE; + q = h = SILC_TREE_GET_HEADER(tree, entry); + } + + /* If entry has duplicates, replace this with one of them */ + if (h->dup) { + h->dup->duplicate = FALSE; + h->dup->parent = h->parent; + h->dup->left = h->left; + h->dup->right = h->right; + h->dup->t = h->t; + + /* Update parent */ + if (h->parent) { + if (h->parent->left == h) + h->parent->left = h->dup; + else + h->parent->right = h->dup; + } else { + tree->root = h->dup; + } + + /* Update leafs */ + if (h->left) + h->left->parent = h->dup; + if (h->right) + h->right->parent = h->dup; + + /* Cleanup the deleted entry */ + SILC_LOG_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h))); + h->parent = h->left = h->right = h->dup = NULL; + h->t = 0; + + tree->count--; + return TRUE; + } + + /* If the entry is not a leaf, swap with the smallest from right side */ + if (h->left && h->right) { + for (q = out = h->right; out->left; q = out = out->left) ; + tmp = *h; + *h = *out; + *out = tmp; + + /* Update node's parent with the replaced node */ + if (out->parent) { + if (out->parent->left == h) + out->parent->left = out; + else + out->parent->right = out; + } else { + tree->root = out; + } + + /* Update parents and leafs */ + if (h->parent == h) + h->parent = out; + if (out->left == out) + out->left = h; + else if (out->right == out) + out->right = h; + out->left->parent = out; + out->right->parent = out; + } + + parent = h->parent; + out = h->left ? h->left : h->right; + if (out) + out->parent = parent; + + /* Cleanup the deleted entry */ + SILC_LOG_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h))); + h->parent = h->left = h->right = h->dup = NULL; + h->t = 0; + + if (!parent) { + tree->root = out; + tree->count--; + return TRUE; + } + + /* Update parent */ + left = parent->left == q; + if (left) + parent->left = out; + else + parent->right = out; + + /* Balance */ + for (;;) { + if (left) { + if (++parent->t == 0) { + h = parent; + goto higher; + } + if (parent->t == 2) { + SILC_ASSERT(parent->right); + if (parent->right->t < 0) { + silc_avl_tree_rot_right(tree, parent->right); + silc_avl_tree_rot_left(tree, parent); + } else { + SILC_ASSERT(parent->right->right); + if (silc_avl_tree_rot_left(tree, parent) == 0) + break; + } + } else { + break; + } + } else { + if (--parent->t == 0) { + h = parent; + goto higher; + } + if (parent->t == (-2)) { + SILC_ASSERT(parent->left); + if (parent->left->t > 0) { + silc_avl_tree_rot_left(tree, parent->left); + silc_avl_tree_rot_right(tree, parent); + } else { + SILC_ASSERT(parent->left->left); + if (silc_avl_tree_rot_right(tree, parent) == 0) + break; + } + } else { + break; + } + } + + /* Only get here on double rotations or single rotations that changed + subtree height - in either event, `parent->parent' is positioned + where `parent' was positioned before any rotations. */ + h = parent->parent; + higher: + if ((parent = h->parent) == NULL) + break; + left = parent->left == h; + } + + tree->count--; + return TRUE; +} + +/* AVL tree operations */ +const struct SilcTreeOpsStruct silc_tree_avl_ops = +{ + silc_avl_tree_add, + silc_avl_tree_del, + silc_avl_tree_find, +}; diff --git a/lib/silcutil/silcruntime.h.in b/lib/silcutil/silcruntime.h.in index 257b4dd5..53d45ea8 100644 --- a/lib/silcutil/silcruntime.h.in +++ b/lib/silcutil/silcruntime.h.in @@ -208,6 +208,7 @@ extern "C" { #include #include #include +#include #include #include #include diff --git a/lib/silcutil/silctree.h b/lib/silcutil/silctree.h new file mode 100644 index 00000000..e4d3f062 --- /dev/null +++ b/lib/silcutil/silctree.h @@ -0,0 +1,427 @@ +/* + + silctree.h + + Author: Pekka Riikonen + + Copyright (C) 2008 Pekka Riikonen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + +*/ + +/****h* silcutil/Binary Search Tree Interface + * + * DESCRIPTION + * + * Binary Search Tree Interface provides simple interface for adding, + * deleting, retrieving and enumerating items in a tree. The inteface + * allows also duplicate values in the tree, and it does not allocate any + * memory. The interface can support many types of binary search trees. + * + * The interface is not thread-safe. If the same SilcTree context must be + * used in multithreaded environment concurrency control must be employed. + * + ***/ + +#ifndef SILCTREE_H +#define SILCTREE_H + +/****s* silcutil/SilcTree + * + * NAME + * + * typedef struct SilcTreeStruct SilcTree; + * + * DESCRIPTION + * + * This is the SilcTree context, and is initialized by calling the + * function silc_tree_init. It need not be uninitialized. + * + ***/ +typedef struct SilcTreeStruct SilcTree; + +/****s* silcutil/SilcTreeHeader + * + * NAME + * + * typedef struct SilcTreeHeaderStruct SilcTreeHeader; + * + * DESCRIPTION + * + * This structure must be present in each context that is added to the + * tree. The structure can be at any place in the context. + * + * EXAMPLE + * + * // Structure that is going to be added to tree + * typedef struct { + * SilcTreeHeader header; + * char *name; + * int id; + * } FooEntry; + * + ***/ +typedef struct SilcTreeHeaderStruct SilcTreeHeader; + +/****f* silcutil/SilcTreeCompare + * + * SYNOPSIS + * + * typedef int (*SilcTreeCompare)(void *entry1, void *entry2, + * void *context); + * + * DESCRIPTION + * + * Callback function of this type is called to compare values in the + * tree. If the `entry1' is smaller, equal to or greater than `entry2' + * this function must return less than, equal to, or greater than zero, + * respectively. + * + ***/ +typedef int (*SilcTreeCompare)(void *entry1, void *entry2, void *context); + +/****d* silcutil/SilcTreeType + * + * NAME + * + * typedef enum { ... } SilcTreeType; + * + * DESCRIPTION + * + * The supported tree types. + * + * SOURCE + */ +typedef enum { + /* AVL Tree. Automatically balancing binary search tree that provides + excellent performance. */ + SILC_TREE_AVL = 0, +} SilcTreeType; +/***/ + +#include "silctree_i.h" + +/* Tree implementations */ +extern DLLAPI const struct SilcTreeOpsStruct silc_tree_avl_ops; + +/****f* silcutil/silc_tree_init + * + * SYNOPSIS + * + * SilcBool silc_tree_init(SilcTree tree, SilcTreeType type, + * SilcTreeCompare compare, void *context, + * SilcUInt16 offset, SilcBool duplicates); + * + * DESCRIPTION + * + * Initializes the `tree' as a tree type indicated by `type'. The + * `compare' function will be called to compare entries in the tree, + * for example, when finding entries from the tree. The `context' is + * delivered to the callback function. + * + * The `offset' is the byte offset of the SilcTreeHeader structure field + * in the entry structure that is going to be added to the tree. Each + * structure that is added to the tree must contain SilcTreeHeader + * structure. Use silc_offsetof to get the byte offset. + * + * If the `duplicates' is TRUE the tree will allow the addition of + * duplicate values. However, the entry context to be added must not + * already be in the tree, but its value may be same as some other + * context's. + * + * The `tree' need not be uninitialized. The caller is responsible of + * freeing the entries it has added to the tree. + * + * Return FALSE if the `type' is of unknown tree type. Returns TRUE + * otherwise. This function does not allocate any memory. + * + * EXAMPLE + * + * // Structure that is going to be added to tree + * typedef struct { + * SilcTreeHeader header; + * char *name; + * int id; + * } FooEntry; + * + * SilcTree tree; + * silc_tree_init(tree, SILC_TREE_AVL, compare, context, + * silc_offsetof(FooEntry, header)); + * + ***/ +#define silc_tree_init(tree, type, compare, context, offset, d) \ + __silc_tree_init(&(tree), type, compare, context, offset, d) +static inline +SilcBool __silc_tree_init(SilcTree *tree, + SilcTreeType type, SilcTreeCompare compare, + void *context, SilcUInt32 offset, + SilcBool duplicates) +{ + switch (type) { + case SILC_TREE_AVL: + tree->ops = &silc_tree_avl_ops; + break; + + default: + return FALSE; + break; + } + + tree->root = NULL; + tree->compare = compare; + tree->context = context; + tree->count = 0; + tree->offset = offset; + tree->duplicates = duplicates; + + return TRUE; +} + +/****f* silcutil/silc_tree_add + * + * SYNOPSIS + * + * SilcBool silc_tree_add(SilcTree *tree, void *entry); + * + * DESCRIPTION + * + * Add `entry' to the `tree'. Returns TRUE after the entry has been + * added to the tree. If the `tree' does not allocate duplicate entries + * this will return FALSE if same value as `entry' is already in the + * tree. + * + * EXAMPLE + * + * FooEntry *client_entry; + * + * client_entry->id = id; + * client_entry->name = name; + * silc_tree_add(tree, client_entry); + * + ***/ +#define silc_tree_add(tree, e) (tree).ops->add(&(tree), (e)) + +/****f* silcutil/silc_tree_del + * + * SYNOPSIS + * + * SilcBool silc_tree_del(SilcTree *tree, void *entry); + * + * DESCRIPTION + * + * Delete entry from the `tree'. If the `entry' is not the actual entry + * context that was added to the tree but is merely a temporary context + * it must be memset'ed to zero (0) initially. The deletion routine will + * assume that the given `entry' is the actual added entry context if its + * SilcTreeHeader structure is not zeroed when deleting the entry. If it + * is zeroed the deletion will first try to find the entry from the tree + * and then delete the found entry. See example for both cases. + * + * Return FALSE if the entry does not exist in the tree. Returns TRUE + * after successful deletion. + * + * EXAMPLE + * + * // Delete the entry, we have access to the originally added context + * silc_tree_del(tree, client_entry); + * + * // Delete client entry with ID 100 + * FooEntry tmp; + * memset(&tmp, 0, sizeof(tmp)); + * tmp.id = 100; + * silc_tree_del(tree, &tmp); + * + * // Delete all entries from the tree + * while ((entry = silc_tree_enumerate(tree, NULL))) + * silc_tree_del(tree, entry); + * + ***/ +#define silc_tree_del(tree, e) (tree).ops->del(&(tree), (e)) + +/****f* silcutil/silc_tree_find + * + * SYNOPSIS + * + * void *silc_tree_find(SilcTree *tree, void *entry); + * + * DESCRIPTION + * + * Find entry from the tree. Returns the found entry or NULL if the + * entry does not exist in the tree and sets silc_errno. + * + * If there are duplicate values in the tree this will find the first + * one. Rest of the duplicate values can be found by calling + * silc_tree_enumerate_duplicates. It will stop the enumeration when + * the last duplicate entry is returned. + * + * EXAMPLE + * + * FooEntry probe, *client_entry; + * + * // Find entry by ID 100 + * probe.id = 100; + * client_entry = silc_tree_find(tree, &probe); + * + ***/ +#define silc_tree_find(tree, e) (tree).ops->find(&(tree), (e), NULL, NULL) + +/****f* silcutil/silc_tree_find_ext + * + * SYNOPSIS + * + * void *silc_tree_find_ext(SilcTree *tree, void *entry, + * SilcTreeCompare compare, void *context); + * + * DESCRIPTION + * + * Same as silc_tree_find but takes a separate comparison function as + * argument. + * + ***/ +#define silc_tree_find_ext(tree, e, compare, context) \ + (tree).ops->find(&(tree), (e), (compare), (context)) + +/****f* silcutil/silc_tree_count + * + * SYNOPSIS + * + * SilcUInt32 silc_tree_count(SilcTree *tree); + * + * DESCRIPTION + * + * Returns the number of entries in the tree. + * + ***/ +#define silc_tree_count(tree) (tree).count + +/****f* silcutil/silc_tree_minmax + * + * SYNOPSIS + * + * void *silc_tree_minmax(SilcTree *tree, SilcBool min); + * + * DESCRIPTION + * + * Returns either smallest or largest value from the `tree'. If the `min' + * is TRUE returns the smallest, otherwise returns the largest. Returns + * NULL if the tree is empty. + * + ***/ +#define silc_tree_minmax(tree, min) __silc_tree_minmax(&(tree), (min)) +static inline +void *__silc_tree_minmax(SilcTree *tree, SilcBool min) +{ + SilcTreeHeader *h; + + h = tree->root; + if (!h) + return NULL; + + if (min) + while (h->left) + h = h->left; + else + while (h->right) + h = h->right; + + return SILC_TREE_GET_ENTRY(tree, h); +} + +/****f* silcutil/silc_tree_enumerate + * + * SYNOPSIS + * + * void *silc_tree_enumerate(SilcTree *tree, void *at); + * + * DESCRIPTION + * + * Enumerates the `tree' starting/continuing at the `at'. When `at' is + * NULL this will start enumeration from the root of the tree. The found + * entry must be given as `at' for next call to continue the enumeration + * in order. The enumeration is done in ascending order starting from the + * smallest value. If there are duplicates in the tree, their order is + * undefined. Returns NULL at the end of the enumeration. + * + * EXAMPLE + * + * // Start enumerating from beginning in order + * for (entry = silc_tree_enumerate(tree, NULL); entry != NULL; + * entry = silc_tree_enumerate(tree, entry)) + * printf("Client entry %s\n", entry->name); + * + * // Delete all entries from the tree + * while ((entry = silc_tree_enumerate(tree, NULL))) + * silc_tree_del(tree, entry); + * + ***/ +#define silc_tree_enumerate(tree, e) __silc_tree_enumerate(&(tree), (e)) +static inline +void *__silc_tree_enumerate(SilcTree *tree, void *at) +{ + SilcTreeHeader *h, *p; + + if (at == NULL) + return __silc_tree_minmax(tree, TRUE); + + h = SILC_TREE_GET_HEADER(tree, at); + + if (h->dup) + return SILC_TREE_GET_ENTRY(tree, h->dup); + else if (h->duplicate) + for (h = h->parent; h->duplicate; h = h->parent) ; + + if (h->right) { + for (h = h->right; h->left; h = h->left) ; + return SILC_TREE_GET_ENTRY(tree, h); + } + + p = h->parent; + while (p && p->right == h) { + h = p; + p = p->parent; + } + + return p ? SILC_TREE_GET_ENTRY(tree, p) : NULL; +} + +/****f* silcutil/silc_tree_enumerate_duplicates + * + * SYNOPSIS + * + * void *silc_tree_enumerate_duplicates(SilcTree *tree, void *at); + * + * DESCRIPTION + * + * Enumerates all duplicate values starting at the `at'. If `at' is the + * only one of that value in the tree this will return NULL. Returns same + * values as `at' until there are no more and will then return NULL. The + * `at' must not be NULL. + * + * EXAMPLE + * + * // Find all entries of ID 100 + * probe.id = 100; + * entry = silc_tree_find(tree, &probe); + * printf("Entry %p ID %d\n", entry, entry->id); + * while ((entry = silc_tree_enumerate_duplicates(tree, entry))) + * printf("Entry %p ID %d\n", entry, entry->id); + * + ***/ +#define silc_tree_enumerate_duplicates(tree, e) \ + __silc_tree_enumerate_dup(&(tree), (e)) +static inline +void *__silc_tree_enumerate_dup(SilcTree *tree, void *at) +{ + SilcTreeHeader *h = SILC_TREE_GET_HEADER(tree, at); + return h->dup ? SILC_TREE_GET_ENTRY(tree, h->dup) : NULL; +} + +#endif /* SILCTREE_H */ diff --git a/lib/silcutil/silctree_i.h b/lib/silcutil/silctree_i.h new file mode 100644 index 00000000..9f3a6aa3 --- /dev/null +++ b/lib/silcutil/silctree_i.h @@ -0,0 +1,64 @@ +/* + + silctree_i.h + + Author: Pekka Riikonen + + Copyright (C) 2008 Pekka Riikonen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + +*/ + +#ifndef SILCTREE_I_H +#define SILCTREE_I_H + +#ifndef SILCTREE_H +#error "Do not include this header directly" +#endif + +/* Tree operatins header */ +struct SilcTreeOpsStruct { + SilcBool (*add)(SilcTree *tree, void *entry); + SilcBool (*del)(SilcTree *tree, void *entry); + void *(*find)(SilcTree *tree, void *entry, SilcTreeCompare compare, + void *context); +}; + +/* Generic tree header, present in each entry in tree */ +struct SilcTreeHeaderStruct { + struct SilcTreeHeaderStruct *parent; + struct SilcTreeHeaderStruct *left; + struct SilcTreeHeaderStruct *right; + struct SilcTreeHeaderStruct *dup; + SilcInt16 t; + unsigned int duplicate : 1; +}; + +/* Tree context */ +struct SilcTreeStruct { + const struct SilcTreeOpsStruct *ops; + SilcTreeHeader *root; + SilcTreeCompare compare; + void *context; + SilcUInt32 count; + unsigned int offset : 31; + unsigned int duplicates : 1; +}; + +/* Get tree header from entry */ +#define SILC_TREE_GET_HEADER(tree, pos) \ + ((void *)((unsigned char *)(pos) + tree->offset)) + +/* Get entry from tree header */ +#define SILC_TREE_GET_ENTRY(tree, pos) \ + ((void *)((unsigned char *)(pos) - tree->offset)) + +#endif /* SILCTREE_I_H */ diff --git a/lib/silcutil/tests/Makefile.am b/lib/silcutil/tests/Makefile.am index 78323eda..77aa4b7a 100644 --- a/lib/silcutil/tests/Makefile.am +++ b/lib/silcutil/tests/Makefile.am @@ -25,7 +25,7 @@ check_PROGRAMS = \ test_silcdll test_silcenv test_silctimer test_silcbitops \ test_silcregex test_silcbuffmt test_silcdir test_silcthreadqueue \ test_silcrand test_silcglobal test_silcbufferstream test_silcxml \ - test_silclocalnetstream + test_silclocalnetstream test_silctree TESTS = test_silcstrutil test_silcstringprep test_silchashtable \ test_silclist test_silcfsm test_silcasync test_silcschedule \ @@ -34,7 +34,7 @@ TESTS = test_silcstrutil test_silcstringprep test_silchashtable \ test_silcdll test_silcenv test_silctimer test_silcbitops \ test_silcregex test_silcbuffmt test_silcdir test_silcthreadqueue \ test_silcrand test_silcglobal test_silcbufferstream \ - test_silclocalnetstream + test_silclocalnetstream test_silctree LIBS = $(SILC_COMMON_LIBS) LDADD = -L.. -L../.. -lsrt diff --git a/lib/silcutil/tests/test_silctree.c b/lib/silcutil/tests/test_silctree.c new file mode 100644 index 00000000..9f614c18 --- /dev/null +++ b/lib/silcutil/tests/test_silctree.c @@ -0,0 +1,122 @@ +/* SilcTree tests */ + +#include "silcruntime.h" + +SilcTree tree; + +typedef struct { + int id; + int od; + char *foo; + SilcTreeHeader header; +} Foo; + +#define NUM 199 +Foo foo[NUM], foo2[NUM], tmp, *entry; + +static int compare(void *e1, void *e2, void *context) +{ + Foo *f1 = e1, *f2 = e2; + SILC_LOG_DEBUG(("%p %d > %p %d", f1, f1->id, f2, f2->id)); + return f1->id - f2->id; +} + +int main(int argc, char **argv) +{ + SilcBool success = FALSE; + int i; + + silc_runtime_init(); + + if (argc > 1 && !strcmp(argv[1], "-d")) { + silc_log_debug(TRUE); + silc_log_quick(TRUE); + silc_log_debug_hexdump(TRUE); + silc_log_set_debug_string("*tree*"); + } + + for (i = 0; i < NUM; i++) { + foo[i].id = i + 1; + foo[i].od = i + 10; + } + + for (i = 0; i < NUM; i++) { + foo2[i].id = (i + 1) % (NUM / 4); + foo2[i].od = (i + 10) % (NUM / 4); + } + + /* AVL */ + SILC_LOG_DEBUG(("Create AVL tree")); + if (!silc_tree_init(tree, SILC_TREE_AVL, compare, NULL, + silc_offsetof(Foo, header), TRUE)) + goto err; + + /* Populate tree */ + SILC_LOG_DEBUG(("Populate tree, %d entries", NUM)); + for (i = 0; i < NUM; i++) + if (!silc_tree_add(tree, &foo[i])) + goto err; + + /* Add duplicates */ + SILC_LOG_DEBUG(("Add duplicates")); + for (i = 0; i < NUM; i++) + if (!silc_tree_add(tree, &foo2[i])) + goto err; + + SILC_LOG_DEBUG(("Tree has %d entries", silc_tree_count(tree))); + if (silc_tree_count(tree) != NUM + NUM) + goto err; + + /* Find random */ + for (i = 0; i < NUM; i++) { + tmp.id = (silc_rand() % NUM) + 1; + SILC_LOG_DEBUG(("Find entry %d", tmp.id)); + if ((entry = silc_tree_find(tree, &tmp)) == NULL) + goto err; + SILC_LOG_DEBUG(("Found entry %p %d", entry, entry->id)); + } + + /* Find non-existing */ + for (i = 0; i < 5; i++) { + tmp.id = (silc_rand() % NUM) + (i % 2 ? -NUM - 1 : NUM + 1); + SILC_LOG_DEBUG(("Find entry %d", tmp.id)); + if (silc_tree_find(tree, &tmp)) + goto err; + } + + /* Enumerate in order */ + for (entry = silc_tree_enumerate(tree, NULL); + entry; + entry = silc_tree_enumerate(tree, entry)) { + SILC_LOG_DEBUG(("Enum entry %d, %p", entry->id, entry)); + } + + /* Delete all */ + for (i = 0; i < NUM; i++) { + memset(&tmp, 0, sizeof(tmp)); + tmp.id = i + 1; + SILC_LOG_DEBUG(("Delete entry %d", tmp.id)); + if (!silc_tree_del(tree, &tmp)) + goto err; + } + + /* Delete remaining duplicates in loop */ + while ((entry = silc_tree_enumerate(tree, NULL))) { + if (!silc_tree_del(tree, entry)) + goto err; + } + + SILC_LOG_DEBUG(("Tree has %d entries", silc_tree_count(tree))); + if (silc_tree_count(tree) != 0) + goto err; + + success = TRUE; + + err: + SILC_LOG_DEBUG(("Testing was %s", success ? "SUCCESS" : "FAILURE")); + fprintf(stderr, "Testing was %s\n", success ? "SUCCESS" : "FAILURE"); + + silc_runtime_uninit(); + + return !success; +} -- 2.24.0