probabilistic splay tree
[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 /* simple prng with 2^31-1 cycle */
30 static inline uint32_t psplay_fast_prng ()
31 {
32   static uint32_t rnd=0xbabeface;
33   return rnd = rnd<<1 ^ ((rnd >> 30) & 1) ^ ((rnd>>2) & 1);
34 }
35
36
37 /*
38   probabilistic distribution as n/255 chance of splaying
39 */
40 #ifndef PSPLAY_PROB_ZIG
41 /* already near root, only approx 6% splay probability */
42 #define PSPLAY_PROB_ZIG 16
43 #endif
44 /* approx 63% splay probability */
45 #ifndef PSPLAY_PROB_ZIGZIG
46 #define PSPLAY_PROB_ZIGZIG 160
47 #endif
48 /* zigzag reduces the tree by 1 level, approx 88% splay probability */
49 #ifndef PSPLAY_PROB_ZIGZAG
50 #define PSPLAY_PROB_ZIGZAG 224
51 #endif
52
53 inline void
54 psplay_splay (PSplay_ref root, PSplay node)
55 {
56   while (node->up)
57     {
58       PSplay p = node->up;              // parent
59       PSplay g = p?p->up:NULL;          // grandparent
60
61       if (g)
62         {
63           if (p == g->left)
64             {
65               // zig..
66               if (node == p->left)
67                 {
68                   // zigzig
69                   if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
70                     return;
71
72                   g->left = p->right;
73                   if (g->left) g->left->up = g;
74                   p->right = g;
75
76                   p->left = node->right;
77                   if (p->left) p->left->up = p;
78                   node->right = p;
79
80                   node->up = g->up;
81                   g->up = p;
82                 }
83               else
84                 {
85                   // zigzag
86                   if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
87                     return;
88
89                   p->right = node->left;
90                   if (p->right) p->right->up = p;
91                   node->left = p;
92
93                   g->left = node->right;
94                   if (g->left) g->left->up = g;
95                   node->right = g;
96
97                   node->up = g->up;
98                   g->up = node;
99                 }
100             }
101           else
102             {
103               // zag..
104               if (node == p->left)
105                 {
106                   // zagzig
107                   if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
108                     return;
109
110                   p->left = node->right;
111                   if (p->left) p->left->up = p;
112                   node->right = p;
113
114                   g->right = node->left;
115                   if (g->right) g->right->up = g;
116                   node->left = g;
117
118                   node->up = g->up;
119                   g->up = node;
120                 }
121               else
122                 {
123                   // zagzag
124                   if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
125                     return;
126
127                   g->right = p->left;
128                   if (g->right) g->right->up = g;
129                   p->left = g;
130
131                   p->right = node->left;
132                   if (p->right) p->right->up = p;
133                   node->left = p;
134
135                   node->up = g->up;
136                   g->up = p;
137                 }
138             }
139
140           p->up = node;
141           if (node->up)
142             {
143               if (node->up->left == g)
144                 node->up->left = node;
145               else
146                 node->up->right = node;
147             }
148           else
149             {
150               *root = node;
151             }
152         }
153       else
154         {
155           if (p)
156             {
157               if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIG)
158                 return;
159
160               if (node == p->left)
161                 {
162                   // zig
163                   p->left = node->right;
164                   if (p->left) p->left->up = p;
165                   node->right = p;
166                 }
167               else
168                 {
169                   // zag
170                   p->right = node->left;
171                   if (p->right) p->right->up = p;
172                   node->left = p;
173                 }
174               p->up = node;
175               node->up = NULL;
176               *root = node;
177             }
178         }
179     }
180 }
181
182
183 PSplay
184 psplay_new (void * key)
185 {
186   return psplay_init (malloc (sizeof (psplay)), key);
187 }
188
189
190 PSplay
191 psplay_init (PSplay self, void* key)
192 {
193   if (self)
194     {
195       self->key = key;
196       self->up = self->left = self->right = NULL;
197     }
198 }
199
200 void
201 psplay_delete (PSplay node)
202 {
203   free (node);
204 };
205
206
207 PSplay
208 psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp)
209 {
210   PSplay n = *root;
211
212   if (!n)
213     *root = node;
214   else
215     {
216       while (n != node)
217         {
218           int c;
219           c = cmp (node->key, n->key);
220
221           if (c < 0)
222             {
223               if (!n->left)
224                 {
225                   n->left = node;
226                   node->up = n;
227                 }
228               n = n->left;
229             }
230           else if (c > 0)
231             {
232               if (!n->right)
233                 {
234                   n->right = node;
235                   node->up = n;
236                 }
237               n = n->right;
238             }
239           else
240             return NULL;
241         }
242       psplay_splay (root, node);
243     }
244   return node;
245 }
246
247
248 PSplay
249 psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp)
250 {
251   PSplay node = *root;
252
253   while (node)
254     {
255       int c;
256       c = cmp (key, node->key);
257
258       if (c < 0)
259           node = node->left;
260       else if (c > 0)
261           node = node->right;
262       else
263         {
264           psplay_splay (root, node);
265           break;
266         }
267     }
268   return node;
269 }
270
271
272 PSplay
273 psplay_remove (PSplay_ref root, PSplay node)
274 {
275   if (!node) return NULL;
276
277   PSplay p = node->up;
278   PSplay_ref r;
279
280   if (p)
281     {
282       if (p->left == node)
283         r = &p->left;
284       else
285         r = &p->right;
286     }
287   else
288     r = root;
289
290   if (!node->left)
291     {
292       // only right leaf
293       *r = node->right;
294       if (*r)
295         (*r)->up = p;
296     }
297   else if (!node->right)
298     {
299       // only left leaf
300       *r = node->left;
301       if (*r)
302         (*r)->up = p;
303     }
304   else
305     {
306       PSplay i;
307       if (psplay_fast_prng()&1) /* 50% probability removing left or right wards */
308         {
309           //left right
310           for (i = node->left; i->right; i = i->right);
311
312           i->right = node->right;
313           i->right->up = i;
314           i->up->right = i->left;
315
316           if (i->left)
317             i->left->up = i->up;
318
319           if (node->left != i)
320             {
321               i->left = node->left;
322               i->left->up = i;
323             }
324         }
325       else
326         {
327           // right right
328           for (i = node->right; i->left; i = i->left);
329
330           i->left = node->left;
331           i->left->up = i;
332           i->up->left = i->right;
333
334           if (i->right)
335             i->right->up = i->up;
336
337           if (node->right != i)
338             {
339               i->right = node->right;
340               i->right->up = i;
341             }
342         }
343       i->up = node->up;
344       *r = i;
345     }
346   return node;
347 }
348
349 /*
350 void
351 psplay_dump (PSplay root, FILE* dest, unsigned level)
352 {
353   static char* sp = "                                        ";
354   fprintf (dest, "%s%p\n", sp+40-level, root);
355   if (level>40 || !root) return;
356   fprintf (dest, "%skey %p (%.4s)\n", sp+40-level, root->key, root->key?root->key:"NULL");
357   fprintf (dest, "%sup %p\n", sp+40-level, root->up);
358   fprintf (dest, "%sleft %p\n", sp+40-level, root->left);
359   psplay_dump (root->left, dest, level+3);
360   fprintf (dest, "%sright %p\n", sp+40-level, root->right);
361   psplay_dump (root->right, dest, level+3);
362   if (level == 0) fprintf (dest, "\n");
363 }
364 */
365
366 /*
367
368 int my_cmp (const void* a, const void* b)
369 {
370   return strcmp (a, b);
371 }
372
373 int
374 main ()
375 {
376   PSplay tree = NULL;
377
378   psplay_insert (&tree, psplay_new("foo"), my_cmp);
379   psplay_insert (&tree, psplay_new("bar"), my_cmp);
380   psplay_insert (&tree, psplay_new("baz"), my_cmp);
381   psplay_insert (&tree, psplay_new("test"), my_cmp);
382   psplay_insert (&tree, psplay_new("pap"), my_cmp);
383   psplay_insert (&tree, psplay_new("qux"), my_cmp);
384
385   psplay_dump (tree, stdout, 0);
386
387   PSplay f = psplay_find (&tree, "baz", my_cmp);
388   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
389   psplay_dump (tree, stdout, 0);
390
391   f = psplay_find (&tree, "test", my_cmp);
392   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
393   psplay_dump (tree, stdout, 0);
394
395   f = psplay_find (&tree, "test", my_cmp);
396   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
397   psplay_dump (tree, stdout, 0);
398
399   f = psplay_find (&tree, "foo", my_cmp);
400   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
401   psplay_dump (tree, stdout, 0);
402
403
404   psplay_delete (psplay_remove (&tree, tree));
405   psplay_dump (tree, stdout, 0);
406
407   psplay_delete (psplay_remove (&tree, tree));
408   psplay_dump (tree, stdout, 0);
409
410   psplay_delete (psplay_remove (&tree, tree));
411   psplay_dump (tree, stdout, 0);
412
413   psplay_delete (psplay_remove (&tree, tree));
414   psplay_dump (tree, stdout, 0);
415
416   psplay_delete (psplay_remove (&tree, tree));
417   psplay_dump (tree, stdout, 0);
418
419   psplay_delete (psplay_remove (&tree, tree));
420   psplay_dump (tree, stdout, 0);
421   return 0;
422 }
423 */