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 }