lib/silcutil/silcavltree.c

   1 /*
   2
   3   silcavltree.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2008 Pekka Riikonen
   8
   9   Redistribution and use in source and binary forms, with or without
  10   modification, are permitted provided that the following conditions are
  11   met:
  12
  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
  20       permission.
  21
  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.
  32
  33 */
  34
  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.
  38
  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
  44    a simple list. */
  45
  46 #include <silcruntime.h>
  47
  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 */
  52
  53 #if SILC_ALV_TREE_DEBUG == 1
  54 #define SILC_TREE_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
  55 #else
  56 #define SILC_TREE_DEBUG(fmt)
  57 #endif
  58
  59 /************************ Static utility functions **************************/
  60
  61 /* Rotate left
  62
  63       /             /
  64      B             D
  65     / \           / \
  66    A   D   ==>   B   E
  67       / \       / \
  68      C   E     A   C
  69 */
  70
  71 static int silc_avl_tree_rot_left(SilcTree *tree, SilcTreeHeader *h)
  72 {
  73   SilcTreeHeader *right, *parent;
  74   int hc;
  75
  76   SILC_ASSERT(h);
  77   SILC_ASSERT(h->right);
  78
  79   right = h->right;
  80   h->right = right->left;
  81   if (right->left)
  82     right->left->parent = h;
  83
  84   parent = h->parent;
  85   right->parent = parent;
  86
  87   if (parent) {
  88     if (parent->left == h)
  89       parent->left = right;
  90     else
  91       parent->right = right;
  92   } else {
  93     tree->root = right;
  94   }
  95
  96   right->left = h;
  97   h->parent = right;
  98
  99   hc = right->t != 0;
 100   h->t -= 1 + SILC_MAX(right->t, 0);
 101   right->t -= 1 - SILC_MIN(h->t, 0);
 102
 103   return hc;
 104 }
 105
 106 /* Rotate right
 107
 108         /           /
 109        D           B
 110       / \         / \
 111      B   E  ==>  A   D
 112     / \             / \
 113    A   C           C   E
 114 */
 115
 116 static int silc_avl_tree_rot_right(SilcTree *tree, SilcTreeHeader *h)
 117 {
 118   SilcTreeHeader *left, *parent;
 119   int hc;
 120
 121   SILC_ASSERT(h);
 122   SILC_ASSERT(h->left);
 123
 124   left = h->left;
 125   h->left = left->right;
 126   if (left->right)
 127     left->right->parent = h;
 128
 129   parent = h->parent;
 130   left->parent = parent;
 131
 132   if (parent) {
 133     if (parent->left == h)
 134       parent->left = left;
 135     else
 136       parent->right = left;
 137   } else {
 138     tree->root = left;
 139   }
 140
 141   left->right = h;
 142   h->parent = left;
 143
 144   hc = left->t != 0;
 145   h->t += 1 - SILC_MIN(left->t, 0);
 146   left->t += 1 + SILC_MAX(h->t, 0);
 147
 148   return hc;
 149 }
 150
 151 /****************************** Public API **********************************/
 152
 153 /* Find entry */
 154
 155 void *silc_avl_tree_find(SilcTree *tree, void *entry,
 156                          SilcCompare compare, void *context)
 157 {
 158   SilcTreeHeader *h;
 159   SilcCompare cmp = compare ? compare : tree->compare;
 160   void *cmp_context = compare ? context : tree->context;
 161   int ret;
 162
 163   SILC_TREE_DEBUG(("AVL tree %p, find %p", tree, entry));
 164
 165   h = tree->root;
 166   while (h) {
 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);
 171     }
 172     if (ret == SILC_COMPARE_STOP)
 173       return NULL;
 174     h = ret > 0 ? h->right : h->left;
 175   }
 176
 177   SILC_TREE_DEBUG(("Not found"));
 178   silc_set_errno_nofail(SILC_ERR_NOT_FOUND);
 179   return NULL;
 180 }
 181
 182 /* Insert entry to tree */
 183
 184 SilcBool silc_avl_tree_add(SilcTree *tree, void *entry)
 185 {
 186   SilcTreeHeader *h, *parent = NULL, *q = NULL;
 187   int ret = 0;
 188
 189   SILC_TREE_DEBUG(("AVL tree %p, adding %p", tree, entry));
 190
 191   /* If tree is empty, add to root */
 192   if (!tree->root) {
 193     h = SILC_TREE_GET_HEADER(tree, entry);
 194     h->parent = h->left = h->right = h->dup = NULL;
 195     h->t = 0;
 196     tree->root = h;
 197
 198     SILC_TREE_DEBUG(("Entry %p added as root", entry));
 199
 200     SILC_ASSERT(!tree->count);
 201     tree->count = 1;
 202     return TRUE;
 203   }
 204
 205   /* Find the spot to add the new entry */
 206   h = tree->root;
 207   while (h) {
 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);
 211       return FALSE;
 212     }
 213
 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);
 217       return FALSE;
 218     }
 219
 220     /* Duplicate entry, add to list */
 221     if (ret == SILC_COMPARE_EQUAL_TO) {
 222       q = SILC_TREE_GET_HEADER(tree, entry);
 223       q->duplicate = TRUE;
 224       q->parent = h;
 225       if (h->dup)
 226         h->dup->parent = q;
 227       q->dup = h->dup;
 228       h->dup = q;
 229       SILC_TREE_DEBUG(("Entry %p is duplicate to %p", entry,
 230                       SILC_TREE_GET_ENTRY(tree, h)));
 231       tree->count++;
 232       return TRUE;
 233     }
 234
 235     parent = h;
 236     if (parent->t)
 237       q = parent;
 238     h = ret > 0 ? h->right : h->left;
 239   }
 240
 241   /* Update parent */
 242   h = SILC_TREE_GET_HEADER(tree, entry);
 243   if (ret < 0)
 244     parent->left = h;
 245   else
 246     parent->right = h;
 247
 248   SILC_TREE_DEBUG(("Entry %p added, parent %p", entry,
 249                    SILC_TREE_GET_ENTRY(tree, parent)));
 250
 251   /* Update the new entry */
 252   h->parent = parent;
 253   h->left = h->right = h->dup = NULL;
 254   h->t = 0;
 255
 256   /* Balance */
 257   while (parent != q) {
 258     parent->t = (parent->right == h) * 2 - 1;
 259     h = parent;
 260     parent = h->parent;
 261   }
 262
 263   if (q) {
 264     if (q->left == h) {
 265       if (--q->t == (-2)) {
 266         if (q->left->t > 0)
 267           silc_avl_tree_rot_left(tree, q->left);
 268         silc_avl_tree_rot_right(tree, q);
 269       }
 270     } else {
 271       if (++q->t == 2) {
 272         if (q->right->t < 0)
 273           silc_avl_tree_rot_right(tree, q->right);
 274         silc_avl_tree_rot_left(tree, q);
 275       }
 276     }
 277   }
 278
 279   tree->count++;
 280   return TRUE;
 281 }
 282
 283 /* Delete entry from tree */
 284
 285 SilcBool silc_avl_tree_del(SilcTree *tree, void *entry)
 286 {
 287   SilcTreeHeader *h, *q, *out, *parent = NULL, tmp;
 288   int left;
 289
 290   SILC_TREE_DEBUG(("AVL tree %p, delete %p", tree, entry));
 291
 292   if (!tree->root || !entry) {
 293     silc_set_errno_nofail(SILC_ERR_INVALID_ARGUMENT);
 294     return FALSE;
 295   }
 296
 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);
 302     if (!entry)
 303       return FALSE;
 304     q = h = SILC_TREE_GET_HEADER(tree, entry);
 305   }
 306
 307   /* If entry has duplicates, replace this with one of them */
 308   if (h->dup) {
 309     h->dup->duplicate = FALSE;
 310     h->dup->parent = h->parent;
 311     h->dup->left = h->left;
 312     h->dup->right = h->right;
 313     h->dup->t = h->t;
 314
 315     /* Update parent */
 316     if (h->parent) {
 317       if (h->parent->left == h)
 318         h->parent->left = h->dup;
 319       else
 320         h->parent->right = h->dup;
 321     } else {
 322       tree->root = h->dup;
 323     }
 324
 325     /* Update leafs */
 326     if (h->left)
 327       h->left->parent = h->dup;
 328     if (h->right)
 329       h->right->parent = h->dup;
 330
 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;
 334     h->t = 0;
 335
 336     tree->count--;
 337     return TRUE;
 338   }
 339
 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) ;
 343     tmp = *h;
 344     *h = *out;
 345     *out = tmp;
 346
 347     /* Update node's parent with the replaced node */
 348     if (out->parent) {
 349       if (out->parent->left == h)
 350         out->parent->left = out;
 351       else
 352         out->parent->right = out;
 353     } else {
 354       tree->root = out;
 355     }
 356
 357     /* Update parents and leafs */
 358     if (h->parent == h)
 359       h->parent = out;
 360     if (out->left == out)
 361       out->left = h;
 362     else if (out->right == out)
 363       out->right = h;
 364     out->left->parent = out;
 365     out->right->parent = out;
 366   }
 367
 368   parent = h->parent;
 369   out = h->left ? h->left : h->right;
 370   if (out)
 371     out->parent = parent;
 372
 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;
 376   h->t = 0;
 377
 378   if (!parent) {
 379     tree->root = out;
 380     tree->count--;
 381     return TRUE;
 382   }
 383
 384   /* Update parent */
 385   left = parent->left == q;
 386   if (left)
 387     parent->left = out;
 388   else
 389     parent->right = out;
 390
 391   /* Balance */
 392   for (;;) {
 393     if (left) {
 394       if (++parent->t == 0) {
 395         h = parent;
 396         goto higher;
 397       }
 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);
 403         } else {
 404           SILC_ASSERT(parent->right->right);
 405           if (silc_avl_tree_rot_left(tree, parent) == 0)
 406             break;
 407         }
 408       } else {
 409         break;
 410       }
 411     } else {
 412       if (--parent->t == 0) {
 413         h = parent;
 414         goto higher;
 415       }
 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);
 421         } else {
 422           SILC_ASSERT(parent->left->left);
 423           if (silc_avl_tree_rot_right(tree, parent) == 0)
 424             break;
 425         }
 426       } else {
 427         break;
 428       }
 429     }
 430
 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. */
 434     h = parent->parent;
 435   higher:
 436     if ((parent = h->parent) == NULL)
 437       break;
 438     left = parent->left == h;
 439   }
 440
 441   tree->count--;
 442   return TRUE;
 443 }
 444
 445 /* AVL tree operations */
 446 const struct SilcTreeOpsStruct silc_tree_avl_ops =
 447 {
 448   silc_avl_tree_add,
 449   silc_avl_tree_del,
 450   silc_avl_tree_find,
 451 };