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.6 2000/11/19 11:05:59 guus Exp $
  21 */
  22
  23 #include <xalloc.h>
  24
  25 #include "rbl.h"
  26
  27 /* Allocate a new rbl node */
  28 rbl_t *new_rbl()
  29 {
  30   return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
  31 }
  32
  33 /* Free a rbl node */
  34 void free_rbl(rbl_t *rbl)
  35 {
  36   free(rbl);
  37 }
  38
  39 /* Allocate a new rbltree header */
  40 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
  41 {
  42   rbltree_t *tree;
  43
  44   tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
  45   if(tree)
  46     {
  47       tree->compare = compare;
  48       tree->delete = delete;
  49     }
  50
  51   return tree;
  52 }
  53
  54 /* Free a rbltree header */
  55 void free_rbltree(rbltree_t *tree)
  56 {
  57   free(tree);
  58 }
  59
  60 /* Search closest match in the tree */
  61 rbl_t *rbl_search_closest(rbltree_t *tree, void *data)
  62 {
  63   rbl_t *rbl, *next;
  64   int result;
  65
  66   next = rbl = tree->top;
  67
  68   while(next)
  69     {
  70       rbl = next;
  71
  72       result = tree->compare(data, rbl->data);
  73
  74       if(result < 0)
  75         next = rbl->left;
  76       else if(result > 0)
  77         next = rbl->right;
  78       else
  79         break;
  80     }
  81
  82   return rbl;
  83 }
  84
  85 /* Search exact match or return NULL pointer */
  86 rbl_t *rbl_search(rbltree_t *tree, void *data)
  87 {
  88   rbl_t *rbl, *next;
  89   int result;
  90
  91   next = rbl = tree->top;
  92
  93   while(next)
  94     {
  95       rbl = next;
  96
  97       result = tree->compare(data, rbl->data);
  98
  99       if(result < 0)
 100         next = rbl->left;
 101       else if(result > 0)
 102         next = rbl->right;
 103       else
 104         return rbl;
 105     }
 106
 107   return NULL;
 108 }
 109
 110 /* Red-black tree operations taken from Introduction to Algorithms,
 111    Cormen, Leiserson & Rivest, chapter 14.
 112 */
 113
 114 void rbl_left_rotate(rbl_t *x)
 115 {
 116   rbl_t *y;
 117
 118   y = x->right;
 119   x->right = y->left;
 120
 121   if(y->left)
 122     y->left->parent = x;
 123
 124   y->parent = x->parent;
 125
 126   if(!x->parent)
 127     x->tree->top = y;
 128   else
 129     if(x == x->parent->left)
 130       x->parent->left = y;
 131     else
 132       x->parent->right = y;
 133
 134   y->left = x;
 135   x->parent = y;
 136 }
 137
 138 void rbl_right_rotate(rbl_t *y)
 139 {
 140   rbl_t *x;
 141
 142   x = y->left;
 143   y->left = x->right;
 144
 145   if(x->right)
 146     x->right->parent = y;
 147
 148   x->parent = y->parent;
 149
 150   if(!y->parent)
 151     y->tree->top = x;
 152   else
 153     if(y == y->parent->right)
 154       y->parent->right = x;
 155     else
 156       y->parent->left = x;
 157
 158   x->right = y;
 159   y->parent = x;
 160 }
 161
 162 /* Insert a node into the rbl tree */
 163 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 164 {
 165   rbl_t *closest, *x, *y;
 166   int result;
 167
 168   rbl->tree = tree;
 169
 170   /* Binary tree and linked list insert */
 171
 172   if(tree->top)
 173     {
 174       closest = rbl_search_closest(tree, rbl->data);
 175       result = tree->compare(rbl->data, closest->data);
 176       if(result < 0)
 177         {
 178           closest->left = rbl;
 179
 180           rbl->prev = closest->prev;
 181           rbl->next = closest;
 182           closest->prev = rbl;
 183
 184           if(rbl->prev)
 185             rbl->prev->next = rbl;
 186           else
 187             tree->head = rbl;
 188         }
 189       else if(result > 0)
 190         {
 191           closest->right = rbl;
 192
 193           rbl->next = closest->next;
 194           rbl->prev = closest;
 195           closest->next = rbl;
 196
 197           if(rbl->next)
 198             rbl->next->prev = rbl;
 199           else
 200             tree->tail = rbl;
 201         }
 202       else
 203         return closest;         /* Ofcourse, we cannot add two identical things */
 204
 205       rbl->parent = closest;
 206     }
 207   else
 208     {
 209       tree->top = rbl;
 210       tree->head = rbl;
 211       tree->tail = rbl;
 212     }
 213
 214   /* Red-black part of insert */
 215
 216   x = rbl;
 217   x->color = RBL_RED;
 218
 219   while(x != tree->top && x->parent->color == RBL_RED)
 220     {
 221       if(x->parent == x->parent->parent->left)
 222         {
 223           y = x->parent->parent->right;
 224           if(y && y->color == RBL_RED)
 225             {
 226               x->parent->color = RBL_BLACK;
 227               y->color = RBL_BLACK;
 228               x->parent->parent->color = RBL_RED;
 229               x = x->parent->parent;
 230             }
 231           else
 232             {
 233               if(x == x->parent->right)
 234                 {
 235                   x = x->parent;
 236                   rbl_left_rotate(x);
 237                 }
 238               x->parent->color = RBL_BLACK;
 239               x->parent->parent->color = RBL_RED;
 240               rbl_right_rotate(x->parent->parent);
 241             }
 242         }
 243       else
 244         {
 245           y = x->parent->parent->left;
 246           if(y && y->color == RBL_RED)
 247             {
 248               x->parent->color = RBL_BLACK;
 249               y->color = RBL_BLACK;
 250               x->parent->parent->color = RBL_RED;
 251               x = x->parent->parent;
 252             }
 253           else
 254             {
 255               if(x == x->parent->left)
 256                 {
 257                   x = x->parent;
 258                   rbl_right_rotate(x);
 259                 }
 260               x->parent->color = RBL_BLACK;
 261               x->parent->parent->color = RBL_RED;
 262               rbl_left_rotate(x->parent->parent);
 263             }
 264         }
 265     }
 266
 267   tree->top->color = RBL_BLACK;
 268   return rbl;
 269 }
 270
 271 /* Create a new node and insert it into the tree */
 272 rbl_t *rbl_insert(rbltree_t *tree, void *data)
 273 {
 274   rbl_t *rbl;
 275
 276   rbl = new_rbl();
 277   rbl->data = data;
 278
 279   if(rbl_insert_rbl(tree, rbl) == rbl)
 280     return rbl;
 281   else
 282     {
 283       free_rbl(rbl);
 284       return NULL;
 285     }
 286 }
 287
 288 /* Restore red-black property after violation due to a deletion */
 289 void rbl_delete_fixup(rbl_t *x)
 290 {
 291   rbl_t *w;
 292
 293   while(x != x->tree->top && x->color == RBL_BLACK)
 294     {
 295       if(x == x->parent->left)
 296         {
 297           w = x->parent->right;
 298           if(w->color == RBL_RED)
 299             {
 300               w->color = RBL_BLACK;
 301               x->parent->color = RBL_RED;
 302               rbl_left_rotate(x->parent);
 303               w = x->parent->right;
 304             }
 305           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
 306             {
 307               w->color = RBL_RED;
 308               x = x->parent;
 309             }
 310           else
 311             {
 312               if(w->right->color == RBL_BLACK)
 313                 {
 314                   w->left->color = RBL_BLACK;
 315                   w->color = RBL_RED;
 316                   rbl_right_rotate(w);
 317                   w = x->parent->right;
 318                 }
 319               w->color = x->parent->color;
 320               x->parent->color = RBL_BLACK;
 321               w->right->color = RBL_BLACK;
 322               rbl_left_rotate(x->parent);
 323               x = x->tree->top;
 324             }
 325         }
 326       else
 327         {
 328           w = x->parent->left;
 329           if(w->color == RBL_RED)
 330             {
 331               w->color = RBL_BLACK;
 332               x->parent->color = RBL_RED;
 333               rbl_right_rotate(x->parent);
 334               w = x->parent->left;
 335             }
 336           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
 337             {
 338               w->color = RBL_RED;
 339               x = x->parent;
 340             }
 341           else
 342             {
 343               if(w->left->color == RBL_BLACK)
 344                 {
 345                   w->right->color = RBL_BLACK;
 346                   w->color = RBL_RED;
 347                   rbl_left_rotate(w);
 348                   w = x->parent->left;
 349                 }
 350               w->color = x->parent->color;
 351               x->parent->color = RBL_BLACK;
 352               w->left->color = RBL_BLACK;
 353               rbl_right_rotate(x->parent);
 354               x = x->tree->top;
 355             }
 356         }
 357     }
 358
 359   x->color = RBL_BLACK;
 360 }
 361
 362 /* Unlink node from the tree, but keep the node intact. */
 363 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
 364 {
 365   rbl_t *x, *y;
 366
 367   /* Binary tree delete */
 368
 369   if(rbl->left && rbl->right)
 370     y = rbl->next;
 371   else
 372     y = rbl;
 373
 374   if(y->left)
 375     x = y->left;
 376   else
 377     x = y->right;
 378
 379   if(x)
 380     x->parent = y->parent;
 381
 382   if(!y->parent)
 383     rbl->tree->top = x;
 384   else
 385     if(y == y->parent->left)
 386       y->parent->left = x;
 387     else
 388       y->parent->right = x;
 389
 390   if(y != rbl)
 391     {
 392       y->left = rbl->left;
 393       y->right = rbl->right;
 394       y->parent = rbl->parent;
 395       if(rbl == rbl->parent->left)
 396         rbl->parent->left = y;
 397       else
 398         rbl->parent->right = y;
 399     }
 400
 401   /* Linked list delete */
 402
 403   if(rbl->prev)
 404     rbl->prev->next = rbl->next;
 405   else
 406     rbl->tree->head = rbl->next;
 407
 408   if(rbl->next)
 409     rbl->next->prev = rbl->prev;
 410   else
 411     rbl->tree->tail = rbl->prev;
 412
 413   /* Red-black part of delete */
 414
 415   if(y->color == RBL_BLACK && x)
 416     rbl_delete_fixup(x);
 417
 418   return rbl;
 419 }
 420
 421 /* Search node in tree and unlink it */
 422 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
 423 {
 424   rbl_t *rbl;
 425
 426   rbl = rbl_search(tree, data);
 427
 428   if(rbl)
 429     return rbl_unlink_rbl(rbl);
 430   else
 431     return NULL;
 432 }
 433
 434 /* Unlink node and free it */
 435 void rbl_delete_rbl(rbl_t *rbl)
 436 {
 437   free_rbl(rbl_unlink_rbl(rbl));
 438 }
 439
 440 /* Search node in tree, unlink and free it */
 441 void rbl_delete(rbltree_t *tree, void *data)
 442 {
 443   free_rbl(rbl_unlink(tree, data));
 444 }
 445
 446 rbl_unlink_rbltree_branch(rbl_t *rbl)
 447 {
 448   if(rbl->left)
 449     rbl_unlink_rbltree_branch(rbl->left);
 450
 451   if(rbl->right)
 452     rbl_unlink_rbltree_branch(rbl->right);
 453
 454   if(rbl->parent)
 455     {
 456       if(rbl == rbl->parent->left)
 457         rbl->parent->left = NULL;
 458       else
 459         rbl->parent->right = NULL;
 460 }
 461
 462 /* Optimized unlinking for a complete tree */
 463 rbl_unlink_rbltree(rbltree_t *tree)
 464 {
 465   rbl_t *rbl, *next;
 466
 467   for(rbl = tree->head; rbl; rbl = next)
 468     {
 469       next = rbl->next;
 470       rbl->tree = NULL;
 471       rbl->parent = NULL;
 472       rbl->left = NULL;
 473       rbl->right = NULL;
 474       rbl->prev = NULL;
 475       rbl->next = NULL;
 476     }
 477
 478   tree->top = NULL;
 479   tree->head = NULL;
 480   tree->tail = NULL;
 481 }
 482
 483 /* Optimized deletion for a complete tree */
 484 rbl_delete_rbltree(rbltree_t *tree)
 485 {
 486   rbl_t *rbl, *next;
 487
 488   for(rbl = tree->head; rbl; rbl = next)
 489     {
 490       next = rbl->next;
 491       tree->delete(rbl->data)
 492     }
 493
 494   tree->top = NULL;
 495   tree->head = NULL;
 496   tree->tail = NULL;
 497 }
 498
 499 /* Do action for each list entry (in order)
 500    Deletion of entry for which action is called is allowed.
 501  */
 502 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
 503 {
 504   rbl_t *rbl, *next;
 505
 506   for(rbl = tree->head; rbl; rbl = next)
 507     {
 508       next = rbl->next;
 509       action(rbl->data);
 510     }
 511 }
 512
 513 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
 514 {
 515   rbl_t *rbl, *next;
 516
 517   for(rbl = tree->head; rbl; rbl = next)
 518     {
 519       next = rbl->next;
 520       action(rbl);
 521     }
 522 }