|
From: Nicholas N. <nj...@ca...> - 2004-06-29 10:02:20
|
Hi,
vg_skiplist.c line 288:
Int size = sizeof(SkipNode) * sizeof(SkipNode *) * SK_MAXHEIGHT;
Surely that should be:
Int size = sizeof(SkipNode) + sizeof(SkipNode *) * SK_MAXHEIGHT;
?
---
While I'm looking at vg_skiplist.c... a SkipNode looks like:
struct _SkipNode {
UInt magic;
UShort level;
SkipNode *next[0];
};
There's no space for the key and value. AFAICT, they're stored before the
start of the _SkipNode struct, and the 'size' and 'keyoffset' elements of
struct _SkipList lets the code find them. The allocation points are
careful to provide this extra space, and there are functions that find the
key and value from a node. Except the head node doesn't seem to have a
key/value pair. Jeremy, is that all true? Wow, pretty nasty. It would
be nice to have a comment explaining this.
N
|
|
From: Jeremy F. <je...@go...> - 2004-06-30 01:08:37
|
On Tue, 2004-06-29 at 11:02 +0100, Nicholas Nethercote wrote: > Hi, > > vg_skiplist.c line 288: > > Int size = sizeof(SkipNode) * sizeof(SkipNode *) * SK_MAXHEIGHT; > > Surely that should be: > > Int size = sizeof(SkipNode) + sizeof(SkipNode *) * SK_MAXHEIGHT; Hm, yes, that will be allocating memory rather more enthusiastically than intended (640 bytes for the head rather than 164). Still, its only the head node. > There's no space for the key and value. AFAICT, they're stored before the > start of the _SkipNode struct, and the 'size' and 'keyoffset' elements of > struct _SkipList lets the code find them. The allocation points are > careful to provide this extra space, and there are functions that find the > key and value from a node. Except the head node doesn't seem to have a > key/value pair. Jeremy, is that all true? Yep, pretty much. That's why it has a different magic number (SKIPLIST_HEAD_MAGIC vs SKIPLIST_MAGIC). If you try to get the data of the head, you'll get an assertion failure. > Wow, pretty nasty. It would > be nice to have a comment explaining this. Yep. J |
|
From: Nicholas N. <nj...@ca...> - 2004-06-30 09:37:28
|
On Tue, 29 Jun 2004, Jeremy Fitzhardinge wrote:
>> Except the head node doesn't seem to have a key/value pair. Jeremy, is
>> that all true?
>
> Yep, pretty much. That's why it has a different magic number
> (SKIPLIST_HEAD_MAGIC vs SKIPLIST_MAGIC). If you try to get the data of
> the head, you'll get an assertion failure.
The struct is:
struct _SkipNode {
UInt magic;
UShort level; // max level (level==0 means 1 'next' pointer)
SkipNode *next[0];
};
Any objections if I change 'magic' to a UShort to make the struct 1 word
smaller?
N
|