src/utils/avltree.c

   1 /*
   2  * SysDB - src/utils/avltree.c
   3  * Copyright (C) 2014 Sebastian 'tokkee' Harl <sh@tokkee.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  16  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  17  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  18  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
  19  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  20  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #if HAVE_CONFIG_H
  29 #       include "config.h"
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #include "sysdb.h"
  33 #include "utils/avltree.h"
  34 #include "utils/error.h"
  35
  36 #include <assert.h>
  37
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include <strings.h>
  41 #include <pthread.h>
  42
  43 /*
  44  * private data types
  45  */
  46
  47 struct node;
  48 typedef struct node node_t;
  49
  50 struct node {
  51         sdb_object_t *obj;
  52
  53         node_t *parent;
  54         node_t *left;
  55         node_t *right;
  56
  57         size_t height;
  58 };
  59
  60 #define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
  61 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
  62 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
  63                         NODE_HEIGHT((n)->left)) + 1)
  64
  65 #define BALANCE(n) \
  66         ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
  67
  68 struct sdb_avltree {
  69         pthread_rwlock_t lock;
  70
  71         node_t *root;
  72         size_t size;
  73 };
  74
  75 struct sdb_avltree_iter {
  76         sdb_avltree_t *tree;
  77         node_t *node;
  78 };
  79
  80 /*
  81  * private helper functions
  82  */
  83
  84 static void
  85 node_destroy(node_t *n)
  86 {
  87         sdb_object_deref(n->obj);
  88         n->obj = NULL;
  89         n->parent = n->left = n->right = NULL;
  90         free(n);
  91 } /* node_destroy */
  92
  93 static node_t *
  94 node_create(sdb_object_t *obj)
  95 {
  96         node_t *n = malloc(sizeof(*n));
  97         if (! n)
  98                 return NULL;
  99
 100         sdb_object_ref(obj);
 101         n->obj = obj;
 102         n->parent = n->left = n->right = NULL;
 103         n->height = 1;
 104         return n;
 105 } /* node_create */
 106
 107 static node_t *
 108 node_next(node_t *n)
 109 {
 110         node_t *next;
 111
 112         if (! n)
 113                 return NULL;
 114
 115         /* descend into the right tree */
 116         if (n->right) {
 117                 next = n->right;
 118                 while (next->left)
 119                         next = next->left;
 120                 return next;
 121         }
 122
 123         /* visit the parent if we're in its left tree */
 124         if (n->parent && (n->parent->left == n))
 125                 return n->parent;
 126
 127         /* find the parent of the sibling sub-tree on the right */
 128         next = n->parent;
 129         next = NULL;
 130         while (n->parent && (n->parent->right == n)) {
 131                 n = n->parent;
 132                 next = n;
 133         }
 134         if (next)
 135                 next = next->parent;
 136         return next;
 137 } /* node_next */
 138
 139 static node_t *
 140 node_smallest(sdb_avltree_t *tree)
 141 {
 142         node_t *n;
 143
 144         if (! tree)
 145                 return NULL;
 146
 147         n = tree->root;
 148         while (n && n->left)
 149                 n = n->left;
 150         return n;
 151 } /* node_smallest */
 152
 153 static void
 154 tree_clear(sdb_avltree_t *tree)
 155 {
 156         node_t *n;
 157
 158         if ((! tree) || (! tree->root))
 159                 return;
 160
 161         /* do a depth-first iteration and delete the leafs */
 162         n = tree->root;
 163         while (n) {
 164                 node_t *tmp;
 165
 166                 if (n->left) {
 167                         n = n->left;
 168                         continue;
 169                 }
 170                 else if (n->right) {
 171                         n = n->right;
 172                         continue;
 173                 }
 174
 175                 tmp = n->parent;
 176                 if (tmp) {
 177                         if (tmp->left == n)
 178                                 tmp->left = NULL;
 179                         else
 180                                 tmp->right = NULL;
 181                 }
 182
 183                 node_destroy(n);
 184                 n = tmp;
 185         }
 186
 187         tree->root = NULL;
 188         tree->size = 0;
 189 } /* tree_clear */
 190
 191 /* Switch node 'n' with its right child, making 'n'
 192  * the new left child of that node. */
 193 static void
 194 rotate_left(sdb_avltree_t *tree, node_t *n)
 195 {
 196         node_t *n2 = n->right;
 197         node_t *c = n2->left;
 198
 199         n2->parent = n->parent;
 200         if (! n2->parent)
 201                 tree->root = n2;
 202         else if (n2->parent->left == n)
 203                 n2->parent->left = n2;
 204         else
 205                 n2->parent->right = n2;
 206
 207         n2->left = n;
 208         n->parent = n2;
 209
 210         n->right = c;
 211         if (c)
 212                 c->parent = n;
 213
 214         n->height = CALC_HEIGHT(n);
 215         n2->height = CALC_HEIGHT(n2);
 216 } /* rotate_left */
 217
 218 /* Switch node 'n' with its left child, making 'n'
 219  * the new right child of that node. */
 220 static void
 221 rotate_right(sdb_avltree_t *tree, node_t *n)
 222 {
 223         node_t *n2 = n->left;
 224         node_t *c = n2->right;
 225
 226         n2->parent = n->parent;
 227         if (! n2->parent)
 228                 tree->root = n2;
 229         else if (n2->parent->left == n)
 230                 n2->parent->left = n2;
 231         else
 232                 n2->parent->right = n2;
 233
 234         n2->right = n;
 235         n->parent = n2;
 236
 237         n->left = c;
 238         if (c)
 239                 c->parent = n;
 240
 241         n->height = CALC_HEIGHT(n);
 242         n2->height = CALC_HEIGHT(n2);
 243 } /* rotate_right */
 244
 245 /* Rebalance a tree starting at node 'n' towards the root;
 246  * also, update the node heights all the way up to the root. */
 247 static void
 248 rebalance(sdb_avltree_t *tree, node_t *n)
 249 {
 250         for ( ; n; n = n->parent) {
 251                 int bf = BALANCE(n);
 252
 253                 if (bf == 0)
 254                         return;
 255
 256                 if ((-1 <= bf) && (bf <= 1)) {
 257                         n->height = CALC_HEIGHT(n);
 258                         continue;
 259                 }
 260
 261                 assert((-2 <= bf) && (bf <= 2));
 262
 263                 if (bf == 2) {
 264                         if (BALANCE(n->left) == -1)
 265                                 rotate_left(tree, n->left);
 266                         rotate_right(tree, n);
 267                 }
 268                 else {
 269                         if (BALANCE(n->right) == 1)
 270                                 rotate_right(tree, n->right);
 271                         rotate_left(tree, n);
 272                 }
 273
 274                 /* n was moved downwards; get back to the previous level */
 275                 n = n->parent;
 276         }
 277 } /* rebalance */
 278
 279 /*
 280  * public API
 281  */
 282
 283 sdb_avltree_t *
 284 sdb_avltree_create(void)
 285 {
 286         sdb_avltree_t *tree;
 287
 288         tree = malloc(sizeof(*tree));
 289         if (! tree)
 290                 return NULL;
 291
 292         pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
 293
 294         tree->root = NULL;
 295         tree->size = 0;
 296         return tree;
 297 } /* sdb_avltree_create */
 298
 299 void
 300 sdb_avltree_destroy(sdb_avltree_t *tree)
 301 {
 302         if (! tree)
 303                 return;
 304
 305         pthread_rwlock_wrlock(&tree->lock);
 306         tree_clear(tree);
 307         pthread_rwlock_unlock(&tree->lock);
 308         pthread_rwlock_destroy(&tree->lock);
 309         free(tree);
 310 } /* sdb_avltree_destroy */
 311
 312 void
 313 sdb_avltree_clear(sdb_avltree_t *tree)
 314 {
 315         if (! tree)
 316                 return;
 317
 318         pthread_rwlock_wrlock(&tree->lock);
 319         tree_clear(tree);
 320         pthread_rwlock_unlock(&tree->lock);
 321 } /* sdb_avltree_clear */
 322
 323 int
 324 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 325 {
 326         node_t *parent;
 327         node_t *n;
 328
 329         int diff = -1;
 330
 331         if (! tree)
 332                 return -1;
 333
 334         n = node_create(obj);
 335         if (! n)
 336                 return -1;
 337
 338         pthread_rwlock_wrlock(&tree->lock);
 339
 340         if (! tree->root) {
 341                 tree->root = n;
 342                 tree->size = 1;
 343                 pthread_rwlock_unlock(&tree->lock);
 344                 return 0;
 345         }
 346
 347         parent = tree->root;
 348         while (42) {
 349                 assert(parent);
 350
 351                 diff = strcasecmp(obj->name, parent->obj->name);
 352                 if (! diff) {
 353                         node_destroy(n);
 354                         pthread_rwlock_unlock(&tree->lock);
 355                         return -1;
 356                 }
 357
 358                 if (diff < 0) {
 359                         if (! parent->left) {
 360                                 parent->left = n;
 361                                 break;
 362                         }
 363                         parent = parent->left;
 364                 }
 365                 else {
 366                         if (! parent->right) {
 367                                 parent->right = n;
 368                                 break;
 369                         }
 370                         parent = parent->right;
 371                 }
 372         }
 373
 374         n->parent = parent;
 375         ++tree->size;
 376
 377         rebalance(tree, parent);
 378         pthread_rwlock_unlock(&tree->lock);
 379         return 0;
 380 } /* sdb_avltree_insert */
 381
 382 sdb_object_t *
 383 sdb_avltree_lookup(sdb_avltree_t *tree, const char *name)
 384 {
 385         node_t *n;
 386
 387         if (! tree)
 388                 return NULL;
 389
 390         n = tree->root;
 391         while (n) {
 392                 int diff = strcasecmp(n->obj->name, name);
 393
 394                 if (! diff) {
 395                         sdb_object_ref(n->obj);
 396                         return n->obj;
 397                 }
 398
 399                 if (diff < 0)
 400                         n = n->right;
 401                 else
 402                         n = n->left;
 403         }
 404         return NULL;
 405 } /* sdb_avltree_lookup_by_name */
 406
 407 sdb_avltree_iter_t *
 408 sdb_avltree_get_iter(sdb_avltree_t *tree)
 409 {
 410         sdb_avltree_iter_t *iter;
 411
 412         if (! tree)
 413                 return NULL;
 414
 415         iter = malloc(sizeof(*iter));
 416         if (! iter)
 417                 return NULL;
 418
 419         pthread_rwlock_rdlock(&tree->lock);
 420
 421         iter->tree = tree;
 422         iter->node = node_smallest(tree);
 423
 424         pthread_rwlock_unlock(&tree->lock);
 425         return iter;
 426 } /* sdb_avltree_get_iter */
 427
 428 void
 429 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
 430 {
 431         if (! iter)
 432                 return;
 433
 434         iter->tree = NULL;
 435         iter->node = NULL;
 436         free(iter);
 437 } /* sdb_avltree_iter_destroy */
 438
 439 bool
 440 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
 441 {
 442         if (! iter)
 443                 return 0;
 444
 445         return iter->node != NULL;
 446 } /* sdb_avltree_iter_has_next */
 447
 448 sdb_object_t *
 449 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
 450 {
 451         node_t *n;
 452
 453         if (! iter)
 454                 return NULL;
 455
 456         n = iter->node;
 457         iter->node = node_next(iter->node);
 458         return n ? n->obj : NULL;
 459 } /* sdb_avltree_iter_get_next */
 460
 461 sdb_object_t *
 462 sdb_avltree_iter_peek_next(sdb_avltree_iter_t *iter)
 463 {
 464         if ((! iter) || (! iter->node))
 465                 return NULL;
 466         return iter->node->obj;
 467 } /* sdb_avltree_iter_peek_next */
 468
 469 size_t
 470 sdb_avltree_size(sdb_avltree_t *tree)
 471 {
 472         return tree ? tree->size : 0;
 473 } /* sdb_avltree_size */
 474
 475 bool
 476 sdb_avltree_valid(sdb_avltree_t *tree)
 477 {
 478         node_t *n;
 479
 480         bool status = 1;
 481         size_t size = 0;
 482
 483         if (! tree)
 484                 return 1;
 485
 486         for (n = node_smallest(tree); n; n = node_next(n)) {
 487                 int bf = BALANCE(n);
 488
 489                 if ((bf < -1) || (1 < bf)) {
 490                         sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
 491                                         NODE_NAME(n), bf);
 492                         status = 0;
 493                 }
 494
 495                 if (NODE_HEIGHT(n) != n->height) {
 496                         sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
 497                                         "%zu; expected: %zu", NODE_NAME(n), n->height,
 498                                         NODE_HEIGHT(n));
 499                         status = 0;
 500                 }
 501
 502                 if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
 503                         sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
 504                                         "node '%s': {left: %s, right: %s}; expected: %s",
 505                                         NODE_NAME(n), NODE_NAME(n->parent->left),
 506                                         NODE_NAME(n->parent->right), NODE_NAME(n));
 507                         status = 0;
 508                 }
 509                 if ((! n->parent) && (n != tree->root)) {
 510                         sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
 511                                         "have a parent", NODE_NAME(n));
 512                         status = 0;
 513                 }
 514
 515                 ++size;
 516         }
 517
 518         if (size != tree->size) {
 519                 sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
 520                                 tree->size, size);
 521                 status = 0;
 522         }
 523         return status;
 524 } /* sdb_avltree_valid */
 525
 526 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 527