Treap instead of splaytree for GSequence
- From: Soeren Sandmann <sandmann daimi au dk>
- To: gtk-devel-list gnome org
- Subject: Treap instead of splaytree for GSequence
- Date: 13 Feb 2007 03:46:11 +0100
GSequence is currently implemented with a splaytree which, even though
it is a neat data structure, has some downsides:
* They are only O(log n) in the amortized sense
This means individual operations can take a long time. This is a
problem for interactive applications where predictable performance is
often more important than good average performance.
* They can be arbitrarily unbalanced at given point in time
This means straightforward recursive algorithms will use O(n)
stackspace in the worst case.
* They involve tree restructuring during lookup
There are two problems with this. One is that the memory pages
containing the nodes in question will get written to, causing more
work for the virtual memory system. The other is that if that
aggregate information will have to be recomputed on lookup.
So I have reimplemented GSequence in terms of a different kind of
tree, a 'treap'. A treap is combination of a heap and a tree, where
all the nodes are in tree order according to the keys and in heap
order according to a randomly assigned priority.
Wikipedia summary:
http://en.wikipedia.org/wiki/Treap
Detailed paper:
http://www-tcs.cs.uni-sb.de/Papers/rst.ps
One of the advantages of splaytrees compared to say red/black trees
was the simple implementation, in particular of join and split, but it
turns out that treaps are even simpler:
[ssp localhost glib]$ svn diff | diffstat
gsequence.c | 654
++++++++++++++++++++++++++++--------------------------------
1 file changed, 311 insertions(+), 343 deletions(-)
The performance as reported by testtreemodel is slightly worse with
treaps than with with splaytrees. The reason for this is that
- gtk_list_store_compare_func() is really slow, so what is getting
measured here is more than anything how many times that function
gets called.
- the testtreemodel inserts the rows in sorted order. This is a
best-case for the splaytree since it automatically keeps recently
accessed items near the root of the tree.
The time difference in this case with 16384 items is 0.06 ms/item for
the splaytree vs. 0.08 ms/item for the treap.
If you change testtreemodel to insert the rows in random order (a
worst-case for splaytrees), the splaytree implementation takes 0.20
ms/item where the treap implementation stays at 0.08. So, for cases
where the comparison function performs reasonably or the items are not
inserted in sorted order, the treap is much faster and its performance
is predictable.
Patch attached. In addition to the treap implementation there are also
some additions to the test suite.
Soren
Index: tests/sequence-test.c
===================================================================
--- tests/sequence-test.c (revision 5334)
+++ tests/sequence-test.c (working copy)
@@ -2,26 +2,25 @@
#include <glib.h>
#include <stdlib.h>
-enum
- {
- NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,
-
- /* Getting iters */
- GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
- INSERT_BEFORE, MOVE, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
- SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
-
- /* dereferencing */
- GET, SET,
-
- /* operations on GSequenceIter * */
- ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
- ITER_MOVE, ITER_GET_SEQUENCE,
-
- /* search */
- ITER_COMPARE, RANGE_GET_MIDPOINT,
- N_OPS
- } Op;
+enum {
+ NEW, FREE, GET_LENGTH, FOREACH, FOREACH_RANGE, SORT, SORT_ITER,
+
+ /* Getting iters */
+ GET_BEGIN_ITER, GET_END_ITER, GET_ITER_AT_POS, APPEND, PREPEND,
+ INSERT_BEFORE, MOVE, SWAP, INSERT_SORTED, INSERT_SORTED_ITER, SORT_CHANGED,
+ SORT_CHANGED_ITER, REMOVE, REMOVE_RANGE, MOVE_RANGE, SEARCH, SEARCH_ITER,
+
+ /* dereferencing */
+ GET, SET,
+
+ /* operations on GSequenceIter * */
+ ITER_IS_BEGIN, ITER_IS_END, ITER_NEXT, ITER_PREV, ITER_GET_POSITION,
+ ITER_MOVE, ITER_GET_SEQUENCE,
+
+ /* search */
+ ITER_COMPARE, RANGE_GET_MIDPOINT,
+ N_OPS
+};
typedef struct SequenceInfo
{
@@ -70,7 +69,10 @@
i = 0;
while (iter != g_sequence_get_end_iter (info->sequence))
{
+ Item *item;
g_assert (list->data == iter);
+ item = get_item (list->data);
+ g_assert (item->seq == info);
iter = g_sequence_iter_next (iter);
list = list->next;
@@ -312,7 +314,8 @@
{
#define N_ITERATIONS 60000
#define N_SEQUENCES 8
-
+#define N_TIMES 24
+
SequenceInfo sequences[N_SEQUENCES];
int k;
@@ -501,8 +504,10 @@
case MOVE:
{
GList *link1, *link2;
- GSequenceIter *iter1 = get_random_iter (seq, &link1);
- GSequenceIter *iter2 = get_random_iter (seq, &link2);
+ SequenceInfo *seq1 = RANDOM_SEQUENCE();
+ SequenceInfo *seq2 = RANDOM_SEQUENCE();
+ GSequenceIter *iter1 = get_random_iter (seq1, &link1);
+ GSequenceIter *iter2 = get_random_iter (seq2, &link2);
if (!g_sequence_iter_is_end (iter1))
{
@@ -511,9 +516,14 @@
if (!link2)
g_assert (g_sequence_iter_is_end (iter2));
- queue_insert_before (seq, link2, link1->data);
+ queue_insert_before (seq2, link2, link1->data);
- g_queue_delete_link (seq->queue, link1);
+ g_queue_delete_link (seq1->queue, link1);
+
+ get_item (iter1)->seq = seq2;
+
+ seq1->n_items--;
+ seq2->n_items++;
}
check_integrity (seq);
@@ -525,6 +535,30 @@
g_sequence_move (iter1, iter1);
}
break;
+ case SWAP:
+ {
+ GList *link1, *link2;
+ SequenceInfo *seq1 = RANDOM_SEQUENCE();
+ SequenceInfo *seq2 = RANDOM_SEQUENCE();
+ GSequenceIter *iter1 = get_random_iter (seq1, &link1);
+ GSequenceIter *iter2 = get_random_iter (seq2, &link2);
+
+ if (!g_sequence_iter_is_end (iter1) &&
+ !g_sequence_iter_is_end (iter2))
+ {
+ gpointer tmp;
+
+ g_sequence_swap (iter1, iter2);
+
+ get_item (iter1)->seq = seq2;
+ get_item (iter2)->seq = seq1;
+
+ tmp = link1->data;
+ link1->data = link2->data;
+ link2->data = tmp;
+ }
+ }
+ break;
case INSERT_SORTED:
{
int i;
@@ -535,7 +569,7 @@
check_sorted (seq);
- for (i = 0; i < 15; ++i)
+ for (i = 0; i < N_TIMES; ++i)
{
GSequenceIter *iter =
g_sequence_insert_sorted (seq->sequence, new_item(seq), compare_items, NULL);
@@ -558,7 +592,7 @@
check_sorted (seq);
- for (i = 0; i < 15; ++i)
+ for (i = 0; i < N_TIMES; ++i)
{
GSequenceIter *iter;
@@ -584,7 +618,7 @@
check_sorted (seq);
- for (i = 0; i < 15; ++i)
+ for (i = 0; i < N_TIMES; ++i)
{
GList *link;
GSequenceIter *iter = get_random_iter (seq, &link);
@@ -611,7 +645,7 @@
check_sorted (seq);
- for (i = 0; i < 15; ++i)
+ for (i = 0; i < N_TIMES; ++i)
{
GList *link;
GSequenceIter *iter = get_random_iter (seq, &link);
@@ -634,7 +668,7 @@
{
int i;
- for (i = 0; i < 15; ++i)
+ for (i = 0; i < N_TIMES; ++i)
{
GList *link;
GSequenceIter *iter = get_random_iter (seq, &link);
@@ -796,7 +830,7 @@
g_assert (g_sequence_get (iter) == item);
/* Make sure that existing items are freed */
- for (i = 0; i < 15; ++i)
+ for (i = 0; i < N_TIMES; ++i)
g_sequence_set (iter, new_item (seq));
check_integrity (seq);
@@ -1113,6 +1147,8 @@
g_sequence_insert_sorted_iter (seq, GINT_TO_POINTER (g_random_int()),
compare_iter, NULL);
}
+
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
g_sequence_free (seq);
}
@@ -1130,15 +1166,23 @@
GSequenceIter *iter;
for (i = 0; i < N_ITEMS; ++i)
- iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
-
+ {
+ iters[i] = g_sequence_append (seq, GINT_TO_POINTER (3000));
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ }
+
i = 0;
iter = g_sequence_get_begin_iter (seq);
+ g_assert (g_sequence_iter_get_sequence (iter) == seq);
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
while (!g_sequence_iter_is_end (iter))
{
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
g_assert (iters[i++] == iter);
iter = g_sequence_iter_next (iter);
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
}
g_sequence_sort (seq, compare, NULL);
@@ -1147,13 +1191,22 @@
iter = g_sequence_get_begin_iter (seq);
while (!g_sequence_iter_is_end (iter))
{
- g_assert (iters[i++] == iter);
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ g_assert (iters[i] == iter);
iter = g_sequence_iter_next (iter);
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
+
+ i++;
}
for (i = N_ITEMS - 1; i >= 0; --i)
- g_sequence_sort_changed (iters[i], compare, NULL);
+ {
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
+ g_assert (g_sequence_iter_get_sequence (iters[i]) == seq);
+ g_assert (g_sequence_get_end_iter (seq) != iters[i]);
+ g_sequence_sort_changed (iters[i], compare, NULL);
+ }
i = 0;
iter = g_sequence_get_begin_iter (seq);
@@ -1162,6 +1215,7 @@
g_assert (iters[i++] == iter);
iter = g_sequence_iter_next (iter);
+ g_sequence_self_test_internal_to_glib_dont_use (seq);
}
}
Index: glib/gsequence.c
===================================================================
--- glib/gsequence.c (revision 5334)
+++ glib/gsequence.c (working copy)
@@ -72,17 +72,18 @@
static void node_free (GSequenceNode *node,
GSequence *seq);
static void node_cut (GSequenceNode *split);
-static void node_insert_after (GSequenceNode *node,
- GSequenceNode *second);
static void node_insert_before (GSequenceNode *node,
GSequenceNode *new);
static void node_unlink (GSequenceNode *node);
+static void node_join (GSequenceNode *left,
+ GSequenceNode *right);
static void node_insert_sorted (GSequenceNode *node,
GSequenceNode *new,
GSequenceNode *end,
GSequenceIterCompareFunc cmp_func,
gpointer cmp_data);
+
/*
* Various helper functions
*/
@@ -551,12 +552,23 @@
node_cut (end);
if (first != begin)
- node_insert_after (node_get_last (first), end);
+ node_join (first, end);
if (dest)
- node_insert_before (dest, begin);
+ {
+ first = node_get_first (dest);
+
+ node_cut (dest);
+
+ node_join (begin, dest);
+
+ if (dest != first)
+ node_join (first, begin);
+ }
else
- node_free (begin, src_seq);
+ {
+ node_free (begin, src_seq);
+ }
}
/**
@@ -899,18 +911,6 @@
seq->access_prohibited = TRUE;
- /* Create a new temporary sequence and put the dummy node into
- * that. The reason for this is that the user compare function
- * will be called with the new node, and if it dereferences,
- * "is_end" will be called on it. But that will crash if the
- * node is not actually in a sequence.
- *
- * node_insert_sorted() makes sure the node is unlinked before
- * is is inserted.
- *
- * The reason we need the "iter" versions at all is that that
- * is the only kind of compare functions GtkTreeView can use.
- */
tmp_seq = g_sequence_new (NULL);
tmp_seq->real_sequence = seq;
@@ -1055,6 +1055,7 @@
g_sequence_get_begin_iter (GSequence *seq)
{
g_return_val_if_fail (seq != NULL, NULL);
+
return node_get_first (seq->end_node);
}
@@ -1104,7 +1105,8 @@
*
* Moves the item pointed to by @src to the position indicated by @dest.
* After calling this function @dest will point to the position immediately
- * after @src.
+ * after @src. It is allowed for @src and @dest to point into different
+ * sequences.
*
* Since: 2.14
**/
@@ -1253,7 +1255,8 @@
* @a: a #GSequenceIter
* @b: a #GSequenceIter
*
- * Swaps the items pointed to by @a and @b
+ * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
+ * to point into difference sequences.
*
* Since: 2.14
**/
@@ -1296,158 +1299,37 @@
}
/*
- * Implementation of the splay tree.
- */
-
-/* Splay Tree vs. Other Kinds of Trees
+ * Implementation of a treap
*
- * There are both advantages and disadvantages to using a splay tree vs. some other
- * kind of tree such as a red/black tree or a btree.
*
- * Advantages of splay trees
- *
- * - They are very simple to implement, especially things like move_range or concatenate
- * are easy to do for splay trees. The algorithm to split a red/black tree, while still O(log n),
- * is much more complicated
- *
- * - If we add aggregates at some point, splay trees make it easy to compute the aggregate
- * for an arbitrary range of the tree. In a red/black tree you would have to pick out
- * the correct subtrees, then call out to the aggregator function to compute them.
- * On the other hand, for a splay tree, aggregates would be invalidated on lookups, so you
- * would call the aggregator much more often. The aggregates could be invalidated lazily though.
- * In both cases, the aggregator function would be called O(log n) times as a side-effect of
- * asking for the aggregate of a range.
- *
- * - If you are only using the list API and never the insert_sorted(), the operations on a
- * splay tree will actually be O(1) rather than O(log n). But this is most likely just
- * not that interesting in practice since the O(log n) of a BTree is actually very fast.
- *
- * The disadvantages
- *
- * - Splay trees are only amortized O(log n) which means individual operations could take a long
- * time, which is undesirable in GUI applications
- *
- * - Red/black trees are more widely known since they are tought in CS101 courses.
- *
- * - Red/black trees or btrees are more efficient. Not only is the red/black algorithm faster
- * in itself, the splaying writes to nodes on lookup which causes dirty pages that the VM
- * system will have to launder.
- *
- * - Splay trees are not necessarily balanced at all which means straight-forward recursive
- * algorithms can use lots of stack.
- *
- * It is likely worth investigating whether a BTree would be a better choice, in particular the
- * algorithm to split a BTree may not be all that complicated given that split/join for nodes
- * will have to be implemented anyway.
- *
*/
-
-static void
-node_update_fields (GSequenceNode *node)
+static guint
+get_priority (GSequenceNode *node)
{
- int n_nodes = 1;
-
- g_assert (node != NULL);
+ guint key = GPOINTER_TO_UINT (node);
- if (node->left)
- n_nodes += node->left->n_nodes;
+ /* This hash function is based on one found on Thomas Wang's
+ * web page at
+ *
+ * http://www.concentric.net/~Ttwang/tech/inthash.htm
+ *
+ */
+ key = (key << 15) - key - 1;
+ key = key ^ (key >> 12);
+ key = key + (key << 2);
+ key = key ^ (key >> 4);
+ key = key + (key << 3) + (key << 11);
+ key = key ^ (key >> 16);
- if (node->right)
- n_nodes += node->right->n_nodes;
-
- node->n_nodes = n_nodes;
+ /* We rely on 0 being less than all other priorities */
+ return key? key : 1;
}
-#define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
-#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
-
-static void
-node_rotate (GSequenceNode *node)
-{
- GSequenceNode *tmp, *old;
-
- g_assert (node->parent);
- g_assert (node->parent != node);
-
- if (NODE_LEFT_CHILD (node))
- {
- /* rotate right */
- tmp = node->right;
-
- node->right = node->parent;
- node->parent = node->parent->parent;
- if (node->parent)
- {
- if (node->parent->left == node->right)
- node->parent->left = node;
- else
- node->parent->right = node;
- }
-
- g_assert (node->right);
-
- node->right->parent = node;
- node->right->left = tmp;
-
- if (node->right->left)
- node->right->left->parent = node->right;
-
- old = node->right;
- }
- else
- {
- /* rotate left */
- tmp = node->left;
-
- node->left = node->parent;
- node->parent = node->parent->parent;
- if (node->parent)
- {
- if (node->parent->right == node->left)
- node->parent->right = node;
- else
- node->parent->left = node;
- }
-
- g_assert (node->left);
-
- node->left->parent = node;
- node->left->right = tmp;
-
- if (node->left->right)
- node->left->right->parent = node->left;
-
- old = node->left;
- }
-
- node_update_fields (old);
- node_update_fields (node);
-}
-
static GSequenceNode *
-splay (GSequenceNode *node)
+find_root (GSequenceNode *node)
{
while (node->parent)
- {
- if (!node->parent->parent)
- {
- /* zig */
- node_rotate (node);
- }
- else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
- (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
- {
- /* zig-zig */
- node_rotate (node->parent);
- node_rotate (node);
- }
- else
- {
- /* zig-zag */
- node_rotate (node);
- node_rotate (node);
- }
- }
+ node = node->parent;
return node;
}
@@ -1457,21 +1339,19 @@
{
GSequenceNode *node = g_slice_new0 (GSequenceNode);
- node->parent = NULL;
- node->parent = NULL;
+ node->n_nodes = 1;
+ node->data = data;
node->left = NULL;
node->right = NULL;
+ node->parent = NULL;
- node->data = data;
- node->n_nodes = 1;
-
return node;
}
static GSequenceNode *
-find_min (GSequenceNode *node)
+node_get_first (GSequenceNode *node)
{
- splay (node);
+ node = find_root (node);
while (node->left)
node = node->left;
@@ -1480,9 +1360,9 @@
}
static GSequenceNode *
-find_max (GSequenceNode *node)
+node_get_last (GSequenceNode *node)
{
- splay (node);
+ node = find_root (node);
while (node->right)
node = node->right;
@@ -1490,96 +1370,104 @@
return node;
}
-static GSequenceNode *
-node_get_first (GSequenceNode *node)
-{
- return splay (find_min (node));
-}
+#define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
+#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
static GSequenceNode *
-node_get_last (GSequenceNode *node)
+node_get_next (GSequenceNode *node)
{
- return splay (find_max (node));
-}
+ GSequenceNode *n = node;
-static gint
-get_n_nodes (GSequenceNode *node)
-{
- if (node)
- return node->n_nodes;
+ if (n->right)
+ {
+ n = n->right;
+ while (n->left)
+ n = n->left;
+ }
else
- return 0;
+ {
+ while (NODE_RIGHT_CHILD (n))
+ n = n->parent;
+
+ if (n->parent)
+ n = n->parent;
+ else
+ n = node;
+ }
+
+ return n;
}
static GSequenceNode *
-node_get_by_pos (GSequenceNode *node,
- gint pos)
+node_get_prev (GSequenceNode *node)
{
- gint i;
+ GSequenceNode *n = node;
- g_assert (node != NULL);
-
- splay (node);
-
- while ((i = get_n_nodes (node->left)) != pos)
+ if (n->left)
{
- if (i < pos)
- {
- node = node->right;
- pos -= (i + 1);
- }
+ n = n->left;
+ while (n->right)
+ n = n->right;
+ }
+ else
+ {
+ while (NODE_LEFT_CHILD (n))
+ n = n->parent;
+
+ if (n->parent)
+ n = n->parent;
else
- {
- node = node->left;
- g_assert (node->parent != NULL);
- }
+ n = node;
}
- return splay (node);
+ return n;
}
-static GSequenceNode *
-node_get_prev (GSequenceNode *node)
+#define N_NODES(n) ((n)? (n)->n_nodes : 0)
+
+static gint
+node_get_pos (GSequenceNode *node)
{
- splay (node);
+ int n_smaller = 0;
if (node->left)
+ n_smaller = node->left->n_nodes;
+
+ while (node)
{
- node = node->left;
- while (node->right)
- node = node->right;
+ if (NODE_RIGHT_CHILD (node))
+ n_smaller += N_NODES (node->parent->left) + 1;
+
+ node = node->parent;
}
- return splay (node);
+ return n_smaller;
}
static GSequenceNode *
-node_get_next (GSequenceNode *node)
+node_get_by_pos (GSequenceNode *node,
+ gint pos)
{
- splay (node);
+ int i;
- if (node->right)
+ node = find_root (node);
+
+ while ((i = N_NODES (node->left)) != pos)
{
- node = node->right;
- while (node->left)
- node = node->left;
- }
+ if (i < pos)
+ {
+ node = node->right;
+ pos -= (i + 1);
+ }
+ else
+ {
+ node = node->left;
+ }
+ }
- return splay (node);
+ return node;
}
-static gint
-node_get_pos (GSequenceNode *node)
-{
- splay (node);
-
- return get_n_nodes (node->left);
-}
-
-/* Return closest node _strictly_ bigger than @needle. This node
- * always exists because the tree has an explicit end node).
- * This end node of @haystack must be passed in @end.
- */
static GSequenceNode *
node_find_closest (GSequenceNode *haystack,
GSequenceNode *needle,
@@ -1590,10 +1478,8 @@
GSequenceNode *best;
gint c;
- g_assert (haystack);
+ haystack = find_root (haystack);
- haystack = splay (haystack);
-
do
{
best = haystack;
@@ -1626,143 +1512,214 @@
return best;
}
-static void
-node_free (GSequenceNode *node,
- GSequence *seq)
+static gint
+node_get_length (GSequenceNode *node)
{
- GPtrArray *stack = g_ptr_array_new ();
+ node = find_root (node);
- splay (node);
+ return node->n_nodes;
+}
- g_ptr_array_add (stack, node);
-
- while (stack->len > 0)
+static void
+real_node_free (GSequenceNode *node,
+ GSequence *seq)
+{
+ if (node)
{
- node = g_ptr_array_remove_index (stack, stack->len - 1);
+ real_node_free (node->left, seq);
+ real_node_free (node->right, seq);
- if (node)
- {
- g_ptr_array_add (stack, node->right);
- g_ptr_array_add (stack, node->left);
-
- if (seq && seq->data_destroy_notify && node != seq->end_node)
- seq->data_destroy_notify (node->data);
-
- g_slice_free (GSequenceNode, node);
- }
+ if (seq && seq->data_destroy_notify && node != seq->end_node)
+ seq->data_destroy_notify (node->data);
+
+ g_slice_free (GSequenceNode, node);
}
+}
+
+static void
+node_free (GSequenceNode *node,
+ GSequence *seq)
+{
+ node = find_root (node);
- g_ptr_array_free (stack, TRUE);
+ real_node_free (node, seq);
}
-/* Splits into two trees. @node will be part of the right tree
- */
static void
-node_cut (GSequenceNode *node)
+node_update_fields (GSequenceNode *node)
{
- splay (node);
+ int n_nodes = 1;
- g_assert (node->parent == NULL);
+ n_nodes += N_NODES (node->left);
+ n_nodes += N_NODES (node->right);
- if (node->left)
- node->left->parent = NULL;
-
- node->left = NULL;
- node_update_fields (node);
+ node->n_nodes = n_nodes;
}
static void
-node_insert_before (GSequenceNode *node,
- GSequenceNode *new)
+node_rotate (GSequenceNode *node)
{
- g_assert (node != NULL);
- g_assert (new != NULL);
+ GSequenceNode *tmp, *old;
- splay (node);
+ g_assert (node->parent);
+ g_assert (node->parent != node);
- new = splay (find_min (new));
- g_assert (new->left == NULL);
+ if (NODE_LEFT_CHILD (node))
+ {
+ /* rotate right */
+ tmp = node->right;
- if (node->left)
- node->left->parent = new;
+ node->right = node->parent;
+ node->parent = node->parent->parent;
+ if (node->parent)
+ {
+ if (node->parent->left == node->right)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
- new->left = node->left;
- new->parent = node;
+ g_assert (node->right);
- node->left = new;
+ node->right->parent = node;
+ node->right->left = tmp;
- node_update_fields (new);
+ if (node->right->left)
+ node->right->left->parent = node->right;
+
+ old = node->right;
+ }
+ else
+ {
+ /* rotate left */
+ tmp = node->left;
+
+ node->left = node->parent;
+ node->parent = node->parent->parent;
+ if (node->parent)
+ {
+ if (node->parent->right == node->left)
+ node->parent->right = node;
+ else
+ node->parent->left = node;
+ }
+
+ g_assert (node->left);
+
+ node->left->parent = node;
+ node->left->right = tmp;
+
+ if (node->left->right)
+ node->left->right->parent = node->left;
+
+ old = node->left;
+ }
+
+ node_update_fields (old);
node_update_fields (node);
}
static void
-node_insert_after (GSequenceNode *node,
- GSequenceNode *new)
+node_update_fields_deep (GSequenceNode *node)
{
- g_assert (node != NULL);
- g_assert (new != NULL);
+ if (node)
+ {
+ node_update_fields (node);
+
+ node_update_fields_deep (node->parent);
+ }
+}
+
+static void
+rotate_down (GSequenceNode *node,
+ guint priority)
+{
+ guint left, right;
- splay (node);
+ left = node->left ? get_priority (node->left) : 0;
+ right = node->right ? get_priority (node->right) : 0;
- new = splay (find_max (new));
- g_assert (new->right == NULL);
- g_assert (node->parent == NULL);
+ while (priority < left || priority < right)
+ {
+ if (left > right)
+ node_rotate (node->left);
+ else
+ node_rotate (node->right);
- if (node->right)
- node->right->parent = new;
+ left = node->left ? get_priority (node->left) : 0;
+ right = node->right ? get_priority (node->right) : 0;
+ }
+}
+
+static void
+node_cut (GSequenceNode *node)
+{
+ while (node->parent)
+ node_rotate (node);
- new->right = node->right;
- new->parent = node;
+ if (node->left)
+ node->left->parent = NULL;
- node->right = new;
-
- node_update_fields (new);
+ node->left = NULL;
node_update_fields (node);
+
+ rotate_down (node, get_priority (node));
}
-static gint
-node_get_length (GSequenceNode *node)
+static void
+node_join (GSequenceNode *left,
+ GSequenceNode *right)
{
- g_assert (node != NULL);
+ GSequenceNode *fake = node_new (NULL);
+
+ fake->left = find_root (left);
+ fake->right = find_root (right);
+ fake->left->parent = fake;
+ fake->right->parent = fake;
+
+ node_update_fields (fake);
- splay (node);
- return node->n_nodes;
+ node_unlink (fake);
+
+ node_free (fake, NULL);
}
static void
-node_unlink (GSequenceNode *node)
+node_insert_before (GSequenceNode *node,
+ GSequenceNode *new)
{
- GSequenceNode *right, *left;
+ new->left = node->left;
+ if (new->left)
+ new->left->parent = new;
- splay (node);
+ new->parent = node;
+ node->left = new;
- left = node->left;
- right = node->right;
+ node_update_fields_deep (new);
- node->parent = node->left = node->right = NULL;
- node_update_fields (node);
+ while (new->parent && get_priority (new) > get_priority (new->parent))
+ node_rotate (new);
- if (right)
- {
- right->parent = NULL;
-
- right = node_get_first (right);
- g_assert (right->left == NULL);
-
- right->left = left;
- if (left)
- {
- left->parent = right;
- node_update_fields (right);
- }
- }
- else if (left)
- {
- left->parent = NULL;
- }
+ rotate_down (new, get_priority (new));
}
static void
+node_unlink (GSequenceNode *node)
+{
+ rotate_down (node, 0);
+
+ if (NODE_RIGHT_CHILD (node))
+ node->parent->right = NULL;
+ else if (NODE_LEFT_CHILD (node))
+ node->parent->left = NULL;
+
+ if (node->parent)
+ node_update_fields_deep (node->parent);
+
+ node->parent = NULL;
+}
+
+static void
node_insert_sorted (GSequenceNode *node,
GSequenceNode *new,
GSequenceNode *end,
@@ -1778,49 +1735,60 @@
node_insert_before (closest, new);
}
-static gint
-node_calc_height (GSequenceNode *node)
+/* Self-test function */
+static int
+count_nodes (GSequenceNode *node)
{
- gint left_height;
- gint right_height;
+ if (!node)
+ return 0;
- if (node)
- {
- left_height = 0;
- right_height = 0;
-
- if (node->left)
- left_height = node_calc_height (node->left);
-
- if (node->right)
- right_height = node_calc_height (node->right);
-
- return MAX (left_height, right_height) + 1;
- }
-
- return 0;
+ return count_nodes (node->left) + count_nodes (node->right) + 1;
}
-
-/* Self-test function */
+
static void
check_node (GSequenceNode *node)
{
if (node)
{
g_assert (node->parent != node);
- g_assert (node->n_nodes ==
- 1 + get_n_nodes (node->left) + get_n_nodes (node->right));
+ if (node->parent)
+ g_assert (node->parent->left == node || node->parent->right == node);
+ g_assert (node->n_nodes == count_nodes (node));
+ if (node->left)
+ g_assert (get_priority (node) >= get_priority (node->left));
+ if (node->right)
+ g_assert (get_priority (node) >= get_priority (node->right));
check_node (node->left);
check_node (node->right);
}
}
+static gint
+compute_height (GSequenceNode *node)
+{
+ int left, right;
+
+ if (!node)
+ return 0;
+
+ left = compute_height (node->left);
+ right = compute_height (node->right);
+
+ return MAX (left, right) + 1;
+}
+
void
g_sequence_self_test_internal_to_glib_dont_use (GSequence *seq)
{
- GSequenceNode *node = splay (seq->end_node);
+ GSequenceNode *node = find_root (seq->end_node);
check_node (node);
+
+ node = node_get_last (node);
+
+ g_assert (seq->end_node == node);
+ g_assert (node->data == seq);
+
}
#define __G_SEQUENCE_C__
Index: ChangeLog
===================================================================
--- ChangeLog (revision 5334)
+++ ChangeLog (working copy)
@@ -1,3 +1,10 @@
+2007-02-11 Soren Sandmann <sandmann daimi au dk>
+
+ * tests/sequence-test.c (run_random_tests): Add test for swap
+ operation.
+
+ * glib/gsequence.c: Replace splay tree with a treap.
+
2007-02-10 Hans Breuer <hans breuer org>
* glib/makefile.msc.in : added gsequence.obj
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
