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 void splay_free_tree(splay_tree_t *tree) {
 281         free(tree);
 282 }
 283
 284 splay_node_t *splay_alloc_node(void) {
 285         return xzalloc(sizeof(splay_node_t));
 286 }
 287
 288 void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
 289         if(node->data && tree->delete) {
 290                 tree->delete(node->data);
 291         }
 292
 293         free(node);
 294 }
 295
 296 /* Searching */
 297
 298 void *splay_search(splay_tree_t *tree, const void *data) {
 299         splay_node_t *node;
 300
 301         node = splay_search_node(tree, data);
 302
 303         return node ? node->data : NULL;
 304 }
 305
 306 void *splay_search_closest(splay_tree_t *tree, const void *data, int *result) {
 307         splay_node_t *node;
 308
 309         node = splay_search_closest_node(tree, data, result);
 310
 311         return node ? node->data : NULL;
 312 }
 313
 314 void *splay_search_closest_smaller(splay_tree_t *tree, const void *data) {
 315         splay_node_t *node;
 316
 317         node = splay_search_closest_smaller_node(tree, data);
 318
 319         return node ? node->data : NULL;
 320 }
 321
 322 void *splay_search_closest_greater(splay_tree_t *tree, const void *data) {
 323         splay_node_t *node;
 324
 325         node = splay_search_closest_greater_node(tree, data);
 326
 327         return node ? node->data : NULL;
 328 }
 329
 330 splay_node_t *splay_search_node(splay_tree_t *tree, const void *data) {
 331         splay_node_t *node;
 332         int result;
 333
 334         node = splay_search_closest_node(tree, data, &result);
 335
 336         return result ? NULL : node;
 337 }
 338
 339 splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const void *data, int *result) {
 340         splay_node_t *node;
 341         int c;
 342
 343         node = tree->root;
 344
 345         if(!node) {
 346                 if(result) {
 347                         *result = 0;
 348                 }
 349
 350                 return NULL;
 351         }
 352
 353         for(;;) {
 354                 c = tree->compare(data, node->data);
 355
 356                 if(c < 0) {
 357                         if(node->left) {
 358                                 node = node->left;
 359                         } else {
 360                                 break;
 361                         }
 362                 } else if(c > 0) {
 363                         if(node->right) {
 364                                 node = node->right;
 365                         } else {
 366                                 break;
 367                         }
 368                 } else {
 369                         break;
 370                 }
 371         }
 372
 373         if(result) {
 374                 *result = c;
 375         }
 376
 377         return node;
 378 }
 379
 380 splay_node_t *splay_search_closest_node(splay_tree_t *tree, const void *data, int *result) {
 381         return splay_top_down(tree, data, result);
 382 }
 383
 384 splay_node_t *splay_search_closest_smaller_node(splay_tree_t *tree, const void *data) {
 385         splay_node_t *node;
 386         int result;
 387
 388         node = splay_search_closest_node(tree, data, &result);
 389
 390         if(result < 0) {
 391                 node = node->prev;
 392         }
 393
 394         return node;
 395 }
 396
 397 splay_node_t *splay_search_closest_greater_node(splay_tree_t *tree, const void *data) {
 398         splay_node_t *node;
 399         int result;
 400
 401         node = splay_search_closest_node(tree, data, &result);
 402
 403         if(result > 0) {
 404                 node = node->next;
 405         }
 406
 407         return node;
 408 }
 409
 410 /* Insertion and deletion */
 411
 412 void splay_insert_top(splay_tree_t *tree, splay_node_t *node) {
 413         node->prev = node->next = node->left = node->right = node->parent = NULL;
 414         tree->head = tree->tail = tree->root = node;
 415         tree->count++;
 416 }
 417
 418 void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
 419         if(!before) {
 420                 if(tree->tail) {
 421                         splay_insert_after(tree, tree->tail, node);
 422                 } else {
 423                         splay_insert_top(tree, node);
 424                 }
 425
 426                 return;
 427         }
 428
 429         node->next = before;
 430
 431         if((node->prev = before->prev)) {
 432                 before->prev->next = node;
 433         } else {
 434                 tree->head = node;
 435         }
 436
 437         before->prev = node;
 438
 439         splay_bottom_up(tree, before);
 440
 441         node->right = before;
 442         before->parent = node;
 443
 444         if((node->left = before->left)) {
 445                 before->left->parent = node;
 446         }
 447
 448         before->left = NULL;
 449
 450         node->parent = NULL;
 451         tree->root = node;
 452         tree->count++;
 453 }
 454
 455 void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
 456         if(!after) {
 457                 if(tree->head) {
 458                         splay_insert_before(tree, tree->head, node);
 459                 } else {
 460                         splay_insert_top(tree, node);
 461                 }
 462
 463                 return;
 464         }
 465
 466         node->prev = after;
 467
 468         if((node->next = after->next)) {
 469                 after->next->prev = node;
 470         } else {
 471                 tree->tail = node;
 472         }
 473
 474         after->next = node;
 475
 476         splay_bottom_up(tree, after);
 477
 478         node->left = after;
 479         after->parent = node;
 480
 481         if((node->right = after->right)) {
 482                 after->right->parent = node;
 483         }
 484
 485         after->right = NULL;
 486
 487         node->parent = NULL;
 488         tree->root = node;
 489         tree->count++;
 490 }
 491
 492 splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
 493         splay_node_t *closest, *new;
 494         int result;
 495
 496         if(!tree->root) {
 497                 new = splay_alloc_node();
 498                 new->data = data;
 499                 splay_insert_top(tree, new);
 500         } else {
 501                 closest = splay_search_closest_node(tree, data, &result);
 502
 503                 if(!result) {
 504                         return NULL;
 505                 }
 506
 507                 new = splay_alloc_node();
 508                 new->data = data;
 509
 510                 if(result < 0) {
 511                         splay_insert_before(tree, closest, new);
 512                 } else {
 513                         splay_insert_after(tree, closest, new);
 514                 }
 515         }
 516
 517         return new;
 518 }
 519
 520 splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
 521         splay_node_t *closest;
 522         int result;
 523
 524         node->left = node->right = node->parent = node->next = node->prev = NULL;
 525
 526         if(!tree->root) {
 527                 splay_insert_top(tree, node);
 528         } else {
 529                 closest = splay_search_closest_node(tree, node->data, &result);
 530
 531                 if(!result) {
 532                         return NULL;
 533                 }
 534
 535                 if(result < 0) {
 536                         splay_insert_before(tree, closest, node);
 537                 } else {
 538                         splay_insert_after(tree, closest, node);
 539                 }
 540         }
 541
 542         return node;
 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         assert(tree->count);
 559         assert(node->prev || tree->head == node);
 560         assert(node->next || tree->tail == node);
 561
 562         if(node->prev) {
 563                 node->prev->next = node->next;
 564         } else {
 565                 tree->head = node->next;
 566         }
 567
 568         if(node->next) {
 569                 node->next->prev = node->prev;
 570         } else {
 571                 tree->tail = node->prev;
 572         }
 573
 574         splay_bottom_up(tree, node);
 575
 576         if(node->prev) {
 577                 node->left->parent = NULL;
 578                 tree->root = node->left;
 579
 580                 if((node->prev->right = node->right)) {
 581                         node->right->parent = node->prev;
 582                 }
 583         } else if(node->next) {
 584                 tree->root = node->right;
 585                 node->right->parent = NULL;
 586         } else {
 587                 tree->root = NULL;
 588         }
 589
 590         tree->count--;
 591 }
 592
 593 void splay_delete_node(splay_tree_t *tree, splay_node_t *node) {
 594         splay_unlink_node(tree, node);
 595         splay_free_node(tree, node);
 596 }
 597
 598 void splay_delete(splay_tree_t *tree, void *data) {
 599         splay_node_t *node;
 600
 601         node = splay_search_node(tree, data);
 602
 603         if(node) {
 604                 splay_delete_node(tree, node);
 605         }
 606 }
 607
 608 /* Fast tree cleanup */
 609
 610 void splay_delete_tree(splay_tree_t *tree) {
 611         for(splay_node_t *node = tree->head, *next; node; node = next) {
 612                 next = node->next;
 613                 splay_free_node(tree, node);
 614                 tree->count--;
 615         }
 616
 617         assert(!tree->count);
 618         free(tree);
 619 }
 620
 621 /* Tree walking */
 622
 623 void splay_foreach(const splay_tree_t *tree, splay_action_t action) {
 624         for(splay_node_t *node = tree->head, *next; node; node = next) {
 625                 next = node->next;
 626                 action(node->data);
 627         }
 628 }
 629
 630 void splay_foreach_node(const splay_tree_t *tree, splay_action_t action) {
 631         for(splay_node_t *node = tree->head, *next; node; node = next) {
 632                 next = node->next;
 633                 action(node);
 634         }
 635 }