src/utils_avltree.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3
   4 #include "utils_avltree.h"
   5
   6 #define BALANCE(n) ((((n)->right == NULL) ? 0 : (n)->right->height) \
   7                                  - (((n)->left == NULL) ? 0 : (n)->left->height))
   8
   9 /*
  10  * private data types
  11  */
  12 struct avl_node_s
  13 {
  14         void *key;
  15         void *value;
  16
  17         int height;
  18         struct avl_node_s *left;
  19         struct avl_node_s *right;
  20         struct avl_node_s *parent;
  21 };
  22 typedef struct avl_node_s avl_node_t;
  23
  24 struct avl_tree_s
  25 {
  26         avl_node_t *root;
  27         int (*compare) (const void *, const void *);
  28 };
  29
  30 struct avl_iterator_s
  31 {
  32         avl_tree_t *tree;
  33         avl_node_t *node;
  34 };
  35
  36 /*
  37  * private functions
  38  */
  39 static void free_node (avl_node_t *n)
  40 {
  41         if (n == NULL)
  42                 return;
  43
  44         if (n->left != NULL)
  45                 free_node (n->left);
  46         if (n->right != NULL)
  47                 free_node (n->right);
  48
  49         free (n);
  50 }
  51
  52 static avl_node_t *search (avl_tree_t *t, void *key)
  53 {
  54         avl_node_t *n;
  55         int cmp;
  56
  57         n = t->root;
  58         while (n != NULL)
  59         {
  60                 cmp = t->compare (key, n->key);
  61                 if (cmp == 0)
  62                         return (n);
  63                 else if (cmp < 0)
  64                         n = n->left;
  65                 else
  66                         n = n->right;
  67         }
  68
  69         return (NULL);
  70 }
  71
  72 static void rebalance (avl_tree_t *t, avl_node_t *n)
  73 {
  74         int height_left;
  75         int height_right;
  76         int height_new;
  77         int cmp;
  78
  79         while (n != NULL)
  80         {
  81                 height_left = (n->left == NULL) ? 0 : n->left->height;
  82                 height_right = (n->right == NULL) ? 0 : n->right->height;
  83
  84                 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
  85
  86                 if (height_new == n->height)
  87                         break;
  88
  89                 cmp = height_right - height_left;
  90                 if (cmp < -1)
  91                 {
  92                         avl_node_t *l;
  93                         avl_node_t *lr;
  94
  95                         l = n->left;
  96                         lr = l->right;
  97
  98                         l->right = n;
  99                         l->parent = n->parent;
 100                         n->parent = l;
 101                         n->left = lr;
 102
 103                         if (n == t->root)
 104                                 t->root = l;
 105                 }
 106                 else if (cmp > 1)
 107                 {
 108                         avl_node_t *r;
 109                         avl_node_t *rl;
 110
 111                         r = n->right;
 112                         rl = r->left;
 113
 114                         r->left = n;
 115                         r->parent = n->parent;
 116                         n->parent = r;
 117                         n->right = rl;
 118
 119                         if (n == t->root)
 120                                 t->root = r;
 121                 }
 122                 else
 123                 {
 124                         n = n->parent;
 125                 }
 126         } /* while (n != NULL) */
 127 } /* void rebalance */
 128
 129 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
 130 {
 131         avl_iterator_t *iter;
 132
 133         iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
 134         if (iter == NULL)
 135                 return (NULL);
 136
 137         iter->tree = t;
 138         iter->node = n;
 139
 140         return (iter);
 141 }
 142
 143 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 144 {
 145         avl_node_t *r; /* return node */
 146
 147         if (n == NULL)
 148         {
 149                 return (NULL);
 150         }
 151         else if (n->right == NULL)
 152         {
 153
 154                 r = n->parent;
 155                 while (r != NULL)
 156                 {
 157                         /* stop if a bigger node is found */
 158                         if (t->compare (n, r) < 0) /* n < r */
 159                                 break;
 160                         r = r->parent;
 161                 }
 162         }
 163         else
 164         {
 165                 r = n->right;
 166                 while (r->left != NULL)
 167                         r = r->left;
 168         }
 169
 170         return (r);
 171 }
 172
 173 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 174 {
 175         avl_node_t *r; /* return node */
 176
 177         if (n == NULL)
 178         {
 179                 return (NULL);
 180         }
 181         else if (n->left == NULL)
 182         {
 183
 184                 r = n->parent;
 185                 while (r != NULL)
 186                 {
 187                         /* stop if a smaller node is found */
 188                         if (t->compare (n, r) > 0) /* n > r */
 189                                 break;
 190                         r = r->parent;
 191                 }
 192         }
 193         else
 194         {
 195                 r = n->left;
 196                 while (r->right != NULL)
 197                         r = r->right;
 198         }
 199
 200         return (r);
 201 }
 202
 203 static void *remove (avl_tree_t *t, avl_node_t *n)
 204 {
 205         void *ret;
 206
 207         assert ((t != NULL) && (n != NULL));
 208
 209         ret = n->value;
 210
 211         if ((n->left == NULL) && (n->right == NULL))
 212         {
 213                 /* Deleting a leave is easy */
 214                 if (n->parent == NULL)
 215                 {
 216                         assert (t->root == n);
 217                         t->root = NULL;
 218                 }
 219                 else
 220                 {
 221                         assert ((n->parent->left == n)
 222                                         || (n->parent->right == n));
 223                         if (n->parent->left == n)
 224                                 n->parent->left = NULL;
 225                         else
 226                                 n->parent->right = NULL;
 227                 }
 228
 229                 free_node (n);
 230         }
 231         else
 232         {
 233                 avl_node_t *r; /* replacement node */
 234                 if (BALANCE (n) < 0)
 235                 {
 236                         assert (n->left != NULL);
 237                         r = avl_node_prev (t, n);
 238                 }
 239                 else
 240                 {
 241                         assert (n->right != NULL);
 242                         r = avl_node_next (t, n);
 243                 }
 244                 n->key   = r->key;
 245                 n->value = r->value;
 246
 247                 remove (t, r);
 248         }
 249
 250         return (ret);
 251 } /* void *remove */
 252
 253 /*
 254  * public functions
 255  */
 256 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 257 {
 258         avl_tree_t *t;
 259
 260         if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 261                 return (NULL);
 262
 263         t->root = NULL;
 264         t->compare = compare;
 265
 266         return (t);
 267 }
 268
 269 void avl_destroy (avl_tree_t *t)
 270 {
 271         free_node (t->root);
 272         free (t);
 273 }
 274
 275 int avl_insert (avl_tree_t *t, void *key, void *value)
 276 {
 277         avl_node_t *new;
 278         avl_node_t *nptr;
 279         int cmp;
 280
 281         if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
 282                 return (-1);
 283
 284         new->key = key;
 285         new->value = value;
 286         new->height = 0;
 287         new->left = NULL;
 288         new->right = NULL;
 289
 290         if (t->root == NULL)
 291         {
 292                 new->parent = NULL;
 293                 t->root = new;
 294                 return (0);
 295         }
 296
 297         nptr = t->root;
 298         while (42)
 299         {
 300                 cmp = t->compare (nptr->key, new->key);
 301                 if (cmp == 0)
 302                 {
 303                         free_node (new);
 304                         return (-1);
 305                 }
 306                 else if (cmp < 0)
 307                 {
 308                         /* nptr < new */
 309                         if (nptr->right == NULL)
 310                         {
 311                                 nptr->right = new;
 312                                 new->parent = nptr;
 313                                 nptr = NULL;
 314                                 break;
 315                         }
 316                         else
 317                         {
 318                                 nptr = nptr->right;
 319                         }
 320                 }
 321                 else /* if (cmp > 0) */
 322                 {
 323                         /* nptr > new */
 324                         if (nptr->left == NULL)
 325                         {
 326                                 nptr->left = new;
 327                                 new->parent = nptr;
 328                                 nptr = NULL;
 329                                 break;
 330                         }
 331                         else
 332                         {
 333                                 nptr = nptr->left;
 334                         }
 335                 }
 336         } /* while (42) */
 337
 338         rebalance (t, new->parent);
 339
 340         return (0);
 341 } /* int avl_insert */
 342
 343 void *avl_remove (avl_tree_t *t, void *key)
 344 {
 345         avl_node_t *n;
 346
 347         assert (t != NULL);
 348
 349         n = search (t, key);
 350         if (n == NULL)
 351                 return (NULL);
 352
 353         return (remove (t, n));
 354 } /* void *avl_remove */
 355
 356 void *avl_get (avl_tree_t *t, void *key)
 357 {
 358         avl_node_t *n;
 359
 360         n = search (t, key);
 361         if (n == NULL)
 362                 return (NULL);
 363
 364         return (n->value);
 365 }
 366
 367 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 368 {
 369         avl_node_t *n;
 370
 371         if (t == NULL)
 372                 return (NULL);
 373
 374         for (n = t->root; n != NULL; n = n->left)
 375                 if (n->left == NULL)
 376                         break;
 377
 378         return (avl_create_iterator (t, n));
 379 } /* avl_iterator_t *avl_get_iterator */
 380
 381 void *avl_iterator_next (avl_iterator_t *iter)
 382 {
 383         avl_node_t *n;
 384
 385         if ((iter == NULL) || (iter->node == NULL))
 386                 return (NULL);
 387
 388         n = avl_node_next (iter->tree, iter->node);
 389
 390         if (n == NULL)
 391                 return (NULL);
 392
 393         iter->node = n;
 394         return (n);
 395
 396 }
 397
 398 void *avl_iterator_prev (avl_iterator_t *iter)
 399 {
 400         avl_node_t *n;
 401
 402         if ((iter == NULL) || (iter->node == NULL))
 403                 return (NULL);
 404
 405         n = avl_node_prev (iter->tree, iter->node);
 406
 407         if (n == NULL)
 408                 return (NULL);
 409
 410         iter->node = n;
 411         return (n);
 412
 413 }
 414
 415 void avl_iterator_destroy (avl_iterator_t *iter)
 416 {
 417         free (iter);
 418 }