1 /*****************************************************************************
3 *****************************************************************************
4 * Copyright (C) 2004 the VideoLAN team
7 * Authors: Cyril Deguet <asmax@videolan.org>
8 * code from projectM http://xmms-projectm.sourceforge.net
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.
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.
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 *****************************************************************************/
28 An implementation of top-down splaying
29 D. Sleator <sleator@cs.cmu.edu>
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].
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.
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:
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.
58 [1] "Fundamentals of data structures in C", Horowitz, Sahni,
59 and Anderson-Freed, Computer Science Press, pp 542-547.
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.
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,
81 #include "splaytree_types.h"
82 #include "splaytree.h"
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);
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)()) {
100 splaytree_t * splaytree;
102 /* Allocate memory for the splaytree struct */
103 if ((splaytree = (splaytree_t*)malloc(sizeof(splaytree_t))) == NULL)
106 /* Set struct entries */
107 splaytree->root = NULL;
108 splaytree->compare = compare;
109 splaytree->copy_key = copy_key;
110 splaytree->free_key = free_key;
112 /* Return instantiated splay tree */
116 /* Destroys a splay tree */
117 int destroy_splaytree(splaytree_t * splaytree) {
119 /* Null argument check */
120 if (splaytree == NULL)
123 /* Recursively free all splaynodes in tree */
124 free_splaynode(splaytree->root, splaytree->free_key);
126 /* Free the splaytree struct itself */
129 /* Done, return success */
134 /* Recursively free all the splaynodes */
135 int free_splaynode(splaynode_t * splaynode, void (*free_key)()) {
137 /* Ok if this happens, a recursive base case */
138 if (splaynode == NULL)
142 free_splaynode(splaynode->left, free_key);
144 /* Free right node */
145 free_splaynode(splaynode->right, free_key);
147 /* Free this node's key */
148 free_key(splaynode->key);
150 /* Note that the data pointers are not freed here.
151 Should be freed with a splay traversal function */
153 /* Free the splaynode structure itself */
156 /* Finished, return success */
161 /* Traverses the entire splay tree with the given function func_ptr */
162 void splay_traverse(void (*func_ptr)(), splaytree_t * splaytree) {
164 /* Null argument check */
166 if (splaytree == NULL)
168 if (func_ptr == NULL)
171 /* Call recursive helper function */
172 splay_traverse_helper(func_ptr, splaytree->root);
177 /* Helper function to traverse the entire splaytree */
178 void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode) {
180 /* Normal if this happens, its a base case of recursion */
181 if (splaynode == NULL)
184 /* Recursively traverse to the left */
185 splay_traverse_helper(func_ptr, splaynode->left);
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);
192 /* Node is of symbolic link type, do nothing */
193 else if (splaynode->type == SYMBOLIC_NODE_TYPE)
196 /* Unknown node type */
200 /* Recursively traverse to the right */
201 splay_traverse_helper(func_ptr, splaynode->right);
207 /* Find the node corresponding to the given key in splaytree, return its data pointer */
208 void * splay_find(void * key, splaytree_t * splaytree) {
210 splaynode_t * splaynode;
216 if (splaytree == NULL)
219 splaynode = splaytree->root;
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;
226 /* We only want perfect matches, so return null when match isn't perfect */
227 if (match_type == CLOSEST_MATCH)
230 /* This shouldn't happen because of the match type check, but whatever */
231 if (splaytree->root == NULL)
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;
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;
247 /* Gets the splaynode that the given key points to */
248 splaynode_t * get_splaynode_of(void * key, splaytree_t * splaytree) {
250 splaynode_t * splaynode;
253 /* Null argument checks */
254 if (splaytree == NULL)
260 splaynode = splaytree->root;
262 /* Find the splaynode */
263 splaynode = splay(key, splaynode, &match_type, splaytree->compare);
264 splaytree->root = splaynode;
266 /* Only perfect matches are valid */
267 if (match_type == CLOSEST_MATCH)
270 /* Return the perfect match splay node */
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)()) {
277 /* Simple top down splay, not requiring key to be in the tree t.
278 What it does is described above. */
280 splaynode_t N, *l, *r, *y;
281 *match_type = CLOSEST_MATCH;
283 if (t == NULL) return t;
284 N.left = N.right = NULL;
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 */
295 if (t->left == NULL) break;
297 r->left = t; /* link right */
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 */
307 if (t->right == NULL) break;
309 l->right = t; /* link left */
313 *match_type = PERFECT_MATCH;
317 l->right = t->left; /* assemble */
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) {
331 splaynode_t * splaynode;
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)
337 /* Set new splaytree root equal to the returned splaynode after deletion */
338 splaytree->root = splaynode;
340 /* Finished, no errors */
344 /* Deletes a splay node */
345 splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
347 splaynode_t * new_root;
351 if (splaynode == NULL)
354 splaynode = splay(key, splaynode, &match_type, compare);
356 /* If entry wasn't found, quit here */
357 if (match_type == CLOSEST_MATCH)
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;
366 /* Otherwise, do something I don't currently understand */
368 new_root = splay(key, splaynode->left, &match_type, compare);
369 new_root->right = splaynode->right;
372 /* Set splay nodes children pointers to null */
373 splaynode->left = splaynode->right = NULL;
375 /* Free the splaynode (and only this node since its children are now empty */
376 free_splaynode(splaynode, free_key);
378 /* Return the resulting tree */
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 */
393 /* Creates the new splay node struct */
394 if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
397 splaynode->data = data;
398 splaynode->type = type;
399 splaynode->key = key;
401 /* Return the new splay node */
405 /* Inserts a link into the splay tree */
406 int splay_insert_link(const void * alias_key, void * orig_key, splaytree_t * splaytree) {
408 splaynode_t * splaynode, * data_node;
412 if (splaytree == NULL)
415 if (alias_key == NULL)
418 if (orig_key == NULL)
421 /* Find the splaynode corresponding to the original key */
422 if ((data_node = get_splaynode_of(orig_key, splaytree)) == NULL)
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;
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);
438 /* Done, return success */
442 /* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
443 int splay_insert(void * data, void * key, splaytree_t * splaytree) {
445 splaynode_t * splaynode;
448 /* Null argument checks */
449 if (splaytree == NULL) {
456 /* Clone the key argument */
457 key_clone = splaytree->copy_key(key);
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;
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);
477 /* Helper function to insert splaynodes into the splaytree */
478 int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree) {
484 /* Null argument checks */
485 if (splaytree == NULL)
488 if (splaynode == NULL)
491 key = splaynode->key;
496 /* Root is null, insert splaynode here */
498 splaynode->left = splaynode->right = NULL;
499 splaytree->root = splaynode;
504 t = splay(key, t, &match_type, splaytree->compare);
506 if ((cmpval = splaytree->compare(key,t->key)) < 0) {
507 splaynode->left = t->left;
508 splaynode->right = t;
510 splaytree->root = splaynode;
515 else if (cmpval > 0) {
516 splaynode->right = t->right;
519 splaytree->root = splaynode;
523 /* Item already exists in tree, don't reinsert */
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) {
535 if (splaytree == NULL)
537 if (splaytree->root == NULL)
544 splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
546 if (closest_key == NULL) return NULL;
547 return splay_find(closest_key, splaytree);
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) {
556 if (splaytree == NULL)
558 if (splaytree->root == NULL)
564 splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
566 if (closest_key == NULL) {
570 return splay_find(closest_key, splaytree);
573 /* Helper function */
574 void splay_find_below_max_helper(void * min_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
576 /* Empty root, return*/
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 */
583 if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
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) {
589 *closest_key = root->key;
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);
596 /* The root key is greater than the given max key, and greater than
597 the closest key, so search left */
599 splay_find_below_max_helper(min_key, closest_key, root->right, compare);
603 /* The root key is less than the found closest key, search right */
605 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
610 /* Helper function */
611 void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
613 /* Empty root, stop */
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 */
620 if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
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) {
626 *closest_key = root->key;
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);
633 /* The root key is less than the given min key, and less than
634 the closest key, so search right */
636 splay_find_above_min_helper(max_key, closest_key, root->left, compare);
640 /* The root key is greater than the found closest key, search left */
642 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
646 /* Find the minimum entry of the splay tree */
647 void * splay_find_min(splaytree_t * t) {
649 splaynode_t * splaynode;
658 while (splaynode->left != NULL)
659 splaynode= splaynode->left;
661 return splaynode->data;
665 /* Find the maximum entry of the splay tree */
666 void * splay_find_max(splaytree_t * t) {
668 splaynode_t * splaynode;
677 while (splaynode->right != NULL) {
678 printf("data:%d\n", *(int*)splaynode->key);
679 splaynode = splaynode->right;
681 return splaynode->data;
684 int splay_size(splaytree_t * t) {
691 return splay_rec_size(t->root);
695 int splay_rec_size(splaynode_t * splaynode) {
700 return 1 + splay_rec_size(splaynode->left) + splay_rec_size(splaynode->right);