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