fixed return value, limit dumping to level 40
[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
462 psplay_print_node (PSplay node, const enum psplay_order_e which, int level, void* data)
463 {
464   FILE* fh = data;
465   static char* sp = "                                        ";
466   if (level>40)
467     {
468       if (which == PSPLAY_PREORDER)
469         fprintf (fh, "%s ...\n", sp+40-level);
470       return PSPLAY_CONT;
471     }
472
473   switch (which)
474     {
475     case PSPLAY_PREORDER:
476       fprintf (fh, "%s%p\n", sp+40-level, node);
477       fprintf (fh, "%skey %p (%.4s)\n", sp+40-level, node->key, node->key?node->key:"NULL");
478       fprintf (fh, "%sup %p\n", sp+40-level, node->up);
479       fprintf (fh, "%sleft %p\n", sp+40-level, node->left);
480       break;
481     case PSPLAY_INORDER:
482       fprintf (fh, "%sright %p\n", sp+40-level, node->right);
483       break;
484     case PSPLAY_POSTORDER:
485       break;
486     }
487
488   return PSPLAY_CONT;
489 }
490
491 void
492 psplay_dump (PSplayroot root, FILE* dest)
493 {
494   psplay_walk (root, NULL, psplay_print_node, 0, dest);
495   fprintf (dest, "\n");
496 }
497
498 int my_cmp (const void* a, const void* b)
499 {
500   return strcmp (a, b);
501 }
502
503
504 #ifdef PSPLAY_TESTMAIN
505 int
506 main ()
507 {
508   psplayroot root = PSPLAYROOT_INITIALIZER(my_cmp, NULL);
509   psplay_init_root (&root, my_cmp, psplay_delete);
510
511   psplay_insert (&root, psplay_new("foo"));
512   psplay_insert (&root, psplay_new("bar"));
513   psplay_insert (&root, psplay_new("baz"));
514   psplay_insert (&root, psplay_new("test"));
515   psplay_insert (&root, psplay_new("pap"));
516   psplay_insert (&root, psplay_new("qux"));
517
518   psplay_dump (&root, stdout);
519
520   PSplay f = psplay_find (&root, "baz");
521   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
522   psplay_dump (&root, stdout);
523
524   f = psplay_find (&root, "test");
525   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
526   psplay_dump (&root, stdout);
527
528   f = psplay_find (&root, "test");
529   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
530   psplay_dump (&root, stdout);
531
532   f = psplay_find (&root, "foo");
533   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
534   psplay_dump (&root, stdout);
535
536
537   psplay_delete (psplay_remove (&root, root.tree));
538   psplay_dump (&root, stdout);
539
540   psplay_delete (psplay_remove (&root, root.tree));
541   psplay_dump (&root, stdout);
542
543   psplay_delete (psplay_remove (&root, root.tree));
544   psplay_dump (&root, stdout);
545
546   printf ("destroying\n");
547   psplay_destroy_root (&root);
548   psplay_dump (&root, stdout);
549
550   psplay_delete (psplay_remove (&root, root.tree));
551   psplay_dump (&root, stdout);
552
553   psplay_delete (psplay_remove (&root, root.tree));
554   psplay_dump (&root, stdout);
555
556   psplay_delete (psplay_remove (&root, root.tree));
557   psplay_dump (&root, stdout);
558   return 0;
559 }
560 #endif