#pragma title P2UPSK
#include "p2upskh.h"
#pragma eject
/*--------------------------------------------------------------------+
| |
| Copyright (c) 1996, SAS Institute Inc. |
| Unpublished - All Rights Reserved |
| |
| S A S / C S A M P L E |
| |
| Name : P2UPSK |
| |
| Language: C |
| |
| Purpose : This source file contains the functions necessary to |
| support the creation and maintenace of a skiplist. |
| |
| Skiplists are really linked list with a little twist. |
| The twist is an extra set of pointers that 'skip' |
| over intermediate nodes during search functions. |
| |
| The extra pointers are assigned during list |
| construction using a random number generator to |
| determine the number of levels in which the node |
| will appear. |
| |
| The following is a very simple skiplist for illustration|
| purposes. Level 1 is a standard linked list terminated |
| with a null pointer. Level 2 is 'skiplist', notice |
| that elements 1, 4, 5, and 7 are not in the list at |
| level 2. Level 3 is a skiplist that has no elements. |
| |
| To search a skiplist you start at the highest level |
| in the list header and follow the pointer chain. When |
| you reach a NIL pointer you drop down one level. If |
| the level drops to zero the key is not in the list. |
| |
| If it is not zero, the you continue along the new |
| level. When you reach a node with a greater key you |
| have gone to far at that level, drop down one level. |
| If the level drops to zero the key is not in the list, |
| otherwise continue along the chain. |
| |
| In this example to find the k=5, start at level 3, |
| NIL is reached where k=3, drop down to level 2. |
| At level 2 the matching node is reached, k=5. It took |
| four compares to find the matching node. A linear |
| search would have taken five. |
| |
| +-------+ |
| | |NIL | |
| +-------+ +---+ |
| |Level 3| ------------->|NIL| |
| +-------+ +---+ +---+ +---+ |
| |Level 2| ------->|*->| |*->| ----------->|NIL| |
| +-------+ +---+ +---+ +---+ +---- +---+ +---+ +---+ |
| |Level 1| |*->| |*->| |*->| |*->| |*->| |*->| |NIL| |
| +-------+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ |
| |
| +-------+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ |
| |Lvls=3 | |k=1| |k=2| |k=3| |k=4| |k=5| |k=6| |k=7| |
| +-------+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ |
| |
| Returns : |
| All functions either return correctly, issue assert(), |
| issue a longjmp(), or abend. |
| |
| |
| Notes : |
| - Programs that build and use skiplist are responsible |
| for freeing storage obtained during contruction. |
| |
| Function delete_node() removes a node from the chain |
| and frees the storage allocated for the the node |
| by insert_node(). If the node has pointers to other |
| allocated storage, it is the callers responsibility |
| to free that storage before calling delete_node(). |
| |
| Function freelist() is provided to delete a skiplist. |
| All storage allocated for each node in the list is |
| freed. If a node has a pointer to other storage, |
| it is the callers responsibility to ensure that |
| storage is freed before calling freelist(). |
| |
| Header Files: P2UPSKH.H |
| |
| Callable Functions: |
| |
| extern newlist() - initalize a header node for a skiplist |
| extern insert_node() - insert a new node in the skiplist, in |
| order |
| extern search_node() - search for a node in the skiplist |
| extern delete_node() - delete a node from the skiplist |
| extern freelist() - free node storage for a skiplist |
| |
| Internal Functions: |
| |
| static newnode() - construct a new node |
| static randomlevel() - select a random skiplist level |
| static slrandom() - scale a pseudo-random number to fit |
| within a given range |
| |
| Calls to External Functions: |
| |
| (*COMP_FP) - insert_node(), search_node(), and delete_node() |
| require a function pointer as the first formal |
| parameter. The function is called to compare a |
| skiplist node data element (argument 1) to a data |
| element (agrument 2). |
| |
| The compare function should be prepared to handle |
| formal arguments as follows: |
| Argument 1: Address of the data element portion of |
| a skiplist node |
| Argument 2: Address of a data element |
| |
| The compare function must determine the return code |
| as follows: |
| -1 = node data element less than data element |
| (argument 1 is less than agrument 2) |
| 0 = data elements are equal |
| (argument 1 and argument 2 are equal) |
| 1 = node data element is higher than data element |
| (argument 1 is higher than agrument 2) |
| |
| |
| |
| References: |
| |
| The article by Fredrick Hegeman[1] provided commentary and sample |
| code upon which these functions are based. The article has a good |
| explanation of skiplist, how they work, and how to tune them. |
| |
| The article by William Pugh[2], the author of skiplists, is a very |
| exhaustive explaination of skiplists and how/why they work. It was |
| used as background information. |
| |
| 1. Hegeman, Frederick |
| "Skip Lists" |
| The C Users Journal |
| Feburary, 1991, Pp. 33-45 |
| |
| 2. Pugh, William. |
| "Skip List: A Probabilistic Alternative To Balanced Trees" |
| Communication of The ACM, XXXIII, |
| 6, June, 1990, Pp. 668-676. |
| |
| Note: Pugh is the author of 'skiplist'. |
| |
| |
+--------------------------------------------------------------------*/
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : newlist |
| |
| Purpose : Allocate storage for and initialize a skiplist header |
| node. |
| |
| The header node looks just like a data node, except, |
| the last member of the node is an array of pointers. |
| |
| Each pointer in the array is a pointer to the first |
| data node of each level of the skiplist or NULL if |
| there are no nodes at that level. |
| |
| Parameters: None |
| |
| Returns : |
| NODE * - pointer to the allocated NODE |
| |
| Notes : |
| - Issues longjmp() to out_of_memory handler when |
| calloc() returns a NULL pointer. |
| |
| |
+--------------------------------------------------------------------*/
extern NODE * newlist( void )
{
NODE *temp = NULL;
int node_header_size; /* Memory for header node */
int node_levels_ptr_total; /* Total memory need for pointers */
/* to the first data node of each */
/* level */
int node_head_size; /* computed size of a header node */
/*--------------------------------------------------------------------+
| Calculate the total memory needed for the header node, plus |
| the memory needed to hold the pointers to the first data node |
| of each level of the skip list. |
+--------------------------------------------------------------------*/
node_header_size = sizeof(NODE);
node_levels_ptr_total = sizeof(NODE *) * (MAXLEVEL- 1);
node_head_size = node_header_size + node_levels_ptr_total;
temp = (NODE *)calloc( node_head_size, 1); /* allocate the header */
/*--------------------------------------------------------------------+
| Ensure memory was allocated. |
+--------------------------------------------------------------------*/
if (temp == NULL)
{
fprintf(stderr,"\nError: Out of memory condition detected!\n");
fprintf(stderr,"\n NULL pointer returned from calloc().\n\n");
fprintf(stderr,"\n At line %d in %s\n", __LINE__,__FILE__);
longjmp(out_of_memory,EXIT_FAILURE);
}
else
{
temp->level=1;
};
return(temp);
}
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : newnode |
| |
| Purpose : Allocate memory for and initialize a new data node |
| with the data provided. |
| |
| Each new node has at least one level in the skiplist, |
| which is 1 or level[0] in the array. |
| |
| Parameters: |
| int nlevel - the skip level at which this node |
| should be inserted |
| |
| PDS_MBR * data - PDS_MBR which contains the member |
| name, ttr, and alias flag for the |
| node to be created |
| |
| Returns : |
| NODE * - pointer to the newly allocated noed, |
| the node has all data from PDS_MBR |
| |
| Notes : |
| - Issues longjmp() to out_of_memory handler when |
| malloc() returns a NULL pointer. |
| |
+--------------------------------------------------------------------*/
static NODE * newnode(int nlevel, PDS_MBR * data)
{
NODE * temp = NULL;
temp = (NODE *)malloc(sizeof(NODE) +
sizeof(NODE *) * (nlevel - 1));
if (temp == NULL)
{
fprintf(stderr,"\nError: Out of memory condition detected!\n");
fprintf(stderr,"\n NULL pointer returned from malloc().\n\n");
fprintf(stderr,"\n At line %d in %s\n", __LINE__,__FILE__);
longjmp(out_of_memory,EXIT_FAILURE);
}
else
{ /* Copy PDS member information to the node allocated */
memcpy(&temp->data, data, sizeof(PDS_MBR));
};
return(temp);
}
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : insert_node |
| |
| Purpose : Create a new node with the provided data element and |
| insert it into the skiplist. |
| |
| If it does NOT exist, it will be inserted in the |
| skiplist at level 0, and at each level selected at |
| at random. Returns a pointer to the new node. |
| |
| NIL will be returned if there is a node in the skiplist |
| with a matching data element. |
| |
| Parameters: |
| int (*COMP_FP)() - function pointer to the routine |
| which will be called to compare |
| the keys |
| |
| NODE * searchlist - pointer to skiplist header where |
| the node will be inserted |
| |
| PDS_MBR * new_data - the data element portion of the |
| node to be inserted |
| |
| Returns : |
| NIL - pointer to NIL if a node with a matching data |
| element is already in the skiplist |
| |
| NODE * - pointer to the address of new node inserted |
| |
| Notes : |
| - insert_node() DOES NOT ALLOW nodes with duplicate |
| keys. |
| - assert() used to enuser no formal agrugments are NULL.|
| |
+--------------------------------------------------------------------*/
extern NODE * insert_node( int (*COMP_FP)(PDS_MBR *, PDS_MBR *),
NODE *searchlist,
PDS_MBR * new_data
)
{
NODE * lnode = NULL;
NODE * tnode = NULL;
NODE *tempptrs[MAXLEVEL];
int i;
int compare_result;
int newlevel;
int while_status = CONTINUE; /* while loop ending status */
int for_status = CONTINUE; /* for loop ending status */
/*--------------------------------------------------------------------+
| Ensure no arguments are NULL. |
+--------------------------------------------------------------------*/
assert( (new_data != NULL) && (searchlist != NULL)
&& ( COMP_FP != NULL)
);
#pragma eject
/*--------------------------------------------------------------------+
| |
| for_loop : This loop starts at the highest level and goes down |
| one level at time until : |
| a) a node is found with a matching key, returns NULL |
| b) end of skiplist with NO matching entry, insert |
| a new node and return a pointer to it |
| |
| while_loop: This loop searches the linklist at each level looking |
| for a matching key - |
| a) searchkey less than - continue search with next |
| node at this level |
| b) searchkey equal to - exit with pointer to the |
| node with the matching key |
| c) searchkey greater than - searchkey not at this |
| level, go down one level |
| and start again |
| |
+--------------------------------------------------------------------*/
lnode = searchlist; /* Start of the list */
for(i = searchlist->level ;
(i >= 0) /* Maxlevel reached? */
&& /* Both must be true */
(for_status == CONTINUE); /* Match found? */
--i)
{
while_status = CONTINUE; /* reset for each pass */
tnode = lnode->pointers[i]; /* Initialize first pointer */
while ( while_status == CONTINUE ) /* Still looking? */
{
if (tnode == NIL) /* Last Node? */
{
/* Last node this level, insert node here, terminate while */
while_status = TERMINATE;
}
else
{
/* Compare the two nodes */
compare_result = (*COMP_FP)(&tnode->data, new_data);
assert( (compare_result == LESSTHAN ) || /* Verify values */
(compare_result == EQUAL ) || /* are within */
(compare_result == GREATERTHAN ) /* range */
);
switch(compare_result)
{
case LESSTHAN: /* Continue search */
lnode = tnode;
tnode = lnode->pointers[i];
break; /* once more, look! */
case EQUAL: /* Match found exit now */
while_status = TERMINATE; /* stop while loop */
for_status = TERMINATE; /* stop for loop */
break; /* tnode has ptr to match */
case GREATERTHAN: /* Match not found at this */
while_status = TERMINATE; /* level, stop while-loop */
break; /* and go down to next lvl */
default: /* The assert() should prevent us from ever */
/* reaching this point. */
abend(ERR_COMPARE_RC);
};
};
}; /* While: End */
/*--------------------------------------------------------------+
| tempptrs keeps track of the where the new node would be |
| placed at each level of the skiplist. The new node will |
| be inserted after the nodes in tempptrs. |
+--------------------------------------------------------------*/
tempptrs[i] = lnode;
};/* For: End */
#pragma eject
/*--------------------------------------------------------------------+
| Determine how to finish up, based on the for_loop ending status - |
| for_status == TERMINATE: node with the same/duplicate key |
| found, do not insert it. |
| for_status ^= TERMINATE: NO DUPLICATE found, this node should |
| be inserted, tempptrs has insertion |
| points |
+--------------------------------------------------------------------*/
if (for_status == TERMINATE) /* Handle duplicate found */
{
lnode = NIL; /* Return NIL */
}
else /* Handle new key found */
{
newlevel = randomlevel(); /* Pick 'skip' level at random */
if (newlevel > searchlist->level)
{
/*-------------------------------------------------------------+
| If we have reached a new 'highest' level, reset the forward |
| pointers for each of the NEW levels. More than 1 level may |
| have been added. |
+-------------------------------------------------------------*/
for ( i = searchlist->level; i < newlevel; ++ i )
{
tempptrs[i] = searchlist;
};
searchlist->level = newlevel; /* indicate new highest */
/* level for skiplist */
};
/*----------------------------------------------------------------+
| Chain new node to next node, chain previous node to new node. |
+----------------------------------------------------------------*/
lnode = newnode(newlevel, new_data); /* construct a new node */
for ( i = 0; i < newlevel; ++i)
{
lnode->pointers[i] = tempptrs[i]->pointers[i]; /*new-> */
tempptrs[i]->pointers[i] = lnode; /* previous->new */
};
};/* else: End */
return(lnode);
}
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : search_node |
| |
| Purpose : Search the skiplist looking for a node with data |
| element matching the one provided. |
| |
| Parameters: |
| int (*COMP_FP) () - function pointer to the routine |
| which will be called to compare |
| the keys |
| |
| NODE * searchlist - skiplist to be searched for the |
| data element provided |
| |
| PDS_MBR * search_data- data element to be located |
| |
| Returns : |
| NIL - pointer to NULL if node not in the skiplist |
| |
| NODE * - pointer to the node with matching data |
| element |
| |
| Notes : |
| |
| - assert() used to enuser no formal agrugments are NULL.|
| |
+--------------------------------------------------------------------*/
extern NODE * search_node ( int (*COMP_FP)(PDS_MBR *, PDS_MBR *),
NODE *searchlist,
PDS_MBR * search_data
)
{
NODE *list;
NODE *temp;
int i;
int compare_result;
int while_status = CONTINUE; /* while loop ending status */
int for_status = CONTINUE; /* for loop ending status */
/*--------------------------------------------------------------------+
| Ensure no arguments are NULL. |
+--------------------------------------------------------------------*/
assert( (search_data != NULL) && (searchlist != NULL)
&& ( COMP_FP != NULL)
);
#pragma eject
/*--------------------------------------------------------------------+
| |
| for_loop : This loop starts at the highest level and goes down |
| one level at a time until : |
| a) a node with a matching key is found |
| b) end of skiplist with NO match entry |
| |
| while_loop: This loop searches the linklist at each level looking |
| for a matching key: |
| a) searchkey less than - continue search with next |
| node |
| b) searchkey equal to - exit with pointer to the |
| node with the matching key |
| c) searchkey greater than - searchkey not in that |
| level, go to next level |
| |
+--------------------------------------------------------------------*/
list = searchlist;
for(i = list->level; /* Start at top level */
(i >= 0) /* Maxlevels reached? */
&& /* Both MUST be True */
(for_status == CONTINUE); /* Match found? */
--i /* Down one level */
)
{ /* For: Start */
while_status = CONTINUE;
temp = list->pointers[i]; /* Aim at first data node */
while( while_status == CONTINUE) /* Last node (=NIL)? */
{ /* While: Strt */
if (temp == NIL)
{/* End of list reached, try next level down */
while_status = TERMINATE; /* Stop while loop */
}
else
{
compare_result = (*COMP_FP)(&temp->data, search_data);
assert( (compare_result == LESSTHAN ) || /* Verify values */
(compare_result == EQUAL ) || /* are within */
(compare_result == GREATERTHAN ) /* range */
);
switch(compare_result)
{
case LESSTHAN: /* Continue search */
list = temp; /* Change to current node */
temp = list->pointers[i]; /* Aim at next compare node*/
break;
case EQUAL: /* Match found, exit now */
while_status = TERMINATE; /* Stop while loop */
for_status = TERMINATE; /* Stop for loop */
break; /* Temp has ptr to match */
case GREATERTHAN: /* Not found at this level */
while_status = TERMINATE; /* Stop while loop */
temp = NIL; /* Mark not at this level */
break; /* Go down to next level */
default: /* The assert() should prevent us from ever */
/* reaching this point. */
abend(ERR_COMPARE_RC);
}; /* Switch : End */
}; /* If : End */
}; /* While : End */
}; /* For : End */
#pragma eject
/*--------------------------------------------------------------------+
| See how we completed and set return accordingly. |
+--------------------------------------------------------------------*/
if (while_status == TERMINATE && for_status == TERMINATE)
{
/* Match found, do nothing, temp points to equal node */
}
else
{ /* Match was not found, set return pointer to NIL */
temp=NIL;
};
return(temp); /* Will be either NIL or pointer to matching node */
}
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : delete_node |
| |
| Purpose : Remove a node from the skiplist which has a matching |
| data element. |
| |
| Parameters: |
| int (*COMP_FP) - function pointer to the routine |
| which will be called to compare |
| the keys |
| |
| NODE * deletelist - skiplist to delete node from |
| |
| PDS_MBR * delete_data- data element to delete |
| |
| Returns : |
| FOUND (1) - if the node is found, it was deleted from |
| the skiplist |
| |
| NOT_FOUND (0) - if the node was not found in the skiplist, |
| no nodes were deleted |
| |
| Notes : |
| |
| - assert() used to enuser no formal agrugments are NULL.|
| |
+--------------------------------------------------------------------*/
extern int delete_node ( int (*COMP_FP)(PDS_MBR *, PDS_MBR *),
NODE *deletelist,
PDS_MBR * delete_data
)
{
int compare_result;
int while_status;
NODE *lnode; /* Get pointer to tnode from here */
NODE *tnode; /* Current node to compare */
NODE *tempptrs[MAXLEVEL];
int i;
int retcode = NOT_FOUND;
/*--------------------------------------------------------------------+
| Ensure no arguments are NULL. |
+--------------------------------------------------------------------*/
assert( (delete_data != NULL) && (deletelist != NULL)
&& ( COMP_FP != NULL)
);
#pragma eject
/*--------------------------------------------------------------------+
| |
| Objective : Determine if the node exist in the skiplist and if |
| it does exist at which levels it exists. |
| |
| for_loop : Starts at the highest level in the skiplist and goes |
| to the lowest level. |
| |
| while_loop: Go through linklist at each level looking for a matching|
| node. When the while_loop finishes, tempptrs[0] |
| will be pointing to the node if it exist, the other |
| pointers in tempptrs[1 thru x] will be either NULL if |
| node DOES NOT exist at that level or a pointer to |
| matching node if it does exist. |
| |
+--------------------------------------------------------------------*/
lnode = deletelist; /* Initialize to data member */
for ( i = lnode->level; i >= 0; --i)
{
tnode = lnode->pointers[i]; /* Set tnode to first data node */
while_status = CONTINUE; /* Initialize for first pass */
while (while_status == CONTINUE)
{
if (tnode == NIL )
{
while_status = TERMINATE; /* Last node reached w/o match */
}
else
{ /* We have a data node, compare to delete data */
compare_result = (*COMP_FP)(&tnode->data, delete_data);
assert( (compare_result == LESSTHAN ) ||/* Ensure values */
(compare_result == EQUAL ) ||/* returned are */
(compare_result == GREATERTHAN ) /* within range */
);
switch(compare_result)
{
case LESSTHAN: /* Continue search */
lnode = tnode; /* Current data node */
tnode = lnode->pointers[i];/* Next compare node */
break;
default:
while_status = TERMINATE; /* Equal or Not In list */
break;
}; /* Switch: End */
}; /* Else : End */
}; /* While : End */
tempptrs[i] = lnode; /* Indicate what was found, either NULL */
/* or pointer to the node at this level */
}; /* For : End */
#pragma eject
/*--------------------------------------------------------------------+
| Every node that exist will be at level[0], this level is a standard |
| linklist. If a node is not at level[0], it does not exist in the |
| skiplist. |
+--------------------------------------------------------------------*/
tnode = lnode->pointers[0]; /* Existing nodes will ALWAYS have an */
/* entry at level[0]. */
if (tnode && ((*COMP_FP)(&tnode->data, delete_data) == EQUAL))
{
/* This node exist and should be deleted. */
retcode = FOUND; /* Set return to found/deleted */
lnode = deletelist; /* Set to skiplist header */
/*----------------------------------------------------------------+
| Unchain the node from each level in which it is a member. |
+----------------------------------------------------------------*/
for (i = 0; i < lnode->level;++i)
{
if (tempptrs[i]->pointers[i] != tnode)
{
/* Do nothing at this level*/
}
else
{
/* Unchain at this level */
tempptrs[i]->pointers[i] = tnode->pointers[i];
};
};
free(tnode); /* Free the storage allocated for this node */
/*----------------------------------------------------------------+
| Start with the highest level used and go down. REDUCE the |
| total levels used by 1 if there are no nodes at that level. |
+----------------------------------------------------------------*/
while( ( i = lnode->level) > 1 /* Level 1? */
&& /* Both must be true */
lnode->pointers[i] == NIL) /* Any nodes this level? */
{
lnode->level = --i;
};
}
else
{
retcode = NOT_FOUND; /* Indicate node not found */
};
return(retcode);
}
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : randomlevel |
| |
| Purpose : Returns an integer from 0 to MAXLEVEL, based on the |
| integers chosen for MAXLEVEL and PARTITION. The |
| ratio of MAXLEVEL/PARTITION determines the |
| distribution of node levels within the skiplist. |
| |
| Parameters: None |
| |
| Returns : A randomly selected node level which is between 0 and |
| MAXLEVEL-1. |
| |
| Notes : |
| |
| |
+--------------------------------------------------------------------*/
static int randomlevel(void)
{
static int first_time = YES;
int newlevel;
int rand_level;
newlevel = 1;
if (first_time == YES)
{
first_time = NO;
srand(SEED);
}
while( (slrandom(MAXLEVEL)) < PARTITION )
{
newlevel += 1;
};
if (newlevel > MAXLEVEL)
{ rand_level = MAXLEVEL;}
else
{rand_level = newlevel;};
return(rand_level);
}
#pragma eject
/*--------------------------------------------------------------------+
| |
| Function : slrandom |
| |
| Purpose : Scale a pseudo-random number returned from the rand() |
| to fit within a specified range |
| |
| Parameters: |
| unsigned int limit - upper limit of the random |
| number to be returned to the |
| caller |
| |
| Returns : Returns a number from 0 to the 'limit' provided on the |
| call. |
| |
| Notes : |
| - This routine depends on the value of RAND_MAX, |
| determined by the implementation, and on the range |
| of limit. A compiler other than SAS/C could have a |
| RAND_MAX close to 2**31, in which case the |
| multiplication could overflow and give unpredictable |
| results. |
| |
+--------------------------------------------------------------------*/
static int slrandom(unsigned int limit)
{
long num;
num = (long) rand();
return( (int) ((num * limit) / (1l + RAND_MAX)) );
}
#pragma eject
/*--------------------------------------------------------------------+
| Function : freelist |
| |
| Purpose : Free skiplist nodes and header node. |
| |
| Parameters: |
| NODE * memlist - skiplist to delete |
| |
| Returns : |
| 0 - always zero |
| |
| Notes : |
| |
+--------------------------------------------------------------------*/
extern int freelist(NODE * memlist )
{
NODE *free_node;
NODE *next_node;
/*--------------------------------------------------------------------+
| If there is a skiplist, then free all data bearing nodes and the |
| skiplist header node, otherwise just exit. |
+--------------------------------------------------------------------*/
if ( memlist != NULL)
{
next_node = memlist->pointers[0];
while( next_node != NULL )
{
free_node = next_node;
next_node = free_node->pointers[0];
free(free_node);
};
/* Handle the header node */
free(memlist);
};
return(0);
}
|
