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