1 /*****************************************************************************
3 *****************************************************************************
4 * Copyright (C) 2004 VideoLAN (Centrale Réseaux) and its contributors
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., 59 Temple Place - Suite 330, Boston, MA 02111, 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,
82 #include "splaytree_types.h"
83 #include "splaytree.h"
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);
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)()) {
101 splaytree_t * splaytree;
103 /* Allocate memory for the splaytree struct */
104 if ((splaytree = (splaytree_t*)malloc(sizeof(splaytree_t))) == NULL)
107 /* Set struct entries */
108 splaytree->root = NULL;
109 splaytree->compare = compare;
110 splaytree->copy_key = copy_key;
111 splaytree->free_key = free_key;
113 /* Return instantiated splay tree */
117 /* Destroys a splay tree */
118 inline int destroy_splaytree(splaytree_t * splaytree) {
120 /* Null argument check */
121 if (splaytree == NULL)
124 /* Recursively free all splaynodes in tree */
125 free_splaynode(splaytree->root, splaytree->free_key);
127 /* Free the splaytree struct itself */
130 /* Done, return success */
135 /* Recursively free all the splaynodes */
136 static inline int free_splaynode(splaynode_t * splaynode, void (*free_key)()) {
138 /* Ok if this happens, a recursive base case */
139 if (splaynode == NULL)
143 free_splaynode(splaynode->left, free_key);
145 /* Free right node */
146 free_splaynode(splaynode->right, free_key);
148 /* Free this node's key */
149 free_key(splaynode->key);
151 /* Note that the data pointers are not freed here.
152 Should be freed with a splay traversal function */
154 /* Free the splaynode structure itself */
157 /* Finished, return success */
162 /* Traverses the entire splay tree with the given function func_ptr */
163 inline void splay_traverse(void (*func_ptr)(), splaytree_t * splaytree) {
165 /* Null argument check */
167 if (splaytree == NULL)
169 if (func_ptr == NULL)
172 /* Call recursive helper function */
173 splay_traverse_helper(func_ptr, splaytree->root);
178 /* Helper function to traverse the entire splaytree */
179 static inline void splay_traverse_helper (void (*func_ptr)(), splaynode_t * splaynode) {
181 /* Normal if this happens, its a base case of recursion */
182 if (splaynode == NULL)
185 /* Recursively traverse to the left */
186 splay_traverse_helper(func_ptr, splaynode->left);
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);
193 /* Node is of symbolic link type, do nothing */
194 else if (splaynode->type == SYMBOLIC_NODE_TYPE)
197 /* Unknown node type */
201 /* Recursively traverse to the right */
202 splay_traverse_helper(func_ptr, splaynode->right);
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) {
211 splaynode_t * splaynode;
217 if (splaytree == NULL)
220 splaynode = splaytree->root;
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;
227 /* We only want perfect matches, so return null when match isn't perfect */
228 if (match_type == CLOSEST_MATCH)
231 /* This shouldn't happen because of the match type check, but whatever */
232 if (splaytree->root == NULL)
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;
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;
248 /* Gets the splaynode that the given key points to */
249 inline splaynode_t * get_splaynode_of(void * key, splaytree_t * splaytree) {
251 splaynode_t * splaynode;
254 /* Null argument checks */
255 if (splaytree == NULL)
261 splaynode = splaytree->root;
263 /* Find the splaynode */
264 splaynode = splay(key, splaynode, &match_type, splaytree->compare);
265 splaytree->root = splaynode;
267 /* Only perfect matches are valid */
268 if (match_type == CLOSEST_MATCH)
271 /* Return the perfect match splay node */
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)()) {
278 /* Simple top down splay, not requiring key to be in the tree t.
279 What it does is described above. */
281 splaynode_t N, *l, *r, *y;
282 *match_type = CLOSEST_MATCH;
284 if (t == NULL) return t;
285 N.left = N.right = NULL;
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 */
296 if (t->left == NULL) break;
298 r->left = t; /* link right */
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 */
308 if (t->right == NULL) break;
310 l->right = t; /* link left */
314 *match_type = PERFECT_MATCH;
318 l->right = t->left; /* assemble */
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) {
332 splaynode_t * splaynode;
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)
338 /* Set new splaytree root equal to the returned splaynode after deletion */
339 splaytree->root = splaynode;
341 /* Finished, no errors */
345 /* Deletes a splay node */
346 static inline splaynode_t * splay_delete_helper(void * key, splaynode_t * splaynode, int (*compare)(), void (*free_key)()) {
348 splaynode_t * new_root;
352 if (splaynode == NULL)
355 splaynode = splay(key, splaynode, &match_type, compare);
357 /* If entry wasn't found, quit here */
358 if (match_type == CLOSEST_MATCH)
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;
367 /* Otherwise, do something I don't currently understand */
369 new_root = splay(key, splaynode->left, &match_type, compare);
370 new_root->right = splaynode->right;
373 /* Set splay nodes children pointers to null */
374 splaynode->left = splaynode->right = NULL;
376 /* Free the splaynode (and only this node since its children are now empty */
377 free_splaynode(splaynode, free_key);
379 /* Return the resulting tree */
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 */
394 /* Creates the new splay node struct */
395 if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
398 splaynode->data = data;
399 splaynode->type = type;
400 splaynode->key = key;
402 /* Return the new splay node */
406 /* Inserts a link into the splay tree */
407 inline int splay_insert_link(void * alias_key, void * orig_key, splaytree_t * splaytree) {
409 splaynode_t * splaynode, * data_node;
413 if (splaytree == NULL)
416 if (alias_key == NULL)
419 if (orig_key == NULL)
422 /* Find the splaynode corresponding to the original key */
423 if ((data_node = get_splaynode_of(orig_key, splaytree)) == NULL)
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;
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);
439 /* Done, return success */
443 /* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
444 inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {
446 splaynode_t * splaynode;
449 /* Null argument checks */
450 if (splaytree == NULL) {
457 /* Clone the key argument */
458 key_clone = splaytree->copy_key(key);
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;
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);
478 /* Helper function to insert splaynodes into the splaytree */
479 static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree) {
485 /* Null argument checks */
486 if (splaytree == NULL)
489 if (splaynode == NULL)
492 key = splaynode->key;
497 /* Root is null, insert splaynode here */
499 splaynode->left = splaynode->right = NULL;
500 splaytree->root = splaynode;
505 t = splay(key, t, &match_type, splaytree->compare);
507 if ((cmpval = splaytree->compare(key,t->key)) < 0) {
508 splaynode->left = t->left;
509 splaynode->right = t;
511 splaytree->root = splaynode;
516 else if (cmpval > 0) {
517 splaynode->right = t->right;
520 splaytree->root = splaynode;
524 /* Item already exists in tree, don't reinsert */
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) {
536 if (splaytree == NULL)
538 if (splaytree->root == NULL)
545 splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);
547 if (closest_key == NULL) return NULL;
548 return splay_find(closest_key, splaytree);
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) {
557 if (splaytree == NULL)
559 if (splaytree->root == NULL)
565 splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);
567 if (closest_key == NULL) {
571 return splay_find(closest_key, splaytree);
574 /* Helper function */
575 static inline void splay_find_below_max_helper(void * min_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
577 /* Empty root, return*/
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 */
584 if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
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) {
590 *closest_key = root->key;
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);
597 /* The root key is greater than the given max key, and greater than
598 the closest key, so search left */
600 splay_find_below_max_helper(min_key, closest_key, root->right, compare);
604 /* The root key is less than the found closest key, search right */
606 splay_find_below_max_helper(min_key, closest_key, root->left, compare);
611 /* Helper function */
612 static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)()) {
614 /* Empty root, stop */
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 */
621 if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
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) {
627 *closest_key = root->key;
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);
634 /* The root key is less than the given min key, and less than
635 the closest key, so search right */
637 splay_find_above_min_helper(max_key, closest_key, root->left, compare);
641 /* The root key is greater than the found closest key, search left */
643 splay_find_above_min_helper(max_key, closest_key, root->right, compare);
647 /* Find the minimum entry of the splay tree */
648 inline void * splay_find_min(splaytree_t * t) {
650 splaynode_t * splaynode;
659 while (splaynode->left != NULL)
660 splaynode= splaynode->left;
662 return splaynode->data;
666 /* Find the maximum entry of the splay tree */
667 inline void * splay_find_max(splaytree_t * t) {
669 splaynode_t * splaynode;
678 while (splaynode->right != NULL) {
679 printf("data:%d\n", *(int*)splaynode->key);
680 splaynode = splaynode->right;
682 return splaynode->data;
685 inline int splay_size(splaytree_t * t) {
692 return splay_rec_size(t->root);
696 static inline int splay_rec_size(splaynode_t * splaynode) {
701 return 1 + splay_rec_size(splaynode->left) + splay_rec_size(splaynode->right);