4.8 Коды для разделенных списков

typedef int T; /* type of item to be sorted */

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)

/*

* levels range from (0 .. MAXLEVEL)

*/

#define MAXLEVEL 15

typedef struct Node_ {

T data; /* user's data */

struct Node_ *forward[1]; /* skip list forward pointer */

} Node;

typedef struct {

Node *hdr; /* list Header */

int listLevel; /* current level of list */

} SkipList;

SkipList list; /* skip list information */

#define NIL list.hdr

Node *insertNode(T data) {

int i, newLevel;

Node *update[MAXLEVEL+1];

Node *x;

/***********************************************

* allocate node for data and insert in list *

***********************************************/

/* find where data belongs */

x = list.hdr;

for (i = list.listLevel; i >= 0; i--) {

while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data))

x = x->forward[i];

update[i] = x;

}

x = x->forward[0];

if (x != NIL && compEQ(x->data, data)) return(x);

/* determine level */

newLevel = 0;

while (rand() < RAND_MAX/2) newLevel++;

if (newLevel > MAXLEVEL) newLevel = MAXLEVEL;

if (newLevel > list.listLevel) {

for (i = list.listLevel + 1; i data = data;

/* update forward links */

for (i = 0; i forward[i] = update[i]->forward[i];

update[i]->forward[i] = x;

}

return(x);

}

void deleteNode(T data) {

int i;

Node *update[MAXLEVEL+1], *x;

/*******************************************

* delete node containing data from list *

*******************************************/

/* find where data belongs */

x = list.hdr;

for (i = list.listLevel; i >= 0; i--) {

while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data))

x = x->forward[i];

update[i] = x;

}

x = x->forward[0];

if (x == NIL || !compEQ(x->data, data)) return;

/* adjust forward pointers */

for (i = 0; i forward[i] != x) break;

update[i]->forward[i] = x->forward[i];

}

free (x);

/* adjust header level */

while ((list.listLevel > 0)

&& (list.hdr->forward[list.listLevel] == NIL))

list.listLevel--;

}

Node *findNode(T data) {

int i;

Node *x = list.hdr;

/*******************************

* find node containing data *

*******************************/

for (i = list.listLevel; i >= 0; i--) {

while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data))

x = x->forward[i];

}

x = x->forward[0];

if (x != NIL && compEQ(x->data, data)) return (x);

return(0);

}

void initList() {

int i;

/**************************

* initialize skip list *

**************************/

if ((list.hdr = malloc(sizeof(Node) + MAXLEVEL*sizeof(Node *))) == 0) {

printf ("insufficient memory (initList)\n");

exit(1);

}

for (i = 0; i forward[i] = NIL;

list.listLevel = 0;

}