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