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,
80 #include "splaytree_types.h"
81 #include "splaytree.h"
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);
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)()) {
99 splaytree_t * splaytree;
101 /* Allocate memory for the splaytree struct */
102 if ((splaytree = (splaytree_t*)malloc(sizeof(splaytree_t))) == NULL)
105 /* Set struct entries */
106 splaytree->root = NULL;
107 splaytree->compare = compare;
108 splaytree->copy_key = copy_key;
109 splaytree->free_key = free_key;
111 /* Return instantiated splay tree */
115 /* Destroys a splay tree */
116 inline int destroy_splaytree(splaytree_t * splaytree) {
118 /* Null argument check */
119 if (splaytree == NULL)
122 /* Recursively free all splaynodes in tree */
123 free_splaynode(splaytree->root, splaytree->free_key);
125 /* Free the splaytree struct itself */
128 /* Done, return success */
133 /* Recursively free all the splaynodes */
134 static inline int free_splaynode(splaynode_t * splaynode, void (*free_key)()) {
136 /* Ok if this happens, a recursive base case */
137 if (splaynode == NULL)
141 free_splaynode(splaynode->left, free_key);
143 /* Free right node */
144 free_splaynode(splaynode->right, free_key);
146 /* Free this node's key */
147 free_key(splaynode->key);
149 /* Note that the data pointers are not freed here.
150 Should be freed with a splay traversal function */
152 /* Free the splaynode structure itself */
155 /* Finished, return success */
160 /* Traverses the entire splay tree with the given function func_ptr */
161 inline void splay_traverse(void (*func_ptr)(), splaytree_t * splaytree) {
163 /* Null argument check */
165 if (splaytree == NULL)
167 if (func_ptr == NULL)
170 /* Call recursive helper function */
171 splay_traverse_helper(func_ptr, splaytree->root);
176 /* Helper function to traverse the entire splaytree */
177 static inline void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode) {
179 /* Normal if this happens, its a base case of recursion */
180 if (splaynode == NULL)
183 /* Recursively traverse to the left */
184 splay_traverse_helper(func_ptr, splaynode->left);
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);
191 /* Node is of symbolic link type, do nothing */
192 else if (splaynode->type == SYMBOLIC_NODE_TYPE)
195 /* Unknown node type */
199 /* Recursively traverse to the right */
200 splay_traverse_helper(func_ptr, splaynode->right);
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) {
209 splaynode_t * splaynode;
215 if (splaytree == NULL)
218 splaynode = splaytree->root;
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;
225 /* We only want perfect matches, so return null when match isn't perfect */
226 if (match_type == CLOSEST_MATCH)
229 /* This shouldn't happen because of the match type check, but whatever */
230 if (splaytree->root == NULL)
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;
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;
246 /* Gets the splaynode that the given key points to */
247 inline splaynode_t * get_splaynode_of(void * key, splaytree_t * splaytree) {
249 splaynode_t * splaynode;
252 /* Null argument checks */
253 if (splaytree == NULL)
259 splaynode = splaytree->root;
261 /* Find the splaynode */
262 splaynode = splay(key, splaynode, &match_type, splaytree->compare);
263 splaytree->root = splaynode;
265 /* Only perfect matches are valid */
266 if (match_type == CLOSEST_MATCH)
269 /* Return the perfect match splay node */
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)()) {
276 /* Simple top down splay, not requiring key to be in the tree t.
277 What it does is described above. */
279 splaynode_t N, *l, *r, *y;
280 *match_type = CLOSEST_MATCH;
282 if (t == NULL) return t;
283 N.left = N.right = NULL;
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 */
294 if (t->left == NULL) break;
296 r->left = t; /* link right */
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 */
306 if (t->right == NULL) break;
308 l->right = t; /* link left */
312 *match_type = PERFECT_MATCH;
316 l->right = t->left; /* assemble */
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) {
330 splaynode_t * splaynode;
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)
336 /* Set new splaytree root equal to the returned splaynode after deletion */
337 splaytree->root = splaynode;
339 /* Finished, no errors */
343 /* Deletes a splay node */
344 static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
346 splaynode_t * new_root;
350 if (splaynode == NULL)
353 splaynode = splay(key, splaynode, &match_type, compare);
355 /* If entry wasn't found, quit here */
356 if (match_type == CLOSEST_MATCH)
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;
365 /* Otherwise, do something I don't currently understand */
367 new_root = splay(key, splaynode->left, &match_type, compare);
368 new_root->right = splaynode->right;
371 /* Set splay nodes children pointers to null */
372 splaynode->left = splaynode->right = NULL;
374 /* Free the splaynode (and only this node since its children are now empty */
375 free_splaynode(splaynode, free_key);
377 /* Return the resulting tree */
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 */
392 /* Creates the new splay node struct */
393 if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
396 splaynode->data = data;
397 splaynode->type = type;
398 splaynode->key = key;
400 /* Return the new splay node */
404 /* Inserts a link into the splay tree */
405 inline int splay_insert_link(void * alias_key, void * orig_key, splaytree_t * splaytree) {
407 splaynode_t * splaynode, * data_node;
411 if (splaytree == NULL)
414 if (alias_key == NULL)
417 if (orig_key == NULL)
420 /* Find the splaynode corresponding to the original key */
421 if ((data_node = get_splaynode_of(orig_key, splaytree)) == NULL)
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;
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);
437 /* Done, return success */
441 /* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
442 inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {
444 splaynode_t * splaynode;
447 /* Null argument checks */
448 if (splaytree == NULL) {
455 /* Clone the key argument */
456 key_clone = splaytree->copy_key(key);
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;
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);
476 /* Helper function to insert splaynodes into the splaytree */
477 static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree) {
483 /* Null argument checks */
484 if (splaytree == NULL)
487 if (splaynode == NULL)
490 key = splaynode->key;
495 /* Root is null, insert splaynode here */
497 splaynode->left = splaynode->right = NULL;
498 splaytree->root = splaynode;
503 t = splay(key, t, &match_type, splaytree->compare);
505 if ((cmpval = splaytree->compare(key,t->key)) < 0) {
506 splaynode->left = t->left;
507 splaynode->right = t;
509 splaytree->root = splaynode;
514 else if (cmpval > 0) {
515 splaynode->right = t->right;
518 splaytree->root = splaynode;
522 /* Item already exists in tree, don't reinsert */
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) {
534 if (splaytree == NULL)
536 if (splaytree->root == NULL)
543 splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
545 if (closest_key == NULL) return NULL;
546 return splay_find(closest_key, splaytree);
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) {
555 if (splaytree == NULL)
557 if (splaytree->root == NULL)
563 splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
565 if (closest_key == NULL) {
569 return splay_find(closest_key, splaytree);
572 /* Helper function */
573 static inline void splay_find_below_max_helper(void * min_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
575 /* Empty root, return*/
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 */
582 if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
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) {
588 *closest_key = root->key;
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);
595 /* The root key is greater than the given max key, and greater than
596 the closest key, so search left */
598 splay_find_below_max_helper(min_key, closest_key, root->right, compare);
602 /* The root key is less than the found closest key, search right */
604 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
609 /* Helper function */
610 static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
612 /* Empty root, stop */
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 */
619 if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
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) {
625 *closest_key = root->key;
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);
632 /* The root key is less than the given min key, and less than
633 the closest key, so search right */
635 splay_find_above_min_helper(max_key, closest_key, root->left, compare);
639 /* The root key is greater than the found closest key, search left */
641 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
645 /* Find the minimum entry of the splay tree */
646 inline void * splay_find_min(splaytree_t * t) {
648 splaynode_t * splaynode;
657 while (splaynode->left != NULL)
658 splaynode= splaynode->left;
660 return splaynode->data;
664 /* Find the maximum entry of the splay tree */
665 inline void * splay_find_max(splaytree_t * t) {
667 splaynode_t * splaynode;
676 while (splaynode->right != NULL) {
677 printf("data:%d\n", *(int*)splaynode->key);
678 splaynode = splaynode->right;
680 return splaynode->data;
683 inline int splay_size(splaytree_t * t) {
690 return splay_rec_size(t->root);
694 static inline int splay_rec_size(splaynode_t * splaynode) {
699 return 1 + splay_rec_size(splaynode->left) + splay_rec_size(splaynode->right);