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 #include <stdlib.h>
  76
  77 #include "common.h"
  78 #include "fatal.h"
  79
  80 #include "splaytree_types.h"
  81 #include "splaytree.h"
  82
  83
  84
  85 static inline splaynode_t * splay (void * key, splaynode_t * t, int * match_type, int (*compare)());
  86 static inline int free_splaynode(splaynode_t * splaynode, void (*free_key)());
  87 static inline void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode);
  88 static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * t, int (*compare)(), void (*free_key)());
  89 static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)());
  90 static inline void splay_find_below_max_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)());
  91 static inline splaynode_t * new_splaynode(int type, void * key, void * data);
  92 static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree);
  93 static inline int splay_rec_size(splaynode_t * splaynode);
  94
  95 /* Creates a splay tree given a compare key function, copy key function, and free key function.
  96    Ah yes, the wonders of procedural programming */
  97 inline splaytree_t * create_splaytree(int (*compare)(), void * (*copy_key)(), void (*free_key)()) {
  98
  99   splaytree_t * splaytree;
 100
 101   /* Allocate memory for the splaytree struct */
 102   if ((splaytree = (splaytree_t*)malloc(sizeof(splaytree_t))) == NULL)
 103     return NULL;
 104
 105   /* Set struct entries */
 106   splaytree->root = NULL;
 107   splaytree->compare = compare;
 108   splaytree->copy_key = copy_key;
 109   splaytree->free_key = free_key;
 110
 111   /* Return instantiated splay tree */
 112   return splaytree;
 113 }
 114
 115 /* Destroys a splay tree */
 116 inline int destroy_splaytree(splaytree_t * splaytree) {
 117
 118   /* Null argument check */
 119   if (splaytree == NULL)
 120     return FAILURE;
 121
 122   /* Recursively free all splaynodes in tree */
 123   free_splaynode(splaytree->root, splaytree->free_key);
 124
 125   /* Free the splaytree struct itself */
 126   free(splaytree);
 127
 128   /* Done, return success */
 129   return SUCCESS;
 130
 131 }
 132
 133 /* Recursively free all the splaynodes */
 134 static inline int free_splaynode(splaynode_t * splaynode, void (*free_key)()) {
 135
 136   /* Ok if this happens, a recursive base case */
 137   if (splaynode == NULL)
 138     return SUCCESS;
 139
 140   /* Free left node */
 141   free_splaynode(splaynode->left, free_key);
 142
 143   /* Free right node */
 144   free_splaynode(splaynode->right, free_key);
 145
 146   /* Free this node's key */
 147   free_key(splaynode->key);
 148
 149   /* Note that the data pointers are not freed here.
 150      Should be freed with a splay traversal function */
 151
 152   /* Free the splaynode structure itself */
 153   free(splaynode);
 154
 155   /* Finished, return success */
 156   return SUCCESS;
 157
 158 }
 159
 160 /* Traverses the entire splay tree with the given function func_ptr */
 161 inline void splay_traverse(void (*func_ptr)(), splaytree_t * splaytree) {
 162
 163   /* Null argument check */
 164
 165   if (splaytree == NULL)
 166     return;
 167   if (func_ptr == NULL)
 168     return;
 169
 170   /* Call recursive helper function */
 171   splay_traverse_helper(func_ptr, splaytree->root);
 172
 173   return;
 174 }
 175
 176 /* Helper function to traverse the entire splaytree */
 177 static inline void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode) {
 178
 179   /* Normal if this happens, its a base case of recursion */
 180   if (splaynode == NULL)
 181     return;
 182
 183   /* Recursively traverse to the left */
 184   splay_traverse_helper(func_ptr, splaynode->left);
 185
 186
 187   /* Node is a of regular type, so its ok to perform the function on it */
 188   if (splaynode->type == REGULAR_NODE_TYPE)
 189       func_ptr(splaynode->data);
 190
 191   /* Node is of symbolic link type, do nothing */
 192   else if (splaynode->type == SYMBOLIC_NODE_TYPE)
 193     ;
 194
 195   /* Unknown node type */
 196   else
 197     ;
 198
 199   /* Recursively traverse to the right */
 200   splay_traverse_helper(func_ptr, splaynode->right);
 201
 202   /* Done */
 203   return;
 204 }
 205
 206 /* Find the node corresponding to the given key in splaytree, return its data pointer */
 207 inline void * splay_find(void * key, splaytree_t * splaytree) {
 208
 209   splaynode_t * splaynode;
 210   int match_type;
 211
 212   if (key == NULL)
 213       return NULL;
 214
 215   if (splaytree == NULL)
 216       return NULL;
 217
 218   splaynode = splaytree->root;
 219
 220   /* Bring the targeted splay node to the top of the splaytree */
 221   splaynode = splay(key, splaynode, &match_type, splaytree->compare);
 222   splaytree->root = splaynode;
 223
 224
 225   /* We only want perfect matches, so return null when match isn't perfect */
 226   if (match_type == CLOSEST_MATCH)
 227     return NULL;
 228
 229   /* This shouldn't happen because of the match type check, but whatever */
 230   if (splaytree->root == NULL)
 231       return NULL;
 232
 233   /* Node is a regular type, return its data pointer */
 234   if (splaytree->root->type == REGULAR_NODE_TYPE) /* regular node */
 235       return splaytree->root->data;
 236
 237   /* If the node is a symlink, pursue one link */
 238   if (splaytree->root->type == SYMBOLIC_NODE_TYPE) /* symbolic node */
 239     return ((splaynode_t*)splaytree->root->data)->data;
 240
 241
 242   /* Unknown type */
 243   return NULL;
 244 }
 245
 246 /* Gets the splaynode that the given key points to */
 247 inline splaynode_t * get_splaynode_of(void * key, splaytree_t * splaytree) {
 248
 249   splaynode_t * splaynode;
 250   int match_type;
 251
 252   /* Null argument checks */
 253   if (splaytree == NULL)
 254       return NULL;
 255
 256   if (key == NULL)
 257       return NULL;
 258
 259   splaynode = splaytree->root;
 260
 261   /* Find the splaynode */
 262   splaynode = splay(key, splaynode, &match_type, splaytree->compare);
 263   splaytree->root = splaynode;
 264
 265   /* Only perfect matches are valid */
 266   if (match_type == CLOSEST_MATCH)
 267     return NULL;
 268
 269   /* Return the perfect match splay node */
 270   return splaynode;
 271 }
 272
 273 /* Finds the desired node, and changes the tree such that it is the root */
 274 static inline splaynode_t * splay (void * key, splaynode_t * t, int * match_type, int (*compare)()) {
 275
 276 /* Simple top down splay, not requiring key to be in the tree t.
 277    What it does is described above. */
 278
 279     splaynode_t N, *l, *r, *y;
 280     *match_type = CLOSEST_MATCH;
 281
 282     if (t == NULL) return t;
 283     N.left = N.right = NULL;
 284     l = r = &N;
 285
 286     for (;;) {
 287     if (compare(key, t->key) < 0) {
 288         if (t->left == NULL) break;
 289         if (compare(key, t->left->key) < 0) {
 290         y = t->left;                           /* rotate right */
 291         t->left = y->right;
 292         y->right = t;
 293         t = y;
 294         if (t->left == NULL) break;
 295         }
 296         r->left = t;                               /* link right */
 297         r = t;
 298         t = t->left;
 299     } else if (compare(key, t->key) > 0) {
 300         if (t->right == NULL) break;
 301         if (compare(key, t->right->key) > 0) {
 302         y = t->right;                          /* rotate left */
 303         t->right = y->left;
 304         y->left = t;
 305         t = y;
 306         if (t->right == NULL) break;
 307         }
 308         l->right = t;                              /* link left */
 309         l = t;
 310         t = t->right;
 311     } else {
 312       *match_type = PERFECT_MATCH;
 313       break;
 314     }
 315     }
 316     l->right = t->left;                                /* assemble */
 317     r->left = t->right;
 318     t->left = N.right;
 319     t->right = N.left;
 320
 321     return t;
 322
 323     //return NULL;
 324 }
 325
 326 /* Deletes a splay node from a splay tree. If the node doesn't exist
 327    then nothing happens */
 328 inline int splay_delete(void * key, splaytree_t * splaytree) {
 329
 330   splaynode_t * splaynode;
 331
 332   /* Use helper function to delete the node and return the resulting tree */
 333   if ((splaynode = splay_delete_helper(key, splaytree->root, splaytree->compare, splaytree->free_key)) == NULL)
 334       return FAILURE;
 335
 336   /* Set new splaytree root equal to the returned splaynode after deletion */
 337   splaytree->root = splaynode;
 338
 339   /* Finished, no errors */
 340   return SUCCESS;
 341 }
 342
 343 /* Deletes a splay node */
 344 static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
 345
 346     splaynode_t * new_root;
 347     int match_type;
 348
 349     /* Argument check */
 350     if (splaynode == NULL)
 351         return NULL;
 352
 353     splaynode = splay(key, splaynode, &match_type, compare);
 354
 355     /* If entry wasn't found, quit here */
 356     if (match_type == CLOSEST_MATCH)
 357         return NULL;
 358
 359     /* If the targeted node's left pointer is null, then set the new root
 360        equal to the splaynode's right child */
 361     if (splaynode->left == NULL) {
 362         new_root = splaynode->right;
 363     }
 364
 365     /* Otherwise, do something I don't currently understand */
 366     else {
 367         new_root = splay(key, splaynode->left, &match_type, compare);
 368         new_root->right = splaynode->right;
 369     }
 370
 371     /* Set splay nodes children pointers to null */
 372     splaynode->left = splaynode->right = NULL;
 373
 374     /* Free the splaynode (and only this node since its children are now empty */
 375     free_splaynode(splaynode, free_key);
 376
 377     /* Return the resulting tree */
 378     return new_root;
 379
 380 }
 381
 382 /* Create a new splay node type */
 383 static inline splaynode_t * new_splaynode(int type, void * key, void * data) {
 384     splaynode_t * splaynode;
 385     /* Argument checks */
 386     if (data == NULL)
 387         return NULL;
 388
 389     if (key == NULL)
 390         return NULL;
 391
 392     /* Creates the new splay node struct */
 393     if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
 394         return NULL;
 395
 396     splaynode->data = data;
 397     splaynode->type = type;
 398     splaynode->key = key;
 399
 400     /* Return the new splay node */
 401     return splaynode;
 402 }
 403
 404 /* Inserts a link into the splay tree */
 405 inline int splay_insert_link(void * alias_key, void * orig_key, splaytree_t * splaytree) {
 406
 407    splaynode_t * splaynode, * data_node;
 408    void * key_clone;
 409
 410    /* Null arguments */
 411    if (splaytree == NULL)
 412         return FAILURE;
 413
 414    if (alias_key == NULL)
 415            return FAILURE;
 416
 417    if (orig_key == NULL)
 418            return FAILURE;
 419
 420    /* Find the splaynode corresponding to the original key */
 421    if ((data_node = get_splaynode_of(orig_key, splaytree)) == NULL)
 422        return FAILURE;
 423
 424    /* Create a new splay node of symbolic link type */
 425    if ((splaynode = new_splaynode(SYMBOLIC_NODE_TYPE, (key_clone = splaytree->copy_key(alias_key)), data_node)) == NULL) {
 426         splaytree->free_key(key_clone);
 427         return OUTOFMEM_ERROR;
 428    }
 429
 430    /* Insert the splaynode into the given splaytree */
 431    if ((splay_insert_node(splaynode, splaytree)) < 0) {
 432      splaynode->left=splaynode->right = NULL;
 433      free_splaynode(splaynode, splaytree->free_key);
 434      return FAILURE;
 435    }
 436
 437    /* Done, return success */
 438    return SUCCESS;
 439 }
 440
 441 /* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
 442 inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {
 443
 444     splaynode_t * splaynode;
 445     void * key_clone;
 446
 447     /* Null argument checks */
 448     if (splaytree == NULL) {
 449         return FAILURE;
 450     }
 451
 452     if (key == NULL)
 453         return FAILURE;
 454
 455     /* Clone the key argument */
 456     key_clone = splaytree->copy_key(key);
 457
 458     /* Create a new splaynode (of regular type) */
 459     if ((splaynode = new_splaynode(REGULAR_NODE_TYPE, key_clone, data)) == NULL) {
 460         splaytree->free_key(key_clone);
 461         return OUTOFMEM_ERROR;
 462     }
 463
 464
 465     /* Inserts the splaynode into the splaytree */
 466     if (splay_insert_node(splaynode, splaytree) < 0) {
 467       splaynode->left=splaynode->right=NULL;
 468       free_splaynode(splaynode, splaytree->free_key);
 469       return FAILURE;
 470     }
 471
 472
 473     return SUCCESS;
 474 }
 475
 476 /* Helper function to insert splaynodes into the splaytree */
 477 static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree) {
 478   int match_type;
 479   int cmpval;
 480   void * key;
 481   splaynode_t * t;
 482
 483   /* Null argument checks */
 484   if (splaytree == NULL)
 485     return FAILURE;
 486
 487   if (splaynode == NULL)
 488     return FAILURE;
 489
 490   key = splaynode->key;
 491
 492   t = splaytree->root;
 493
 494
 495   /* Root is null, insert splaynode here */
 496   if (t == NULL) {
 497     splaynode->left = splaynode->right = NULL;
 498     splaytree->root = splaynode;
 499     return SUCCESS;
 500
 501   }
 502
 503   t = splay(key, t, &match_type, splaytree->compare);
 504
 505   if ((cmpval = splaytree->compare(key,t->key)) < 0) {
 506     splaynode->left = t->left;
 507     splaynode->right = t;
 508     t->left = NULL;
 509     splaytree->root = splaynode;
 510     return SUCCESS;
 511
 512   }
 513
 514   else if (cmpval > 0) {
 515     splaynode->right = t->right;
 516     splaynode->left = t;
 517     t->right = NULL;
 518     splaytree->root = splaynode;
 519     return SUCCESS;
 520    }
 521
 522    /* Item already exists in tree, don't reinsert */
 523   else {
 524
 525     return FAILURE;
 526   }
 527 }
 528
 529 /* Returns the 'maximum' key that is less than the given key in the splaytree */
 530 inline void * splay_find_below_max(void * key, splaytree_t * splaytree) {
 531
 532     void * closest_key;
 533
 534     if (splaytree == NULL)
 535         return NULL;
 536     if (splaytree->root == NULL)
 537         return NULL;
 538     if (key == NULL)
 539         return NULL;
 540
 541     closest_key = NULL;
 542
 543     splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
 544
 545     if (closest_key == NULL) return NULL;
 546     return splay_find(closest_key, splaytree);
 547 }
 548
 549
 550 /* Returns the 'minimum' key that is greater than the given key in the splaytree */
 551 inline void * splay_find_above_min(void * key, splaytree_t * splaytree) {
 552
 553     void * closest_key;
 554
 555     if (splaytree == NULL)
 556         return NULL;
 557     if (splaytree->root == NULL)
 558         return NULL;
 559     if (key == NULL)
 560         return NULL;
 561     closest_key = NULL;
 562
 563     splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
 564
 565     if (closest_key == NULL) {
 566         return NULL;
 567     }
 568
 569     return splay_find(closest_key, splaytree);
 570 }
 571
 572 /* Helper function */
 573 static inline void splay_find_below_max_helper(void * min_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
 574
 575         /* Empty root, return*/
 576         if (root == NULL)
 577             return;
 578
 579         /* The root key is less than the previously found closest key.
 580            Also try to make the key non null if the value is less than the max key */
 581
 582         if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
 583
 584             /*  The root key is less than the given max key, so this is the
 585                 smallest change from the given max key */
 586             if (compare(root->key, min_key) > 0) {
 587
 588                 *closest_key = root->key;
 589
 590                 /* Look right again in case even a greater key exists that is
 591                    still less than the given max key */
 592                 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
 593             }
 594
 595             /* The root key is greater than the given max key, and greater than
 596                the closest key, so search left */
 597             else {
 598                 splay_find_below_max_helper(min_key, closest_key, root->right, compare);
 599             }
 600         }
 601
 602         /* The root key is less than the found closest key, search right */
 603         else {
 604                 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
 605         }
 606
 607 }
 608
 609 /* Helper function */
 610 static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
 611
 612         /* Empty root, stop */
 613         if (root == NULL)
 614             return;
 615
 616         /* The root key is greater than the previously found closest key.
 617            Also try to make the key non null if the value is less than the min key */
 618
 619         if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
 620
 621             /*  The root key is greater than the given min key, so this is the
 622                 smallest change from the given min key */
 623             if (compare(root->key, max_key) < 0) {
 624
 625                 *closest_key = root->key;
 626
 627                /* Look left again in case even a smaller key exists that is
 628                   still greater than the given min key */
 629                 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
 630             }
 631
 632             /* The root key is less than the given min key, and less than
 633                the closest key, so search right */
 634             else {
 635                 splay_find_above_min_helper(max_key, closest_key, root->left, compare);
 636             }
 637         }
 638
 639         /* The root key is greater than the found closest key, search left */
 640         else {
 641                 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
 642         }
 643 }
 644
 645 /* Find the minimum entry of the splay tree */
 646 inline void * splay_find_min(splaytree_t * t) {
 647
 648     splaynode_t * splaynode;
 649
 650     if (t == NULL)
 651         return NULL;
 652     if (t->root == NULL)
 653         return NULL;
 654
 655     splaynode = t->root;
 656
 657     while (splaynode->left != NULL)
 658         splaynode= splaynode->left;
 659
 660     return splaynode->data;
 661 }
 662
 663
 664 /* Find the maximum entry of the splay tree */
 665 inline void * splay_find_max(splaytree_t * t) {
 666
 667     splaynode_t * splaynode;
 668
 669     if (t == NULL)
 670         return NULL;
 671     if (t->root == NULL)
 672         return NULL;
 673
 674     splaynode = t->root;
 675
 676     while (splaynode->right != NULL) {
 677       printf("data:%d\n", *(int*)splaynode->key);
 678         splaynode = splaynode->right;
 679     }
 680     return splaynode->data;
 681 }
 682
 683 inline int splay_size(splaytree_t * t) {
 684
 685     if (t == NULL)
 686       return 0;
 687     if (t->root == NULL)
 688       return 0;
 689
 690     return splay_rec_size(t->root);
 691
 692 }
 693
 694 static inline int splay_rec_size(splaynode_t * splaynode) {
 695
 696   if (!splaynode)
 697     return 0;
 698
 699   return 1 + splay_rec_size(splaynode->left) + splay_rec_size(splaynode->right);
 700
 701 }