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.3 2000/11/18 23:21:00 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   /* Red-black part of insert */
 194
 195   rbl->color = RBL_RED;
 196
 197   while(rbl->parent && rbl->parent->color == RBL_RED)
 198     {
 199       if(rbl->parent == rbl->parent->parent->left)
 200         {
 201           y = rbl->parent->parent->right;
 202           if(y->color == RBL_RED)
 203             {
 204               rbl->parent->color = RBL_BLACK;
 205               y->color = RBL_BLACK;
 206               rbl->parent->parent->color = RBL_RED;
 207               rbl = rbl->parent->parent;
 208             }
 209           else
 210             {
 211               if(rbl == rbl->parent->right)
 212                 {
 213                   rbl = rbl->parent;
 214                   rbl_left_rotate(rbl);
 215                 }
 216               rbl->parent->color = RBL_BLACK;
 217               rbl->parent->parent->color = RBL_RED;
 218               rbl_right_rotate(rbl->parent->parent);
 219             }
 220         }
 221       else
 222         {
 223           y = rbl->parent->parent->left;
 224           if(y->color == RBL_RED)
 225             {
 226               rbl->parent->color = RBL_BLACK;
 227               y->color = RBL_BLACK;
 228               rbl->parent->parent->color = RBL_RED;
 229               rbl = rbl->parent->parent;
 230             }
 231           else
 232             {
 233               if(rbl == rbl->parent->left)
 234                 {
 235                   rbl = rbl->parent;
 236                   rbl_right_rotate(rbl);
 237                 }
 238               rbl->parent->color = RBL_BLACK;
 239               rbl->parent->parent->color = RBL_RED;
 240               rbl_left_rotate(rbl->parent->parent);
 241             }
 242         }
 243     }
 244
 245   tree->top->color = RBL_BLACK;
 246
 247   return rbl;
 248 }
 249
 250 /* Create a new node and insert it into the tree */
 251 rbl_t rbl_insert(rbltree_t *tree, void *data)
 252 {
 253   rbl_t *rbl;
 254
 255   rbl = new_rbl();
 256   rbl->data = data;
 257
 258   return rbl_insert_rbl(tree, rbl);
 259 }
 260
 261 /* Restore red-black property after violation due to a deletion */
 262 void rbl_delete_fixup(rbl_t *x)
 263 {
 264   rbl_t *w;
 265
 266   while(x != x->tree->top && x->color == RBL_BLACK)
 267     {
 268       if(x == x->parent->left)
 269         {
 270           w = x->parent->right;
 271           if(w->color == RBL_RED)
 272             {
 273               w->color = RBL_BLACK;
 274               x->partent->color = RBL_RED;
 275               rbl_left_rotate(x->parent);
 276               w = x->parent->right;
 277             }
 278           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
 279             {
 280               w->color = RBL_RED;
 281               x = x->parent;
 282             }
 283           else
 284             {
 285               if(w->right->color == RBL_BLACK)
 286                 {
 287                   w->left->color = RBL_BLACK;
 288                   w->color = RBL_RED;
 289                   rbl_right_rotate(w);
 290                   w = x->parent->right;
 291                 }
 292               w->color = x->parent->color;
 293               x->parent->color = RBL_BLACK;
 294               w->right->color = RBL_BLACK;
 295               rbl_left_rotate(x->parent);
 296               x = x->tree->top;
 297             }
 298         }
 299       else
 300         {
 301           w = x->parent->left;
 302           if(w->color == RBL_RED)
 303             {
 304               w->color = RBL_BLACK;
 305               x->partent->color = RBL_RED;
 306               rbl_right_rotate(x->parent);
 307               w = x->parent->left;
 308             }
 309           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
 310             {
 311               w->color = RBL_RED;
 312               x = x->parent;
 313             }
 314           else
 315             {
 316               if(w->left->color == RBL_BLACK)
 317                 {
 318                   w->right->color = RBL_BLACK;
 319                   w->color = RBL_RED;
 320                   rbl_left_rotate(w);
 321                   w = x->parent->left;
 322                 }
 323               w->color = x->parent->color;
 324               x->parent->color = RBL_BLACK;
 325               w->left->color = RBL_BLACK;
 326               rbl_right_rotate(x->parent);
 327               x = x->tree->top;
 328             }
 329         }
 330     }
 331
 332   x->color = RBL_BLACK;
 333 }
 334
 335 /* Unlink node from the tree, but keep the node intact. */
 336 rbl_t rbl_unlink_rbl(rbl_t *rbl)
 337 {
 338   rbl_t *x, *y;
 339
 340   /* Binary tree delete */
 341
 342   if(rbl->left && rbl->right)
 343     y = rbl->next;
 344   else
 345     y = rbl;
 346
 347   if(y->left)
 348     x = y->left;
 349   else
 350     x = y->right;
 351
 352   if(x)
 353     x->parent = y->parent;
 354
 355   if(!y->parent)
 356     rbl->tree->top = x;
 357   else
 358     if(y == y->parent->left)
 359       y->parent->left = x;
 360     else
 361       y->parent->right = x;
 362
 363   if(y != rbl)
 364     {
 365       y->left = rbl->left;
 366       y->right = rbl->right;
 367       y->parent = rbl->parent;
 368       if(rbl == rbl->parent->left)
 369         rbl->parent->left = y;
 370       else
 371         rbl->parent->right = y;
 372     }
 373
 374   /* Linked list delete */
 375
 376   if(rbl->prev)
 377     rbl->prev->next = rbl->next;
 378   else
 379     rbl->tree->head = rbl->next;
 380
 381   if(rbl->next)
 382     rbl->next->prev = rbl->prev;
 383   else
 384     rbl->tree->tail = rbl->prev;
 385
 386   /* Red-black part of delete */
 387
 388   if(y->color == RBL_BLACK)
 389     rbl_delete_fixup(x);
 390
 391   return rbl;
 392 }
 393
 394 /* Search node in tree and unlink it */
 395 rbl_t rbl_unlink(rbltree_t *tree, void *data)
 396 {
 397   rbl_t *rbl;
 398
 399   rbl = rbl_search(tree, data);
 400
 401   if(rbl)
 402     return rbl_unlink_rbl(rbl);
 403   else
 404     return NULL;
 405 }
 406
 407 /* Unlink node and free it */
 408 void rbl_delete_rbl(rbl_t *rbl)
 409 {
 410   free_rbl(rbl_unlink_rbl(rbl));
 411 }
 412
 413 /* Search node in tree, unlink and free it */
 414 void rbl_delete(rbltree_t *tree, void *data)
 415 {
 416   free_rbl(rbl_unlink(tree, data));
 417 }
 418
 419 /* Do action for each list entry (in order)
 420    Deletion of entry for which action is called is allowed.
 421  */
 422 void rbl_foreach(rbltree_t *tree, rbl_action_t *action)
 423 {
 424   rbl_t *rbl, *next;
 425
 426   for(rbl = tree->head; rbl; rbl = next);
 427     {
 428       next = rbl->next;
 429       action(rbl);
 430     }
 431 }