git.sesse.net Git - vlc/blob - modules/visualization/galaktos/splaytree.c

   1 /*****************************************************************************
   2  * splaytree.c:
   3  *****************************************************************************
   4  * Copyright (C) 2004 the VideoLAN team
   5  * $Id$
   6  *
   7  * Authors: Cyril Deguet <asmax@videolan.org>
   8  *          code from projectM http://xmms-projectm.sourceforge.net
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  23  *****************************************************************************/
  24
  25
  26
  27 /*
  28                 An implementation of top-down splaying
  29                     D. Sleator <sleator@cs.cmu.edu>
  30                              March 1992
  31
  32   "Splay trees", or "self-adjusting search trees" are a simple and
  33   efficient data structure for storing an ordered set.  The data
  34   structure consists of a binary tree, without parent pointers, and no
  35   additional fields.  It allows searching, insertion, deletion,
  36   deletemin, deletemax, splitting, joining, and many other operations,
  37   all with amortized logarithmic performance.  Since the trees adapt to
  38   the sequence of requests, their performance on real access patterns is
  39   typically even better.  Splay trees are described in a number of texts
  40   and papers [1,2,3,4,5].
  41
  42   The code here is adapted from simple top-down splay, at the bottom of
  43   page 669 of [3].  It can be obtained via anonymous ftp from
  44   spade.pc.cs.cmu.edu in directory /usr/sleator/public.
  45
  46   The chief modification here is that the splay operation works even if the
  47   item being splayed is not in the tree, and even if the tree root of the
  48   tree is NULL.  So the line:
  49
  50                               t = splay(i, t);
  51
  52   causes it to search for item with key i in the tree rooted at t.  If it's
  53   there, it is splayed to the root.  If it isn't there, then the node put
  54   at the root is the last one before NULL that would have been reached in a
  55   normal binary search for i.  (It's a neighbor of i in the tree.)  This
  56   allows many other operations to be easily implemented, as shown below.
  57
  58   [1] "Fundamentals of data structures in C", Horowitz, Sahni,
  59        and Anderson-Freed, Computer Science Press, pp 542-547.
  60
  61   [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
  62        Harper Collins, 1991, pp 243-251.
  63   [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
  64        JACM Volume 32, No 3, July 1985, pp 652-686.
  65   [4] "Data Structure and Algorithm Analysis", Mark Weiss,
  66        Benjamin Cummins, 1992, pp 119-130.
  67   [5] "Data Structures, Algorithms, and Performance", Derick Wood,
  68        Addison-Wesley, 1993, pp 367-375.
  69
  70   The following code was written by Daniel Sleator, and is released
  71   in the public domain. It has been heavily modified by Carmelo Piccione,
  72   (cep@andrew.cmu.edu), to suit personal needs,
  73 */
  74
  75
  76 #include "common.h"
  77 #include "fatal.h"
  78
  79 #include "splaytree_types.h"
  80 #include "splaytree.h"
  81
  82
  83
  84 static inline splaynode_t * splay (void * key, splaynode_t * t, int * match_type, int (*compare)());
  85 static inline int free_splaynode(splaynode_t * splaynode, void (*free_key)());
  86 static inline void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode);
  87 static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * t, int (*compare)(), void (*free_key)());
  88 static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)());
  89 static inline void splay_find_below_max_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)());
  90 static inline splaynode_t * new_splaynode(int type, void * key, void * data);
  91 static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree);
  92 static inline int splay_rec_size(splaynode_t * splaynode);
  93
  94 /* Creates a splay tree given a compare key function, copy key function, and free key function.
  95    Ah yes, the wonders of procedural programming */
  96 inline splaytree_t * create_splaytree(int (*compare)(), void * (*copy_key)(), void (*free_key)()) {
  97
  98   splaytree_t * splaytree;
  99
 100   /* Allocate memory for the splaytree struct */
 101   if ((splaytree = (splaytree_t*)malloc(sizeof(splaytree_t))) == NULL)
 102     return NULL;
 103
 104   /* Set struct entries */
 105   splaytree->root = NULL;
 106   splaytree->compare = compare;
 107   splaytree->copy_key = copy_key;
 108   splaytree->free_key = free_key;
 109
 110   /* Return instantiated splay tree */
 111   return splaytree;
 112 }
 113
 114 /* Destroys a splay tree */
 115 inline int destroy_splaytree(splaytree_t * splaytree) {
 116
 117   /* Null argument check */
 118   if (splaytree == NULL)
 119     return FAILURE;
 120
 121   /* Recursively free all splaynodes in tree */
 122   free_splaynode(splaytree->root, splaytree->free_key);
 123
 124   /* Free the splaytree struct itself */
 125   free(splaytree);
 126
 127   /* Done, return success */
 128   return SUCCESS;
 129
 130 }
 131
 132 /* Recursively free all the splaynodes */
 133 static inline int free_splaynode(splaynode_t * splaynode, void (*free_key)()) {
 134
 135   /* Ok if this happens, a recursive base case */
 136   if (splaynode == NULL)
 137     return SUCCESS;
 138
 139   /* Free left node */
 140   free_splaynode(splaynode->left, free_key);
 141
 142   /* Free right node */
 143   free_splaynode(splaynode->right, free_key);
 144
 145   /* Free this node's key */
 146   free_key(splaynode->key);
 147
 148   /* Note that the data pointers are not freed here.
 149      Should be freed with a splay traversal function */
 150
 151   /* Free the splaynode structure itself */
 152   free(splaynode);
 153
 154   /* Finished, return success */
 155   return SUCCESS;
 156
 157 }
 158
 159 /* Traverses the entire splay tree with the given function func_ptr */
 160 inline void splay_traverse(void (*func_ptr)(), splaytree_t * splaytree) {
 161
 162   /* Null argument check */
 163
 164   if (splaytree == NULL)
 165     return;
 166   if (func_ptr == NULL)
 167         return;
 168
 169   /* Call recursive helper function */
 170   splay_traverse_helper(func_ptr, splaytree->root);
 171
 172   return;
 173 }
 174
 175 /* Helper function to traverse the entire splaytree */
 176 static inline void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode) {
 177
 178   /* Normal if this happens, its a base case of recursion */
 179   if (splaynode == NULL)
 180     return;
 181
 182   /* Recursively traverse to the left */
 183   splay_traverse_helper(func_ptr, splaynode->left);
 184
 185
 186   /* Node is a of regular type, so its ok to perform the function on it */
 187   if (splaynode->type == REGULAR_NODE_TYPE)
 188         func_ptr(splaynode->data);
 189
 190   /* Node is of symbolic link type, do nothing */
 191   else if (splaynode->type == SYMBOLIC_NODE_TYPE)
 192         ;
 193
 194   /* Unknown node type */
 195   else
 196     ;
 197
 198   /* Recursively traverse to the right */
 199   splay_traverse_helper(func_ptr, splaynode->right);
 200
 201   /* Done */
 202   return;
 203 }
 204
 205 /* Find the node corresponding to the given key in splaytree, return its data pointer */
 206 inline void * splay_find(void * key, splaytree_t * splaytree) {
 207
 208   splaynode_t * splaynode;
 209   int match_type;
 210
 211   if (key == NULL)
 212           return NULL;
 213
 214   if (splaytree == NULL)
 215           return NULL;
 216
 217   splaynode = splaytree->root;
 218
 219   /* Bring the targeted splay node to the top of the splaytree */
 220   splaynode = splay(key, splaynode, &match_type, splaytree->compare);
 221   splaytree->root = splaynode;
 222
 223
 224   /* We only want perfect matches, so return null when match isn't perfect */
 225   if (match_type == CLOSEST_MATCH)
 226     return NULL;
 227
 228   /* This shouldn't happen because of the match type check, but whatever */
 229   if (splaytree->root == NULL)
 230           return NULL;
 231
 232   /* Node is a regular type, return its data pointer */
 233   if (splaytree->root->type == REGULAR_NODE_TYPE) /* regular node */
 234         return splaytree->root->data;
 235
 236   /* If the node is a symlink, pursue one link */
 237   if (splaytree->root->type == SYMBOLIC_NODE_TYPE) /* symbolic node */
 238         return ((splaynode_t*)splaytree->root->data)->data;
 239
 240
 241   /* Unknown type */
 242   return NULL;
 243 }
 244
 245 /* Gets the splaynode that the given key points to */
 246 inline splaynode_t * get_splaynode_of(void * key, splaytree_t * splaytree) {
 247
 248   splaynode_t * splaynode;
 249   int match_type;
 250
 251   /* Null argument checks */
 252   if (splaytree == NULL)
 253           return NULL;
 254
 255   if (key == NULL)
 256           return NULL;
 257
 258   splaynode = splaytree->root;
 259
 260   /* Find the splaynode */
 261   splaynode = splay(key, splaynode, &match_type, splaytree->compare);
 262   splaytree->root = splaynode;
 263
 264   /* Only perfect matches are valid */
 265   if (match_type == CLOSEST_MATCH)
 266     return NULL;
 267
 268   /* Return the perfect match splay node */
 269   return splaynode;
 270 }
 271
 272 /* Finds the desired node, and changes the tree such that it is the root */
 273 static inline splaynode_t * splay (void * key, splaynode_t * t, int * match_type, int (*compare)()) {
 274
 275 /* Simple top down splay, not requiring key to be in the tree t.
 276    What it does is described above. */
 277
 278     splaynode_t N, *l, *r, *y;
 279     *match_type = CLOSEST_MATCH;
 280
 281         if (t == NULL) return t;
 282     N.left = N.right = NULL;
 283     l = r = &N;
 284
 285     for (;;) {
 286         if (compare(key, t->key) < 0) {
 287             if (t->left == NULL) break;
 288             if (compare(key, t->left->key) < 0) {
 289                 y = t->left;                           /* rotate right */
 290                 t->left = y->right;
 291                 y->right = t;
 292                 t = y;
 293                 if (t->left == NULL) break;
 294             }
 295             r->left = t;                               /* link right */
 296             r = t;
 297             t = t->left;
 298         } else if (compare(key, t->key) > 0) {
 299             if (t->right == NULL) break;
 300             if (compare(key, t->right->key) > 0) {
 301                 y = t->right;                          /* rotate left */
 302                 t->right = y->left;
 303                 y->left = t;
 304                 t = y;
 305                 if (t->right == NULL) break;
 306             }
 307             l->right = t;                              /* link left */
 308             l = t;
 309             t = t->right;
 310         } else {
 311           *match_type = PERFECT_MATCH;
 312           break;
 313         }
 314     }
 315     l->right = t->left;                                /* assemble */
 316     r->left = t->right;
 317     t->left = N.right;
 318     t->right = N.left;
 319
 320     return t;
 321
 322     //return NULL;
 323 }
 324
 325 /* Deletes a splay node from a splay tree. If the node doesn't exist
 326    then nothing happens */
 327 inline int splay_delete(void * key, splaytree_t * splaytree) {
 328
 329   splaynode_t * splaynode;
 330
 331   /* Use helper function to delete the node and return the resulting tree */
 332   if ((splaynode = splay_delete_helper(key, splaytree->root, splaytree->compare, splaytree->free_key)) == NULL)
 333           return FAILURE;
 334
 335   /* Set new splaytree root equal to the returned splaynode after deletion */
 336   splaytree->root = splaynode;
 337
 338   /* Finished, no errors */
 339   return SUCCESS;
 340 }
 341
 342 /* Deletes a splay node */
 343 static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
 344
 345     splaynode_t * new_root;
 346     int match_type;
 347
 348         /* Argument check */
 349     if (splaynode == NULL)
 350                 return NULL;
 351
 352     splaynode = splay(key, splaynode, &match_type, compare);
 353
 354         /* If entry wasn't found, quit here */
 355         if (match_type == CLOSEST_MATCH)
 356                 return NULL;
 357
 358         /* If the targeted node's left pointer is null, then set the new root
 359            equal to the splaynode's right child */
 360         if (splaynode->left == NULL) {
 361             new_root = splaynode->right;
 362         }
 363
 364         /* Otherwise, do something I don't currently understand */
 365         else {
 366             new_root = splay(key, splaynode->left, &match_type, compare);
 367             new_root->right = splaynode->right;
 368         }
 369
 370         /* Set splay nodes children pointers to null */
 371         splaynode->left = splaynode->right = NULL;
 372
 373         /* Free the splaynode (and only this node since its children are now empty */
 374         free_splaynode(splaynode, free_key);
 375
 376         /* Return the resulting tree */
 377         return new_root;
 378
 379 }
 380
 381 /* Create a new splay node type */
 382 static inline splaynode_t * new_splaynode(int type, void * key, void * data) {
 383         splaynode_t * splaynode;
 384         /* Argument checks */
 385         if (data == NULL)
 386                 return NULL;
 387
 388         if (key == NULL)
 389                 return NULL;
 390
 391         /* Creates the new splay node struct */
 392         if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
 393                 return NULL;
 394
 395         splaynode->data = data;
 396         splaynode->type = type;
 397         splaynode->key = key;
 398
 399         /* Return the new splay node */
 400         return splaynode;
 401 }
 402
 403 /* Inserts a link into the splay tree */
 404 inline int splay_insert_link(void * alias_key, void * orig_key, splaytree_t * splaytree) {
 405
 406    splaynode_t * splaynode, * data_node;
 407    void * key_clone;
 408
 409    /* Null arguments */
 410    if (splaytree == NULL)
 411                 return FAILURE;
 412
 413    if (alias_key == NULL)
 414                 return FAILURE;
 415
 416    if (orig_key == NULL)
 417                 return FAILURE;
 418
 419    /* Find the splaynode corresponding to the original key */
 420    if ((data_node = get_splaynode_of(orig_key, splaytree)) == NULL)
 421            return FAILURE;
 422
 423    /* Create a new splay node of symbolic link type */
 424    if ((splaynode = new_splaynode(SYMBOLIC_NODE_TYPE, (key_clone = splaytree->copy_key(alias_key)), data_node)) == NULL) {
 425                 splaytree->free_key(key_clone);
 426                 return OUTOFMEM_ERROR;
 427    }
 428
 429    /* Insert the splaynode into the given splaytree */
 430    if ((splay_insert_node(splaynode, splaytree)) < 0) {
 431      splaynode->left=splaynode->right = NULL;
 432      free_splaynode(splaynode, splaytree->free_key);
 433      return FAILURE;
 434    }
 435
 436    /* Done, return success */
 437    return SUCCESS;
 438 }
 439
 440 /* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
 441 inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {
 442
 443         splaynode_t * splaynode;
 444         void * key_clone;
 445
 446         /* Null argument checks */
 447         if (splaytree == NULL) {
 448             return FAILURE;
 449         }
 450
 451         if (key == NULL)
 452                 return FAILURE;
 453
 454         /* Clone the key argument */
 455         key_clone = splaytree->copy_key(key);
 456
 457         /* Create a new splaynode (of regular type) */
 458         if ((splaynode = new_splaynode(REGULAR_NODE_TYPE, key_clone, data)) == NULL) {
 459                 splaytree->free_key(key_clone);
 460                 return OUTOFMEM_ERROR;
 461         }
 462
 463
 464         /* Inserts the splaynode into the splaytree */
 465         if (splay_insert_node(splaynode, splaytree) < 0) {
 466           splaynode->left=splaynode->right=NULL;
 467           free_splaynode(splaynode, splaytree->free_key);
 468           return FAILURE;
 469         }
 470
 471
 472         return SUCCESS;
 473 }
 474
 475 /* Helper function to insert splaynodes into the splaytree */
 476 static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree) {
 477   int match_type;
 478   int cmpval;
 479   void * key;
 480   splaynode_t * t;
 481
 482   /* Null argument checks */
 483   if (splaytree == NULL)
 484     return FAILURE;
 485
 486   if (splaynode == NULL)
 487         return FAILURE;
 488
 489   key = splaynode->key;
 490
 491   t = splaytree->root;
 492
 493
 494   /* Root is null, insert splaynode here */
 495   if (t == NULL) {
 496         splaynode->left = splaynode->right = NULL;
 497         splaytree->root = splaynode;
 498         return SUCCESS;
 499
 500   }
 501
 502   t = splay(key, t, &match_type, splaytree->compare);
 503
 504   if ((cmpval = splaytree->compare(key,t->key)) < 0) {
 505         splaynode->left = t->left;
 506         splaynode->right = t;
 507         t->left = NULL;
 508         splaytree->root = splaynode;
 509         return SUCCESS;
 510
 511   }
 512
 513   else if (cmpval > 0) {
 514         splaynode->right = t->right;
 515         splaynode->left = t;
 516         t->right = NULL;
 517         splaytree->root = splaynode;
 518         return SUCCESS;
 519    }
 520
 521    /* Item already exists in tree, don't reinsert */
 522   else {
 523
 524     return FAILURE;
 525   }
 526 }
 527
 528 /* Returns the 'maximum' key that is less than the given key in the splaytree */
 529 inline void * splay_find_below_max(void * key, splaytree_t * splaytree) {
 530
 531         void * closest_key;
 532
 533         if (splaytree == NULL)
 534                 return NULL;
 535         if (splaytree->root == NULL)
 536                 return NULL;
 537         if (key == NULL)
 538                 return NULL;
 539
 540         closest_key = NULL;
 541
 542         splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
 543
 544         if (closest_key == NULL) return NULL;
 545         return splay_find(closest_key, splaytree);
 546 }
 547
 548
 549 /* Returns the 'minimum' key that is greater than the given key in the splaytree */
 550 inline void * splay_find_above_min(void * key, splaytree_t * splaytree) {
 551
 552         void * closest_key;
 553
 554         if (splaytree == NULL)
 555                 return NULL;
 556         if (splaytree->root == NULL)
 557                 return NULL;
 558         if (key == NULL)
 559                 return NULL;
 560         closest_key = NULL;
 561
 562         splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
 563
 564         if (closest_key == NULL) {
 565                 return NULL;
 566         }
 567
 568         return splay_find(closest_key, splaytree);
 569 }
 570
 571 /* Helper function */
 572 static inline void splay_find_below_max_helper(void * min_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
 573
 574                 /* Empty root, return*/
 575                 if (root == NULL)
 576                         return;
 577
 578                 /* The root key is less than the previously found closest key.
 579                    Also try to make the key non null if the value is less than the max key */
 580
 581                 if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
 582
 583                         /*  The root key is less than the given max key, so this is the
 584                                 smallest change from the given max key */
 585                         if (compare(root->key, min_key) > 0) {
 586
 587                                 *closest_key = root->key;
 588
 589                                 /* Look right again in case even a greater key exists that is
 590                                    still less than the given max key */
 591                                 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
 592                         }
 593
 594                         /* The root key is greater than the given max key, and greater than
 595                            the closest key, so search left */
 596                         else {
 597                                 splay_find_below_max_helper(min_key, closest_key, root->right, compare);
 598                         }
 599                 }
 600
 601                 /* The root key is less than the found closest key, search right */
 602                 else {
 603                                 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
 604                 }
 605
 606 }
 607
 608 /* Helper function */
 609 static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
 610
 611                 /* Empty root, stop */
 612                 if (root == NULL)
 613                         return;
 614
 615                 /* The root key is greater than the previously found closest key.
 616                    Also try to make the key non null if the value is less than the min key */
 617
 618                 if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
 619
 620                         /*  The root key is greater than the given min key, so this is the
 621                                 smallest change from the given min key */
 622                         if (compare(root->key, max_key) < 0) {
 623
 624                                 *closest_key = root->key;
 625
 626                            /* Look left again in case even a smaller key exists that is
 627                                   still greater than the given min key */
 628                                 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
 629                         }
 630
 631                         /* The root key is less than the given min key, and less than
 632                            the closest key, so search right */
 633                         else {
 634                                 splay_find_above_min_helper(max_key, closest_key, root->left, compare);
 635                         }
 636                 }
 637
 638                 /* The root key is greater than the found closest key, search left */
 639                 else {
 640                                 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
 641                 }
 642 }
 643
 644 /* Find the minimum entry of the splay tree */
 645 inline void * splay_find_min(splaytree_t * t) {
 646
 647         splaynode_t * splaynode;
 648
 649         if (t == NULL)
 650                 return NULL;
 651         if (t->root == NULL)
 652                 return NULL;
 653
 654         splaynode = t->root;
 655
 656         while (splaynode->left != NULL)
 657                 splaynode= splaynode->left;
 658
 659         return splaynode->data;
 660 }
 661
 662
 663 /* Find the maximum entry of the splay tree */
 664 inline void * splay_find_max(splaytree_t * t) {
 665
 666         splaynode_t * splaynode;
 667
 668         if (t == NULL)
 669                 return NULL;
 670         if (t->root == NULL)
 671                 return NULL;
 672
 673         splaynode = t->root;
 674
 675         while (splaynode->right != NULL) {
 676           printf("data:%d\n", *(int*)splaynode->key);
 677                 splaynode = splaynode->right;
 678         }
 679         return splaynode->data;
 680 }
 681
 682 inline int splay_size(splaytree_t * t) {
 683
 684         if (t == NULL)
 685           return 0;
 686         if (t->root == NULL)
 687           return 0;
 688
 689         return splay_rec_size(t->root);
 690
 691 }
 692
 693 static inline int splay_rec_size(splaynode_t * splaynode) {
 694
 695   if (!splaynode)
 696     return 0;
 697
 698   return 1 + splay_rec_size(splaynode->left) + splay_rec_size(splaynode->right);
 699
 700 }