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 "utils/avltree.h"
  33
  34 #include <stdlib.h>
  35
  36 #include <pthread.h>
  37
  38 /*
  39  * private data types
  40  */
  41
  42 struct node;
  43 typedef struct node node_t;
  44
  45 struct node {
  46         sdb_object_t *obj;
  47
  48         node_t *parent;
  49         node_t *left;
  50         node_t *right;
  51 };
  52
  53 struct sdb_avltree {
  54         pthread_rwlock_t lock;
  55
  56         sdb_object_cmp_cb cmp;
  57
  58         node_t *root;
  59         size_t size;
  60 };
  61
  62 struct sdb_avltree_iter {
  63         sdb_avltree_t *tree;
  64         node_t *node;
  65 };
  66
  67 /*
  68  * private helper functions
  69  */
  70
  71 static void
  72 node_destroy(node_t *n)
  73 {
  74         sdb_object_deref(n->obj);
  75         n->obj = NULL;
  76         n->parent = n->left = n->right = NULL;
  77         free(n);
  78 } /* node_destroy */
  79
  80 static node_t *
  81 node_create(sdb_object_t *obj)
  82 {
  83         node_t *n = malloc(sizeof(*n));
  84         if (! n)
  85                 return NULL;
  86
  87         sdb_object_ref(obj);
  88         n->obj = obj;
  89         n->parent = n->left = n->right = NULL;
  90         return n;
  91 } /* node_create */
  92
  93 static node_t *
  94 node_next(node_t *n)
  95 {
  96         node_t *next;
  97
  98         if (! n)
  99                 return NULL;
 100
 101         /* descend into the right tree */
 102         if (n->right) {
 103                 next = n->right;
 104                 while (next->left)
 105                         next = next->left;
 106                 return next;
 107         }
 108
 109         /* visit the parent if we're in its left tree */
 110         if (n->parent && (n->parent->left == n))
 111                 return n->parent;
 112
 113         /* find the parent of the sibling sub-tree on the right */
 114         next = n->parent;
 115         next = NULL;
 116         while (n->parent && (n->parent->right == n)) {
 117                 n = n->parent;
 118                 next = n;
 119         }
 120         if (next)
 121                 next = next->parent;
 122         return next;
 123 } /* node_next */
 124
 125 static void
 126 tree_clear(sdb_avltree_t *tree)
 127 {
 128         node_t *n;
 129
 130         n = tree->root;
 131         while (n) {
 132                 node_t *tmp = node_next(n);
 133
 134                 node_destroy(n);
 135                 n = tmp;
 136         }
 137
 138         tree->root = NULL;
 139         tree->size = 0;
 140 } /* tree_clear */
 141
 142 /*
 143  * public API
 144  */
 145
 146 sdb_avltree_t *
 147 sdb_avltree_create(sdb_object_cmp_cb cmp)
 148 {
 149         sdb_avltree_t *tree;
 150
 151         tree = malloc(sizeof(*tree));
 152         if (! tree)
 153                 return NULL;
 154
 155         if (! cmp)
 156                 cmp = sdb_object_cmp_by_name;
 157
 158         pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
 159         tree->cmp = cmp;
 160
 161         tree->root = NULL;
 162         tree->size = 0;
 163         return tree;
 164 } /* sdb_avltree_create */
 165
 166 void
 167 sdb_avltree_destroy(sdb_avltree_t *tree)
 168 {
 169         if (! tree)
 170                 return;
 171
 172         pthread_rwlock_wrlock(&tree->lock);
 173         tree_clear(tree);
 174         pthread_rwlock_unlock(&tree->lock);
 175         pthread_rwlock_destroy(&tree->lock);
 176         free(tree);
 177 } /* sdb_avltree_destroy */
 178
 179 void
 180 sdb_avltree_clear(sdb_avltree_t *tree)
 181 {
 182         if (! tree)
 183                 return;
 184
 185         pthread_rwlock_wrlock(&tree->lock);
 186         tree_clear(tree);
 187         pthread_rwlock_unlock(&tree->lock);
 188 } /* sdb_avltree_clear */
 189
 190 int
 191 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 192 {
 193         node_t *parent;
 194         node_t *n;
 195
 196         int diff = -1;
 197
 198         if (! tree)
 199                 return -1;
 200
 201         n = node_create(obj);
 202         if (! n)
 203                 return -1;
 204
 205         parent = tree->root;
 206         while (parent) {
 207                 diff = tree->cmp(obj, parent->obj);
 208                 if (! diff) {
 209                         node_destroy(n);
 210                         return -1;
 211                 }
 212
 213                 if (diff < 0) {
 214                         if (! parent->left) {
 215                                 parent->left = n;
 216                                 break;
 217                         }
 218                         parent = parent->left;
 219                 }
 220                 else {
 221                         if (! parent->right) {
 222                                 parent->right = n;
 223                                 break;
 224                         }
 225                         parent = parent->right;
 226                 }
 227         }
 228
 229         if (! parent) {
 230                 /* new root */
 231                 if (diff < 0)
 232                         n->right = tree->root;
 233                 else
 234                         n->left = tree->root;
 235                 tree->root = n;
 236         }
 237
 238         n->parent = parent;
 239         ++tree->size;
 240
 241         /* XXX: rebalance */
 242         return 0;
 243 } /* sdb_avltree_insert */
 244
 245 sdb_avltree_iter_t *
 246 sdb_avltree_get_iter(sdb_avltree_t *tree)
 247 {
 248         sdb_avltree_iter_t *iter;
 249
 250         if (! tree)
 251                 return NULL;
 252
 253         iter = malloc(sizeof(*iter));
 254         if (! iter)
 255                 return NULL;
 256
 257         pthread_rwlock_rdlock(&tree->lock);
 258
 259         iter->tree = tree;
 260         iter->node = tree->root->left;
 261         while (iter->node && iter->node->left)
 262                 iter->node = iter->node->left;
 263
 264         pthread_rwlock_unlock(&tree->lock);
 265         return iter;
 266 } /* sdb_avltree_get_iter */
 267
 268 void
 269 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
 270 {
 271         if (! iter)
 272                 return;
 273
 274         iter->tree = NULL;
 275         iter->node = NULL;
 276         free(iter);
 277 } /* sdb_avltree_iter_destroy */
 278
 279 _Bool
 280 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
 281 {
 282         if (! iter)
 283                 return 0;
 284
 285         return iter->node != NULL;
 286 } /* sdb_avltree_iter_has_next */
 287
 288 sdb_object_t *
 289 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
 290 {
 291         node_t *n;
 292
 293         if (! iter)
 294                 return NULL;
 295
 296         n = iter->node;
 297         iter->node = node_next(iter->node);
 298         return n ? n->obj : NULL;
 299 } /* sdb_avltree_iter_get_next */
 300
 301 size_t
 302 sdb_avltree_size(sdb_avltree_t *tree)
 303 {
 304         return tree ? tree->size : 0;
 305 } /* sdb_avltree_size */
 306
 307 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 308