www.pipapo.org Git - rxpd/blob - 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