5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2008 Pekka Riikonen
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are
13 1. Redistributions of source code must retain the above copyright
14 notice, this list of conditions and the following disclaimer.
15 2. Redistributions in binary form must reproduce the above copyright
16 notice, this list of conditions and the following disclaimer in the
17 documentation and/or other materials provided with the distribution.
18 3. The name of the author may not be used to endorse or promote
19 products derived from this software without specific prior written
22 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
25 NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 /* AVL Tree. This code is based on code in libdict package. I am putting
36 all changes under the same license, that is the revised BSD license. The
37 original code is copyright by Farooq Mela.
39 Main differences are that this implementation does not use a separate
40 node context but the user provided entry itself is the node in the tree,
41 thus avoiding issues like memory allocation, cleanup, etc., and making
42 the interface more generic. This interface does not allocate any
43 memory. This implementation also supports duplicates by adding them to
46 #include <silcruntime.h>
48 /* Define to 1 if you want hash table debug enabled */
49 #ifndef SILC_AVL_TREE_DEBUG
50 #define SILC_AVL_TREE_DEBUG 0
51 #endif /* !SILC_AVL_TREE_DEBUG */
53 #if SILC_ALV_TREE_DEBUG == 1
54 #define SILC_TREE_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
56 #define SILC_TREE_DEBUG(fmt)
59 /************************ Static utility functions **************************/
71 static int silc_avl_tree_rot_left(SilcTree *tree, SilcTreeHeader *h)
73 SilcTreeHeader *right, *parent;
77 SILC_ASSERT(h->right);
80 h->right = right->left;
82 right->left->parent = h;
85 right->parent = parent;
88 if (parent->left == h)
91 parent->right = right;
100 h->t -= 1 + SILC_MAX(right->t, 0);
101 right->t -= 1 - SILC_MIN(h->t, 0);
116 static int silc_avl_tree_rot_right(SilcTree *tree, SilcTreeHeader *h)
118 SilcTreeHeader *left, *parent;
122 SILC_ASSERT(h->left);
125 h->left = left->right;
127 left->right->parent = h;
130 left->parent = parent;
133 if (parent->left == h)
136 parent->right = left;
145 h->t += 1 - SILC_MIN(left->t, 0);
146 left->t += 1 + SILC_MAX(h->t, 0);
151 /****************************** Public API **********************************/
155 void *silc_avl_tree_find(SilcTree *tree, void *entry,
156 SilcCompare compare, void *context)
159 SilcCompare cmp = compare ? compare : tree->compare;
160 void *cmp_context = compare ? context : tree->context;
163 SILC_TREE_DEBUG(("AVL tree %p, find %p", tree, entry));
167 ret = cmp(entry, SILC_TREE_GET_ENTRY(tree, h), cmp_context);
168 if (ret == SILC_COMPARE_EQUAL_TO) {
169 SILC_TREE_DEBUG(("Found %p", SILC_TREE_GET_ENTRY(tree, h)));
170 return SILC_TREE_GET_ENTRY(tree, h);
172 if (ret == SILC_COMPARE_STOP)
174 h = ret > 0 ? h->right : h->left;
177 SILC_TREE_DEBUG(("Not found"));
178 silc_set_errno_nofail(SILC_ERR_NOT_FOUND);
182 /* Insert entry to tree */
184 SilcBool silc_avl_tree_add(SilcTree *tree, void *entry)
186 SilcTreeHeader *h, *parent = NULL, *q = NULL;
189 SILC_TREE_DEBUG(("AVL tree %p, adding %p", tree, entry));
191 /* If tree is empty, add to root */
193 h = SILC_TREE_GET_HEADER(tree, entry);
194 h->parent = h->left = h->right = h->dup = NULL;
198 SILC_TREE_DEBUG(("Entry %p added as root", entry));
200 SILC_ASSERT(!tree->count);
205 /* Find the spot to add the new entry */
208 /* Same entry context must not be in tree */
209 if (entry == SILC_TREE_GET_ENTRY(tree, h)) {
210 silc_set_errno_nofail(SILC_ERR_ALREADY_EXISTS);
214 ret = tree->compare(entry, SILC_TREE_GET_ENTRY(tree, h), tree->context);
215 if (!tree->duplicates && ret == SILC_COMPARE_EQUAL_TO) {
216 silc_set_errno_nofail(SILC_ERR_ALREADY_EXISTS);
220 /* Duplicate entry, add to list */
221 if (ret == SILC_COMPARE_EQUAL_TO) {
222 q = SILC_TREE_GET_HEADER(tree, entry);
229 SILC_TREE_DEBUG(("Entry %p is duplicate to %p", entry,
230 SILC_TREE_GET_ENTRY(tree, h)));
238 h = ret > 0 ? h->right : h->left;
242 h = SILC_TREE_GET_HEADER(tree, entry);
248 SILC_TREE_DEBUG(("Entry %p added, parent %p", entry,
249 SILC_TREE_GET_ENTRY(tree, parent)));
251 /* Update the new entry */
253 h->left = h->right = h->dup = NULL;
257 while (parent != q) {
258 parent->t = (parent->right == h) * 2 - 1;
265 if (--q->t == (-2)) {
267 silc_avl_tree_rot_left(tree, q->left);
268 silc_avl_tree_rot_right(tree, q);
273 silc_avl_tree_rot_right(tree, q->right);
274 silc_avl_tree_rot_left(tree, q);
283 /* Delete entry from tree */
285 SilcBool silc_avl_tree_del(SilcTree *tree, void *entry)
287 SilcTreeHeader *h, *q, *out, *parent = NULL, tmp;
290 SILC_TREE_DEBUG(("AVL tree %p, delete %p", tree, entry));
292 if (!tree->root || !entry) {
293 silc_set_errno_nofail(SILC_ERR_INVALID_ARGUMENT);
297 /* Unless the incoming entry is already the one to be deleted find it
298 from the tree first. */
299 q = h = SILC_TREE_GET_HEADER(tree, entry);
300 if (!h->parent && !h->left && !h->right && !h->t) {
301 entry = silc_avl_tree_find(tree, entry, NULL, NULL);
304 q = h = SILC_TREE_GET_HEADER(tree, entry);
307 /* If entry has duplicates, replace this with one of them */
309 h->dup->duplicate = FALSE;
310 h->dup->parent = h->parent;
311 h->dup->left = h->left;
312 h->dup->right = h->right;
317 if (h->parent->left == h)
318 h->parent->left = h->dup;
320 h->parent->right = h->dup;
327 h->left->parent = h->dup;
329 h->right->parent = h->dup;
331 /* Cleanup the deleted entry */
332 SILC_TREE_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h)));
333 h->parent = h->left = h->right = h->dup = NULL;
340 /* If the entry is not a leaf, swap with the smallest from right side */
341 if (h->left && h->right) {
342 for (q = out = h->right; out->left; q = out = out->left) ;
347 /* Update node's parent with the replaced node */
349 if (out->parent->left == h)
350 out->parent->left = out;
352 out->parent->right = out;
357 /* Update parents and leafs */
360 if (out->left == out)
362 else if (out->right == out)
364 out->left->parent = out;
365 out->right->parent = out;
369 out = h->left ? h->left : h->right;
371 out->parent = parent;
373 /* Cleanup the deleted entry */
374 SILC_TREE_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h)));
375 h->parent = h->left = h->right = h->dup = NULL;
385 left = parent->left == q;
394 if (++parent->t == 0) {
398 if (parent->t == 2) {
399 SILC_ASSERT(parent->right);
400 if (parent->right->t < 0) {
401 silc_avl_tree_rot_right(tree, parent->right);
402 silc_avl_tree_rot_left(tree, parent);
404 SILC_ASSERT(parent->right->right);
405 if (silc_avl_tree_rot_left(tree, parent) == 0)
412 if (--parent->t == 0) {
416 if (parent->t == (-2)) {
417 SILC_ASSERT(parent->left);
418 if (parent->left->t > 0) {
419 silc_avl_tree_rot_left(tree, parent->left);
420 silc_avl_tree_rot_right(tree, parent);
422 SILC_ASSERT(parent->left->left);
423 if (silc_avl_tree_rot_right(tree, parent) == 0)
431 /* Only get here on double rotations or single rotations that changed
432 subtree height - in either event, `parent->parent' is positioned
433 where `parent' was positioned before any rotations. */
436 if ((parent = h->parent) == NULL)
438 left = parent->left == h;
445 /* AVL tree operations */
446 const struct SilcTreeOpsStruct silc_tree_avl_ops =