fixed typo
[rxpd] / src / psplay.c
1 /*
2     psplay.c - probabilistic splay tree
3
4   Copyright (C)
5     2004, 2005, 2006,   Christian Thaeter <chth@gmx.net>
6   Copyright (C)         CinelerraCV
7     2007,               Christian Thaeter <ct@pipapo.org>
8
9   This program is free software; you can redistribute it and/or
10   modify it under the terms of the GNU General Public License as
11   published by the Free Software Foundation; either version 2 of the
12   License, or (at your option) any later version.
13
14   This program is distributed in the hope that it will be useful,
15   but WITHOUT ANY WARRANTY; without even the implied warranty of
16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17   GNU General Public License for more details.
18
19   You should have received a copy of the GNU General Public License
20   along with this program; if not, write to the Free Software
21   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 */
23
24 #include "psplay.h"
25 #include <stdio.h>
26 #include <string.h>
27 #include <stdlib.h>
28 /*
29   probabilistic distribution as n/255 chance of splaying
30 */
31 #ifndef PSPLAY_PROB_ZIG
32 /* already near root, only approx 6% splay probability */
33 #define PSPLAY_PROB_ZIG 16
34 #endif
35 /* approx 63% splay probability */
36 #ifndef PSPLAY_PROB_ZIGZIG
37 #define PSPLAY_PROB_ZIGZIG 160
38 #endif
39 /* zigzag reduces the tree by 1 level, approx 88% splay probability */
40 #ifndef PSPLAY_PROB_ZIGZAG
41 #define PSPLAY_PROB_ZIGZAG 224
42 #endif
43
44
45
46 /* simple prng with 2^31-1 cycle */
47 static inline uint32_t psplay_fast_prng ()
48 {
49   static uint32_t rnd=0xbabeface;
50   return rnd = rnd<<1 ^ ((rnd >> 30) & 1) ^ ((rnd>>2) & 1);
51 }
52
53
54 PSplayroot
55 psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete)
56 {
57   if (self)
58     {
59       self->tree = NULL;
60       self->cmp = cmp;
61       self->delete = delete;
62       self->elem_cnt = 0;
63     }
64   return self;
65 }
66
67
68 PSplayroot
69 psplay_destroy_root (PSplayroot self)
70 {
71   if (self) while (self->tree)
72     {
73       PSplay n = psplay_remove (self, self->tree);
74       if (self->delete)
75         self->delete (n);
76     }
77   return self;
78 }
79
80
81
82
83
84
85 //
86 inline void
87 psplay_splay (PSplay* root, PSplay node)
88 {
89   while (node->up)
90     {
91       PSplay p = node->up;              // parent
92       PSplay g = p?p->up:NULL;          // grandparent
93
94       if (g)
95         {
96           if (p == g->left)
97             {
98               // zig..
99               if (node == p->left)
100                 {
101                   // zigzig
102                   if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZIG)
103                     return;
104
105                   g->left = p->right;
106                   if (g->left) g->left->up = g;
107                   p->right = g;
108
109                   p->left = node->right;
110                   if (p->left) p->left->up = p;
111                   node->right = p;
112
113                   node->up = g->up;
114                   g->up = p;
115                 }
116               else
117                 {
118                   // zigzag
119                   if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZAG)
120                     return;
121
122                   p->right = node->left;
123                   if (p->right) p->right->up = p;
124                   node->left = p;
125
126                   g->left = node->right;
127                   if (g->left) g->left->up = g;
128                   node->right = g;
129
130                   node->up = g->up;
131                   g->up = node;
132                 }
133             }
134           else
135             {
136               // zag..
137               if (node == p->left)
138                 {
139                   // zagzig
140                   if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZAG)
141                     return;
142
143                   p->left = node->right;
144                   if (p->left) p->left->up = p;
145                   node->right = p;
146
147                   g->right = node->left;
148                   if (g->right) g->right->up = g;
149                   node->left = g;
150
151                   node->up = g->up;
152                   g->up = node;
153                 }
154               else
155                 {
156                   // zagzag
157                   if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZIG)
158                     return;
159
160                   g->right = p->left;
161                   if (g->right) g->right->up = g;
162                   p->left = g;
163
164                   p->right = node->left;
165                   if (p->right) p->right->up = p;
166                   node->left = p;
167
168                   node->up = g->up;
169                   g->up = p;
170                 }
171             }
172
173           p->up = node;
174           if (node->up)
175             {
176               if (node->up->left == g)
177                 node->up->left = node;
178               else
179                 node->up->right = node;
180             }
181           else
182             {
183               *root = node;
184             }
185         }
186       else
187         {
188           if (p)
189             {
190               if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIG)
191                 return;
192
193               if (node == p->left)
194                 {
195                   // zig
196                   p->left = node->right;
197                   if (p->left) p->left->up = p;
198                   node->right = p;
199                 }
200               else
201                 {
202                   // zag
203                   p->right = node->left;
204                   if (p->right) p->right->up = p;
205                   node->left = p;
206                 }
207               p->up = node;
208               node->up = NULL;
209               *root = node;
210             }
211         }
212     }
213 }
214
215
216 PSplay
217 psplay_new (void * key)
218 {
219   return psplay_init (malloc (sizeof (psplay)), key);
220 }
221
222
223 PSplay
224 psplay_init (PSplay self, const void* key)
225 {
226   if (self)
227     {
228       self->key = key;
229       self->up = self->left = self->right = NULL;
230     }
231   return self;
232 }
233
234 void
235 psplay_delete (PSplay node)
236 {
237   free (node);
238 };
239
240
241 PSplay
242 psplay_insert (PSplayroot root, PSplay node)
243 {
244   PSplay n = root->tree;
245
246   if (!n)
247     root->tree = node;
248   else
249     {
250       while (n != node)
251         {
252           int c;
253           c = root->cmp (node->key, n->key);
254
255           if (c < 0)
256             {
257               if (!n->left)
258                 {
259                   n->left = node;
260                   node->up = n;
261                 }
262               n = n->left;
263             }
264           else if (c > 0)
265             {
266               if (!n->right)
267                 {
268                   n->right = node;
269                   node->up = n;
270                 }
271               n = n->right;
272             }
273           else
274             return NULL;
275         }
276       psplay_splay (&root->tree, node);
277     }
278   ++root->elem_cnt;
279   return node;
280 }
281
282
283 PSplay
284 psplay_find (PSplayroot root, void* key)
285 {
286   PSplay node = root->tree;
287
288   while (node)
289     {
290       int c;
291       c = root->cmp (key, node->key);
292
293       if (c < 0)
294           node = node->left;
295       else if (c > 0)
296           node = node->right;
297       else
298         {
299           psplay_splay (&root->tree, node);
300           break;
301         }
302     }
303   return node;
304 }
305
306
307 PSplay
308 psplay_remove (PSplayroot root, PSplay node)
309 {
310   if (!node) return NULL;
311
312   PSplay p = node->up;
313   PSplay* r;
314
315   if (p)
316     {
317       if (p->left == node)
318         r = &p->left;
319       else
320         r = &p->right;
321     }
322   else
323     r = &root->tree;
324
325   if (!node->left)
326     {
327       // only right leaf
328       *r = node->right;
329       if (*r)
330         (*r)->up = p;
331     }
332   else if (!node->right)
333     {
334       // only left leaf
335       *r = node->left;
336       if (*r)
337         (*r)->up = p;
338     }
339   else
340     {
341       PSplay i;
342       if (psplay_fast_prng()&1) /* 50% probability removing left or right wards */
343         {
344           //left right
345           for (i = node->left; i->right; i = i->right);
346
347           i->right = node->right;
348           i->right->up = i;
349           i->up->right = i->left;
350
351           if (i->left)
352             i->left->up = i->up;
353
354           if (node->left != i)
355             {
356               i->left = node->left;
357               i->left->up = i;
358             }
359         }
360       else
361         {
362           // right right
363           for (i = node->right; i->left; i = i->left);
364
365           i->left = node->left;
366           i->left->up = i;
367           i->up->left = i->right;
368
369           if (i->right)
370             i->right->up = i->up;
371
372           if (node->right != i)
373             {
374               i->right = node->right;
375               i->right->up = i;
376             }
377         }
378       i->up = node->up;
379       *r = i;
380     }
381   node->up = node->left = node->right = NULL;
382   --root->elem_cnt;
383   return node;
384 }
385
386 /*
387   Walking a tree calls a 'action' three times PSPLAY_PREORDER before visiting the left subtree,
388   PSPLAY_INORDER after visiting the left subtree and before the right subtree, PSPLAY_POSTORDER
389   finally after visiting the right subtree. Example: For to traverse the tree in order action
390   would only handle PSPLAY_INORDER.
391   This action returns PSLPLAY_CONT when the traversal of the tree shall continue.
392   An 'action' must not alter the tree itself but it can indicate aborting the tree traversal and
393   how the current node is handled by its return value:
394    PSPLAY_STOP:
395      just stops the traversal
396    PSPLAY_REMOVE:
397      stops the traversal and removes the current node, calling the delete handler registered in root
398    any other psplay_delete_t:
399      stops the traversal and removes the current node, calling the returned delete handler with it
400 */
401 const psplay_delete_t PSPLAY_CONT = (psplay_delete_t)0x0;
402 const psplay_delete_t PSPLAY_STOP = (psplay_delete_t)0x1;
403 const psplay_delete_t PSPLAY_REMOVE = (psplay_delete_t)0x2;
404
405 static int
406 psplay_handle (PSplayroot root, PSplay node, psplay_delete_t res)
407 {
408   if (res == PSPLAY_CONT)
409     return 1;
410
411   if (res == PSPLAY_STOP)
412     ;
413   else if (res == PSPLAY_REMOVE)
414     {
415       psplay_remove (root, node);
416       if (root->delete)
417         root->delete (node);
418     }
419   else
420     {
421       psplay_remove (root, node);
422       res (node);
423     }
424   return 0;
425 }
426
427
428 int
429 psplay_walk (PSplayroot root, PSplay node, psplay_action_t action, int level, void* data)
430 {
431   if (!root->tree)
432     return 1;
433
434   if (!node)
435     node = root->tree;
436
437   psplay_delete_t res;
438
439   res = action (node, PSPLAY_PREORDER, level, data);
440   if (!psplay_handle (root, node, res))
441     return 0;
442
443   if (node->left)
444     if (!psplay_walk (root, node->left, action, level+1, data))
445       return 0;
446
447   res = action (node, PSPLAY_INORDER, level, data);
448   if (!psplay_handle (root, node, res))
449     return 0;
450
451   if (node->right)
452     if (!psplay_walk (root, node->right, action, level+1, data))
453       return 0;
454
455   res = action (node, PSPLAY_POSTORDER, level, data);
456   if (!psplay_handle (root, node, res))
457     return 0;
458
459   return 1;
460 }
461
462 psplay_delete_t
463 psplay_print_node (PSplay node, const enum psplay_order_e which, int level, void* data)
464 {
465   FILE* fh = data;
466   static char* sp = "                                        ";
467   if (level>40)
468     {
469       if (which == PSPLAY_PREORDER)
470         fprintf (fh, "%s ...\n", sp+40-level);
471       return PSPLAY_CONT;
472     }
473
474   switch (which)
475     {
476     case PSPLAY_PREORDER:
477       fprintf (fh, "%s%p\n", sp+40-level, node);
478       fprintf (fh, "%skey %p (%.4s)\n", sp+40-level, (char*)node->key, node->key?(char*)node->key:"NULL");
479       fprintf (fh, "%sup %p\n", sp+40-level, node->up);
480       fprintf (fh, "%sleft %p\n", sp+40-level, node->left);
481       break;
482     case PSPLAY_INORDER:
483       fprintf (fh, "%sright %p\n", sp+40-level, node->right);
484       break;
485     case PSPLAY_POSTORDER:
486       break;
487     }
488
489   return PSPLAY_CONT;
490 }
491
492 void
493 psplay_dump (PSplayroot root, FILE* dest)
494 {
495   psplay_walk (root, NULL, psplay_print_node, 0, dest);
496   fprintf (dest, "\n");
497 }
498
499 int my_cmp (const void* a, const void* b)
500 {
501   return strcmp (a, b);
502 }
503
504
505 #ifdef PSPLAY_TESTMAIN
506 int
507 main ()
508 {
509   psplayroot root = PSPLAYROOT_INITIALIZER(my_cmp, NULL);
510   psplay_init_root (&root, my_cmp, psplay_delete);
511
512   psplay_insert (&root, psplay_new("foo"));
513   psplay_insert (&root, psplay_new("bar"));
514   psplay_insert (&root, psplay_new("baz"));
515   psplay_insert (&root, psplay_new("test"));
516   psplay_insert (&root, psplay_new("pap"));
517   psplay_insert (&root, psplay_new("qux"));
518
519   psplay_dump (&root, stdout);
520
521   PSplay f = psplay_find (&root, "baz");
522   printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
523   psplay_dump (&root, stdout);
524
525   f = psplay_find (&root, "test");
526   printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
527   psplay_dump (&root, stdout);
528
529   f = psplay_find (&root, "test");
530   printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
531   psplay_dump (&root, stdout);
532
533   f = psplay_find (&root, "foo");
534   printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
535   psplay_dump (&root, stdout);
536
537
538   psplay_delete (psplay_remove (&root, root.tree));
539   psplay_dump (&root, stdout);
540
541   psplay_delete (psplay_remove (&root, root.tree));
542   psplay_dump (&root, stdout);
543
544   psplay_delete (psplay_remove (&root, root.tree));
545   psplay_dump (&root, stdout);
546
547   printf ("destroying\n");
548   psplay_destroy_root (&root);
549   psplay_dump (&root, stdout);
550
551   psplay_delete (psplay_remove (&root, root.tree));
552   psplay_dump (&root, stdout);
553
554   psplay_delete (psplay_remove (&root, root.tree));
555   psplay_dump (&root, stdout);
556
557   psplay_delete (psplay_remove (&root, root.tree));
558   psplay_dump (&root, stdout);
559   return 0;
560 }
561 #endif