CODEWITHSUNDEEP
calgorithmlinked-list
barfatchen
barfatchen

Reputation: 1698

Skip list source code from book , A structure confused me

I have googled skip list and found a book "Ontroduction to Algorithms" http://epaperpress.com/sortsearch/index.html and get the skip list tutorial sample from the following http://epaperpress.com/sortsearch/skl.html

There is a skl.c which is running well , but as I study the code I have found something confused me , showes as the follwoing :

typedef int keyType;            /* type of key */

/* user data stored in tree */
typedef struct {
    int stuff;                  /* optional related data */
} recType;


/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;

/* implementation independent declarations */
typedef struct {
    nodeType *hdr;              /* list Header */
    int listLevel;              /* current level of list */
} SkipList;

SkipList list;                  /* skip list information */

and the function confused me is the following :

void initList() {
    int i;

   /**************************
    *  initialize skip list  *
    **************************/

    if ((list.hdr = malloc(
        sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *))) == 0) {
        printf ("insufficient memory (initList)\n");
        exit(1);
    }
    for (i = 0; i <= MAXLEVEL; i++)
        list.hdr->forward[i] = NIL;
    list.listLevel = 0;
}

Seems MAXLEVEL = 15 in this test , so in initList() , it would do list.hdr->forward[0] = NIL; to list.hdr->forward[15] = NIL; and look at nodeType structure , it has the forward var struct nodeTag *forward[1]; , not struct nodeTag *forward[MAXLEVEL];

I think the correct structure should be :

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[MAXLEVEL]; /* skip list forward pointer */
} nodeType;

not 

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;

Or I missed something ?

Upvotes: 0

Views: 1700

Answers (1)

Charlie Burns
Charlie Burns

Reputation: 7044

I think the original is correct.

Look carefully at this malloc:

list.hdr = malloc(sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *)));

Note the MAXLEVEL*sizeof(nodeType *) in the expression. What this is doing is allocating a nodeType AND MAXLEVEL * nodeType* in a single malloc. So it is allocating the node and an array of nodeType*. This works because the array is the last field in the structure. So the node and the array are one contiguous piece of memory.

Argubly more correct would have been the typedef 

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[0]; /* skip list forward pointer */
} nodeType;

Note the zero array size.

This is a common C idiom when used with the malloc expression above. It allows you to decide the array size at runtime rather than compile time. But remember that the array must be the last field in struct.

Rici makes two very good points in his comment below.

Upvotes: 1

Related Questions