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, const 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                 n->height = height_new;
  90
  91                 cmp = height_right - height_left;
  92                 if (cmp < -1)
  93                 {
  94                         avl_node_t *l;
  95                         avl_node_t *lr;
  96
  97                         l = n->left;
  98                         lr = l->right;
  99
 100                         l->right = n;
 101                         l->parent = n->parent;
 102                         n->parent = l;
 103                         n->left = lr;
 104
 105                         if (lr != NULL)
 106                                 lr->parent = n;
 107
 108                         if (l->parent == NULL)
 109                         {
 110                                 assert (t->root == n);
 111                                 t->root = l;
 112                         }
 113                         else
 114                         {
 115                                 assert ((l->parent->left == n) || (l->parent->right == n));
 116                                 if (l->parent->left == n)
 117                                         l->parent->left = l;
 118                                 else
 119                                         l->parent->right = l;
 120                         }
 121                 }
 122                 else if (cmp > 1)
 123                 {
 124                         avl_node_t *r;
 125                         avl_node_t *rl;
 126
 127                         r = n->right;
 128                         rl = r->left;
 129
 130                         r->left = n;
 131                         r->parent = n->parent;
 132                         n->parent = r;
 133                         n->right = rl;
 134
 135                         if (rl != NULL)
 136                                 rl->parent = n;
 137
 138                         if (r->parent == NULL)
 139                         {
 140                                 assert (t->root == n);
 141                                 t->root = r;
 142                         }
 143                         else
 144                         {
 145                                 assert ((r->parent->left == n) || (r->parent->right == n));
 146                                 if (r->parent->left == n)
 147                                         r->parent->left = r;
 148                                 else
 149                                         r->parent->right = r;
 150                         }
 151                 }
 152                 else
 153                 {
 154                         n = n->parent;
 155                 }
 156
 157                 assert ((n == NULL) || (n->parent == NULL)
 158                                 || (n->parent->left == n)
 159                                 || (n->parent->right == n));
 160         } /* while (n != NULL) */
 161 } /* void rebalance */
 162
 163 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
 164 {
 165         avl_iterator_t *iter;
 166
 167         iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
 168         if (iter == NULL)
 169                 return (NULL);
 170
 171         iter->tree = t;
 172         iter->node = n;
 173
 174         return (iter);
 175 }
 176
 177 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 178 {
 179         avl_node_t *r; /* return node */
 180
 181         if (n == NULL)
 182         {
 183                 return (NULL);
 184         }
 185         else if (n->right == NULL)
 186         {
 187
 188                 r = n->parent;
 189                 while (r != NULL)
 190                 {
 191                         /* stop if a bigger node is found */
 192                         if (t->compare (n, r) < 0) /* n < r */
 193                                 break;
 194                         r = r->parent;
 195                 }
 196         }
 197         else
 198         {
 199                 r = n->right;
 200                 while (r->left != NULL)
 201                         r = r->left;
 202         }
 203
 204         return (r);
 205 }
 206
 207 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 208 {
 209         avl_node_t *r; /* return node */
 210
 211         if (n == NULL)
 212         {
 213                 return (NULL);
 214         }
 215         else if (n->left == NULL)
 216         {
 217
 218                 r = n->parent;
 219                 while (r != NULL)
 220                 {
 221                         /* stop if a smaller node is found */
 222                         if (t->compare (n, r) > 0) /* n > r */
 223                                 break;
 224                         r = r->parent;
 225                 }
 226         }
 227         else
 228         {
 229                 r = n->left;
 230                 while (r->right != NULL)
 231                         r = r->right;
 232         }
 233
 234         return (r);
 235 }
 236
 237 static int _remove (avl_tree_t *t, avl_node_t *n)
 238 {
 239         assert ((t != NULL) && (n != NULL));
 240
 241         if ((n->left == NULL) && (n->right == NULL))
 242         {
 243                 /* Deleting a leave is easy */
 244                 if (n->parent == NULL)
 245                 {
 246                         assert (t->root == n);
 247                         t->root = NULL;
 248                 }
 249                 else
 250                 {
 251                         assert ((n->parent->left == n)
 252                                         || (n->parent->right == n));
 253                         if (n->parent->left == n)
 254                                 n->parent->left = NULL;
 255                         else
 256                                 n->parent->right = NULL;
 257
 258                         rebalance (t, n->parent);
 259                 }
 260
 261                 free_node (n);
 262         }
 263         else
 264         {
 265                 avl_node_t *r; /* replacement node */
 266                 if (BALANCE (n) < 0)
 267                 {
 268                         assert (n->left != NULL);
 269                         r = avl_node_prev (t, n);
 270                 }
 271                 else
 272                 {
 273                         assert (n->right != NULL);
 274                         r = avl_node_next (t, n);
 275                 }
 276                 n->key   = r->key;
 277                 n->value = r->value;
 278
 279                 _remove (t, r);
 280         }
 281
 282         return (0);
 283 } /* void *_remove */
 284
 285 /*
 286  * public functions
 287  */
 288 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 289 {
 290         avl_tree_t *t;
 291
 292         if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 293                 return (NULL);
 294
 295         t->root = NULL;
 296         t->compare = compare;
 297
 298         return (t);
 299 }
 300
 301 void avl_destroy (avl_tree_t *t)
 302 {
 303         free_node (t->root);
 304         free (t);
 305 }
 306
 307 int avl_insert (avl_tree_t *t, void *key, void *value)
 308 {
 309         avl_node_t *new;
 310         avl_node_t *nptr;
 311         int cmp;
 312
 313         if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
 314                 return (-1);
 315
 316         new->key = key;
 317         new->value = value;
 318         new->height = 1;
 319         new->left = NULL;
 320         new->right = NULL;
 321
 322         if (t->root == NULL)
 323         {
 324                 new->parent = NULL;
 325                 t->root = new;
 326                 return (0);
 327         }
 328
 329         nptr = t->root;
 330         while (42)
 331         {
 332                 cmp = t->compare (nptr->key, new->key);
 333                 if (cmp == 0)
 334                 {
 335                         free_node (new);
 336                         return (-1);
 337                 }
 338                 else if (cmp < 0)
 339                 {
 340                         /* nptr < new */
 341                         if (nptr->right == NULL)
 342                         {
 343                                 nptr->right = new;
 344                                 new->parent = nptr;
 345                                 nptr = NULL;
 346                                 break;
 347                         }
 348                         else
 349                         {
 350                                 nptr = nptr->right;
 351                         }
 352                 }
 353                 else /* if (cmp > 0) */
 354                 {
 355                         /* nptr > new */
 356                         if (nptr->left == NULL)
 357                         {
 358                                 nptr->left = new;
 359                                 new->parent = nptr;
 360                                 nptr = NULL;
 361                                 break;
 362                         }
 363                         else
 364                         {
 365                                 nptr = nptr->left;
 366                         }
 367                 }
 368         } /* while (42) */
 369
 370         assert ((new->parent != NULL)
 371                         && ((new->parent->left == new)
 372                                 || (new->parent->right == new)));
 373
 374         return (0);
 375 } /* int avl_insert */
 376
 377 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 378 {
 379         avl_node_t *n;
 380
 381         assert (t != NULL);
 382
 383         n = search (t, key);
 384         if (n == NULL)
 385                 return (-1);
 386
 387         if (rkey != NULL)
 388                 *rkey = n->key;
 389         if (rvalue != NULL)
 390                 *rvalue = n->value;
 391
 392         return (_remove (t, n));
 393 } /* void *avl_remove */
 394
 395 int avl_get (avl_tree_t *t, const void *key, void **value)
 396 {
 397         avl_node_t *n;
 398
 399         assert (value != NULL);
 400
 401         n = search (t, key);
 402         if (n == NULL)
 403                 return (-1);
 404
 405         *value = n->value;
 406
 407         return (0);
 408 }
 409
 410 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 411 {
 412         avl_node_t *n;
 413
 414         if (t == NULL)
 415                 return (NULL);
 416
 417         for (n = t->root; n != NULL; n = n->left)
 418                 if (n->left == NULL)
 419                         break;
 420
 421         return (avl_create_iterator (t, n));
 422 } /* avl_iterator_t *avl_get_iterator */
 423
 424 void *avl_iterator_next (avl_iterator_t *iter)
 425 {
 426         avl_node_t *n;
 427
 428         if ((iter == NULL) || (iter->node == NULL))
 429                 return (NULL);
 430
 431         n = avl_node_next (iter->tree, iter->node);
 432
 433         if (n == NULL)
 434                 return (NULL);
 435
 436         iter->node = n;
 437         return (n);
 438
 439 }
 440
 441 void *avl_iterator_prev (avl_iterator_t *iter)
 442 {
 443         avl_node_t *n;
 444
 445         if ((iter == NULL) || (iter->node == NULL))
 446                 return (NULL);
 447
 448         n = avl_node_prev (iter->tree, iter->node);
 449
 450         if (n == NULL)
 451                 return (NULL);
 452
 453         iter->node = n;
 454         return (n);
 455
 456 }
 457
 458 void avl_iterator_destroy (avl_iterator_t *iter)
 459 {
 460         free (iter);
 461 }