|
From: Jeremy F. <je...@go...> - 2004-07-27 21:04:37
|
On Tue, 2004-07-27 at 21:16 +0100, Nicholas Nethercote wrote:
> Hi,
>
> I just found a bug in the skiplist implementation; you're going to love
> this.
>
> A skiplist node looks like this:
>
> struct _SkipNode {
> UInt magic;
> UShort level; /* level is the max level (level == 0 means 1 next pointer) */
> SkipNode *next[0];
> };
>
> Part of VG_(SkipNode_Alloc)() looks like this:
>
> n->level = h;
> n->magic = SKIPLIST_MAGIC;
> while (h-- >= 0)
> n->next[h] = NULL;
>
> Seems reasonable, right? Er, actually, that loop iterates from h-1 to -1.
> Bad use of post-decrementing. Whoops.
>
> So why are things still working? Because next[-1] is actually 'level'. So
> the 'level' field of every SkipNode is zero. Hmm, there goes our nice
> logarithmic lookups; the skiplist has effectively degenerated into a
> linked list... or something like that; I didn't investigate to work out
> exactly what is happening.
Oh, nasty. I'm pretty sure I'd checked that some actual skipping was
going on, but maybe not.
Anyway, I'll take a look.
J
|