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                          SilcCompare compare, void *context)
 146 {
 147   SilcTreeHeader *h;
 148   SilcCompare 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 == SILC_COMPARE_EQUAL_TO) {
 158       SILC_LOG_DEBUG(("Found %p", SILC_TREE_GET_ENTRY(tree, h)));
 159       return SILC_TREE_GET_ENTRY(tree, h);
 160     }
 161     if (ret == SILC_COMPARE_STOP)
 162       return NULL;
 163     h = ret > 0 ? h->right : h->left;
 164   }
 165
 166   SILC_LOG_DEBUG(("Not found"));
 167   silc_set_errno(SILC_ERR_NOT_FOUND);
 168   return NULL;
 169 }
 170
 171 /* Insert entry to tree */
 172
 173 SilcBool silc_avl_tree_add(SilcTree *tree, void *entry)
 174 {
 175   SilcTreeHeader *h, *parent = NULL, *q = NULL;
 176   int ret = 0;
 177
 178   SILC_LOG_DEBUG(("AVL tree %p, adding %p", tree, entry));
 179
 180   /* If tree is empty, add to root */
 181   if (!tree->root) {
 182     h = SILC_TREE_GET_HEADER(tree, entry);
 183     h->parent = h->left = h->right = h->dup = NULL;
 184     h->t = 0;
 185     tree->root = h;
 186
 187     SILC_LOG_DEBUG(("Entry %p added as root", entry));
 188
 189     SILC_ASSERT(!tree->count);
 190     tree->count = 1;
 191     return TRUE;
 192   }
 193
 194   /* Find the spot to add the new entry */
 195   h = tree->root;
 196   while (h) {
 197     /* Same entry context must not be in tree */
 198     if (entry == SILC_TREE_GET_ENTRY(tree, h)) {
 199       silc_set_errno(SILC_ERR_ALREADY_EXISTS);
 200       return FALSE;
 201     }
 202
 203     ret = tree->compare(entry, SILC_TREE_GET_ENTRY(tree, h), tree->context);
 204     if (!tree->duplicates && ret == SILC_COMPARE_EQUAL_TO) {
 205       silc_set_errno(SILC_ERR_ALREADY_EXISTS);
 206       return FALSE;
 207     }
 208
 209     /* Duplicate entry, add to list */
 210     if (ret == SILC_COMPARE_EQUAL_TO) {
 211       q = SILC_TREE_GET_HEADER(tree, entry);
 212       q->duplicate = TRUE;
 213       q->parent = h;
 214       if (h->dup)
 215         h->dup->parent = q;
 216       q->dup = h->dup;
 217       h->dup = q;
 218       SILC_LOG_DEBUG(("Entry %p is duplicate to %p", entry,
 219                       SILC_TREE_GET_ENTRY(tree, h)));
 220       tree->count++;
 221       return TRUE;
 222     }
 223
 224     parent = h;
 225     if (parent->t)
 226       q = parent;
 227     h = ret > 0 ? h->right : h->left;
 228   }
 229
 230   /* Update parent */
 231   h = SILC_TREE_GET_HEADER(tree, entry);
 232   if (ret < 0)
 233     parent->left = h;
 234   else
 235     parent->right = h;
 236
 237   SILC_LOG_DEBUG(("Entry %p added, parent %p", entry,
 238                   SILC_TREE_GET_ENTRY(tree, parent)));
 239
 240   /* Update the new entry */
 241   h->parent = parent;
 242   h->left = h->right = h->dup = NULL;
 243   h->t = 0;
 244
 245   /* Balance */
 246   while (parent != q) {
 247     parent->t = (parent->right == h) * 2 - 1;
 248     h = parent;
 249     parent = h->parent;
 250   }
 251
 252   if (q) {
 253     if (q->left == h) {
 254       if (--q->t == (-2)) {
 255         if (q->left->t > 0)
 256           silc_avl_tree_rot_left(tree, q->left);
 257         silc_avl_tree_rot_right(tree, q);
 258       }
 259     } else {
 260       if (++q->t == 2) {
 261         if (q->right->t < 0)
 262           silc_avl_tree_rot_right(tree, q->right);
 263         silc_avl_tree_rot_left(tree, q);
 264       }
 265     }
 266   }
 267
 268   tree->count++;
 269   return TRUE;
 270 }
 271
 272 /* Delete entry from tree */
 273
 274 SilcBool silc_avl_tree_del(SilcTree *tree, void *entry)
 275 {
 276   SilcTreeHeader *h, *q, *out, *parent = NULL, tmp;
 277   int left;
 278
 279   SILC_LOG_DEBUG(("AVL tree %p, delete %p", tree, entry));
 280
 281   if (!tree->root || !entry) {
 282     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
 283     return FALSE;
 284   }
 285
 286   /* Unless the incoming entry is already the one to be deleted find it
 287      from the tree first. */
 288   q = h = SILC_TREE_GET_HEADER(tree, entry);
 289   if (!h->parent && !h->left && !h->right && !h->t) {
 290     entry = silc_avl_tree_find(tree, entry, NULL, NULL);
 291     if (!entry)
 292       return FALSE;
 293     q = h = SILC_TREE_GET_HEADER(tree, entry);
 294   }
 295
 296   /* If entry has duplicates, replace this with one of them */
 297   if (h->dup) {
 298     h->dup->duplicate = FALSE;
 299     h->dup->parent = h->parent;
 300     h->dup->left = h->left;
 301     h->dup->right = h->right;
 302     h->dup->t = h->t;
 303
 304     /* Update parent */
 305     if (h->parent) {
 306       if (h->parent->left == h)
 307         h->parent->left = h->dup;
 308       else
 309         h->parent->right = h->dup;
 310     } else {
 311       tree->root = h->dup;
 312     }
 313
 314     /* Update leafs */
 315     if (h->left)
 316       h->left->parent = h->dup;
 317     if (h->right)
 318       h->right->parent = h->dup;
 319
 320     /* Cleanup the deleted entry */
 321     SILC_LOG_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h)));
 322     h->parent = h->left = h->right = h->dup = NULL;
 323     h->t = 0;
 324
 325     tree->count--;
 326     return TRUE;
 327   }
 328
 329   /* If the entry is not a leaf, swap with the smallest from right side */
 330   if (h->left && h->right) {
 331     for (q = out = h->right; out->left; q = out = out->left) ;
 332     tmp = *h;
 333     *h = *out;
 334     *out = tmp;
 335
 336     /* Update node's parent with the replaced node */
 337     if (out->parent) {
 338       if (out->parent->left == h)
 339         out->parent->left = out;
 340       else
 341         out->parent->right = out;
 342     } else {
 343       tree->root = out;
 344     }
 345
 346     /* Update parents and leafs */
 347     if (h->parent == h)
 348       h->parent = out;
 349     if (out->left == out)
 350       out->left = h;
 351     else if (out->right == out)
 352       out->right = h;
 353     out->left->parent = out;
 354     out->right->parent = out;
 355   }
 356
 357   parent = h->parent;
 358   out = h->left ? h->left : h->right;
 359   if (out)
 360     out->parent = parent;
 361
 362   /* Cleanup the deleted entry */
 363   SILC_LOG_DEBUG(("Deleted %p", SILC_TREE_GET_ENTRY(tree, h)));
 364   h->parent = h->left = h->right = h->dup = NULL;
 365   h->t = 0;
 366
 367   if (!parent) {
 368     tree->root = out;
 369     tree->count--;
 370     return TRUE;
 371   }
 372
 373   /* Update parent */
 374   left = parent->left == q;
 375   if (left)
 376     parent->left = out;
 377   else
 378     parent->right = out;
 379
 380   /* Balance */
 381   for (;;) {
 382     if (left) {
 383       if (++parent->t == 0) {
 384         h = parent;
 385         goto higher;
 386       }
 387       if (parent->t == 2) {
 388         SILC_ASSERT(parent->right);
 389         if (parent->right->t < 0) {
 390           silc_avl_tree_rot_right(tree, parent->right);
 391           silc_avl_tree_rot_left(tree, parent);
 392         } else {
 393           SILC_ASSERT(parent->right->right);
 394           if (silc_avl_tree_rot_left(tree, parent) == 0)
 395             break;
 396         }
 397       } else {
 398         break;
 399       }
 400     } else {
 401       if (--parent->t == 0) {
 402         h = parent;
 403         goto higher;
 404       }
 405       if (parent->t == (-2)) {
 406         SILC_ASSERT(parent->left);
 407         if (parent->left->t > 0) {
 408           silc_avl_tree_rot_left(tree, parent->left);
 409           silc_avl_tree_rot_right(tree, parent);
 410         } else {
 411           SILC_ASSERT(parent->left->left);
 412           if (silc_avl_tree_rot_right(tree, parent) == 0)
 413             break;
 414         }
 415       } else {
 416         break;
 417       }
 418     }
 419
 420     /* Only get here on double rotations or single rotations that changed
 421        subtree height - in either event, `parent->parent' is positioned
 422        where `parent' was positioned before any rotations. */
 423     h = parent->parent;
 424   higher:
 425     if ((parent = h->parent) == NULL)
 426       break;
 427     left = parent->left == h;
 428   }
 429
 430   tree->count--;
 431   return TRUE;
 432 }
 433
 434 /* AVL tree operations */
 435 const struct SilcTreeOpsStruct silc_tree_avl_ops =
 436 {
 437   silc_avl_tree_add,
 438   silc_avl_tree_del,
 439   silc_avl_tree_find,
 440 };