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