git.tinc-vpn.org Git - tinc/blob - src/splay_tree.c

   1 /*
   2     splay_tree.c -- splay tree and linked list convenience
   3     Copyright (C) 2004-2013 Guus Sliepen <guus@tinc-vpn.org>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License along
  16     with this program; if not, write to the Free Software Foundation, Inc.,
  17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "system.h"
  21
  22 #include "splay_tree.h"
  23 #include "xalloc.h"
  24
  25 /* Splay operation */
  26
  27 static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *result) {
  28         splay_node_t left = {NULL}, right = {NULL};
  29         splay_node_t *leftbottom = &left, *rightbottom = &right, *child, *grandchild;
  30         splay_node_t *root = tree->root;
  31         int c;
  32
  33         if(!root) {
  34                 if(result) {
  35                         *result = 0;
  36                 }
  37
  38                 return NULL;
  39         }
  40
  41         while((c = tree->compare(data, root->data))) {
  42                 if(c < 0 && (child = root->left)) {
  43                         c = tree->compare(data, child->data);
  44
  45                         if(c < 0 && (grandchild = child->left)) {
  46                                 rightbottom->left = child;
  47                                 child->parent = rightbottom;
  48                                 rightbottom = child;
  49
  50                                 if((root->left = child->right)) {
  51                                         child->right->parent = root;
  52                                 }
  53
  54                                 child->right = root;
  55                                 root->parent = child;
  56
  57                                 child->left = NULL;
  58                                 grandchild->parent = NULL;
  59
  60                                 root = grandchild;
  61                         } else if(c > 0 && (grandchild = child->right)) {
  62                                 leftbottom->right = child;
  63                                 child->parent = leftbottom;
  64                                 leftbottom = child;
  65
  66                                 child->right = NULL;
  67                                 grandchild->parent = NULL;
  68
  69                                 rightbottom->left = root;
  70                                 root->parent = rightbottom;
  71                                 rightbottom = root;
  72
  73                                 root->left = NULL;
  74
  75                                 root = grandchild;
  76                         } else {
  77                                 rightbottom->left = root;
  78                                 root->parent = rightbottom;
  79                                 rightbottom = root;
  80
  81                                 root->left = NULL;
  82                                 child->parent = NULL;
  83
  84                                 root = child;
  85                                 break;
  86                         }
  87                 } else if(c > 0 && (child = root->right)) {
  88                         c = tree->compare(data, child->data);
  89
  90                         if(c > 0 && (grandchild = child->right)) {
  91                                 leftbottom->right = child;
  92                                 child->parent = leftbottom;
  93                                 leftbottom = child;
  94
  95                                 if((root->right = child->left)) {
  96                                         child->left->parent = root;
  97                                 }
  98
  99                                 child->left = root;
 100                                 root->parent = child;
 101
 102                                 child->right = NULL;
 103                                 grandchild->parent = NULL;
 104
 105                                 root = grandchild;
 106                         } else if(c < 0 && (grandchild = child->left)) {
 107                                 rightbottom->left = child;
 108                                 child->parent = rightbottom;
 109                                 rightbottom = child;
 110
 111                                 child->left = NULL;
 112                                 grandchild->parent = NULL;
 113
 114                                 leftbottom->right = root;
 115                                 root->parent = leftbottom;
 116                                 leftbottom = root;
 117
 118                                 root->right = NULL;
 119
 120                                 root = grandchild;
 121                         } else {
 122                                 leftbottom->right = root;
 123                                 root->parent = leftbottom;
 124                                 leftbottom = root;
 125
 126                                 root->right = NULL;
 127                                 child->parent = NULL;
 128
 129                                 root = child;
 130                                 break;
 131                         }
 132                 } else {
 133                         break;
 134                 }
 135         }
 136
 137         /* Merge trees */
 138
 139         if(left.right) {
 140                 if(root->left) {
 141                         leftbottom->right = root->left;
 142                         root->left->parent = leftbottom;
 143                 }
 144
 145                 root->left = left.right;
 146                 left.right->parent = root;
 147         }
 148
 149         if(right.left) {
 150                 if(root->right) {
 151                         rightbottom->left = root->right;
 152                         root->right->parent = rightbottom;
 153                 }
 154
 155                 root->right = right.left;
 156                 right.left->parent = root;
 157         }
 158
 159         /* Return result */
 160
 161         tree->root = root;
 162
 163         if(result) {
 164                 *result = c;
 165         }
 166
 167         return tree->root;
 168 }
 169
 170 static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
 171         splay_node_t *parent, *grandparent, *greatgrandparent;
 172
 173         while((parent = node->parent)) {
 174                 if(!(grandparent = parent->parent)) { /* zig */
 175                         if(node == parent->left) {
 176                                 if((parent->left = node->right)) {
 177                                         parent->left->parent = parent;
 178                                 }
 179
 180                                 node->right = parent;
 181                         } else {
 182                                 if((parent->right = node->left)) {
 183                                         parent->right->parent = parent;
 184                                 }
 185
 186                                 node->left = parent;
 187                         }
 188
 189                         parent->parent = node;
 190                         node->parent = NULL;
 191                 } else {
 192                         greatgrandparent = grandparent->parent;
 193
 194                         if(node == parent->left && parent == grandparent->left) { /* left zig-zig */
 195                                 if((grandparent->left = parent->right)) {
 196                                         grandparent->left->parent = grandparent;
 197                                 }
 198
 199                                 parent->right = grandparent;
 200                                 grandparent->parent = parent;
 201
 202                                 if((parent->left = node->right)) {
 203                                         parent->left->parent = parent;
 204                                 }
 205
 206                                 node->right = parent;
 207                                 parent->parent = node;
 208                         } else if(node == parent->right && parent == grandparent->right) { /* right zig-zig */
 209                                 if((grandparent->right = parent->left)) {
 210                                         grandparent->right->parent = grandparent;
 211                                 }
 212
 213                                 parent->left = grandparent;
 214                                 grandparent->parent = parent;
 215
 216                                 if((parent->right = node->left)) {
 217                                         parent->right->parent = parent;
 218                                 }
 219
 220                                 node->left = parent;
 221                                 parent->parent = node;
 222                         } else if(node == parent->right && parent == grandparent->left) { /* left-right zig-zag */
 223                                 if((parent->right = node->left)) {
 224                                         parent->right->parent = parent;
 225                                 }
 226
 227                                 node->left = parent;
 228                                 parent->parent = node;
 229
 230                                 if((grandparent->left = node->right)) {
 231                                         grandparent->left->parent = grandparent;
 232                                 }
 233
 234                                 node->right = grandparent;
 235                                 grandparent->parent = node;
 236                         } else { /* right-left zig-zag */
 237                                 if((parent->left = node->right)) {
 238                                         parent->left->parent = parent;
 239                                 }
 240
 241                                 node->right = parent;
 242                                 parent->parent = node;
 243
 244                                 if((grandparent->right = node->left)) {
 245                                         grandparent->right->parent = grandparent;
 246                                 }
 247
 248                                 node->left = grandparent;
 249                                 grandparent->parent = node;
 250                         }
 251
 252                         if((node->parent = greatgrandparent)) {
 253                                 if(grandparent == greatgrandparent->left) {
 254                                         greatgrandparent->left = node;
 255                                 } else {
 256                                         greatgrandparent->right = node;
 257                                 }
 258                         }
 259                 }
 260         }
 261
 262         tree->root = node;
 263 }
 264
 265 /* (De)constructors */
 266
 267 splay_tree_t *splay_alloc_tree(splay_compare_t compare, splay_action_t delete) {
 268         splay_tree_t *tree;
 269
 270         tree = xzalloc(sizeof(splay_tree_t));
 271         tree->compare = compare;
 272         tree->delete = delete;
 273
 274         return tree;
 275 }
 276
 277 void splay_free_tree(splay_tree_t *tree) {
 278         free(tree);
 279 }
 280
 281 splay_node_t *splay_alloc_node(void) {
 282         return xzalloc(sizeof(splay_node_t));
 283 }
 284
 285 void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
 286         if(node->data && tree->delete) {
 287                 tree->delete(node->data);
 288         }
 289
 290         free(node);
 291 }
 292
 293 /* Searching */
 294
 295 void *splay_search(splay_tree_t *tree, const void *data) {
 296         splay_node_t *node;
 297
 298         node = splay_search_node(tree, data);
 299
 300         return node ? node->data : NULL;
 301 }
 302
 303 void *splay_search_closest(splay_tree_t *tree, const void *data, int *result) {
 304         splay_node_t *node;
 305
 306         node = splay_search_closest_node(tree, data, result);
 307
 308         return node ? node->data : NULL;
 309 }
 310
 311 void *splay_search_closest_smaller(splay_tree_t *tree, const void *data) {
 312         splay_node_t *node;
 313
 314         node = splay_search_closest_smaller_node(tree, data);
 315
 316         return node ? node->data : NULL;
 317 }
 318
 319 void *splay_search_closest_greater(splay_tree_t *tree, const void *data) {
 320         splay_node_t *node;
 321
 322         node = splay_search_closest_greater_node(tree, data);
 323
 324         return node ? node->data : NULL;
 325 }
 326
 327 splay_node_t *splay_search_node(splay_tree_t *tree, const void *data) {
 328         splay_node_t *node;
 329         int result;
 330
 331         node = splay_search_closest_node(tree, data, &result);
 332
 333         return result ? NULL : node;
 334 }
 335
 336 splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const void *data, int *result) {
 337         splay_node_t *node;
 338         int c;
 339
 340         node = tree->root;
 341
 342         if(!node) {
 343                 if(result) {
 344                         *result = 0;
 345                 }
 346
 347                 return NULL;
 348         }
 349
 350         for(;;) {
 351                 c = tree->compare(data, node->data);
 352
 353                 if(c < 0) {
 354                         if(node->left) {
 355                                 node = node->left;
 356                         } else {
 357                                 break;
 358                         }
 359                 } else if(c > 0) {
 360                         if(node->right) {
 361                                 node = node->right;
 362                         } else {
 363                                 break;
 364                         }
 365                 } else {
 366                         break;
 367                 }
 368         }
 369
 370         if(result) {
 371                 *result = c;
 372         }
 373
 374         return node;
 375 }
 376
 377 splay_node_t *splay_search_closest_node(splay_tree_t *tree, const void *data, int *result) {
 378         return splay_top_down(tree, data, result);
 379 }
 380
 381 splay_node_t *splay_search_closest_smaller_node(splay_tree_t *tree, const void *data) {
 382         splay_node_t *node;
 383         int result;
 384
 385         node = splay_search_closest_node(tree, data, &result);
 386
 387         if(result < 0) {
 388                 node = node->prev;
 389         }
 390
 391         return node;
 392 }
 393
 394 splay_node_t *splay_search_closest_greater_node(splay_tree_t *tree, const void *data) {
 395         splay_node_t *node;
 396         int result;
 397
 398         node = splay_search_closest_node(tree, data, &result);
 399
 400         if(result > 0) {
 401                 node = node->next;
 402         }
 403
 404         return node;
 405 }
 406
 407 /* Insertion and deletion */
 408
 409 splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
 410         splay_node_t *closest, *new;
 411         int result;
 412
 413         if(!tree->root) {
 414                 new = splay_alloc_node();
 415                 new->data = data;
 416                 splay_insert_top(tree, new);
 417         } else {
 418                 closest = splay_search_closest_node(tree, data, &result);
 419
 420                 if(!result) {
 421                         return NULL;
 422                 }
 423
 424                 new = splay_alloc_node();
 425                 new->data = data;
 426
 427                 if(result < 0) {
 428                         splay_insert_before(tree, closest, new);
 429                 } else {
 430                         splay_insert_after(tree, closest, new);
 431                 }
 432         }
 433
 434         return new;
 435 }
 436
 437 splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
 438         splay_node_t *closest;
 439         int result;
 440
 441         node->left = node->right = node->parent = node->next = node->prev = NULL;
 442
 443         if(!tree->root) {
 444                 splay_insert_top(tree, node);
 445         } else {
 446                 closest = splay_search_closest_node(tree, node->data, &result);
 447
 448                 if(!result) {
 449                         return NULL;
 450                 }
 451
 452                 if(result < 0) {
 453                         splay_insert_before(tree, closest, node);
 454                 } else {
 455                         splay_insert_after(tree, closest, node);
 456                 }
 457         }
 458
 459         return node;
 460 }
 461
 462 void splay_insert_top(splay_tree_t *tree, splay_node_t *node) {
 463         node->prev = node->next = node->left = node->right = node->parent = NULL;
 464         tree->head = tree->tail = tree->root = node;
 465         tree->count++;
 466         tree->generation++;
 467 }
 468
 469 void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
 470         if(!before) {
 471                 if(tree->tail) {
 472                         splay_insert_after(tree, tree->tail, node);
 473                 } else {
 474                         splay_insert_top(tree, node);
 475                 }
 476
 477                 return;
 478         }
 479
 480         node->next = before;
 481
 482         if((node->prev = before->prev)) {
 483                 before->prev->next = node;
 484         } else {
 485                 tree->head = node;
 486         }
 487
 488         before->prev = node;
 489
 490         splay_bottom_up(tree, before);
 491
 492         node->right = before;
 493         before->parent = node;
 494
 495         if((node->left = before->left)) {
 496                 before->left->parent = node;
 497         }
 498
 499         before->left = NULL;
 500
 501         node->parent = NULL;
 502         tree->root = node;
 503         tree->count++;
 504         tree->generation++;
 505 }
 506
 507 void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
 508         if(!after) {
 509                 if(tree->head) {
 510                         splay_insert_before(tree, tree->head, node);
 511                 } else {
 512                         splay_insert_top(tree, node);
 513                 }
 514
 515                 return;
 516         }
 517
 518         node->prev = after;
 519
 520         if((node->next = after->next)) {
 521                 after->next->prev = node;
 522         } else {
 523                 tree->tail = node;
 524         }
 525
 526         after->next = node;
 527
 528         splay_bottom_up(tree, after);
 529
 530         node->left = after;
 531         after->parent = node;
 532
 533         if((node->right = after->right)) {
 534                 after->right->parent = node;
 535         }
 536
 537         after->right = NULL;
 538
 539         node->parent = NULL;
 540         tree->root = node;
 541         tree->count++;
 542         tree->generation++;
 543 }
 544
 545 splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
 546         splay_node_t *node;
 547
 548         node = splay_search_node(tree, data);
 549
 550         if(node) {
 551                 splay_unlink_node(tree, node);
 552         }
 553
 554         return node;
 555 }
 556
 557 void splay_unlink_node(splay_tree_t *tree, splay_node_t *node) {
 558         if(node->prev) {
 559                 node->prev->next = node->next;
 560         } else {
 561                 tree->head = node->next;
 562         }
 563
 564         if(node->next) {
 565                 node->next->prev = node->prev;
 566         } else {
 567                 tree->tail = node->prev;
 568         }
 569
 570         splay_bottom_up(tree, node);
 571
 572         if(node->prev) {
 573                 node->left->parent = NULL;
 574                 tree->root = node->left;
 575
 576                 if((node->prev->right = node->right)) {
 577                         node->right->parent = node->prev;
 578                 }
 579         } else if(node->next) {
 580                 tree->root = node->right;
 581                 node->right->parent = NULL;
 582         } else {
 583                 tree->root = NULL;
 584         }
 585
 586         tree->count--;
 587         tree->generation++;
 588 }
 589
 590 void splay_delete_node(splay_tree_t *tree, splay_node_t *node) {
 591         splay_unlink_node(tree, node);
 592         splay_free_node(tree, node);
 593 }
 594
 595 void splay_delete(splay_tree_t *tree, void *data) {
 596         splay_node_t *node;
 597
 598         node = splay_search_node(tree, data);
 599
 600         if(node) {
 601                 splay_delete_node(tree, node);
 602         }
 603 }
 604
 605 /* Fast tree cleanup */
 606
 607 void splay_delete_tree(splay_tree_t *tree) {
 608         for(splay_node_t *node = tree->head, *next; node; node = next) {
 609                 next = node->next;
 610                 splay_free_node(tree, node);
 611         }
 612
 613         splay_free_tree(tree);
 614 }
 615
 616 /* Tree walking */
 617
 618 void splay_foreach(const splay_tree_t *tree, splay_action_t action) {
 619         for(splay_node_t *node = tree->head, *next; node; node = next) {
 620                 next = node->next;
 621                 action(node->data);
 622         }
 623 }
 624
 625 void splay_foreach_node(const splay_tree_t *tree, splay_action_t action) {
 626         for(splay_node_t *node = tree->head, *next; node; node = next) {
 627                 next = node->next;
 628                 action(node);
 629         }
 630 }