From 5cb175294a8c9db1e3777af3568e714bd7883d5b Mon Sep 17 00:00:00 2001
From: Jeremy Fitzhardinge <jeremy@valgrind.org>
Date: Tue, 27 Jul 2004 21:49:23 +0000
Subject: [PATCH] Fix the skiplist brokenness Nick found:  - use a simple
 memset to initialize the next pointer vector  - fix some previously
 unexercised code as a result of the above Still haven't verified we're
 actually getting skipping, but it doesn't crash with a make regtest.

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@2532
---
 coregrind/vg_skiplist.c | 28 ++++++++++++++++++----------
 1 file changed, 18 insertions(+), 10 deletions(-)

diff --git a/coregrind/vg_skiplist.c b/coregrind/vg_skiplist.c
index 350f53c175..fac7b7c0af 100644
--- a/coregrind/vg_skiplist.c
+++ b/coregrind/vg_skiplist.c
@@ -210,11 +210,14 @@ static inline void validate_skiplist(const SkipList *l, const Char *where)
 
 void *VG_(SkipNode_Alloc)(const SkipList *l)
 {
-   UInt size = l->size;
-   Int h = get_height();
+   UInt size;
+   Int h;
    SkipNode *n;
    Char *ret;
 
+   h = get_height();
+
+   size = l->size;
    size += sizeof(SkipNode) + (h+1)*sizeof(SkipNode *);
 
    if (l->arena == -1)
@@ -229,8 +232,7 @@ void *VG_(SkipNode_Alloc)(const SkipList *l)
    n->level = h;
    n->magic = SKIPLIST_MAGIC;
 
-   while(h-- >= 0)
-      n->next[h] = NULL;
+   VG_(memset)(n->next, 0, sizeof(n->next[0]) * (h+1));
 
    return ret;
 }
@@ -349,7 +351,7 @@ void *VG_(SkipList_Find)(const SkipList *l, void *k)
 void VG_(SkipList_Insert)(SkipList *l, void *data)
 {
    SkipNode *update[SK_MAXHEIGHT];
-   SkipNode *n;
+   SkipNode *n, *nn;
    void *k = key_of_data(l, data);
    Int i;
 
@@ -372,19 +374,25 @@ void VG_(SkipList_Insert)(SkipList *l, void *data)
       l->head->level = 0;
    }
 
-   n = SkipList__Find(l, k, update);
-   
-   vg_assert(n == NULL || (l->cmp)(key_of_node(l, n), k) != 0);
-
    n = node_of_data(l, data);
 
+   /* update size of head's next vector to fit this new node */
    vg_assert(l->head != NULL);
    if (l->head->level < n->level) {
       for(i = l->head->level+1; i <= n->level; i++)
-	 l->head->next[i] = n;
+	 l->head->next[i] = NULL;
       l->head->level = n->level;
    }
 
+   /* Look for the node, but we're mostly interested in setting
+      "update", which is the set of previous nodes with next pointers
+      we need to fix up. */
+   nn = SkipList__Find(l, k, update);
+   
+   /* check the new entry is unique */
+   vg_assert(nn == NULL || (l->cmp)(key_of_node(l, nn), k) != 0);
+
+   /* update the previous node's next pointers */
    for(i = 0; i <= n->level; i++) {
       n->next[i] = update[i]->next[i];
       update[i]->next[i] = n;
-- 
2.47.2