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