probabilistic splay tree
authorChristian Thaeter <ct@pipapo.org>
Sun, 30 Sep 2007 01:40:12 +0000 (03:40 +0200)
committerChristian Thaeter <ct@pipapo.org>
Sun, 30 Sep 2007 01:40:12 +0000 (03:40 +0200)
psplay.c [new file with mode: 0644]
psplay.h [new file with mode: 0644]

diff --git a/psplay.c b/psplay.c
new file mode 100644 (file)
index 0000000..b9c7fe1
--- /dev/null
+++ b/psplay.c
@@ -0,0 +1,423 @@
+/*
+    psplay.c - probabilistic splay tree
+
+  Copyright (C)
+    2004, 2005, 2006,   Christian Thaeter <chth@gmx.net>
+  Copyright (C)         CinelerraCV
+    2007,               Christian Thaeter <ct@pipapo.org>
+
+  This program is free software; you can redistribute it and/or
+  modify it under the terms of the GNU General Public License as
+  published by the Free Software Foundation; either version 2 of the
+  License, or (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "psplay.h"
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+/* simple prng with 2^31-1 cycle */
+static inline uint32_t psplay_fast_prng ()
+{
+  static uint32_t rnd=0xbabeface;
+  return rnd = rnd<<1 ^ ((rnd >> 30) & 1) ^ ((rnd>>2) & 1);
+}
+
+
+/*
+  probabilistic distribution as n/255 chance of splaying
+*/
+#ifndef PSPLAY_PROB_ZIG
+/* already near root, only approx 6% splay probability */
+#define PSPLAY_PROB_ZIG 16
+#endif
+/* approx 63% splay probability */
+#ifndef PSPLAY_PROB_ZIGZIG
+#define PSPLAY_PROB_ZIGZIG 160
+#endif
+/* zigzag reduces the tree by 1 level, approx 88% splay probability */
+#ifndef PSPLAY_PROB_ZIGZAG
+#define PSPLAY_PROB_ZIGZAG 224
+#endif
+
+inline void
+psplay_splay (PSplay_ref root, PSplay node)
+{
+  while (node->up)
+    {
+      PSplay p = node->up;              // parent
+      PSplay g = p?p->up:NULL;          // grandparent
+
+      if (g)
+        {
+          if (p == g->left)
+            {
+              // zig..
+              if (node == p->left)
+                {
+                  // zigzig
+                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
+                    return;
+
+                  g->left = p->right;
+                  if (g->left) g->left->up = g;
+                  p->right = g;
+
+                  p->left = node->right;
+                  if (p->left) p->left->up = p;
+                  node->right = p;
+
+                  node->up = g->up;
+                  g->up = p;
+                }
+              else
+                {
+                  // zigzag
+                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
+                    return;
+
+                  p->right = node->left;
+                  if (p->right) p->right->up = p;
+                  node->left = p;
+
+                  g->left = node->right;
+                  if (g->left) g->left->up = g;
+                  node->right = g;
+
+                  node->up = g->up;
+                  g->up = node;
+                }
+            }
+          else
+            {
+              // zag..
+              if (node == p->left)
+                {
+                  // zagzig
+                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
+                    return;
+
+                  p->left = node->right;
+                  if (p->left) p->left->up = p;
+                  node->right = p;
+
+                  g->right = node->left;
+                  if (g->right) g->right->up = g;
+                  node->left = g;
+
+                  node->up = g->up;
+                  g->up = node;
+                }
+              else
+                {
+                  // zagzag
+                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
+                    return;
+
+                  g->right = p->left;
+                  if (g->right) g->right->up = g;
+                  p->left = g;
+
+                  p->right = node->left;
+                  if (p->right) p->right->up = p;
+                  node->left = p;
+
+                  node->up = g->up;
+                  g->up = p;
+                }
+            }
+
+          p->up = node;
+          if (node->up)
+            {
+              if (node->up->left == g)
+                node->up->left = node;
+              else
+                node->up->right = node;
+            }
+          else
+            {
+              *root = node;
+            }
+        }
+      else
+        {
+          if (p)
+            {
+              if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIG)
+                return;
+
+              if (node == p->left)
+                {
+                  // zig
+                  p->left = node->right;
+                  if (p->left) p->left->up = p;
+                  node->right = p;
+                }
+              else
+                {
+                  // zag
+                  p->right = node->left;
+                  if (p->right) p->right->up = p;
+                  node->left = p;
+                }
+              p->up = node;
+              node->up = NULL;
+              *root = node;
+            }
+        }
+    }
+}
+
+
+PSplay
+psplay_new (void * key)
+{
+  return psplay_init (malloc (sizeof (psplay)), key);
+}
+
+
+PSplay
+psplay_init (PSplay self, void* key)
+{
+  if (self)
+    {
+      self->key = key;
+      self->up = self->left = self->right = NULL;
+    }
+}
+
+void
+psplay_delete (PSplay node)
+{
+  free (node);
+};
+
+
+PSplay
+psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp)
+{
+  PSplay n = *root;
+
+  if (!n)
+    *root = node;
+  else
+    {
+      while (n != node)
+        {
+          int c;
+          c = cmp (node->key, n->key);
+
+          if (c < 0)
+            {
+              if (!n->left)
+                {
+                  n->left = node;
+                  node->up = n;
+                }
+              n = n->left;
+            }
+          else if (c > 0)
+            {
+              if (!n->right)
+                {
+                  n->right = node;
+                  node->up = n;
+                }
+              n = n->right;
+            }
+          else
+            return NULL;
+        }
+      psplay_splay (root, node);
+    }
+  return node;
+}
+
+
+PSplay
+psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp)
+{
+  PSplay node = *root;
+
+  while (node)
+    {
+      int c;
+      c = cmp (key, node->key);
+
+      if (c < 0)
+          node = node->left;
+      else if (c > 0)
+          node = node->right;
+      else
+        {
+          psplay_splay (root, node);
+          break;
+        }
+    }
+  return node;
+}
+
+
+PSplay
+psplay_remove (PSplay_ref root, PSplay node)
+{
+  if (!node) return NULL;
+
+  PSplay p = node->up;
+  PSplay_ref r;
+
+  if (p)
+    {
+      if (p->left == node)
+        r = &p->left;
+      else
+        r = &p->right;
+    }
+  else
+    r = root;
+
+  if (!node->left)
+    {
+      // only right leaf
+      *r = node->right;
+      if (*r)
+        (*r)->up = p;
+    }
+  else if (!node->right)
+    {
+      // only left leaf
+      *r = node->left;
+      if (*r)
+        (*r)->up = p;
+    }
+  else
+    {
+      PSplay i;
+      if (psplay_fast_prng()&1) /* 50% probability removing left or right wards */
+        {
+          //left right
+          for (i = node->left; i->right; i = i->right);
+
+          i->right = node->right;
+          i->right->up = i;
+          i->up->right = i->left;
+
+          if (i->left)
+            i->left->up = i->up;
+
+          if (node->left != i)
+            {
+              i->left = node->left;
+              i->left->up = i;
+            }
+        }
+      else
+        {
+          // right right
+          for (i = node->right; i->left; i = i->left);
+
+          i->left = node->left;
+          i->left->up = i;
+          i->up->left = i->right;
+
+          if (i->right)
+            i->right->up = i->up;
+
+          if (node->right != i)
+            {
+              i->right = node->right;
+              i->right->up = i;
+            }
+        }
+      i->up = node->up;
+      *r = i;
+    }
+  return node;
+}
+
+/*
+void
+psplay_dump (PSplay root, FILE* dest, unsigned level)
+{
+  static char* sp = "                                        ";
+  fprintf (dest, "%s%p\n", sp+40-level, root);
+  if (level>40 || !root) return;
+  fprintf (dest, "%skey %p (%.4s)\n", sp+40-level, root->key, root->key?root->key:"NULL");
+  fprintf (dest, "%sup %p\n", sp+40-level, root->up);
+  fprintf (dest, "%sleft %p\n", sp+40-level, root->left);
+  psplay_dump (root->left, dest, level+3);
+  fprintf (dest, "%sright %p\n", sp+40-level, root->right);
+  psplay_dump (root->right, dest, level+3);
+  if (level == 0) fprintf (dest, "\n");
+}
+*/
+
+/*
+
+int my_cmp (const void* a, const void* b)
+{
+  return strcmp (a, b);
+}
+
+int
+main ()
+{
+  PSplay tree = NULL;
+
+  psplay_insert (&tree, psplay_new("foo"), my_cmp);
+  psplay_insert (&tree, psplay_new("bar"), my_cmp);
+  psplay_insert (&tree, psplay_new("baz"), my_cmp);
+  psplay_insert (&tree, psplay_new("test"), my_cmp);
+  psplay_insert (&tree, psplay_new("pap"), my_cmp);
+  psplay_insert (&tree, psplay_new("qux"), my_cmp);
+
+  psplay_dump (tree, stdout, 0);
+
+  PSplay f = psplay_find (&tree, "baz", my_cmp);
+  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
+  psplay_dump (tree, stdout, 0);
+
+  f = psplay_find (&tree, "test", my_cmp);
+  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
+  psplay_dump (tree, stdout, 0);
+
+  f = psplay_find (&tree, "test", my_cmp);
+  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
+  psplay_dump (tree, stdout, 0);
+
+  f = psplay_find (&tree, "foo", my_cmp);
+  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
+  psplay_dump (tree, stdout, 0);
+
+
+  psplay_delete (psplay_remove (&tree, tree));
+  psplay_dump (tree, stdout, 0);
+
+  psplay_delete (psplay_remove (&tree, tree));
+  psplay_dump (tree, stdout, 0);
+
+  psplay_delete (psplay_remove (&tree, tree));
+  psplay_dump (tree, stdout, 0);
+
+  psplay_delete (psplay_remove (&tree, tree));
+  psplay_dump (tree, stdout, 0);
+
+  psplay_delete (psplay_remove (&tree, tree));
+  psplay_dump (tree, stdout, 0);
+
+  psplay_delete (psplay_remove (&tree, tree));
+  psplay_dump (tree, stdout, 0);
+  return 0;
+}
+*/
diff --git a/psplay.h b/psplay.h
new file mode 100644 (file)
index 0000000..d9645f7
--- /dev/null
+++ b/psplay.h
@@ -0,0 +1,67 @@
+/*
+    psplay.h - probabilistic splay tree
+
+  Copyright (C)
+    2004, 2005, 2006,   Christian Thaeter <chth@gmx.net>
+  Copyright (C)         CinelerraCV
+    2007,               Christian Thaeter <ct@pipapo.org>
+
+  This program is free software; you can redistribute it and/or
+  modify it under the terms of the GNU General Public License as
+  published by the Free Software Foundation; either version 2 of the
+  License, or (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#ifndef PSPLAY_H
+#define PSPLAY_H
+
+#include <stdint.h>
+#include <stdio.h>
+
+typedef struct psplay_struct psplay;
+typedef psplay* PSplay;
+typedef PSplay* PSplay_ref;
+
+struct psplay_struct
+{
+  void* key;
+  PSplay up;
+  PSplay left;
+  PSplay right;
+};
+
+typedef int (*psplay_cmp_t)(const void*, const void*);
+
+PSplay
+psplay_new (void * key);
+
+PSplay
+psplay_init (PSplay self, void* key);
+
+void
+psplay_delete (PSplay node);
+
+PSplay
+psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp);
+
+PSplay
+psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp);
+
+PSplay
+psplay_remove (PSplay_ref root, PSplay node);
+
+/*
+void
+psplay_dump (PSplay root, FILE* dest, unsigned level);
+*/
+
+#endif