www.tinc-vpn.org Git - tinc/blob - lib/rbl.c

   1 /*
   2     rbl.c -- red-black tree + linked list convenience
   3     Copyright (C) 2000 Ivo Timmermans <itimmermans@bigfoot.com>,
   4                   2000 Guus Sliepen <guus@sliepen.warande.net>
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20     $Id: rbl.c,v 1.1.2.4 2000/11/18 23:22:44 guus Exp $
  21 */
  22
  23
  24 /* Allocate a new rbl node */
  25 rbl_t *new_rbl()
  26 {
  27   return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
  28 }
  29
  30 /* Free a rbl node */
  31 void free_rbl(rbl_t *rbl)
  32 {
  33   free(rbl);
  34 }
  35
  36 /* Allocate a new rbltree header */
  37 rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_action_t *delete)
  38 {
  39   rbltree_t *tree;
  40
  41   tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
  42   if(tree)
  43     {
  44       tree->compare = compare;
  45       tree->delete = delete;
  46     }
  47
  48   return tree;
  49 }
  50
  51 /* Free a rbltree header */
  52 void free_rbltree(rbltree_t *tree)
  53 {
  54   free(tree);
  55 }
  56
  57 /* Search closest match in the tree */
  58 rbl_t rbl_search_closest(rbltree_t *tree, void *data)
  59 {
  60   rbl_t *rbl, *next;
  61   int result;
  62
  63   next = rbl = tree->top;
  64
  65   while(next)
  66     {
  67       rbl = next;
  68
  69       result = tree->compare(rbl->data, data);
  70
  71       if(result < 0)
  72         next = rbl->left;
  73       else if(result > 0)
  74         next = rbl->right;
  75       else
  76         break;
  77     }
  78
  79   return rbl;
  80 }
  81
  82 /* Search exact match or return NULL pointer */
  83 rbl_t rbl_search(rbltree_t *tree, void *data)
  84 {
  85   rbl_t *rbl, *next;
  86   int result;
  87
  88   next = rbl = tree->top;
  89
  90   while(next)
  91     {
  92       rbl = next;
  93
  94       result = tree->compare(rbl->data, data);
  95
  96       if(result < 0)
  97         next = rbl->left;
  98       else if(result > 0)
  99         next = rbl->right;
 100       else
 101         return rbl;
 102     }
 103
 104   return NULL;
 105 }
 106
 107 /* Red-black tree operations taken from Introduction to Algorithms,
 108    Cormen, Leiserson & Rivest, chapter 14.
 109 */
 110
 111 void rbl_left_rotate(rbl_t *x)
 112 {
 113   rbl_t *y;
 114
 115   y = x->right;
 116   x->right = y->left;
 117
 118   if(y->left)
 119     y->left->parent = x;
 120
 121   y->parent = x->parent;
 122
 123   if(!x->parent)
 124     x->tree->top = y;
 125   else
 126     if(x == x->parent->left)
 127       x->parent->left = y;
 128     else
 129       x->parent->right = y;
 130
 131   y->left = x;
 132   x->parent = y;
 133 }
 134
 135 void rbl_right_rotate(rbl_t *y)
 136 {
 137   rbl_t *x;
 138
 139   x = y->left;
 140   y->left = x->right;
 141
 142   if(x->right)
 143     x->right->parent = y;
 144
 145   x->parent = y->parent;
 146
 147   if(!y->parent)
 148     y->tree->top = x;
 149   else
 150     if(y == y->parent->right)
 151       y->parent->right = x;
 152     else
 153       y->parent->left = x;
 154
 155   x->right = y;
 156   y->parent = x;
 157 }
 158
 159 /* Insert a node into the rbl tree */
 160 rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 161 {
 162    rbl_t *closest, y;
 163    int result;
 164
 165   /* Binary tree and linked list insert */
 166
 167   if(tree->top)
 168     {
 169       closest = rbl_search_closest(tree, rbl->data);
 170       result = tree->compare(rbl->data, data);
 171       if(result < 0)
 172         {
 173           closest->left = rbl;
 174           rbl->prev = closest->prev;
 175           rbl->next = closest;
 176           closest->prev = rbl;
 177           rbl->prev->next = rbl;
 178         }
 179       else if(result > 0)
 180         {
 181           closest->right = rbl;
 182           rbl->next = closest->right;
 183           rbl->prev = closest;
 184           closest->next = rbl;
 185           rbl->next->prev = rbl;
 186         }
 187       else
 188         return closest;         /* Ofcourse, we cannot add two identical things */
 189     }
 190   else
 191     tree->top = rbl;
 192
 193   /* Linked list fixup */
 194
 195   if(!rbl->prev)
 196     tree->head = rbl;
 197
 198   if(!rbl->next)
 199     tree->tail = rbl;
 200
 201   /* Red-black part of insert */
 202
 203   rbl->color = RBL_RED;
 204
 205   while(rbl->parent && rbl->parent->color == RBL_RED)
 206     {
 207       if(rbl->parent == rbl->parent->parent->left)
 208         {
 209           y = rbl->parent->parent->right;
 210           if(y->color == RBL_RED)
 211             {
 212               rbl->parent->color = RBL_BLACK;
 213               y->color = RBL_BLACK;
 214               rbl->parent->parent->color = RBL_RED;
 215               rbl = rbl->parent->parent;
 216             }
 217           else
 218             {
 219               if(rbl == rbl->parent->right)
 220                 {
 221                   rbl = rbl->parent;
 222                   rbl_left_rotate(rbl);
 223                 }
 224               rbl->parent->color = RBL_BLACK;
 225               rbl->parent->parent->color = RBL_RED;
 226               rbl_right_rotate(rbl->parent->parent);
 227             }
 228         }
 229       else
 230         {
 231           y = rbl->parent->parent->left;
 232           if(y->color == RBL_RED)
 233             {
 234               rbl->parent->color = RBL_BLACK;
 235               y->color = RBL_BLACK;
 236               rbl->parent->parent->color = RBL_RED;
 237               rbl = rbl->parent->parent;
 238             }
 239           else
 240             {
 241               if(rbl == rbl->parent->left)
 242                 {
 243                   rbl = rbl->parent;
 244                   rbl_right_rotate(rbl);
 245                 }
 246               rbl->parent->color = RBL_BLACK;
 247               rbl->parent->parent->color = RBL_RED;
 248               rbl_left_rotate(rbl->parent->parent);
 249             }
 250         }
 251     }
 252
 253   tree->top->color = RBL_BLACK;
 254
 255   return rbl;
 256 }
 257
 258 /* Create a new node and insert it into the tree */
 259 rbl_t rbl_insert(rbltree_t *tree, void *data)
 260 {
 261   rbl_t *rbl;
 262
 263   rbl = new_rbl();
 264   rbl->data = data;
 265
 266   return rbl_insert_rbl(tree, rbl);
 267 }
 268
 269 /* Restore red-black property after violation due to a deletion */
 270 void rbl_delete_fixup(rbl_t *x)
 271 {
 272   rbl_t *w;
 273
 274   while(x != x->tree->top && x->color == RBL_BLACK)
 275     {
 276       if(x == x->parent->left)
 277         {
 278           w = x->parent->right;
 279           if(w->color == RBL_RED)
 280             {
 281               w->color = RBL_BLACK;
 282               x->partent->color = RBL_RED;
 283               rbl_left_rotate(x->parent);
 284               w = x->parent->right;
 285             }
 286           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
 287             {
 288               w->color = RBL_RED;
 289               x = x->parent;
 290             }
 291           else
 292             {
 293               if(w->right->color == RBL_BLACK)
 294                 {
 295                   w->left->color = RBL_BLACK;
 296                   w->color = RBL_RED;
 297                   rbl_right_rotate(w);
 298                   w = x->parent->right;
 299                 }
 300               w->color = x->parent->color;
 301               x->parent->color = RBL_BLACK;
 302               w->right->color = RBL_BLACK;
 303               rbl_left_rotate(x->parent);
 304               x = x->tree->top;
 305             }
 306         }
 307       else
 308         {
 309           w = x->parent->left;
 310           if(w->color == RBL_RED)
 311             {
 312               w->color = RBL_BLACK;
 313               x->partent->color = RBL_RED;
 314               rbl_right_rotate(x->parent);
 315               w = x->parent->left;
 316             }
 317           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
 318             {
 319               w->color = RBL_RED;
 320               x = x->parent;
 321             }
 322           else
 323             {
 324               if(w->left->color == RBL_BLACK)
 325                 {
 326                   w->right->color = RBL_BLACK;
 327                   w->color = RBL_RED;
 328                   rbl_left_rotate(w);
 329                   w = x->parent->left;
 330                 }
 331               w->color = x->parent->color;
 332               x->parent->color = RBL_BLACK;
 333               w->left->color = RBL_BLACK;
 334               rbl_right_rotate(x->parent);
 335               x = x->tree->top;
 336             }
 337         }
 338     }
 339
 340   x->color = RBL_BLACK;
 341 }
 342
 343 /* Unlink node from the tree, but keep the node intact. */
 344 rbl_t rbl_unlink_rbl(rbl_t *rbl)
 345 {
 346   rbl_t *x, *y;
 347
 348   /* Binary tree delete */
 349
 350   if(rbl->left && rbl->right)
 351     y = rbl->next;
 352   else
 353     y = rbl;
 354
 355   if(y->left)
 356     x = y->left;
 357   else
 358     x = y->right;
 359
 360   if(x)
 361     x->parent = y->parent;
 362
 363   if(!y->parent)
 364     rbl->tree->top = x;
 365   else
 366     if(y == y->parent->left)
 367       y->parent->left = x;
 368     else
 369       y->parent->right = x;
 370
 371   if(y != rbl)
 372     {
 373       y->left = rbl->left;
 374       y->right = rbl->right;
 375       y->parent = rbl->parent;
 376       if(rbl == rbl->parent->left)
 377         rbl->parent->left = y;
 378       else
 379         rbl->parent->right = y;
 380     }
 381
 382   /* Linked list delete */
 383
 384   if(rbl->prev)
 385     rbl->prev->next = rbl->next;
 386   else
 387     rbl->tree->head = rbl->next;
 388
 389   if(rbl->next)
 390     rbl->next->prev = rbl->prev;
 391   else
 392     rbl->tree->tail = rbl->prev;
 393
 394   /* Red-black part of delete */
 395
 396   if(y->color == RBL_BLACK)
 397     rbl_delete_fixup(x);
 398
 399   return rbl;
 400 }
 401
 402 /* Search node in tree and unlink it */
 403 rbl_t rbl_unlink(rbltree_t *tree, void *data)
 404 {
 405   rbl_t *rbl;
 406
 407   rbl = rbl_search(tree, data);
 408
 409   if(rbl)
 410     return rbl_unlink_rbl(rbl);
 411   else
 412     return NULL;
 413 }
 414
 415 /* Unlink node and free it */
 416 void rbl_delete_rbl(rbl_t *rbl)
 417 {
 418   free_rbl(rbl_unlink_rbl(rbl));
 419 }
 420
 421 /* Search node in tree, unlink and free it */
 422 void rbl_delete(rbltree_t *tree, void *data)
 423 {
 424   free_rbl(rbl_unlink(tree, data));
 425 }
 426
 427 /* Do action for each list entry (in order)
 428    Deletion of entry for which action is called is allowed.
 429  */
 430 void rbl_foreach(rbltree_t *tree, rbl_action_t *action)
 431 {
 432   rbl_t *rbl, *next;
 433
 434   for(rbl = tree->head; rbl; rbl = next);
 435     {
 436       next = rbl->next;
 437       action(rbl);
 438     }
 439 }