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.5 2000/11/19 02:04:29 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 // fprintf(stderr, "comparing %s     with %s        = %d\n", rbl->data, data, result);
  75
  76       if(result < 0)
  77         next = rbl->left;
  78       else if(result > 0)
  79         next = rbl->right;
  80       else
  81         break;
  82     }
  83
  84   return rbl;
  85 }
  86
  87 /* Search exact match or return NULL pointer */
  88 rbl_t *rbl_search(rbltree_t *tree, void *data)
  89 {
  90   rbl_t *rbl, *next;
  91   int result;
  92
  93   next = rbl = tree->top;
  94
  95   while(next)
  96     {
  97       rbl = next;
  98
  99       result = tree->compare(rbl->data, data);
 100
 101       if(result < 0)
 102         next = rbl->left;
 103       else if(result > 0)
 104         next = rbl->right;
 105       else
 106         return rbl;
 107     }
 108
 109   return NULL;
 110 }
 111
 112 /* Red-black tree operations taken from Introduction to Algorithms,
 113    Cormen, Leiserson & Rivest, chapter 14.
 114 */
 115
 116 void rbl_left_rotate(rbl_t *x)
 117 {
 118   rbl_t *y;
 119
 120   y = x->right;
 121   x->right = y->left;
 122
 123   if(y->left)
 124     y->left->parent = x;
 125
 126   y->parent = x->parent;
 127
 128   if(!x->parent)
 129     x->tree->top = y;
 130   else
 131     if(x == x->parent->left)
 132       x->parent->left = y;
 133     else
 134       x->parent->right = y;
 135
 136   y->left = x;
 137   x->parent = y;
 138 }
 139
 140 void rbl_right_rotate(rbl_t *y)
 141 {
 142   rbl_t *x;
 143
 144   x = y->left;
 145   y->left = x->right;
 146
 147   if(x->right)
 148     x->right->parent = y;
 149
 150   x->parent = y->parent;
 151
 152   if(!y->parent)
 153     y->tree->top = x;
 154   else
 155     if(y == y->parent->right)
 156       y->parent->right = x;
 157     else
 158       y->parent->left = x;
 159
 160   x->right = y;
 161   y->parent = x;
 162 }
 163
 164 /* Insert a node into the rbl tree */
 165 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 166 {
 167   rbl_t *closest, *x, *y;
 168   int result;
 169
 170   rbl->tree = tree;
 171
 172   /* Binary tree and linked list insert */
 173
 174   if(tree->top)
 175     {
 176       closest = rbl_search_closest(tree, rbl->data);
 177       result = tree->compare(rbl->data, closest->data);
 178       if(result < 0)
 179         {
 180           closest->left = rbl;
 181
 182           rbl->prev = closest->prev;
 183           rbl->next = closest;
 184           closest->prev = rbl;
 185
 186           if(rbl->prev)
 187             rbl->prev->next = rbl;
 188           else
 189             tree->head = rbl;
 190         }
 191       else if(result > 0)
 192         {
 193           closest->right = rbl;
 194
 195           rbl->next = closest->next;
 196           rbl->prev = closest;
 197           closest->next = rbl;
 198
 199           if(rbl->next)
 200             rbl->next->prev = rbl;
 201           else
 202             tree->tail = rbl;
 203         }
 204       else
 205         return closest;         /* Ofcourse, we cannot add two identical things */
 206
 207       rbl->parent = closest;
 208     }
 209   else
 210     {
 211       tree->top = rbl;
 212       tree->head = rbl;
 213       tree->tail = rbl;
 214     }
 215
 216   /* Red-black part of insert */
 217
 218   x = rbl;
 219   x->color = RBL_RED;
 220
 221   while(x != tree->top && x->parent->color == RBL_RED)
 222     {
 223       if(x->parent == x->parent->parent->left)
 224         {
 225           y = x->parent->parent->right;
 226           if(y && y->color == RBL_RED)
 227             {
 228               x->parent->color = RBL_BLACK;
 229               y->color = RBL_BLACK;
 230               x->parent->parent->color = RBL_RED;
 231               x = x->parent->parent;
 232             }
 233           else
 234             {
 235               if(x == x->parent->right)
 236                 {
 237                   x = x->parent;
 238                   rbl_left_rotate(x);
 239                 }
 240               x->parent->color = RBL_BLACK;
 241               x->parent->parent->color = RBL_RED;
 242               rbl_right_rotate(x->parent->parent);
 243             }
 244         }
 245       else
 246         {
 247           y = x->parent->parent->left;
 248           if(y && y->color == RBL_RED)
 249             {
 250               x->parent->color = RBL_BLACK;
 251               y->color = RBL_BLACK;
 252               x->parent->parent->color = RBL_RED;
 253               x = x->parent->parent;
 254             }
 255           else
 256             {
 257               if(x == x->parent->left)
 258                 {
 259                   x = x->parent;
 260                   rbl_right_rotate(x);
 261                 }
 262               x->parent->color = RBL_BLACK;
 263               x->parent->parent->color = RBL_RED;
 264               rbl_left_rotate(x->parent->parent);
 265             }
 266         }
 267     }
 268
 269   tree->top->color = RBL_BLACK;
 270   return rbl;
 271 }
 272
 273 /* Create a new node and insert it into the tree */
 274 rbl_t *rbl_insert(rbltree_t *tree, void *data)
 275 {
 276   rbl_t *rbl;
 277
 278   rbl = new_rbl();
 279   rbl->data = data;
 280
 281   if(rbl_insert_rbl(tree, rbl) == rbl)
 282     return rbl;
 283   else
 284     {
 285       free_rbl(rbl);
 286       return NULL;
 287     }
 288 }
 289
 290 /* Restore red-black property after violation due to a deletion */
 291 void rbl_delete_fixup(rbl_t *x)
 292 {
 293   rbl_t *w;
 294
 295   while(x != x->tree->top && x->color == RBL_BLACK)
 296     {
 297       if(x == x->parent->left)
 298         {
 299           w = x->parent->right;
 300           if(w->color == RBL_RED)
 301             {
 302               w->color = RBL_BLACK;
 303               x->parent->color = RBL_RED;
 304               rbl_left_rotate(x->parent);
 305               w = x->parent->right;
 306             }
 307           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
 308             {
 309               w->color = RBL_RED;
 310               x = x->parent;
 311             }
 312           else
 313             {
 314               if(w->right->color == RBL_BLACK)
 315                 {
 316                   w->left->color = RBL_BLACK;
 317                   w->color = RBL_RED;
 318                   rbl_right_rotate(w);
 319                   w = x->parent->right;
 320                 }
 321               w->color = x->parent->color;
 322               x->parent->color = RBL_BLACK;
 323               w->right->color = RBL_BLACK;
 324               rbl_left_rotate(x->parent);
 325               x = x->tree->top;
 326             }
 327         }
 328       else
 329         {
 330           w = x->parent->left;
 331           if(w->color == RBL_RED)
 332             {
 333               w->color = RBL_BLACK;
 334               x->parent->color = RBL_RED;
 335               rbl_right_rotate(x->parent);
 336               w = x->parent->left;
 337             }
 338           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
 339             {
 340               w->color = RBL_RED;
 341               x = x->parent;
 342             }
 343           else
 344             {
 345               if(w->left->color == RBL_BLACK)
 346                 {
 347                   w->right->color = RBL_BLACK;
 348                   w->color = RBL_RED;
 349                   rbl_left_rotate(w);
 350                   w = x->parent->left;
 351                 }
 352               w->color = x->parent->color;
 353               x->parent->color = RBL_BLACK;
 354               w->left->color = RBL_BLACK;
 355               rbl_right_rotate(x->parent);
 356               x = x->tree->top;
 357             }
 358         }
 359     }
 360
 361   x->color = RBL_BLACK;
 362 }
 363
 364 /* Unlink node from the tree, but keep the node intact. */
 365 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
 366 {
 367   rbl_t *x, *y;
 368
 369   /* Binary tree delete */
 370
 371   if(rbl->left && rbl->right)
 372     y = rbl->next;
 373   else
 374     y = rbl;
 375
 376   if(y->left)
 377     x = y->left;
 378   else
 379     x = y->right;
 380
 381   if(x)
 382     x->parent = y->parent;
 383
 384   if(!y->parent)
 385     rbl->tree->top = x;
 386   else
 387     if(y == y->parent->left)
 388       y->parent->left = x;
 389     else
 390       y->parent->right = x;
 391
 392   if(y != rbl)
 393     {
 394       y->left = rbl->left;
 395       y->right = rbl->right;
 396       y->parent = rbl->parent;
 397       if(rbl == rbl->parent->left)
 398         rbl->parent->left = y;
 399       else
 400         rbl->parent->right = y;
 401     }
 402
 403   /* Linked list delete */
 404
 405   if(rbl->prev)
 406     rbl->prev->next = rbl->next;
 407   else
 408     rbl->tree->head = rbl->next;
 409
 410   if(rbl->next)
 411     rbl->next->prev = rbl->prev;
 412   else
 413     rbl->tree->tail = rbl->prev;
 414
 415   /* Red-black part of delete */
 416
 417   if(y->color == RBL_BLACK)
 418     rbl_delete_fixup(x);
 419
 420   return rbl;
 421 }
 422
 423 /* Search node in tree and unlink it */
 424 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
 425 {
 426   rbl_t *rbl;
 427
 428   rbl = rbl_search(tree, data);
 429
 430   if(rbl)
 431     return rbl_unlink_rbl(rbl);
 432   else
 433     return NULL;
 434 }
 435
 436 /* Unlink node and free it */
 437 void rbl_delete_rbl(rbl_t *rbl)
 438 {
 439   free_rbl(rbl_unlink_rbl(rbl));
 440 }
 441
 442 /* Search node in tree, unlink and free it */
 443 void rbl_delete(rbltree_t *tree, void *data)
 444 {
 445   free_rbl(rbl_unlink(tree, data));
 446 }
 447
 448 /* Do action for each list entry (in order)
 449    Deletion of entry for which action is called is allowed.
 450  */
 451 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
 452 {
 453   rbl_t *rbl, *next;
 454
 455   for(rbl = tree->head; rbl; rbl = next)
 456     {
 457       next = rbl->next;
 458       action(rbl);
 459     }
 460 }