Re: Splay trees
- From: "Timur I. Bakeyev" <gtk listserv bat ru>
- To: gtk-devel-list redhat com
- Subject: Re: Splay trees
- Date: Thu, 18 Mar 1999 04:22:20 +0300
On Mon, Mar 15, 1999 at 11:29:48AM +0100, Soeren Sandmann wrote:
>
> On march 5th I uploaded a patch that implements splay trees, but I have
> not heard anything since, nor has the patch been moved to
> ftp.gtk.org/pub/gtk/patches.
>
> Is this patch going to be included in GLib?
I've got patches from the author and attach them in this letter. Please,
check and consider, if this'll go to the GLib. From my point of view, Splay
Trees is a useful code, and should go into the library. There are several
cases, when they simplify our (programmers) life and give a neat solution.
One more point - caches, based on splay trees allows easy implementation
of LRU algorithm, if any...
With best regards, Timur Bakeyev.
P.S> Where such pieces of code should go in CVS - into HEAD or HACKS?
==============================================================================
Here is the author's comments:
This patch implements splay trees.
Splay trees are self adjusting binary search trees that have several advantages over other trees:
*) They are faster for skewed access patterns since they contain a kind of
builtin cache.
*) They do not use any memory for balancing information.
I will write reference documentation for them if the patch is accepted
into GLib.
The patch is made with diff -Pur.
Søren Sandmann
=============================================================================
Here is a comment from Samba, which also uses Splay Trees:
/*
* This module implements "splay" trees. Splay trees are binary trees
* that are rearranged (splayed) whenever a node is accessed. The
* splaying process *tends* to make the tree bushier (improves balance),
* and the nodes that are accessed most frequently *tend* to be closer to
* the top.
*
* References: "Self-Adjusting Binary Search Trees", by Daniel Sleator and
* Robert Tarjan. Journal of the Association for Computing
* Machinery Vol 32, No. 3, July 1985 pp. 652-686
*
* See also: http://www.cs.cmu.edu/~sleator/
*/
=============================================================================
--- ./tests/Makefile.am.orig Mon Mar 15 20:18:50 1999
+++ ./tests/Makefile.am Thu Mar 18 03:20:47 1999
@@ -11,6 +11,7 @@
queue-test \
relation-test \
slist-test \
+ splaytree-test \
stack-test \
string-test \
strfunc-test \
@@ -28,6 +29,7 @@
queue_test_LDADD = $(top_builddir)/libglib.la
relation_test_LDADD = $(top_builddir)/libglib.la
slist_test_LDADD = $(top_builddir)/libglib.la
+splaytree_test_LDADD = $(top_builddir)/libglib.la
stack_test_LDADD = $(top_builddir)/libglib.la
string_test_LDADD = $(top_builddir)/libglib.la
strfunc_test_LDADD = $(top_builddir)/libglib.la
--- ./tests/splaytree-test.c.orig Thu Mar 18 03:44:09 1999
+++ ./tests/splaytree-test.c Thu Mar 18 03:13:28 1999
@@ -0,0 +1,108 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+#undef G_LOG_DOMAIN
+
+#include <stdio.h>
+#include <string.h>
+#include "glib.h"
+
+int array[10000];
+gboolean failed = FALSE;
+
+#define TEST(m,cond) G_STMT_START { failed = !(cond); \
+if (failed) \
+ { if (!m) \
+ g_print ("\n(%s:%d) failed for: %s\n", __FILE__, __LINE__, ( # cond )); \
+ else \
+ g_print ("\n(%s:%d) failed for: %s: (%s)\n", __FILE__, __LINE__, ( # cond ), (gchar*)m); \
+ } \
+else \
+ g_print ("."); fflush (stdout); \
+} G_STMT_END
+
+#define C2P(c) ((gpointer) ((long) (c)))
+#define P2C(p) ((gchar) ((long) (p)))
+
+#define GLIB_TEST_STRING "el dorado "
+#define GLIB_TEST_STRING_5 "el do"
+
+typedef struct {
+ guint age;
+ gchar name[40];
+} GlibTestInfo;
+
+
+static gint
+my_compare (gconstpointer a,
+ gconstpointer b)
+{
+ const char *cha = a;
+ const char *chb = b;
+
+ return *cha - *chb;
+}
+
+static gint
+my_traverse (gpointer key,
+ gpointer value,
+ gpointer data)
+{
+ char *ch = key;
+ g_assert ((*ch) > 0);
+ return FALSE;
+}
+
+int
+main (int argc,
+ char *argv[])
+{
+ gint i, j;
+ GSplayTree *tree;
+ char chars[62];
+
+ tree = g_splay_tree_new (my_compare);
+ i = 0;
+ for (j = 0; j < 10; j++, i++)
+ {
+ chars[i] = '0' + j;
+ g_splay_tree_insert (tree, &chars[i], &chars[i]);
+ }
+ for (j = 0; j < 26; j++, i++)
+ {
+ chars[i] = 'A' + j;
+ g_splay_tree_insert (tree, &chars[i], &chars[i]);
+ }
+ for (j = 0; j < 26; j++, i++)
+ {
+ chars[i] = 'a' + j;
+ g_splay_tree_insert (tree, &chars[i], &chars[i]);
+ }
+
+ g_splay_tree_traverse (tree, my_traverse, G_IN_ORDER, NULL);
+
+ g_assert (g_splay_tree_nnodes (tree) == (10 + 26 + 26));
+
+ for (i = 0; i < 10; i++)
+ g_splay_tree_remove (tree, &chars[i]);
+
+ g_splay_tree_traverse (tree, my_traverse, G_IN_ORDER, NULL);
+
+ return 0;
+}
+
--- ./glib.def.orig Mon Mar 15 20:18:40 1999
+++ ./glib.def Thu Mar 18 03:22:16 1999
@@ -324,6 +324,15 @@
g_source_remove
g_source_remove_by_source_data
g_source_remove_by_user_data
+ g_splay_tree_new
+ g_splay_tree_destroy
+ g_splay_tree_insert
+ g_splay_tree_remove
+ g_splay_tree_lookup
+ g_splay_tree_traverse
+ g_splay_tree_height
+ g_splay_tree_nnodes
+ g_splay_tree_delete_min
g_static_mutex_get_mutex_impl
g_static_private_get
g_static_private_set
--- ./Makefile.am.orig Mon Mar 15 20:18:36 1999
+++ ./Makefile.am Thu Mar 18 03:17:54 1999
@@ -48,6 +48,7 @@
grel.c \
gscanner.c \
gslist.c \
+ gsplaytree.c \
gstack.c \
gstrfuncs.c \
gstring.c \
--- ./glib.h.orig Wed Mar 17 18:58:56 1999
+++ ./glib.h Thu Mar 18 03:16:13 1999
@@ -702,6 +702,7 @@
typedef struct _GScanner GScanner;
typedef struct _GScannerConfig GScannerConfig;
typedef struct _GSList GSList;
+typedef struct _GSplayTree GSplayTree;
typedef struct _GStack GStack;
typedef struct _GString GString;
typedef struct _GStringChunk GStringChunk;
@@ -1097,6 +1098,26 @@
gint g_tree_height (GTree *tree);
gint g_tree_nnodes (GTree *tree);
+
+
+/* Splay trees
+ */
+GSplayTree* g_splay_tree_new (GCompareFunc key_compare_func);
+void g_splay_tree_destroy (GSplayTree *stree);
+void g_splay_tree_insert (GSplayTree *stree,
+ gpointer key,
+ gpointer value);
+void g_splay_tree_remove (GSplayTree *stree,
+ gpointer key);
+gpointer g_splay_tree_lookup (GSplayTree *stree,
+ gpointer key);
+void g_splay_tree_traverse (GSplayTree *stree,
+ GTraverseFunc traverse_func,
+ GTraverseType traverse_type,
+ gpointer data);
+gint g_splay_tree_height (GSplayTree *stree);
+gint g_splay_tree_nnodes (GSplayTree *stree);
+void g_splay_tree_delete_min (GSplayTree *stree);
/* N-way tree implementation
--- ./gsplaytree.c.orig Thu Mar 18 03:43:39 1999
+++ ./gsplaytree.c Thu Mar 18 03:13:27 1999
@@ -0,0 +1,642 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * MT safe
+ */
+#include "glib.h"
+
+
+typedef struct _GRealSplayTree GRealSplayTree;
+typedef struct _GSplayTreeNode GSplayTreeNode;
+
+struct _GRealSplayTree
+{
+ GSplayTreeNode *root;
+ GCompareFunc key_compare;
+};
+
+struct _GSplayTreeNode
+{
+ GSplayTreeNode *left; /* left subtree */
+ GSplayTreeNode *right; /* right subtree */
+ gpointer key; /* key for this node */
+ gpointer value; /* value stored at this node */
+};
+
+static GSplayTreeNode *g_splay_tree_node_new (gpointer key,
+ gpointer value);
+static void g_splay_tree_node_free (GSplayTreeNode *node);
+static void g_splay_tree_node_destroy (GSplayTreeNode *node);
+static GSplayTreeNode *g_splay_tree_node_splay (GSplayTreeNode *node,
+ GCompareFunc compare,
+ gpointer key);
+static GSplayTreeNode *g_splay_tree_node_splay_max (GSplayTreeNode *node);
+static GSplayTreeNode *g_splay_tree_node_splay_min (GSplayTreeNode *node);
+static GSplayTreeNode *g_splay_tree_node_insert (GSplayTreeNode *node,
+ GCompareFunc compare,
+ gpointer key,
+ gpointer value);
+static GSplayTreeNode *g_splay_tree_node_join (GSplayTreeNode *node1,
+ GSplayTreeNode *node2);
+static GSplayTreeNode *g_splay_tree_node_remove (GSplayTreeNode *node,
+ GCompareFunc compare,
+ gpointer key);
+static GSplayTreeNode *g_splay_tree_node_delete_min (GSplayTreeNode *node);
+static gint g_splay_tree_node_pre_order (GSplayTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_splay_tree_node_in_order (GSplayTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_splay_tree_node_post_order (GSplayTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_splay_tree_node_count (GSplayTreeNode *node);
+static gint g_splay_tree_node_height (GSplayTreeNode *node);
+
+G_LOCK_DEFINE_STATIC (g_splay_tree_global);
+static GMemChunk *node_mem_chunk = NULL;
+static GSplayTreeNode *node_free_list = NULL;
+
+
+static GSplayTreeNode *
+g_splay_tree_node_new (gpointer key, gpointer value)
+{
+ GSplayTreeNode *node;
+
+ G_LOCK (g_splay_tree_global);
+ if (node_free_list)
+ {
+ node = node_free_list;
+ node_free_list = node->right;
+ }
+ else
+ {
+ if (!node_mem_chunk)
+ node_mem_chunk = g_mem_chunk_new ("GLib GSplayTreeNode mem chunk",
+ sizeof (GSplayTreeNode),
+ 1024,
+ G_ALLOC_ONLY);
+
+ node = g_chunk_new (GSplayTreeNode, node_mem_chunk);
+ }
+ G_UNLOCK (g_splay_tree_global);
+
+ node -> key = key;
+ node -> value = value;
+ return node;
+}
+
+static void
+g_splay_tree_node_destroy (GSplayTreeNode *node)
+{
+ if (node)
+ {
+ g_splay_tree_node_destroy (node->right);
+ g_splay_tree_node_destroy (node->left);
+ g_splay_tree_node_free (node);
+ }
+}
+
+static void
+g_splay_tree_node_free (GSplayTreeNode *node)
+{
+ G_LOCK (g_splay_tree_global);
+ node->right = node_free_list;
+ node_free_list = node;
+ G_UNLOCK (g_splay_tree_global);
+}
+
+static GSplayTreeNode *
+g_splay_tree_node_splay (GSplayTreeNode *node,
+ GCompareFunc compare,
+ gpointer key)
+{
+ gint cmp;
+
+ GSplayTreeNode *left_max, *right_min, header, *tmp;
+
+ header.left = header.right = NULL;
+ left_max = right_min = &header;
+
+ if (node == NULL)
+ return node;
+
+ while ( (cmp = (* compare)(key, node->key)) != 0)
+ {
+ if (cmp < 0)
+ {
+ if (node->left == NULL)
+ break;
+ cmp = (* compare)(key, node->left->key);
+ if (cmp == 0)
+ {
+ /* link right */
+ right_min->left = node;
+ right_min = node;
+ node = node->left;
+ }
+ else if (cmp < 0)
+ {
+ /* rotate right */
+ tmp = node->left;
+ node->left = tmp->right;
+ tmp->right = node;
+ if (tmp->left == NULL)
+ {
+ node = tmp;
+ break;
+ }
+ /* link right */
+ right_min->left = tmp;
+ right_min = tmp;
+ node = tmp->left;
+ }
+ else
+ {
+ /* link right */
+ right_min->left = node;
+ right_min = node;
+ node = node->left;
+ if (node->right == NULL)
+ break;
+ /* link left */
+ left_max->right = node;
+ left_max = node;
+ node = node->right;
+ }
+ }
+ else
+ {
+ if (node->right == NULL)
+ break;
+ cmp = (* compare)(key, node->right->key);
+ if (cmp == 0)
+ {
+ /* link left */
+ left_max->right = node;
+ left_max = node;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ {
+ /* rotate left */
+ tmp = node->right;
+ node->right = tmp->left;
+ tmp->left = node;
+ if (tmp->right == NULL)
+ {
+ node = tmp;
+ break;
+ }
+ /* link left */
+ left_max->right = tmp;
+ left_max = tmp;
+ node = tmp->right;
+ }
+ else
+ {
+ /* link left */
+ left_max->right = node;
+ left_max = node;
+ node = node->right;
+ if (node->left == NULL)
+ break;
+ /* link right */
+ right_min->left = node;
+ right_min = node;
+ node = node->left;
+ }
+ }
+ }
+ /* assemble */
+ left_max->right = node->left;
+ right_min->left = node->right;
+ node->left = header.right;
+ node->right = header.left;
+ return node;
+}
+
+static GSplayTreeNode *
+g_splay_tree_node_splay_min (GSplayTreeNode *node)
+{
+ GSplayTreeNode *left_max, *right_min, header, *tmp;
+
+ header.left = header.right = NULL;
+ left_max = right_min = &header;
+
+ if (node == NULL)
+ return node;
+
+ while ( TRUE )
+ {
+ if (node->left == NULL)
+ break;
+ /* rotate right */
+ tmp = node->left;
+ node->left = tmp->right;
+ tmp->right = node;
+ if (tmp->left == NULL)
+ {
+ node = tmp;
+ break;
+ }
+ /* link right */
+ right_min->left = tmp;
+ right_min = tmp;
+ node = tmp->left;
+ }
+ /* assemble */
+ left_max->right = node->left;
+ right_min->left = node->right;
+ node->left = header.right;
+ node->right = header.left;
+ return node;
+}
+
+static GSplayTreeNode *
+g_splay_tree_node_splay_max (GSplayTreeNode *node)
+{
+ GSplayTreeNode *left_max, *right_min, header, *tmp;
+
+ header.left = header.right = NULL;
+ left_max = right_min = &header;
+
+ if (node == NULL)
+ return node;
+
+ while ( TRUE )
+ {
+ if (node->right == NULL)
+ break;
+ /* rotate left */
+ tmp = node->right;
+ node->right = tmp->left;
+ tmp->left = node;
+ if (tmp->right == NULL)
+ {
+ node = tmp;
+ break;
+ }
+ /* link left */
+ left_max->right = tmp;
+ left_max = tmp;
+ node = tmp->right;
+
+ }
+ /* assemble */
+ left_max->right = node->left;
+ right_min->left = node->right;
+ node->left = header.right;
+ node->right = header.left;
+ return node;
+}
+
+
+static GSplayTreeNode *
+g_splay_tree_node_insert (GSplayTreeNode *node,
+ GCompareFunc compare,
+ gpointer key,
+ gpointer value)
+{
+ GSplayTreeNode *n;
+ gint cmp;
+
+ if (node)
+ {
+ cmp = (* compare)(node->key, key);
+
+ node = g_splay_tree_node_splay (node, compare, key);
+
+ if (cmp == 0)
+ return node;
+ else
+ {
+ n = g_splay_tree_node_new (key, value);
+ if (cmp > 0)
+ {
+ n -> right = node;
+ n -> left = node->left;
+ node -> left = NULL;
+ return n;
+ }
+ else
+ {
+ n -> left = node;
+ n -> right = node->right;
+ node -> right = NULL;
+ return n;
+ }
+ }
+ }
+ else
+ {
+ n = g_splay_tree_node_new (key, value);
+ n -> left = NULL;
+ n -> right = NULL;
+ return n;
+ }
+}
+
+static GSplayTreeNode *
+g_splay_tree_node_join (GSplayTreeNode *node1, GSplayTreeNode *node2)
+{
+ if (!node1)
+ return node2;
+ node1 = g_splay_tree_node_splay_max (node1);
+ node1 -> left = node2;
+ return node1;
+}
+
+static GSplayTreeNode *
+g_splay_tree_node_remove (GSplayTreeNode *node,
+ GCompareFunc compare,
+ gpointer key)
+{
+ GSplayTreeNode *r;
+
+ if (!node)
+ return node;
+
+ node = g_splay_tree_node_splay (node, compare, key);
+ if ((* compare)(node->key, key)==0)
+ {
+ r = g_splay_tree_node_join (node->left, node->right);
+ g_splay_tree_node_free (node);
+ return r;
+ }
+ else
+ return node;
+}
+
+static GSplayTreeNode *
+g_splay_tree_node_delete_min (GSplayTreeNode *node)
+{
+ GSplayTreeNode *n;
+
+ if (!node)
+ return node;
+
+ n = g_splay_tree_node_splay_min (node)->left;
+ g_splay_tree_node_free (node);
+
+ return n;
+}
+
+GSplayTree *
+g_splay_tree_new (GCompareFunc key_compare_func)
+{
+ GRealSplayTree *rst;
+
+ g_return_val_if_fail (key_compare_func != NULL, NULL);
+
+ rst = g_new (GRealSplayTree, 1);
+
+ rst -> root = NULL;
+ rst -> key_compare = key_compare_func;
+
+ return (GSplayTree *) rst;
+}
+
+void
+g_splay_tree_destroy (GSplayTree *stree)
+{
+ GRealSplayTree *rst;
+
+ g_return_if_fail (stree != NULL);
+
+ rst = (GRealSplayTree *)stree;
+
+ g_splay_tree_node_destroy (rst -> root);
+ g_free (rst);
+}
+
+void
+g_splay_tree_insert (GSplayTree *stree, gpointer key, gpointer value)
+{
+ GRealSplayTree *rst;
+
+ g_return_if_fail (stree != NULL);
+
+ rst = (GRealSplayTree *)stree;
+
+ rst->root = g_splay_tree_node_insert (rst->root, rst->key_compare, key, value);
+}
+
+void
+g_splay_tree_remove (GSplayTree *stree, gpointer key)
+{
+ GRealSplayTree *rst;
+
+ g_return_if_fail (stree != NULL);
+
+ rst = (GRealSplayTree *)stree;
+
+ rst->root = g_splay_tree_node_remove (rst->root, rst->key_compare, key);
+}
+
+void
+g_splay_tree_delete_min (GSplayTree *stree)
+{
+ GRealSplayTree *rst;
+
+ g_return_if_fail (stree != NULL);
+
+ rst = (GRealSplayTree *)stree;
+
+ rst->root = g_splay_tree_node_delete_min (rst->root);
+}
+
+gpointer
+g_splay_tree_lookup (GSplayTree *stree, gpointer key)
+{
+ GRealSplayTree *rst;
+
+ g_return_val_if_fail (stree != NULL, NULL);
+
+ rst = (GRealSplayTree *)stree;
+
+ if (rst->root)
+ {
+ rst -> root = g_splay_tree_node_splay (rst->root, rst->key_compare, key);
+ if ( (* rst->key_compare)(rst->root->key, key) == 0)
+ return rst->root->value;
+ else
+ return NULL;
+ }
+ else
+ return NULL;
+}
+
+static gint
+g_splay_tree_node_pre_order (GSplayTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data)
+{
+ if ((*traverse_func)(node->key, node->value, data))
+ return TRUE;
+ if (node->left)
+ {
+ if (g_splay_tree_node_pre_order (node->left, traverse_func, data))
+ return TRUE;
+ }
+ if (node->right)
+ {
+ if (g_splay_tree_node_pre_order (node->right, traverse_func, data))
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static gint
+g_splay_tree_node_in_order (GSplayTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data)
+{
+ if (node->left)
+ {
+ if (g_splay_tree_node_in_order (node->left, traverse_func, data))
+ return TRUE;
+ }
+ if ((*traverse_func) (node->key, node->value, data))
+ return TRUE;
+ if (node->right)
+ {
+ if (g_splay_tree_node_in_order (node->right, traverse_func, data))
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static gint
+g_splay_tree_node_post_order (GSplayTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data)
+{
+ if (node->left)
+ {
+ if (g_splay_tree_node_post_order (node->left, traverse_func, data))
+ return TRUE;
+ }
+ if (node->right)
+ {
+ if (g_splay_tree_node_post_order (node->right, traverse_func, data))
+ return TRUE;
+ }
+ if ((*traverse_func) (node->key, node->value, data))
+ return TRUE;
+ return FALSE;
+}
+
+void
+g_splay_tree_traverse (GSplayTree *stree,
+ GTraverseFunc traverse_func,
+ GTraverseType traverse_type,
+ gpointer data)
+{
+ GRealSplayTree *rst;
+
+ g_return_if_fail (stree != NULL);
+
+ rst = (GRealSplayTree *)stree;
+
+ if (!rst->root)
+ return;
+
+ switch (traverse_type)
+ {
+ case G_PRE_ORDER:
+ g_splay_tree_node_pre_order (rst->root, traverse_func, data);
+ break;
+
+ case G_IN_ORDER:
+ g_splay_tree_node_in_order (rst->root, traverse_func, data);
+ break;
+
+ case G_POST_ORDER:
+ g_splay_tree_node_post_order (rst->root, traverse_func, data);
+ break;
+
+ case G_LEVEL_ORDER:
+ g_warning ("g_splay_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
+ break;
+ }
+}
+
+static gint
+g_splay_tree_node_count (GSplayTreeNode *node)
+{
+ gint count;
+
+ count = 1;
+
+ if (node->left)
+ count += g_splay_tree_node_count (node->left);
+ if (node->right)
+ count += g_splay_tree_node_count (node->right);
+
+ return count;
+}
+
+gint
+g_splay_tree_nnodes (GSplayTree *stree)
+{
+ GRealSplayTree *rst;
+
+ g_return_val_if_fail (stree != NULL, 0);
+
+ rst = (GRealSplayTree *)stree;
+
+ if (rst->root)
+ return g_splay_tree_node_count (rst->root);
+ else
+ return 0;
+}
+
+gint
+g_splay_tree_height (GSplayTree *stree)
+{
+ GRealSplayTree *rst;
+
+ g_return_val_if_fail (stree != NULL, 0);
+
+ rst = (GRealSplayTree *)stree;
+
+ if (rst->root)
+ return g_splay_tree_node_height (rst->root);
+ else
+ return 0;
+}
+
+gint
+g_splay_tree_node_height (GSplayTreeNode *node)
+{
+ gint left_height;
+ gint right_height;
+
+ if (node)
+ {
+ left_height = g_splay_tree_node_height (node->left);
+ right_height = g_splay_tree_node_height (node->right);
+ return MAX (left_height, right_height) + 1;
+ }
+ else
+ return 0;
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
