#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); }