Re: Splay trees
- From: Josh MacDonald <jmacd CS Berkeley EDU>
- To: gtk-devel-list redhat com
- Cc: sandmann daimi au dk
- Subject: Re: Splay trees
- Date: Sat, 20 Mar 1999 18:30:17 -0800
Would it be possible to merge the implementation of Splay trees with
the other balanced tree implementation in glib, since they share so
much? I think this should not be accepted until then.
-josh
Quoting Timur I. Bakeyev (gtk@listserv.bat.ru):
> 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;
> +}
>
>
> --
> To unsubscribe: mail gtk-devel-list-request@redhat.com with
> "unsubscribe" as the Subject.
--
-josh
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
