implemented a tree-walking api for psplay
[rxpd] / 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 }
232
233 void
234 psplay_delete (PSplay node)
235 {
236   free (node);
237 };
238
239
240 PSplay
241 psplay_insert (PSplayroot root, PSplay node)
242 {
243   PSplay n = root->tree;
244
245   if (!n)
246     root->tree = node;
247   else
248     {
249       while (n != node)
250         {
251           int c;
252           c = root->cmp (node->key, n->key);
253
254           if (c < 0)
255             {
256               if (!n->left)
257                 {
258                   n->left = node;
259                   node->up = n;
260                 }
261               n = n->left;
262             }
263           else if (c > 0)
264             {
265               if (!n->right)
266                 {
267                   n->right = node;
268                   node->up = n;
269                 }
270               n = n->right;
271             }
272           else
273             return NULL;
274         }
275       psplay_splay (&root->tree, node);
276     }
277   ++root->elem_cnt;
278   return node;
279 }
280
281
282 PSplay
283 psplay_find (PSplayroot root, void* key)
284 {
285   PSplay node = root->tree;
286
287   while (node)
288     {
289       int c;
290       c = root->cmp (key, node->key);
291
292       if (c < 0)
293           node = node->left;
294       else if (c > 0)
295           node = node->right;
296       else
297         {
298           psplay_splay (&root->tree, node);
299           break;
300         }
301     }
302   return node;
303 }
304
305
306 PSplay
307 psplay_remove (PSplayroot root, PSplay node)
308 {
309   if (!node) return NULL;
310
311   PSplay p = node->up;
312   PSplay* r;
313
314   if (p)
315     {
316       if (p->left == node)
317         r = &p->left;
318       else
319         r = &p->right;
320     }
321   else
322     r = &root->tree;
323
324   if (!node->left)
325     {
326       // only right leaf
327       *r = node->right;
328       if (*r)
329         (*r)->up = p;
330     }
331   else if (!node->right)
332     {
333       // only left leaf
334       *r = node->left;
335       if (*r)
336         (*r)->up = p;
337     }
338   else
339     {
340       PSplay i;
341       if (psplay_fast_prng()&1) /* 50% probability removing left or right wards */
342         {
343           //left right
344           for (i = node->left; i->right; i = i->right);
345
346           i->right = node->right;
347           i->right->up = i;
348           i->up->right = i->left;
349
350           if (i->left)
351             i->left->up = i->up;
352
353           if (node->left != i)
354             {
355               i->left = node->left;
356               i->left->up = i;
357             }
358         }
359       else
360         {
361           // right right
362           for (i = node->right; i->left; i = i->left);
363
364           i->left = node->left;
365           i->left->up = i;
366           i->up->left = i->right;
367
368           if (i->right)
369             i->right->up = i->up;
370
371           if (node->right != i)
372             {
373               i->right = node->right;
374               i->right->up = i;
375             }
376         }
377       i->up = node->up;
378       *r = i;
379     }
380   node->up = node->left = node->right = NULL;
381   --root->elem_cnt;
382   return node;
383 }
384
385 /*
386   Walking a tree calls a 'action' three times PSPLAY_PREORDER before visiting the left subtree,
387   PSPLAY_INORDER after visiting the left subtree and before the right subtree, PSPLAY_POSTORDER
388   finally after visiting the right subtree. Example: For to traverse the tree in order action
389   would only handle PSPLAY_INORDER.
390   This action returns PSLPLAY_CONT when the traversal of the tree shall continue.
391   An 'action' must not alter the tree itself but it can indicate aborting the tree traversal and
392   how the current node is handled by its return value:
393    PSPLAY_STOP:
394      just stops the traversal
395    PSPLAY_REMOVE:
396      stops the traversal and removes the current node, calling the delete handler registered in root
397    any other psplay_delete_t:
398      stops the traversal and removes the current node, calling the returned delete handler with it
399 */
400 const psplay_delete_t PSPLAY_CONT = (psplay_delete_t)0x0;
401 const psplay_delete_t PSPLAY_STOP = (psplay_delete_t)0x1;
402 const psplay_delete_t PSPLAY_REMOVE = (psplay_delete_t)0x2;
403
404 static int
405 psplay_handle (PSplayroot root, PSplay node, psplay_delete_t res)
406 {
407   if (res == PSPLAY_CONT)
408     return 1;
409
410   if (res == PSPLAY_STOP)
411     ;
412   else if (res == PSPLAY_REMOVE)
413     {
414       psplay_remove (root, node);
415       if (root->delete)
416         root->delete (node);
417     }
418   else
419     {
420       psplay_remove (root, node);
421       res (node);
422     }
423   return 0;
424 }
425
426
427 int
428 psplay_walk (PSplayroot root, PSplay node, psplay_action_t action, int level, void* data)
429 {
430   if (!root->tree)
431     return 1;
432
433   if (!node)
434     node = root->tree;
435
436   psplay_delete_t res;
437
438   res = action (node, PSPLAY_PREORDER, level, data);
439   if (!psplay_handle (root, node, res))
440     return 0;
441
442   if (node->left)
443     if (!psplay_walk (root, node->left, action, level+1, data))
444       return 0;
445
446   res = action (node, PSPLAY_INORDER, level, data);
447   if (!psplay_handle (root, node, res))
448     return 0;
449
450   if (node->right)
451     if (!psplay_walk (root, node->right, action, level+1, data))
452       return 0;
453
454   res = action (node, PSPLAY_POSTORDER, level, data);
455   if (!psplay_handle (root, node, res))
456     return 0;
457
458   return 1;
459 }
460
461 psplay_delete_t psplay_print_node (PSplay node, const enum psplay_order_e which, int level, void* data)
462 {
463   static char* sp = "                                        ";
464   if (level>40) return;
465
466   FILE* fh = data;
467
468   switch (which)
469     {
470     case PSPLAY_PREORDER:
471       fprintf (fh, "%s%p\n", sp+40-level, node);
472       fprintf (fh, "%skey %p (%.4s)\n", sp+40-level, node->key, node->key?node->key:"NULL");
473       fprintf (fh, "%sup %p\n", sp+40-level, node->up);
474       fprintf (fh, "%sleft %p\n", sp+40-level, node->left);
475       break;
476     case PSPLAY_INORDER:
477       fprintf (fh, "%sright %p\n", sp+40-level, node->right);
478       break;
479     case PSPLAY_POSTORDER:
480       break;
481     }
482
483   return PSPLAY_CONT;
484 }
485
486 void
487 psplay_dump (PSplayroot root, FILE* dest)
488 {
489   psplay_walk (root, NULL, psplay_print_node, 0, dest);
490   fprintf (dest, "\n");
491 }
492
493 int my_cmp (const void* a, const void* b)
494 {
495   return strcmp (a, b);
496 }
497
498
499 #ifdef PSPLAY_TESTMAIN
500 int
501 main ()
502 {
503   psplayroot root = PSPLAYROOT_INITIALIZER(my_cmp, NULL);
504   psplay_init_root (&root, my_cmp, psplay_delete);
505
506   psplay_insert (&root, psplay_new("foo"));
507   psplay_insert (&root, psplay_new("bar"));
508   psplay_insert (&root, psplay_new("baz"));
509   psplay_insert (&root, psplay_new("test"));
510   psplay_insert (&root, psplay_new("pap"));
511   psplay_insert (&root, psplay_new("qux"));
512
513   psplay_dump (&root, stdout);
514
515   PSplay f = psplay_find (&root, "baz");
516   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
517   psplay_dump (&root, stdout);
518
519   f = psplay_find (&root, "test");
520   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
521   psplay_dump (&root, stdout);
522
523   f = psplay_find (&root, "test");
524   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
525   psplay_dump (&root, stdout);
526
527   f = psplay_find (&root, "foo");
528   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
529   psplay_dump (&root, stdout);
530
531
532   psplay_delete (psplay_remove (&root, root.tree));
533   psplay_dump (&root, stdout);
534
535   psplay_delete (psplay_remove (&root, root.tree));
536   psplay_dump (&root, stdout);
537
538   psplay_delete (psplay_remove (&root, root.tree));
539   psplay_dump (&root, stdout);
540
541   printf ("destroying\n");
542   psplay_destroy_root (&root);
543   psplay_dump (&root, stdout);
544
545   psplay_delete (psplay_remove (&root, root.tree));
546   psplay_dump (&root, stdout);
547
548   psplay_delete (psplay_remove (&root, root.tree));
549   psplay_dump (&root, stdout);
550
551   psplay_delete (psplay_remove (&root, root.tree));
552   psplay_dump (&root, stdout);
553   return 0;
554 }
555 #endif