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