//http://epaperpress.com/sortsearch/skl.html
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <unistd.h>
/* implementation dependent declarations */
typedef enum {
STATUS_OK,
STATUS_MEM_EXHAUSTED,
STATUS_DUPLICATE_KEY,
STATUS_KEY_NOT_FOUND
} statusEnum;
typedef int keyType; /* type of key */
/* user data stored in tree */
typedef struct {
int stuff; /* optional related data */
} recType;
typedef struct IntruListNode {
struct IntruListNode *next;
struct IntruListNode *prev;
} IntruListNode ;
typedef struct IntruList {
IntruListNode *first;
IntruListNode *last;
} IntruList;
static IntruList *ilist[3] = {NULL,NULL,NULL} ;
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15
typedef struct nodeTag {
keyType key; /* key used for searching */
recType rec; /* user data */
IntruListNode intrunode[3] ;
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 */
#define NIL list.hdr
void RemoveFromIntruList(int ilevel,IntruListNode* inode)
{
if( (ilist[ilevel]->first != NULL) )
{
if(ilist[ilevel]->first == inode) {
ilist[ilevel]->first = inode->next ;
}else{
if(inode->prev != NULL)
inode->prev->next = inode->next;
}
}
if(ilist[ilevel]->first != NULL)
ilist[ilevel]->first->prev = NULL ;
if (ilist[ilevel]->last != NULL)
{
if(ilist[ilevel]->last == inode ){
ilist[ilevel]->last = inode->prev;
}else{
if (inode->next != NULL)
inode->next->prev = inode->prev ;
}
}
if(ilist[ilevel]->last != NULL)
ilist[ilevel]->last->next = NULL ;
inode->next = NULL ;
inode->prev = NULL ;
}
void AddToIntruList(int ilevel,IntruListNode* inode)
{
// first amd last has prev,next = NULL , still it is in list !!
if( (inode == ilist[ilevel]->first) || (inode == ilist[ilevel]->last) )
return ;
if( (inode->prev != NULL) || (inode->next != NULL) ) //important: node has prev means it is in list already !!
return ;
inode->next=NULL ;
inode->prev = NULL ;
if(ilist[ilevel]->last==NULL)
{
ilist[ilevel]->first = inode;
ilist[ilevel]->last = inode;
}else{
ilist[ilevel]->last->next = inode;
inode->prev = ilist[ilevel]->last;
ilist[ilevel]->last = inode;
}
}
statusEnum setIntruList(keyType key,int *ptr)
{
int i;
nodeType *x = list.hdr;
/*******************************
* find node containing data *
*******************************/
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL && compLT(x->forward[i]->key, key))
x = x->forward[i];
}
x = x->forward[0];
if (x != NIL && compEQ(x->key, key)) {
IntruListNode* inode= NULL ;
for(i=0;i<3;i++)
{
if(ptr[i]==0) //remove from IntruListNode
{
RemoveFromIntruList(i,&(x->intrunode[i])) ;
}else{ //add to IntruListNode
AddToIntruList(i,&(x->intrunode[i])) ;
}
} //for
return STATUS_OK;
}else{
return STATUS_KEY_NOT_FOUND;
}
}
statusEnum insert(keyType key, recType *rec) {
int i, newLevel;
nodeType *update[MAXLEVEL+1];
nodeType *x;
/***********************************************
* allocate node for data and insert in list *
***********************************************/
/* find where key belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL && compLT(x->forward[i]->key, key))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x != NIL && compEQ(x->key, key))
return STATUS_DUPLICATE_KEY;
/* determine level */
for (
newLevel = 0;
rand() < RAND_MAX/2 && newLevel < MAXLEVEL;
newLevel++);
if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel; i++)
update[i] = NIL;
list.listLevel = newLevel;
}
/* make new node */
if ((x = malloc(sizeof(nodeType) + newLevel*sizeof(nodeType *))) == 0)
return STATUS_MEM_EXHAUSTED;
x->key = key;
x->rec = *rec;
/* update forward links */
for (i = 0; i <= newLevel; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
for(i=0;i<3;i++)
{
IntruListNode* inode = &(x->intrunode[i]) ;
inode->next=NULL ;
inode->prev = NULL ;
}
/*
for(i=0;i<3;i++)
{
printf("insert (%d)...ilist->first=(%p),last=(%p)\n",i,ilist[i]->first,ilist[i]->last) ;
}
*/
return STATUS_OK;
}
statusEnum delete(keyType key) {
int i;
nodeType *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]->key, key))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == NIL || !compEQ(x->key, key)) return STATUS_KEY_NOT_FOUND;
/* adjust forward pointers */
for (i = 0; i <= list.listLevel; i++) {
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
IntruListNode* inode= NULL ;
for(i=0;i<3;i++)
{
RemoveFromIntruList(i,&(x->intrunode[i])) ;
} //for
/*
for(i=0;i<3;i++)
{
printf("delete (%d)...ilist->first=(%p),last=(%p)\n",i,ilist[i]->first,ilist[i]->last) ;
}
*/
//printf("free..(%d)\n",x->key) ;
free (x);
/* adjust header level */
while ((list.listLevel > 0)
&& (list.hdr->forward[list.listLevel] == NIL))
list.listLevel--;
return STATUS_OK;
}
statusEnum find(keyType key, recType *rec) {
int i;
nodeType *x = list.hdr;
/*******************************
* find node containing data *
*******************************/
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
}
x = x->forward[0];
if (x != NIL && compEQ(x->key, key)) {
*rec = x->rec;
return STATUS_OK;
}
return STATUS_KEY_NOT_FOUND;
}
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;
for(i=0;i<3;i++)
{
ilist[i] = calloc(1, sizeof(IntruList));
ilist[i]->first=NULL;
ilist[i]->last=NULL;
} //for
}
int main(int argc, char **argv) {
int i, maxnum, random;
recType *rec;
keyType *key;
statusEnum status;
/* command-line:
*
* skl maxnum [random]
*
* skl 2000
* process 2000 sequential records
* skl 4000 r
* process 4000 random records
*
*/
maxnum = atoi(argv[1]);
random = argc > 2;
initList();
if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
fprintf (stderr, "insufficient memory (rec)\n");
exit(1);
}
if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
fprintf (stderr, "insufficient memory (key)\n");
exit(1);
}
if (random) {
/* fill "a" with unique random numbers */
for (i = 0; i < maxnum; i++){
key[i] = rand() ;
rec[i].stuff = key[i] * 3 ;
}
printf ("ran, %d items\n", maxnum);
} else {
for (i = 0; i < maxnum; i++){
key[i] = i;
rec[i].stuff = key[i] * 3;
}//for
printf ("seq, %d items\n", maxnum);
}
for (i = 0; i < maxnum; i++) {
status = insert(key[i], &rec[i]);
if (status)
printf("pt1: error = %d\n", status);
}
int num1=0,num2=0,num3=0;
int iarray[3] ;
for (i = 0; i < maxnum; i++) {
int itmp ;
itmp = (i % 5) ;
if(itmp==0){
iarray[0]=0;iarray[1]=0;iarray[2]=0;
}else if(itmp==1){
iarray[0]=0;iarray[1]=1;iarray[2]=1;
}else if(itmp==2){
iarray[0]=1;iarray[1]=0;iarray[2]=0;
}else if(itmp==3){
iarray[0]=1;iarray[1]=0;iarray[2]=1;
}else if(itmp==4){
iarray[0]=1;iarray[1]=1;iarray[2]=1;
}
status = setIntruList(key[i],iarray) ;
if (status){
printf("setIntruList error,(%d)(%d)",key[i],status) ;
exit(0) ;
}
} // for
printf("========================= \n") ;
#ifdef DEBUG
IntruListNode * listx ;
size_t offset ;
for(i=0;i<3;i++)
{
listx = ilist[i]->first ;
offset = offsetof(nodeType,intrunode[0]) + sizeof(IntruListNode) * i ;
//printf("(%d)(%d)\n",i,offset) ;
while(1)
{
if (listx==NULL)
break;
if(listx != NULL)
{
nodeType* node = (nodeType *) ( (char *)(listx) - offset) ;
printf("(%p)(%d)==>",node,node->key) ;
}
if(listx != NULL) listx = listx->next ;
}
printf("\n") ;
} //for
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \n") ;
for(i=0;i<3;i++)
{
listx = ilist[i]->last ;
offset = offsetof(nodeType,intrunode[0]) + sizeof(IntruListNode) * i ;
//printf("(%d)(%d)\n",i,offset) ;
while(1)
{
if (listx==NULL)
break;
if(listx != NULL)
{
nodeType* node = (nodeType *) ( (char *)(listx) - offset) ;
printf("(%p)(%d)==>",node,node->key) ;
}
if(listx != NULL) listx = listx->prev ;
}
printf("\n") ;
} //for
#endif
printf("========================= \n") ;
for (i = maxnum-1; i >= 0; i--) {
status = delete(key[i]);
if (status)
printf("pt3: error = %d\n", status);
}
for(i=0;i<3;i++)
{
printf(" (%d)...ilist->first=(%p),last=(%p)\n",i,ilist[i]->first,ilist[i]->last) ;
}
for (i = maxnum-1; i >= 0; i--) {
status = find(key[i], &rec[i]);
if (status != STATUS_KEY_NOT_FOUND)
printf("deleted data should be notfound!! \n");
}
exit(0) ;
printf("========================= \n") ;
insert(4, &rec[4]);
iarray[0]=1;iarray[1]=0;iarray[2]=1;
setIntruList(4,iarray) ;
iarray[0]=0;iarray[1]=0;iarray[2]=1;
setIntruList(4,iarray) ;
iarray[0]=0;iarray[1]=0;iarray[2]=1;
setIntruList(4,iarray) ;
insert(5, &rec[5]);
iarray[0]=1;iarray[1]=0;iarray[2]=1;
setIntruList(5,iarray) ;
iarray[0]=0;iarray[1]=0;iarray[2]=0;
setIntruList(4,iarray) ;
iarray[0]=0;iarray[1]=0;iarray[2]=0;
setIntruList(5,iarray) ;
//delete(4) ;
for(i=0;i<3;i++)
{
printf(" (%d)...ilist->first=(%p),last=(%p)\n",i,ilist[i]->first,ilist[i]->last) ;
}
#ifdef DEBUG2
IntruListNode * listx ;
size_t offset ;
for(i=0;i<3;i++)
{
listx = ilist[i]->first ;
offset = offsetof(nodeType,intrunode[0]) + sizeof(IntruListNode) * i ;
//printf("(%d)(%d)\n",i,offset) ;
while(1)
{
if (listx==NULL)
break;
if(listx != NULL)
{
nodeType* node = (nodeType *) ( (char *)(listx) - offset) ;
printf("(%p)(%d)==>",node,node->key) ;
}
if(listx != NULL) listx = listx->next ;
}
printf("\n") ;
} //for
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \n") ;
for(i=0;i<3;i++)
{
listx = ilist[i]->last ;
offset = offsetof(nodeType,intrunode[0]) + sizeof(IntruListNode) * i ;
//printf("(%d)(%d)\n",i,offset) ;
while(1)
{
if (listx==NULL)
break;
if(listx != NULL)
{
nodeType* node = (nodeType *) ( (char *)(listx) - offset) ;
printf("(%p)(%d)==>",node,node->key) ;
}
if(listx != NULL) listx = listx->prev ;
}
printf("\n") ;
} //for
for(i=0;i<3;i++)
{
printf(" (%d)...ilist->first=(%p),last=(%p)\n",i,ilist[i]->first,ilist[i]->last) ;
}
#endif
return 0;
}
留言列表
