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