git.meshlink.io Git - meshlink/blob - src/splay_tree.c

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