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 <pthread.h>
  40
  41 /*
  42  * private data types
  43  */
  44
  45 struct node;
  46 typedef struct node node_t;
  47
  48 struct node {
  49         sdb_object_t *obj;
  50
  51         node_t *parent;
  52         node_t *left;
  53         node_t *right;
  54
  55         size_t height;
  56 };
  57
  58 #define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
  59 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
  60 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
  61                         NODE_HEIGHT((n)->left)) + 1)
  62
  63 #define BALANCE(n) \
  64         ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
  65
  66 struct sdb_avltree {
  67         pthread_rwlock_t lock;
  68
  69         sdb_object_cmp_cb cmp;
  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         n = node_smallest(tree);
 159         while (n) {
 160                 node_t *tmp = node_next(n);
 161
 162                 node_destroy(n);
 163                 n = tmp;
 164         }
 165
 166         tree->root = NULL;
 167         tree->size = 0;
 168 } /* tree_clear */
 169
 170 /* Switch node 'n' with its right child, making 'n'
 171  * the new left child of that node. */
 172 static void
 173 rotate_left(sdb_avltree_t *tree, node_t *n)
 174 {
 175         node_t *n2 = n->right;
 176         node_t *c = n2->left;
 177
 178         n2->parent = n->parent;
 179         if (! n2->parent)
 180                 tree->root = n2;
 181         else if (n2->parent->left == n)
 182                 n2->parent->left = n2;
 183         else
 184                 n2->parent->right = n2;
 185
 186         n2->left = n;
 187         n->parent = n2;
 188
 189         n->right = c;
 190         if (c)
 191                 c->parent = n;
 192
 193         n->height = CALC_HEIGHT(n);
 194         n2->height = CALC_HEIGHT(n2);
 195 } /* rotate_left */
 196
 197 /* Switch node 'n' with its left child, making 'n'
 198  * the new right child of that node. */
 199 static void
 200 rotate_right(sdb_avltree_t *tree, node_t *n)
 201 {
 202         node_t *n2 = n->left;
 203         node_t *c = n2->right;
 204
 205         n2->parent = n->parent;
 206         if (! n2->parent)
 207                 tree->root = n2;
 208         else if (n2->parent->left == n)
 209                 n2->parent->left = n2;
 210         else
 211                 n2->parent->right = n2;
 212
 213         n2->right = n;
 214         n->parent = n2;
 215
 216         n->left = c;
 217         if (c)
 218                 c->parent = n;
 219
 220         n->height = CALC_HEIGHT(n);
 221         n2->height = CALC_HEIGHT(n2);
 222 } /* rotate_right */
 223
 224 /* Rebalance a tree starting at node 'n' towards the root;
 225  * also, update the node heights all the way up to the root. */
 226 static void
 227 rebalance(sdb_avltree_t *tree, node_t *n)
 228 {
 229         for ( ; n; n = n->parent) {
 230                 int bf = BALANCE(n);
 231
 232                 if (bf == 0)
 233                         return;
 234
 235                 if ((-1 <= bf) && (bf <= 1)) {
 236                         n->height = CALC_HEIGHT(n);
 237                         continue;
 238                 }
 239
 240                 assert((-2 <= bf) && (bf <= 2));
 241
 242                 if (bf == 2) {
 243                         if (BALANCE(n->left) == -1)
 244                                 rotate_left(tree, n->left);
 245                         rotate_right(tree, n);
 246                 }
 247                 else {
 248                         if (BALANCE(n->right) == 1)
 249                                 rotate_right(tree, n->right);
 250                         rotate_left(tree, n);
 251                 }
 252
 253                 /* n was moved downwards; get back to the previous level */
 254                 n = n->parent;
 255         }
 256 } /* rebalance */
 257
 258 /*
 259  * public API
 260  */
 261
 262 sdb_avltree_t *
 263 sdb_avltree_create(sdb_object_cmp_cb cmp)
 264 {
 265         sdb_avltree_t *tree;
 266
 267         tree = malloc(sizeof(*tree));
 268         if (! tree)
 269                 return NULL;
 270
 271         if (! cmp)
 272                 cmp = sdb_object_cmp_by_name;
 273
 274         pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
 275         tree->cmp = cmp;
 276
 277         tree->root = NULL;
 278         tree->size = 0;
 279         return tree;
 280 } /* sdb_avltree_create */
 281
 282 void
 283 sdb_avltree_destroy(sdb_avltree_t *tree)
 284 {
 285         if (! tree)
 286                 return;
 287
 288         pthread_rwlock_wrlock(&tree->lock);
 289         tree_clear(tree);
 290         pthread_rwlock_unlock(&tree->lock);
 291         pthread_rwlock_destroy(&tree->lock);
 292         free(tree);
 293 } /* sdb_avltree_destroy */
 294
 295 void
 296 sdb_avltree_clear(sdb_avltree_t *tree)
 297 {
 298         if (! tree)
 299                 return;
 300
 301         pthread_rwlock_wrlock(&tree->lock);
 302         tree_clear(tree);
 303         pthread_rwlock_unlock(&tree->lock);
 304 } /* sdb_avltree_clear */
 305
 306 int
 307 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 308 {
 309         node_t *parent;
 310         node_t *n;
 311
 312         int diff = -1;
 313
 314         if (! tree)
 315                 return -1;
 316
 317         n = node_create(obj);
 318         if (! n)
 319                 return -1;
 320
 321         pthread_rwlock_wrlock(&tree->lock);
 322
 323         if (! tree->root) {
 324                 tree->root = n;
 325                 tree->size = 1;
 326                 pthread_rwlock_unlock(&tree->lock);
 327                 return 0;
 328         }
 329
 330         parent = tree->root;
 331         while (42) {
 332                 assert(parent);
 333
 334                 diff = tree->cmp(obj, parent->obj);
 335                 if (! diff) {
 336                         node_destroy(n);
 337                         pthread_rwlock_unlock(&tree->lock);
 338                         return -1;
 339                 }
 340
 341                 if (diff < 0) {
 342                         if (! parent->left) {
 343                                 parent->left = n;
 344                                 break;
 345                         }
 346                         parent = parent->left;
 347                 }
 348                 else {
 349                         if (! parent->right) {
 350                                 parent->right = n;
 351                                 break;
 352                         }
 353                         parent = parent->right;
 354                 }
 355         }
 356
 357         n->parent = parent;
 358         ++tree->size;
 359
 360         rebalance(tree, parent);
 361         pthread_rwlock_unlock(&tree->lock);
 362         return 0;
 363 } /* sdb_avltree_insert */
 364
 365 sdb_avltree_iter_t *
 366 sdb_avltree_get_iter(sdb_avltree_t *tree)
 367 {
 368         sdb_avltree_iter_t *iter;
 369
 370         if (! tree)
 371                 return NULL;
 372
 373         iter = malloc(sizeof(*iter));
 374         if (! iter)
 375                 return NULL;
 376
 377         pthread_rwlock_rdlock(&tree->lock);
 378
 379         iter->tree = tree;
 380         iter->node = node_smallest(tree);
 381
 382         pthread_rwlock_unlock(&tree->lock);
 383         return iter;
 384 } /* sdb_avltree_get_iter */
 385
 386 void
 387 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
 388 {
 389         if (! iter)
 390                 return;
 391
 392         iter->tree = NULL;
 393         iter->node = NULL;
 394         free(iter);
 395 } /* sdb_avltree_iter_destroy */
 396
 397 _Bool
 398 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
 399 {
 400         if (! iter)
 401                 return 0;
 402
 403         return iter->node != NULL;
 404 } /* sdb_avltree_iter_has_next */
 405
 406 sdb_object_t *
 407 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
 408 {
 409         node_t *n;
 410
 411         if (! iter)
 412                 return NULL;
 413
 414         n = iter->node;
 415         iter->node = node_next(iter->node);
 416         return n ? n->obj : NULL;
 417 } /* sdb_avltree_iter_get_next */
 418
 419 size_t
 420 sdb_avltree_size(sdb_avltree_t *tree)
 421 {
 422         return tree ? tree->size : 0;
 423 } /* sdb_avltree_size */
 424
 425 _Bool
 426 sdb_avltree_valid(sdb_avltree_t *tree)
 427 {
 428         node_t *n;
 429
 430         _Bool status = 1;
 431         size_t size = 0;
 432
 433         if (! tree)
 434                 return 1;
 435
 436         for (n = node_smallest(tree); n; n = node_next(n)) {
 437                 int bf = BALANCE(n);
 438
 439                 if ((bf < -1) || (1 < bf)) {
 440                         sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
 441                                         NODE_NAME(n), bf);
 442                         status = 0;
 443                 }
 444
 445                 if (NODE_HEIGHT(n) != n->height) {
 446                         sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
 447                                         "%zu; expected: %zu", NODE_NAME(n), n->height,
 448                                         NODE_HEIGHT(n));
 449                         status = 0;
 450                 }
 451
 452                 if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
 453                         sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
 454                                         "node '%s': {left: %s, right: %s}; expected: %s",
 455                                         NODE_NAME(n), NODE_NAME(n->parent->left),
 456                                         NODE_NAME(n->parent->right), NODE_NAME(n));
 457                         status = 0;
 458                 }
 459                 if ((! n->parent) && (n != tree->root)) {
 460                         sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
 461                                         "have a parent", NODE_NAME(n));
 462                         status = 0;
 463                 }
 464
 465                 ++size;
 466         }
 467
 468         if (size != tree->size) {
 469                 sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
 470                                 tree->size, size);
 471                 status = 0;
 472         }
 473         return status;
 474 } /* sdb_avltree_valid */
 475
 476 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 477