www.sas.com > Service and Support > Technical Support
 
Technical Support SAS - The power to know(tm)
  TS Home | Intro to Services | News and Info | Contact TS | Site Map | FAQ | Feedback


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

Copyright (c) 2000 SAS Institute Inc. All Rights Reserved.
Terms of Use & Legal Information | Privacy Statement