--- /dev/null
+/*
+
+ silcavltree.c
+
+ Author: Pekka Riikonen <priikone@silcnet.org>
+
+ 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 <silcruntime.h>
+
+/************************ 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,
+};
projects / runtime.git / blobdiff