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