Article 1169 of comp.sources.amiga:
Submitted-by: agmsmith@dragon.achilles.net
Posting-number: Volume 96, Issue 34
Archive-name: libs/SkipListLib-1.0/part03

#!/bin/sh
# this is src.03 (part 3 of libs/SkipListLib-1.0)
# do not concatenate these parts, unpack them in order with /bin/sh
# file SkipListLib/Source/SkipList.c continued
#
if test ! -r _shar_seq_.tmp; then
	echo 'Please unpack part 1 first!'
	exit 1
fi
(read Scheck
 if test "$Scheck" != 3; then
	echo Please unpack part "$Scheck" next!
	exit 1
 else
	exit 0
 fi
) < _shar_seq_.tmp || exit 1
if test ! -f _shar_wnt_.tmp; then
	echo 'x - still skipping SkipListLib/Source/SkipList.c'
else
echo 'x - continuing file SkipListLib/Source/SkipList.c'
sed 's/^X//' << 'SHAR_EOF' >> 'SkipListLib/Source/SkipList.c' &&
X    }
X    *PointerToUpdate = NULL;
X  }
X
X  TheList->activeLevels = NewLevel;
X
X  TempULong = 1 << (NewLevel * 2);
X  if (TempULong == 0) /* Did it overflow? */
X    TempULong = ~0L; /* Peg at largest ULONG. */
X  TheList->nextSizeUp = TempULong;
X
X  TempULong = 1 << ((NewLevel - 1) * 2);
X  if (TempULong == 1)
X    TempULong = 0; /* Special range extension for empty lists. */
X  TheList->nextSizeDown = TempULong;
}
X
X
X
/******************************************************************************
X * Adds the given node to the given list.  If there is an existing node with
X * an equal value then it will be deleted (removed and deallocated) before
X * this one is added.  Presumably TheNode has been allocated by
X * AllocateSkipNode or an equivalent user function that has set the nodeLevel
X * and allocated a hidden array.  Returns the node prior to the inserted node
X * in the list, or NULL if the inserted one is the first in the list (useful
X * for implementing previous node pointers).  Always succeeds (you've already
X * allocated the memory for the node so there isn't anything that normally can
X * go wrong).  Don't insert a node that is already in some other list, that
X * would corrupt the other list badly.
X *
X * If you have to have data simultaneously in several lists, you need to have
X * a SkipNodeRecord for each list.  An easy way is to create a bunch of
X * SkipNodeRecords with the user data portion just containing a pointer to
X * your actual data.  If you want to get tricky and do everything in one
X * record, you can create a variable sized user data record that contains
X * custom allocated SkipNodeRecords and their associated hidden pointer arrays
X * following it in memory.  You would also need a custom destroyUserData
X * function to avoid incorrect deallocations.  As well, you would need to use
X * GenerateRandomLevelNumber to generate random sized SkipNodeRecords within
X * your variable data record.  Alternatively you can waste memory and have a
X * fixed size record by using SKIPLISTLEVELCAP for the hidden array size (but
X * remember to still specify a proper random level number in the nodeLevel
X * fields).
X */
X
static SkipNodePointer InsertSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register SkipNodePointer a1 __asm("a1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipNodePointer TheNode = a1;
X  SkipListBasePointer OurBase = a6;
X
X  short AddressOffset;
X  LONG ComparisonResult;
X  SkipNodePointer CurrentNode;
X  UBYTE MinimumLevel;
X  SkipNodePointer NextNode;
X  SkipNodePointer NodesToUpdate [SKIPLISTLEVELCAP];
X  SkipNodePointer PreviousNode;
X
#if DEBUGMODE
X  if (TheList == NULL || TheNode == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList or TheNode in InsertSkipNode.",
X    OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
#if DEBUGMODE
X  if (TheList->activeLevels <= 0 || TheList->activeLevels > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Corrupt TheList header in InsertSkipNode.", OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
X  /* Start off at the list header, treating it like a fake node. */
X
X  CurrentNode = (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1];
X
X  /* This outer loop scans down the levels of pointers (starting at the
X     sparsest list) until we get to the bottom (the list with all nodes).  The
X     AddressOffset hack is used to get the node's LevelPointers[] entry
X     quickly for several nodes with the same level index value (yup, negative
X     indices for a backwards array).  The general idea is to fill up
X     NodesToUpdate with the node at each level that is just before the new
X     node in sort order. */
X
X  AddressOffset = -(TheList->activeLevels * sizeof (SkipNodePointer));
X  while (AddressOffset < 0)
X  {
X    AddressOffset += sizeof (SkipNodePointer);
X
X    /* Scan right along this pointer level until we hit the largest node less
X       than (as defined by the user's comparison function) the one we want to
X       insert. */
X
X    while (TRUE)
X    {
X      /* Get the pointer to the next node at the current level.  This mess
X         boils down to one M68000 instruction, vs having extra shifts and
X         other operations if we used PointerArray[-i]. */
X
X      NextNode = * (SkipNodePointerPointer)
X      (((char *) &CurrentNode->next) + AddressOffset);
X
X      if (NextNode == NULL)
X        break; /* Hit end of this level.  Go to next level. */
X
X      /* Compare the node being searched for and the next node.  Use the user's
X         comparison function or if none, use a string comparison. */
X
X      if (TheList->compareUserData == NULL)
X        ComparisonResult = CompareNodesAsStrings (NextNode, TheNode, OurBase);
X      else
X        ComparisonResult = TheList->compareUserData (NextNode, TheNode);
X
X      if (ComparisonResult >= 0)
X        break; /* Reached a node greater or equal to the new one. */
X
X      CurrentNode = NextNode; /* Scan along the same level some more. */
X    }
X
X    /* Store away the node we stopped at on this level in the NodesToUpdate
X       array, again in backwards array order.  This node is the one which will
X       be just before the new one on this level.  Of course, the new one may
X       or may not be tall enough to actually be on this level. */
X
X    *(SkipNodePointerPointer)
X    (((char *) (&NodesToUpdate[SKIPLISTLEVELCAP-1])) + AddressOffset) =
X    CurrentNode;
X  }
X
X  /* Ok, move CurrentNode forwards one, to the node which is greater than or
X     equal to the new node's sort key.  Or NULL if at the end of the list. */
X
X  CurrentNode = CurrentNode->next;
X
X  /* See if this equal or larger node is equal to the new one.  If it is,
X     it has to be deleted before the new one is inserted. */
X
X  if (CurrentNode != NULL)
X  {
X    if (TheList->compareUserData == NULL)
X      ComparisonResult = CompareNodesAsStrings (CurrentNode, TheNode, OurBase);
X    else
X      ComparisonResult = TheList->compareUserData (CurrentNode, TheNode);
X
X    if (ComparisonResult == 0)
X    {
X      /* Oh, oh.  Have to delete the current node.  Patch up the pointers that
X         used to point to this old node to point around it to the appropriate
X         next ones.  We have several levels of pointers to fix up (the loop
X         goes from the top level used by the dead node to the bottom level). */
X
X      MinimumLevel = CurrentNode->size.asBytes.nodeLevel;
X      if (TheList->activeLevels < MinimumLevel)
X        MinimumLevel = TheList->activeLevels;
X
X      AddressOffset = -(MinimumLevel * sizeof (SkipNodePointer));
X      while (AddressOffset < 0)
X      {
X        AddressOffset += sizeof (SkipNodePointer);
X
X        /* Get the address of the node to fix up.  It's the one just before
X           the current node, in the level of pointers being fixed. */
X
X        PreviousNode = *(SkipNodePointerPointer)
X        (((char *) (&NodesToUpdate[SKIPLISTLEVELCAP-1])) + AddressOffset);
X
X        /* Replace the next pointer at the current level in the previous node
X           with the next pointer at the same level in the dead node. */
X
X        *(SkipNodePointerPointer)
X        (((char *) &PreviousNode->next) + AddressOffset) =
X        *(SkipNodePointerPointer)
X        (((char *) &CurrentNode->next) + AddressOffset);
X      }
X
X      /* Dispose of the dead node.  Don't need to update the list size related
X         values here since the list will end up with the same size as it had
X         before (this removal and the insert cancel out). */
X
X      --TheList->size;
X      CurrentNode->next = NULL; /* So user doesn't use it accidentally. */
X      DeallocateSkipNodeA6 (TheList, CurrentNode, OurBase);
X    }
X  }
X
X  /* Duplicates have been removed, now insert the node.  Wheeee!  The level
X     pointers for the previous nodes that are in levels above the new node
X     just go over its top level, so they don't change.  The ones on the same
X     levels have to be patched, in traditional linked list fashion. */
X
X  MinimumLevel = TheNode->size.asBytes.nodeLevel;
X  if (TheList->activeLevels < MinimumLevel)
X    MinimumLevel = TheList->activeLevels;
X
X  AddressOffset = -(MinimumLevel * sizeof (SkipNodePointer));
X  while (AddressOffset < 0)
X  {
X    AddressOffset += sizeof (SkipNodePointer);
X
X    /* Get the address of the node to fix up.  It's the one just before
X       the new node, in the level of pointers being fixed. */
X
X    PreviousNode = *(SkipNodePointerPointer)
X    (((char *) (&NodesToUpdate[SKIPLISTLEVELCAP-1])) + AddressOffset);
X
X    /* Replace the next pointer at the current level in the previous node
X       with a pointer to the new node.  The new node's next pointer takes over
X       the previous node's value. */
X
X    *(SkipNodePointerPointer)
X    (((char *) &TheNode->next) + AddressOffset) =
X    *(SkipNodePointerPointer)
X    (((char *) &PreviousNode->next) + AddressOffset);
X
X    *(SkipNodePointerPointer)
X    (((char *) &PreviousNode->next) + AddressOffset) = TheNode;
X  }
X  ++TheList->size; /* One more node in the list. */
X
X  /* Check for the size getting large enough to make it worth while to
X     activate a new level of pointers. */
X
X  if (TheList->size >= TheList->nextSizeUp)
X    UpdateListActiveLevels (TheList, OurBase);
X
X  /* Return the node just before the new one.  Or if there is none, return
X     NULL.  Just use the previous node on the bottom level of pointers (that's
X     the level where all nodes are listed) to find the node before the newly
X     inserted one. */
X
X  PreviousNode = NodesToUpdate [SKIPLISTLEVELCAP-1];
X  if (PreviousNode ==
X  (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1])
X    return NULL; /* This is the list header pretending to be a node. */
X
X  return PreviousNode;
}
X
X
X
/******************************************************************************
X * Removes a node with a value equal to TheNode's value from the list.  Returns
X * the node it removed, or NULL if it couldn't find one matching TheNode in
X * value (equality as decided by your compareUserData function).  Doesn't
X * deallocate the node it removed.  TheNode doesn't have to be a fully
X * initialised node if your compareUserData function doesn't use the
X * SkipNodeRecord fields (the default comparison function uses the size field,
X * doesn't need the nodeLevel field or use the hidden array before the record
X * (thus you don't need to use AllocateSkipNode to create a full SkipNode for
X * comparison purposes).
X */
X
static SkipNodePointer RemoveSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register SkipNodePointer a1 __asm("a1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipNodePointer TheNode = a1;
X  SkipListBasePointer OurBase = a6;
X
X  short AddressOffset;
X  LONG ComparisonResult;
X  SkipNodePointer CurrentNode;
X  SkipNodePointer RemovedNode;
X  UBYTE MinimumLevel;
X  SkipNodePointer NextNode;
X  SkipNodePointer NodesToUpdate [SKIPLISTLEVELCAP];
X  SkipNodePointer PreviousNode;
X
#if DEBUGMODE
X  if (TheList == NULL || TheNode == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList or TheNode in RemoveSkipNode.",
X    OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
#if DEBUGMODE
X  if (TheList->activeLevels <= 0 || TheList->activeLevels > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Corrupt TheList header in RemoveSkipNode.", OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
X  /* Start off at the list header, treating it like a fake node. */
X
X  CurrentNode = (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1];
X
X  /* This outer loop scans down the levels of pointers (starting at the
X     sparsest list) until we get to the bottom (the list with all nodes).  The
X     AddressOffset hack is used to get the node's LevelPointers[] entry
X     quickly for several nodes with the same level index value (yup, negative
X     indices for a backwards array).  The general idea is to fill up
X     NodesToUpdate with the node at each level that is just before the
X     searched for node in sort order. */
X
X  AddressOffset = -(TheList->activeLevels * sizeof (SkipNodePointer));
X  while (AddressOffset < 0)
X  {
X    AddressOffset += sizeof (SkipNodePointer);
X
X    /* Scan right along this pointer level until we hit the largest node less
X       than (as defined by the user's comparison function) the one we want to
X       delete. */
X
X    while (TRUE)
X    {
X      /* Get the pointer to the next node at the current level.  This mess
X         boils down to one M68000 instruction, vs having extra shifts and
X         other operations if we used PointerArray[-i]. */
X
X      NextNode = * (SkipNodePointerPointer)
X      (((char *) &CurrentNode->next) + AddressOffset);
X
X      if (NextNode == NULL)
X        break; /* Hit end of this level.  Go to next level. */
X
X      /* Compare the next node and the node being searched for.  Use the
X         user's comparison function or if none, use a string comparison. */
X
X      if (TheList->compareUserData == NULL)
X        ComparisonResult = CompareNodesAsStrings (NextNode, TheNode, OurBase);
X      else
X        ComparisonResult = TheList->compareUserData (NextNode, TheNode);
X
X      if (ComparisonResult >= 0)
X        break; /* Reached a node greater or equal to the searched one. */
X
X      CurrentNode = NextNode; /* Scan along the same level some more. */
X    }
X
X    /* Store away the node we stopped at on this level in the NodesToUpdate
X       array, again in backwards array order.  This node is the one which will
X       be just before the deleted one on this level.  Of course, the deleted
X       one may or may not be tall enough to actually be on this level. */
X
X    *(SkipNodePointerPointer)
X    (((char *) (&NodesToUpdate[SKIPLISTLEVELCAP-1])) + AddressOffset) =
X    CurrentNode;
X  }
X
X  /* Ok, the node to be removed is just after CurrentNode; the node which is
X     greater than or equal to the searched for node's sort key.  Or NULL if at
X     the end of the list. */
X
X  RemovedNode = CurrentNode->next;
X
X  /* See if this equal or larger node is equal to the one being deleted.  If
X     it is, delete it. */
X
X  if (RemovedNode != NULL)
X  {
X    if (TheList->compareUserData == NULL)
X      ComparisonResult = CompareNodesAsStrings (RemovedNode, TheNode, OurBase);
X    else
X      ComparisonResult = TheList->compareUserData (RemovedNode, TheNode);
X
X    if (ComparisonResult == 0)
X    {
X      /* Delete the current node.  Patch up the pointers that used to point to
X         this old node to point around it to the appropriate next ones.  We
X         have several levels of pointers to fix up (the loop goes from the top
X         level used by the dead node to the bottom level). */
X
X      MinimumLevel = RemovedNode->size.asBytes.nodeLevel;
X      if (TheList->activeLevels < MinimumLevel)
X        MinimumLevel = TheList->activeLevels;
X
X      AddressOffset = -(MinimumLevel * sizeof (SkipNodePointer));
X      while (AddressOffset < 0)
X      {
X        AddressOffset += sizeof (SkipNodePointer);
X
X        /* Get the address of the node to fix up.  It's the one just before
X           the removed node, in the level of pointers being fixed. */
X
X        PreviousNode = *(SkipNodePointerPointer)
X        (((char *) (&NodesToUpdate[SKIPLISTLEVELCAP-1])) + AddressOffset);
X
X        /* Replace the next pointer at the current level in the previous node
X           with the next pointer at the same level in the dead node. */
X
X        *(SkipNodePointerPointer)
X        (((char *) &PreviousNode->next) + AddressOffset) =
X        *(SkipNodePointerPointer)
X        (((char *) &RemovedNode->next) + AddressOffset);
X      }
X
X      /* Dispose of the dead node.  Don't deallocate it.  Also adjust the list
X         size and number of active levels. */
X
X      if (--TheList->size < TheList->nextSizeDown)
X        UpdateListActiveLevels (TheList, OurBase);
X
X      RemovedNode->next = NULL; /* So user doesn't use it accidentally. */
X    }
X    else /* Not an equal node. */
X      RemovedNode = NULL; /* Nope, didn't find it after all. */
X  }
X  return RemovedNode;
}
X
X
X
/******************************************************************************
X * This removes a node matching TheNode's value and then deallocates it.
X * Returns non-zero if it actually removed anything, zero if it couldn't find
X * your node.  Does a RemoveSkipNode followed by DeallocateSkipNode, so see
X * those functions for details.
X */
X
static ULONG DeleteSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register SkipNodePointer a1 __asm("a1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipNodePointer TheNode = a1;
X  SkipListBasePointer OurBase = a6;
X
X  SkipNodePointer DeletedNode;
X
X  DeletedNode = RemoveSkipNodeA6 (TheList, TheNode, OurBase);
X  if (DeletedNode != NULL)
X    DeallocateSkipNodeA6 (TheList, DeletedNode, OurBase);
X
X  return (DeletedNode != NULL);
}
X
X
X
/******************************************************************************
X * This function clears the list back to an empty list state, more efficiently
X * than using Delete on individual nodes.  All SkipNodes are deallocated (see
X * DeallocateSkipNode) and the list header is reset to an empty list state.
X */
X
static void DeleteAllSkipNodes (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipListBasePointer OurBase = a6;
X
X  ULONG DeleteCount;
X  int i;
X  SkipNodePointer NextNode;
X  SkipNodePointer NodeToDelete;
X
#if DEBUGMODE
X  if (TheList == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList in DeleteAllSkipNodes.", OurBase);
X    #endif
X    return;
X  }
#endif
X
#if DEBUGMODE
X  if (TheList->activeLevels <= 0 || TheList->activeLevels > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Corrupt TheList header in DeleteAllSkipNodes.",
X    OurBase);
X    #endif
X    return;
X  }
#endif
X
X  /* Deallocate all the nodes, and count how many there were. */
X
X  NextNode = TheList->levelPointers [SKIPLISTLEVELCAP-1];
#if DEBUGMODE
X  DeleteCount = 0;
#endif
X  while (NextNode != NULL)
X  {
X    NodeToDelete = NextNode;
X    NextNode = NextNode->next;
#if DEBUGMODE
X    ++DeleteCount;
X    NodeToDelete->next = NULL; /* So user doesn't use it. */
#endif
X    DeallocateSkipNodeA6 (TheList, NodeToDelete, OurBase);
X  }
X
#if DEBUGMODE && VERBOSE_CODE
X  if (DeleteCount != TheList->size)
X    DisplayErrorMessage (
X    "TheList->size doesn't match node count in DeleteAllSkipNodes.", OurBase);
#endif
X
X  /* Clear the skip list header to an empty list state. */
X
X  for (i = SKIPLISTLEVELCAP - 1; i >= 0; i--)
X    TheList->levelPointers [i] = NULL;
X
X  TheList->activeLevels = 1;
X  TheList->size = 0;
X  TheList->nextSizeUp = 4;
X  TheList->nextSizeDown = 0;
}
X
X
X
/******************************************************************************
X * Finds a node with a value equal to TheNode's value from the list.  Returns
X * the node it found, or NULL if it couldn't find it.  TheNode doesn't have to
X * be a fully initialised node (see RemoveSkipNode for details).
X */
X
static SkipNodePointer FindSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register SkipNodePointer a1 __asm("a1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipNodePointer TheNode = a1;
X  SkipListBasePointer OurBase = a6;
X
X  short AddressOffset;
X  LONG ComparisonResult;
X  SkipNodePointer CurrentNode;
X  SkipNodePointer NextNode;
X
#if DEBUGMODE
X  if (TheList == NULL || TheNode == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList or TheNode in FindSkipNode.",
X    OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
#if DEBUGMODE
X  if (TheList->activeLevels <= 0 || TheList->activeLevels > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Corrupt TheList header in FindSkipNode.", OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
X  /* Start off at the list header, treating it like a fake node. */
X
X  CurrentNode = (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1];
X
X  /* This outer loop scans down the levels of pointers (starting at the
X     sparsest list) until we get to the bottom (the list with all nodes).  The
X     AddressOffset hack is used to get the node's LevelPointers[] entry
X     quickly for several nodes with the same level index value (yup, negative
X     indices for a backwards array).  The general idea is to go along each
X     level and drop down to a more detailed level just before passing the
X     searched for node in sort order. */
X
X  AddressOffset = -(TheList->activeLevels * sizeof (SkipNodePointer));
X  while (AddressOffset < 0)
X  {
X    AddressOffset += sizeof (SkipNodePointer);
X
X    /* Scan right along this pointer level until we hit the largest node less
X       than (as defined by the user's comparison function) the one we want to
X       insert. */
X
X    while (TRUE)
X    {
X      /* Get the pointer to the next node at the current level.  This mess
X         boils down to one M68000 instruction, vs having extra shifts and
X         other operations if we used PointerArray[-i]. */
X
X      NextNode = * (SkipNodePointerPointer)
X      (((char *) &CurrentNode->next) + AddressOffset);
X
X      if (NextNode == NULL)
X        break; /* Hit end of this level.  Go to next level. */
X
X      /* Compare the node being searched for and the next node.  Use the user's
X         comparison function or if none, use a string comparison. */
X
X      if (TheList->compareUserData == NULL)
X        ComparisonResult = CompareNodesAsStrings (NextNode, TheNode, OurBase);
X      else
X        ComparisonResult = TheList->compareUserData (NextNode, TheNode);
X
X      if (ComparisonResult >= 0)
X        break; /* Reached a node greater or equal to the new one. */
X
X      CurrentNode = NextNode; /* Scan along the same level some more. */
X    }
X  }
X
X  /* Got the node just before the desired one in value.  Does the desired node
X     follow right after? */
X
X  CurrentNode = CurrentNode->next;
X
X  if (CurrentNode == NULL)
X    return NULL; /* Nothing follows right after the lower node. */
X
X  /* Is that following node equal to our desired one? */
X
X  if (TheList->compareUserData == NULL)
X    ComparisonResult = CompareNodesAsStrings (CurrentNode, TheNode, OurBase);
X  else
X    ComparisonResult = TheList->compareUserData (CurrentNode, TheNode);
X
X  if (ComparisonResult == 0)
X    return CurrentNode; /* Yes, we found it! */
X
X  return NULL; /* No, this node will be larger.  Didn't find it. */
}
X
X
X
/******************************************************************************
X * Finds a node with the largest value less than TheNode's value in TheList.
X * If it can't be found (no nodes less than TheNode) then it returns NULL.
X * TheNode doesn't have to be a fully initialised node (see RemoveSkipNode for
X * details).
X */
X
static SkipNodePointer FindBelowSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register SkipNodePointer a1 __asm("a1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipNodePointer TheNode = a1;
X  SkipListBasePointer OurBase = a6;
X
X  short AddressOffset;
X  LONG ComparisonResult;
X  SkipNodePointer CurrentNode;
X  SkipNodePointer NextNode;
X
#if DEBUGMODE
X  if (TheList == NULL || TheNode == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList or TheNode in FindBelowSkipNode.",
X    OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
#if DEBUGMODE
X  if (TheList->activeLevels <= 0 || TheList->activeLevels > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage (
X    "Corrupt TheList header in FindBelowSkipNode.", OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
X  /* See the FindSkipNode function for comments.  This code is mostly copied
X     from there. */
X
X  CurrentNode = (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1];
X  AddressOffset = -(TheList->activeLevels * sizeof (SkipNodePointer));
X  while (AddressOffset < 0)
X  {
X    AddressOffset += sizeof (SkipNodePointer);
X    while (TRUE)
X    {
X      NextNode = * (SkipNodePointerPointer)
X      (((char *) &CurrentNode->next) + AddressOffset);
X
X      if (NextNode == NULL)
X        break;
X
X      if (TheList->compareUserData == NULL)
X        ComparisonResult = CompareNodesAsStrings (NextNode, TheNode, OurBase);
X      else
X        ComparisonResult = TheList->compareUserData (NextNode, TheNode);
X
X      if (ComparisonResult >= 0)
X        break;
X
X      CurrentNode = NextNode;
X    }
X  }
X
X  if (CurrentNode ==
X  (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1])
X    return NULL; /* At the list header fake node, nothing before TheNode. */
X
X  return CurrentNode; /* Yup, this is the one before TheNode. */
}
X
X
X
/******************************************************************************
X * Finds a node with the smallest value equal or greater than TheNode's value
X * in TheList.  If it can't be found (no nodes greater than or equal to
X * TheNode) then it returns NULL.  TheNode doesn't have to be a fully
X * initialised node (see RemoveSkipNode for details).
X */
X
static SkipNodePointer FindAboveOrEqualSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register SkipNodePointer a1 __asm("a1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipNodePointer TheNode = a1;
X  SkipListBasePointer OurBase = a6;
X
X  short AddressOffset;
X  LONG ComparisonResult;
X  SkipNodePointer CurrentNode;
X  SkipNodePointer NextNode;
X
#if DEBUGMODE
X  if (TheList == NULL || TheNode == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList or TheNode in FindAboveOrEqualSkipNode.",
X    OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
#if DEBUGMODE
X  if (TheList->activeLevels <= 0 || TheList->activeLevels > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage (
X    "Corrupt TheList header in FindAboveOrEqualSkipNode.", OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
X  /* See the FindSkipNode function for comments.  This code is mostly copied
X     from there. */
X
X  CurrentNode = (SkipNodePointer) &TheList->levelPointers [SKIPLISTLEVELCAP-1];
X  AddressOffset = -(TheList->activeLevels * sizeof (SkipNodePointer));
X  while (AddressOffset < 0)
X  {
X    AddressOffset += sizeof (SkipNodePointer);
X    while (TRUE)
X    {
X      NextNode = * (SkipNodePointerPointer)
X      (((char *) &CurrentNode->next) + AddressOffset);
X
X      if (NextNode == NULL)
X        break;
X
X      if (TheList->compareUserData == NULL)
X        ComparisonResult = CompareNodesAsStrings (NextNode, TheNode, OurBase);
X      else
X        ComparisonResult = TheList->compareUserData (NextNode, TheNode);
X
X      if (ComparisonResult >= 0)
X        break;
X
X      CurrentNode = NextNode;
X    }
X  }
X
X  return CurrentNode->next;  /* That was easy. */
}
X
X
X
/******************************************************************************
X * Returns a random number from 1 to SKIPLISTLEVELCAP.  There's a 3/4 chance
X * of getting 1 returned, 3/16 of getting 2, and in general 3/(4^n) of getting
X * n.  Uses the cached random numbers in the list.  If TheList is NULL then it
X * will call the random number generator directly.
X */
X
static ULONG GenerateRandomLevelNumber (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipListBasePointer OurBase = a6;
X
X  int LevelNumber;
X  int RandomIndex;
X  ULONG RandomNumber;
X
X  /* First get a 32 bit random number. */
X
X  if (TheList == NULL)
X    RandomNumber = Random250LongA6 (OurBase->random250Base);
X  else /* Can use the cached numbers in the list. */
X  {
X    RandomIndex = TheList->randomIndex;
X    RandomNumber = TheList->randomCache [RandomIndex];
X    if (--RandomIndex < 0)
X    {
X      /* Just ran out of cached random numbers.  Refill the cache. */
X
X      Random250ArrayA6 (RANDOMCACHESIZE, TheList->randomCache,
X      OurBase->random250Base);
X      RandomIndex = RANDOMCACHESIZE - 1;
X    }
X    TheList->randomIndex = RandomIndex;
X  }
X
X  /* Convert it to our special probability distribution.
X     3/4 of the time you get 1, 3/16 you get 2, etc. */
X
X  LevelNumber = 1;
X  while (LevelNumber < SKIPLISTLEVELCAP)
X  {
X    if (RandomNumber & 3) /* If lower 2 bits are non-zero; 3/4 of the time. */
X      break;
X
X    RandomNumber >>= 2;
X    LevelNumber++;
X  }
X
X  return LevelNumber;
}
X
X
X
/******************************************************************************
X * Returns the value of RANDOMCACHESIZE used by the library.
X */
X
static ULONG GetRANDOMCACHESIZE (void)
{
X  return RANDOMCACHESIZE;
}
X
X
X
/******************************************************************************
X * Returns the value of SKIPLISTLEVELCAP used by the library.
X */
X
static ULONG GetSKIPLISTLEVELCAP (void)
{
X  return SKIPLISTLEVELCAP;
}
X
X
X
/******************************************************************************
X * Dummy function used for finding the end of the code segment.  Must
X * be at the end of this file!
X */
X
static void EndOfCode (void)
{
}
SHAR_EOF
echo 'File SkipListLib/Source/SkipList.c is complete' &&
chmod 0600 SkipListLib/Source/SkipList.c ||
echo 'restore of SkipListLib/Source/SkipList.c failed'
Wc_c="`wc -c < 'SkipListLib/Source/SkipList.c'`"
test 64052 -eq "$Wc_c" ||
	echo 'SkipListLib/Source/SkipList.c: original size 64052, current size' "$Wc_c"
rm -f _shar_wnt_.tmp
fi
# ============= SkipListLib/Source/SkipList.h ==============
if test -f 'SkipListLib/Source/SkipList.h' -a X"$1" != X"-c"; then
	echo 'x - skipping SkipListLib/Source/SkipList.h (File already exists)'
	rm -f _shar_wnt_.tmp
else
> _shar_wnt_.tmp
echo 'x - extracting SkipListLib/Source/SkipList.h (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'SkipListLib/Source/SkipList.h' &&
#ifndef SKIPLIST_H
#define SKIPLIST_H
/***********************************************************************
X * Exported functions from SkipList.library - an Amiga shared library
X * for fast random and sequential access sorted lists.
X *
X * $Header: Big:Programming/C/SkipLists/RCS/SkipList.h,v 1.6 1996/08/29 12:26:24 AGMS Exp $
X *
X * Implemented by Alexander G. M. Smith, Ottawa Canada,
X * agmsmith@achilles.net, agmsmith@bix.com, 71330.3173@compuserve.com,
X * and various other places including the Ottawa Freenet.
X *
X * This code is put into the public domain by AGMS, so you can copy it,
X * hack it up, sell it, and do whatever you want to it.  See SkipList.c
X * for algorithm credits and explanations.
X *
X * $Log: SkipList.h,v $
X * Revision 1.6  1996/08/29  12:26:24  AGMS
X * Added comment for how to simulate duplicate keys.
X *
X * Revision 1.5  1996/08/19  15:05:10  AGMS
X * Changed FindBelowOrEqualSkipNode to FindBelowSkipNode.
X *
X * Revision 1.4  1996/08/17  13:01:36  AGMS
X * Documentation changes.
X *
X * Revision 1.3  1996/08/14  14:33:26  AGMS
X * Minor corrections.
X *
X * Revision 1.2  1996/08/11  13:17:00  AGMS
X * Defined the functions that skiplist library exports and wrote
X * up descriptions of what they do.
X *
X * Revision 1.1  1996/08/05  19:09:55  AGMS
X * Initial revision
X */
X
/* Define COMPILE_FOR_SKIPLIST_LIBRARY when making the library (so it
X   doesn't have the library call declarations), leave it undefined if
X   you are just using the library. */
X
X
#ifndef EXEC_TYPES_H
X  #include <exec/types.h>
#endif
X
#define SKIPLISTLEVELCAP 16
X  /* A skip list has at most this many levels of pointers in use.  List
X  nodes are also allocated with at most this many levels.  Some of the
X  levels aren't used even though they are allocated, until the list size
X  grows large enough.  This value is related to the number of bits in a
X  random number (for convenience 32 bits are generated per batch and we
X  need 2 bits per level, thus 16 levels).  This also means that the list
X  can hold 4^16 = 4294967296 entries before becoming inefficient.  If
X  you change this value, you'll need to recompile the library and make
X  sure that no programs written with the old value use your library
X  (the list header sizes would be wrong). */
X
X
#define RANDOMCACHESIZE 8
X  /* A cache of pseudo-random numbers is stored in each skip list and
X  used for generating the random sizes of new nodes.  Whenever the
X  cache is empty, it is refilled in one call to the random number
X  generator.  This is done because generating a single random number at
X  a time has some overhead (locking semaphores in Random250, library
X  function call overhead).  The tradeoff is that some memory is used
X  in each list. If you want to, you can define this to be 1 for
X  minimal memory use.  Use larger values if new node creation time is a
X  concern.  If you change this value, you'll need to recompile the
X  library and make sure that no programs written with the old value use
X  your library (the list header sizes would be wrong). */
X
X
#define SKIPLISTLIBRARYNAME "skiplist.library"
X  /* So you don't have to type in the name of this library.  Note that
X  all letters are lower case.  If you have a custom version of the
X  library, it would be a good idea to give it a different name here. */
X
X
/* This structure contains a node in a skip list.  It is a doubly
X   variable size record so don't try to allocate it yourself, use the
X   AllocateSkipNode function instead.  There is a variable size array of
X   pointers before the start of this record (number of entries specified
X   by the "nodeLevel" field), with the very last element in the array
X   overlapping with the "next" field.  The variable size user data
X   follows after this record in memory.  Normally the user's record
X   structure will have a SkipNodeRecord right at the front followed by
X   user specified fields. */
X
typedef struct SkipNodeStruct SkipNodeRecord, *SkipNodePointer,
**SkipNodePointerPointer;
X
struct SkipNodeStruct
{
X  SkipNodePointer next;
X    /* Points to the next node in the list.  You can use it for
X    iterating through the list, but don't change its value.  This is
X    also the last element in an array of pointers hidden before the
X    start of this record. */
X
X  union
X  {
X    struct
X    {
X      UBYTE nodeLevel;
X      UBYTE userSize [3];
X    } asBytes;
X
X    ULONG asLong;
X  } size;
X    /* This 4 byte value contains the size of the node, which is set
X    when the node is allocated and can't be changed.  The nodeLevel
X    field (first byte assuming it is running on a big-endien processor)
X    contains the number of pointer levels that this node has.  It is
X    generated by GenerateRandomLevelNumber().  The userSize field (the
X    next 3 bytes) contains the size of the user's record in bytes
X    (includes the size of the user visible part of the SkipNodeRecord),
X    thus allowing up to 16 megabytes of user data in a node.  The
X    actual size of the whole record including invisibles is:
X    (levels - 1) * sizeof (SkipNodePointer) + sizeof (UserRecord). */
X
X  /****** UserData ******* follows after this, though you don't see it
X  in this structure declaration.  It is long word (4 byte) aligned. */
};
X
X
X
/* This structure contains a skip list.  You need to allocate memory
X    for this structure and call the InitSkipList function before using
X    it.  The fields are read only unless otherwise noted.  It is not
X    multitasking safe - it won't work properly if you have two tasks
X    simultaneously trying to change the same list (OK for different
X    lists). */
X
typedef struct SkipListStruct
{
X  SkipNodePointer levelPointers [SKIPLISTLEVELCAP];
X    /* Points to the various levels of linked list.  The list of all the
X    nodes is at index SKIPLISTLEVELCAP-1.  The list with roughly every
X    4th node is at index SKIPLISTLEVELCAP-2, roughly every 16th is in
X    the list at SKIPLISTLEVELCAP-3 and so on.  This backwards array
X    indexing corresponds to the order in the array hidden before each
X    node record.  Users can iterate through all the nodes using
X    levelPointers [SKIPLISTLEVELCAP-1] to start, and the next pointers
X    in the SkipNodes to continue on. */
X
X  UBYTE activeLevels;
X    /* Current number of levels being used in this skip list.  Equals
X    one plus (integer portion of log base 4 of the list size).  Can
X    vary from 1 to SKIPLISTLEVELCAP.  Set to 1 for the special case of
X    an empty list (levelPointers [SKIPLISTLEVELCAP-1] will be NULL),
X    stays 1 when there are 1 to 3 nodes, 2 when there are 4 to 15
X    nodes, 3 for 16 to 63 nodes and so on.  Note that this field
X    comes just after the level pointer array, the same as in the node
X    record.  That way the code can treat the list header a bit like a
X    node.  See also nextSizeUp and nextSizeDown, which are tied to
X    this variable. */
X
X  UBYTE randomIndex;
X    /* Next available number to use from the randomCache array
X    field.  Counts down to zero, then refills the array and
X    resets to RANDOMCACHESIZE-1. */
X
X  UWORD filler;
X    /* Pads the fields so the following 32 bit values are aligned on a
X    4 byte boundary for better speed on 32 bit processors.  You can use
X    this field for your own data if you want to. */
X
X  ULONG size;
X    /* Number of nodes in this list.  We assume that it never
X    overflows, so don't try to add more than about four billion
X    nodes :-). */
X
X  ULONG nextSizeUp;
X    /* If the list size increases to this value just after adding a
X    node, activeLevels will be incremented and the new higher level of
X    pointers re-threaded and both nextSize fields recalculated.  It is
X    normally equal to 4^activeLevels. */
X
X  ULONG nextSizeDown;
X    /* If the list size equals this value just before deleting a node,
X    activeLevels will be decremented and thus the highest level of
X    pointers won't be used any more until the size goes up again.  Both
X    nextSize fields are updated when activeLevels changes.  It is
X    normally equal to 4^(activeLevels-1).  It doesn't have a useful
X    value when the list is empty. */
X
X  ULONG (*destroyUserData) (SkipNodePointer UserData);
X    /* A user provided (you can set this field) pointer to a cleanup
X    function.  This C style function (arguments on the stack, registers
X    A2-A6, D2-D7 preserved, result returned in D0) will be called
X    whenever a list node is going to be deallocated (not just removed).
X    Deallocations happen during insert over an existing node and in
X    calls to DeallocateSkipNode, DeleteSkipNode, DeleteAllSkipNodes,
X    but not RemoveSkipNode.  If you return zero then the memory used by
X    the node won't be deallocated, this is useful if you allocated the
X    memory using something other than AllocateSkipNode.  Returning
X    non-zero will deallocate the memory.  For future compatability,
X    please return a non-zero value of 1 to signal normal memory
X    deallocation, other values could be useful for other special cases
X    in the future.  You should also set the node's size.asLong field to
X    zero so that attempts to deallocate it twice can be detected by
X    DeallocateSkipNode.  If you allocated a resource of some sort (like
X    an open file) as part of your user data, you might want to
X    deallocate it in your destroyUserData function.  If you are using
X    C++, this would be a good place for a destructor function.  This
X    function is called after the destroyed node has been removed from
X    the list, so its next pointer will be meaningless.  The default
X    value of NULL means that no function call will be done and the
X    memory will be deallocated. */
X
X  LONG (*compareUserData) (SkipNodePointer A, SkipNodePointer B);
X    /* A user provided pointer to a comparison function.  You should
X    set this field after initialisation and before adding any nodes.
X    It is only safe to change it when the list is empty (otherwise your
X    list will get out of sorted order).  This C style function
X    (arguments on the stack, etc) will be called whenever a comparison
X    needs to be done between two nodes.  It should return a value less
X    than zero if A < B, zero if A = B, and greater than zero if A > B,
X    if you want the list to be in ascending order.  Return the opposite
X    sign for descending order.  If you want to have a list with nodes
X    that have the same sort key value, you can't (by design).  Instead,
X    fake it with a secondary comparison that you use when the keys are
X    equal (comparing node addresses works well).  The default value of
X    NULL means that the user data will be compared as if it is an
X    international string, using Strnicmp from utility.library with the
X    user data size as a limit to the string length (thus we need V37
X    (AmigaDOS 2.04) of the operating system for Strnicmp). */
X
X  ULONG randomCache [RANDOMCACHESIZE];
X    /* An array of previously computed pseudo-random numbers used for
X    extra speed when creating large numbers of new nodes.  RandomIndex
X    specifies the next one to be used. */
X
} SkipListRecord, *SkipListPointer;
X
X
X
#ifndef COMPILE_FOR_SKIPLIST_LIBRARY
/***********************************************************************
X * User's point of view library function declarations.
X */
X
extern APTR SkipListBase;
X  /* A global variable you have to declare somewhere and put the result
X  of OpenLibrary (SKIPLISTLIBRARYNAME, 0) into.  Otherwise the following
X  function calls will crash. */
X
X
#ifdef __GNUC__
/* This set of function declarations works for GNU C 2.7.0.  It isn't
as clean as native support for Amiga shared libraries, but it works and
generates efficient code. */
X
#ifndef LIBCALL_DECLARATION
X  #define LIBCALL_DECLARATION extern __inline
#endif
X  /* The declaration for library call functions in GNU C.  These ones
X  are declared external inline so they will only work if you compile in
X  optimised mode (where inlines work).  Otherwise, you may have to
X  remove the extern keyword to avoid missing function errors during
X  linking.  But then it may have other problems if more than one object
X  file included these declarations.  I normally compile in optimised
X  mode. */
X
X
LIBCALL_DECLARATION void InitSkipList (SkipListPointer TheList)
{
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-30)"
X  :                                 /* Outputs. */
X  : "r" (a6), "r" (a0)              /* Inputs. */
X  : "a0","a1","d0","d1", "memory"   /* Changed things. */);
}
/* This function initialises a skip list record (you provide a pointer
to an allocated SkipListRecord) to an empty list state.  It is always
successful.  Don't do it to an already initialised skip list, otherwise
you'll lose the memory that was allocated for its nodes.  You must call
this function before using the other skip list functions on that list.
Remember to set the function pointer fields (usually compareUserData
and maybe destroyUserData) immediately after calling this function. */
X
X
X
LIBCALL_DECLARATION SkipNodePointer AllocateSkipNode (SkipListPointer
TheList, ULONG UserRecordSize, ULONG MemoryFlags)
{
X  register SkipNodePointer _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register ULONG d0 __asm("d0") = UserRecordSize;
X  register ULONG d1 __asm("d1") = MemoryFlags;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-36)"
X  : "=r" (_res)                             /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (d0), "r" (d1)  /* Inputs. */
X  : "a0","a1","d0","d1", "memory");         /* Changed. */
X  return _res;
}
/* Allocate a new SkipNode record, returns a pointer to the record or
NULL if it fails.  The UserRecordSize is the size of your record
(structure in C talk), which includes a SkipNodeRecord at the very
front.  Maximum size is almost 16 megabytes.  The actual memory
allocated is a bit larger, for a randomly sized hidden array of
pointers before your record in memory.  TheList is an existing list
which is only used for its cache of random numbers (so it doesn't have
to be the same as the list the new SkipNode will be eventually added
to).  TheList can also be NULL, which makes it slightly slower.
MemoryFlags specify which kind of memory to allocate, see exec/memory.h
for the various types (or just use MEMF_ANY or 0 if you don't care).
Your new record will have its SkipNode fields initialised.  If you
include the MEMF_CLEAR flag then the user data area will be cleared to
zero. */
X
X
X
LIBCALL_DECLARATION void DeallocateSkipNode (SkipListPointer TheList,
SkipNodePointer TheNode)
{
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-42)"
X  :                                 /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
}
/* This function deallocates the memory used by a SkipNode.  If the
destroyUserData function in TheList is NULL or it returns non-zero
(preferably 1) when called, then the memory is deallocated (including
the hidden array before the SkipNode).  If destroyUserData returns
zero, no deallocation is done (useful for situations where you are
allocating memory in a nonstandard way). */
X
X
X
LIBCALL_DECLARATION SkipNodePointer InsertSkipNode (SkipListPointer
TheList, SkipNodePointer TheNode)
{
X  register SkipNodePointer _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-48)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Adds the given node to the given list.  If there is an existing node
with an equal value then it will be deleted (removed and deallocated)
before this one is added.  Presumably TheNode has been allocated by
AllocateSkipNode or an equivalent user function that has set the
nodeLevel and allocated a hidden array.  Returns the node prior to the
inserted node in the list, or NULL if the inserted one is the first in
the list (useful for implementing previous node pointers).  Always
succeeds (you've already allocated the memory for the node so there
isn't anything that normally can go wrong).  Don't insert a node that
is already in some other list, that would corrupt the other list badly.
X
If you have to have data simultaneously in several lists, you need to
have a SkipNodeRecord for each list.  An easy way is to create a bunch
of SkipNodeRecords with the user data portion just containing a pointer
to your actual data.  If you want to get tricky and do everything in
one record, you can create a variable sized user data record that
contains custom allocated SkipNodeRecords and their associated hidden
pointer arrays following it in memory.  You would also need a custom
destroyUserData function to avoid incorrect deallocations.  As well,
you would need to use GenerateRandomLevelNumber to generate random
sized SkipNodeRecords within your variable data record.  Alternatively
you can waste memory and have a fixed size record by using
SKIPLISTLEVELCAP for the hidden array size (but remember to still
specify a proper random level number in the nodeLevel fields). */
X
X
X
LIBCALL_DECLARATION SkipNodePointer RemoveSkipNode (SkipListPointer
TheList, SkipNodePointer TheNode)
{
X  register SkipNodePointer _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-54)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Removes a node with a value equal to TheNode's value from the list.
Returns the node it removed, or NULL if it couldn't find one matching
TheNode in value (equality as decided by your compareUserData
function).  Doesn't deallocate the node it removed.  TheNode doesn't
have to be a fully initialised node if your compareUserData function
doesn't use the SkipNodeRecord fields (the default comparison function
uses the size field, doesn't need the nodeLevel field or use the hidden
array before the record (thus you don't need to use AllocateSkipNode to
create a full SkipNode for comparison purposes). */
X
X
X
LIBCALL_DECLARATION ULONG DeleteSkipNode (SkipListPointer
TheList, SkipNodePointer TheNode)
{
X  register ULONG _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-60)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* This removes a node matching TheNode's value and then deallocates
it.  Returns non-zero if it actually removed anything, zero if it
couldn't find your node.  Does a RemoveSkipNode followed by
DeallocateSkipNode, so see those functions for details. */
X
X
X
LIBCALL_DECLARATION void DeleteAllSkipNodes (SkipListPointer TheList)
{
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-66)"
X  :                                 /* Outputs. */
X  : "r" (a6), "r" (a0)              /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
}
/* This function clears the list back to an empty list state, more
efficiently than using Delete on individual nodes.  All SkipNodes are
deallocated (see DeallocateSkipNode) and the list header is reset to an
empty list state. */
X
X
X
LIBCALL_DECLARATION SkipNodePointer FindSkipNode (SkipListPointer
TheList, SkipNodePointer TheNode)
{
X  register SkipNodePointer _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-72)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Finds a node with a value equal to TheNode's value from the list.
Returns the node it found, or NULL if it couldn't find it.  TheNode
doesn't have to be a fully initialised node (see RemoveSkipNode for
details). */
X
X
X
LIBCALL_DECLARATION SkipNodePointer FindBelowSkipNode
(SkipListPointer TheList, SkipNodePointer TheNode)
{
X  register SkipNodePointer _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-78)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Finds a node with the largest value less than TheNode's value in
TheList.  If it can't be found (no nodes less than TheNode) then it
returns NULL.  TheNode doesn't have to be a fully initialised node (see
RemoveSkipNode for details). */
X
X
X
LIBCALL_DECLARATION SkipNodePointer FindAboveOrEqualSkipNode
(SkipListPointer TheList, SkipNodePointer TheNode)
{
X  register SkipNodePointer _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-84)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Finds a node with the smallest value equal or greater than TheNode's
value in TheList.  If it can't be found (no nodes greater than or equal
to TheNode) then it returns NULL.  TheNode doesn't have to be a fully
initialised node (see RemoveSkipNode for details). */
X
X
X
LIBCALL_DECLARATION ULONG GenerateRandomLevelNumber (SkipListPointer
TheList)
{
X  register ULONG _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-90)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6), "r" (a0)              /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Returns a random number from 1 to SKIPLISTLEVELCAP.  There's a 3/4
chance of getting 1 returned, 3/16 of getting 2, and in general 3/(4^n)
of getting n.  Uses the cached random numbers in the list.  If TheList
is NULL then it will call the random number generator directly. */
X
X
X
LIBCALL_DECLARATION ULONG GetRANDOMCACHESIZE (void)
{
X  register ULONG _res __asm("d0");
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-96)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6)                        /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Returns the value of RANDOMCACHESIZE used by the library. */
X
X
X
LIBCALL_DECLARATION ULONG GetSKIPLISTLEVELCAP (void)
{
X  register ULONG _res __asm("d0");
X  register APTR a6 __asm("a6") = SkipListBase;
X  __asm __volatile ("jsr a6@(-102)"
X  : "=r" (_res)                     /* Outputs. */
X  : "r" (a6)                        /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
X  return _res;
}
/* Returns the value of SKIPLISTLEVELCAP used by the library. */
X
#endif /* ifdef __GNUC__ */
X
/* Put other compiler's library declarations here, with the appropriate #ifdef
X   for that compiler around them.  Please send me a copy if you do, so that I
X   can update the main version on AmiNet. */
X
#endif /* ifndef COMPILE_FOR_SKIPLIST_LIBRARY */
#endif /* ifndef SKIPLIST_H */
SHAR_EOF
chmod 0600 SkipListLib/Source/SkipList.h ||
echo 'restore of SkipListLib/Source/SkipList.h failed'
Wc_c="`wc -c < 'SkipListLib/Source/SkipList.h'`"
test 23923 -eq "$Wc_c" ||
	echo 'SkipListLib/Source/SkipList.h: original size 23923, current size' "$Wc_c"
rm -f _shar_wnt_.tmp
fi
rm -f _shar_seq_.tmp
echo You have unpacked the last part
exit 0
-- 
Bill Zimmer - zim@ibx.com


