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 /************************ Static utility functions **************************/
  49
  50 /* Rotate left
  51
  52       /             /
  53      B             D
  54     / \           / \
  55    A   D   ==>   B   E
  56       / \       / \
  57      C   E     A   C
  58 */
  59
  60 static int silc_avl_tree_rot_left(SilcTree *tree, SilcTreeHeader *h)
  61 {
  62   SilcTreeHeader *right, *parent;
  63   int hc;
  64
  65   SILC_ASSERT(h);
  66   SILC_ASSERT(h->right);
  67
  68   right = h->right;
  69   h->right = right->left;
  70   if (right->left)
  71     right->left->parent = h;
  72
  73   parent = h->parent;
  74   right->parent = parent;
  75
  76   if (parent) {
  77     if (parent->left == h)
  78       parent->left = right;
  79     else
  80       parent->right = right;
  81   } else {
  82     tree->root = right;
  83   }
  84
  85   right->left = h;
  86   h->parent = right;
  87
  88   hc = right->t != 0;
  89   h->t -= 1 + SILC_MAX(right->t, 0);
  90   right->t -= 1 - SILC_MIN(h->t, 0);
  91
  92   return hc;
  93 }
  94
  95 /* Rotate right
  96
  97         /           /
  98        D           B
  99       / \         / \
 100      B   E  ==>  A   D
 101     / \             / \
 102    A   C           C   E
 103 */
 104
 105 static int silc_avl_tree_rot_right(SilcTree *tree, SilcTreeHeader *h)
 106 {
 107   SilcTreeHeader *left, *parent;
 108   int hc;
 109
 110   SILC_ASSERT(h);
 111   SILC_ASSERT(h->left);
 112
 113   left = h->left;
 114   h->left = left->right;
 115   if (left->right)
 116     left->right->parent = h;
 117
 118   parent = h->parent;
 119   left->parent = parent;
 120
 121   if (parent) {
 122     if (parent->left == h)
 123       parent->left = left;
 124     else
 125       parent->right = left;
 126   } else {
 127     tree->root = left;
 128   }
 129
 130   left->right = h;
 131   h->parent = left;
 132
 133   hc = left->t != 0;
 134   h->t += 1 - SILC_MIN(left->t, 0);
 135   left->t += 1 + SILC_MAX(h->t, 0);
 136
 137   return hc;
 138 }
 139
 140 /****************************** Public API **********************************/
 141
 142 /* Find entry */
 143
 144 void *silc_avl_tree_find(SilcTree *tree, void *entry,
 145                          SilcTreeCompare compare, void *context)
 146 {
 147   SilcTreeHeader *h;
 148   SilcTreeCompare cmp = compare ? compare : tree->compare;
 149   void *cmp_context = compare ? context : tree->context;
 150   int ret;
 151
 152   SILC_LOG_DEBUG(("AVL tree %p, find %p", tree, entry));
 153
 154   h = tree->root;
 155   while (h) {
 156     ret = cmp(entry, SILC_TREE_GET_ENTRY(tree, h), cmp_context);
 157     if (!ret) {
 158       SILC_LOG_DEBUG(("Found %p", SILC_TREE_GET_ENTRY(tree, h)));
 159       return SILC_TREE_GET_ENTRY(tree, h);
 160     }
 161     h = ret > 0 ? h->right : h->left;
 162   }
 163
 164   SILC_LOG_DEBUG(("Not found"));
 165   silc_set_errno(SILC_ERR_NOT_FOUND);
 166   return NULL;
 167 }
 168
 169 /* Insert entry to tree */
 170
 171 SilcBool silc_avl_tree_add(SilcTree *tree, void *entry)
 172 {
 173   SilcTreeHeader *h, *parent = NULL, *q = NULL;
 174   int ret = 0;
 175
 176   SILC_LOG_DEBUG(("AVL tree %p, adding %p", tree, entry));
 177
 178   /* If tree is empty, add to root */
 179   if (!tree->root) {
 180     h = SILC_TREE_GET_HEADER(tree, entry);
 181     h->parent = h->left = h->right = h->dup = NULL;
 182     h->t = 0;
 183     tree->root = h;
 184
 185     SILC_LOG_DEBUG(("Entry %p added as root", entry));
 186
 187     SILC_ASSERT(!tree->count);
 188     tree->count = 1;
 189     return TRUE;
 190   }
 191
 192   /* Find the spot to add the new entry */
 193   h = tree->root;
 194   while (h) {
 195     /* Same entry context must not be in tree */
 196     if (entry == SILC_TREE_GET_ENTRY(tree, h)) {
 197       silc_set_errno(SILC_ERR_ALREADY_EXISTS);
 198       return FALSE;
 199     }
 200
 201     ret = tree->compare(entry, SILC_TREE_GET_ENTRY(tree, h), tree->context);
 202     if (!tree->duplicates && ret == 0) {
 203       silc_set_errno(SILC_ERR_ALREADY_EXISTS);
 204       return FALSE;
 205     }
 206
 207     /* Duplicate entry, add to list */
 208     if (ret == 0) {
 209       q = SILC_TREE_GET_HEADER(tree, entry);
 210       q->duplicate = TRUE;
 211       q->parent = h;
 212       if (h->dup)
 213         h->dup->parent = q;
 214       q->dup = h->dup;
 215       h->dup = q;
 216       SILC_LOG_DEBUG(("Entry %p is duplicate to %p", entry,
 217                       SILC_TREE_GET_ENTRY(tree, h)));
 218       tree->count++;
 219       return TRUE;
 220     }
 221
 222     parent = h;
 223     if (parent->t)
 224       q = parent;
 225     h = ret > 0 ? h->right : h->left;
 226   }
 227
 228   /* Update parent */
 229   h = SILC_TREE_GET_HEADER(tree, entry);
 230   if (ret < 0)
 231     parent->left = h;
 232   else
 233     parent->right = h;
 234
 235   SILC_LOG_DEBUG(("Entry %p added, parent %p", entry,
 236                   SILC_TREE_GET_ENTRY(tree, parent)));
 237
 238   /* Update the new entry */
 239   h->parent = parent;
 240   h->left = h->right = h->dup = NULL;
 241   h->t = 0;
 242
 243   /* Balance */
 244   while (parent != q) {
 245     parent->t = (parent->right == h) * 2 - 1;
 246     h = parent;
 247     parent = h->parent;
 248   }
 249
 250   if (q) {
 251     if (q->left == h) {
 252       if (--q->t == (-2)) {
 253         if (q->left->t > 0)
 254           silc_avl_tree_rot_left(tree, q->left);
 255         silc_avl_tree_rot_right(tree, q);
 256       }
 257     } else {
 258       if (++q->t == 2) {
 259         if (q->right->t < 0)
 260           silc_avl_tree_rot_right(tree, q->right);
 261         silc_avl_tree_rot_left(tree, q);
 262       }
 263     }
 264   }
 265
 266   tree->count++;
 267   return TRUE;
 268 }
 269
 270 /* Delete entry from tree */
 271
 272 SilcBool silc_avl_tree_del(SilcTree *tree, void *entry)
 273 {
 274   SilcTreeHeader *h, *q, *out, *parent = NULL, tmp;
 275   int left;
 276
 277   SILC_LOG_DEBUG(("AVL tree %p, delete %p", tree, entry));
 278
 279   if (!tree->root || !entry) {
 280     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
 281     return FALSE;
 282   }
 283
 284   /* Unless the incoming entry is already the one to be deleted find it
 285      from the tree first. */
 286   q = h = SILC_TREE_GET_HEADER(tree, entry);
 287   if (!h->parent && !h->left && !h->right && !h->t) {
 288     entry = silc_avl_tree_find(tree, entry, NULL, NULL);
 289     if (!entry)
 290       return FALSE;
 291     q = h = SILC_TREE_GET_HEADER(tree, entry);
 292   }
 293
 294   /* If entry has duplicates, replace this with one of them */
 295   if (h->dup) {
 296     h->dup->duplicate = FALSE;
 297     h->dup->parent = h->parent;
 298     h->dup->left = h->left;
 299     h->dup->right = h->right;
 300     h->dup->t = h->t;
 301
 302     /* Update parent */
 303     if (h->parent) {
 304       if (h->parent->left == h)
 305         h->parent->left = h->dup;
 306       else
 307         h->parent->right = h->dup;
 308     } else {
 309       tree->root = h->dup;
 310     }
 311
 312     /* Update leafs */
 313     if (h->left)
 314       h->left->parent = h->dup;
 315     if (h->right)
 316       h->right->parent = h->dup;
 317
 318     /* Cleanup the deleted entry */
 319     SILC_LOG_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h)));
 320     h->parent = h->left = h->right = h->dup = NULL;
 321     h->t = 0;
 322
 323     tree->count--;
 324     return TRUE;
 325   }
 326
 327   /* If the entry is not a leaf, swap with the smallest from right side */
 328   if (h->left && h->right) {
 329     for (q = out = h->right; out->left; q = out = out->left) ;
 330     tmp = *h;
 331     *h = *out;
 332     *out = tmp;
 333
 334     /* Update node's parent with the replaced node */
 335     if (out->parent) {
 336       if (out->parent->left == h)
 337         out->parent->left = out;
 338       else
 339         out->parent->right = out;
 340     } else {
 341       tree->root = out;
 342     }
 343
 344     /* Update parents and leafs */
 345     if (h->parent == h)
 346       h->parent = out;
 347     if (out->left == out)
 348       out->left = h;
 349     else if (out->right == out)
 350       out->right = h;
 351     out->left->parent = out;
 352     out->right->parent = out;
 353   }
 354
 355   parent = h->parent;
 356   out = h->left ? h->left : h->right;
 357   if (out)
 358     out->parent = parent;
 359
 360   /* Cleanup the deleted entry */
 361   SILC_LOG_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h)));
 362   h->parent = h->left = h->right = h->dup = NULL;
 363   h->t = 0;
 364
 365   if (!parent) {
 366     tree->root = out;
 367     tree->count--;
 368     return TRUE;
 369   }
 370
 371   /* Update parent */
 372   left = parent->left == q;
 373   if (left)
 374     parent->left = out;
 375   else
 376     parent->right = out;
 377
 378   /* Balance */
 379   for (;;) {
 380     if (left) {
 381       if (++parent->t == 0) {
 382         h = parent;
 383         goto higher;
 384       }
 385       if (parent->t == 2) {
 386         SILC_ASSERT(parent->right);
 387         if (parent->right->t < 0) {
 388           silc_avl_tree_rot_right(tree, parent->right);
 389           silc_avl_tree_rot_left(tree, parent);
 390         } else {
 391           SILC_ASSERT(parent->right->right);
 392           if (silc_avl_tree_rot_left(tree, parent) == 0)
 393             break;
 394         }
 395       } else {
 396         break;
 397       }
 398     } else {
 399       if (--parent->t == 0) {
 400         h = parent;
 401         goto higher;
 402       }
 403       if (parent->t == (-2)) {
 404         SILC_ASSERT(parent->left);
 405         if (parent->left->t > 0) {
 406           silc_avl_tree_rot_left(tree, parent->left);
 407           silc_avl_tree_rot_right(tree, parent);
 408         } else {
 409           SILC_ASSERT(parent->left->left);
 410           if (silc_avl_tree_rot_right(tree, parent) == 0)
 411             break;
 412         }
 413       } else {
 414         break;
 415       }
 416     }
 417
 418     /* Only get here on double rotations or single rotations that changed
 419        subtree height - in either event, `parent->parent' is positioned
 420        where `parent' was positioned before any rotations. */
 421     h = parent->parent;
 422   higher:
 423     if ((parent = h->parent) == NULL)
 424       break;
 425     left = parent->left == h;
 426   }
 427
 428   tree->count--;
 429   return TRUE;
 430 }
 431
 432 /* AVL tree operations */
 433 const struct SilcTreeOpsStruct silc_tree_avl_ops =
 434 {
 435   silc_avl_tree_add,
 436   silc_avl_tree_del,
 437   silc_avl_tree_find,
 438 };