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

#!/bin/sh
# this is src.02 (part 2 of libs/SkipListLib-1.0)
# do not concatenate these parts, unpack them in order with /bin/sh
# file SkipListLib/Examples/WordCounter.c continued
#
if test ! -r _shar_seq_.tmp; then
	echo 'Please unpack part 1 first!'
	exit 1
fi
(read Scheck
 if test "$Scheck" != 2; 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/Examples/WordCounter.c'
else
echo 'x - continuing file SkipListLib/Examples/WordCounter.c'
sed 's/^X//' << 'SHAR_EOF' >> 'SkipListLib/Examples/WordCounter.c' &&
X * name, it counts the number of different words in the file and shows how
X * many times each word is used.  Features an unlimited number of words
X * (except by free memory) and probabalisticly optimal counting.
X *
X * $Header: Big:Programming/C/SkipLists/RCS/WordCounter.c,v 1.2 1996/08/29 14:20:10 AGMS Exp $
X *
X * By Alexander G. M. Smith, agmsmith@achilles.net, July 1996.
X * Compiled with GNU C version 2.7.0, command line:
X *   gcc -v -noixemul -O2 -Wall WordCounter.c
X *
X * $Log: WordCounter.c,v $
X * Revision 1.2  1996/08/29  14:20:10  AGMS
X * Added sorted list of counts, showing how you can have a list with
X * duplicate key values by using a subkey.
X *
X * Revision 1.1  1996/08/19  17:45:38  AGMS
X * Initial revision
X */
X
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <proto/exec.h>
#include "SkipList.h"
X
APTR SkipListBase;
X
X
/* This structure is used in a list of all the words, in sorted order by word.
X   Each one also has a counter for the number of times the word has been found
X   in the input text. */
X
typedef struct WordCountStruct
{
X  SkipNodeRecord  skipNode; /* Links skip nodes, must be at front of record. */
X  ULONG count;   /* Number of times this word occurs in the input file. */
X  char word [1]; /* A variable sized string, record size extended to fit. */
} WordCountRecord, *WordCountPointer;
X
X
X
/* This structure is used in a list of counts, with lower counts coming
X   first.  For the cases with identical counts, the alphabetical order of the
X   word being counted is used to determine the sub-order. */
X
typedef struct SortByCountStruct
{
X  SkipNodeRecord  skipNode;  /* Links skip nodes, must be at front of record. */
X  WordCountPointer wordPntr; /* Points to the word and count to use. */
} SortByCountRecord, *SortByCountPointer;
X
X
X
/******************************************************************************
X * This is a callback function that the skip list routines use to compare two
X * nodes in the sorted-by-word list.  Returns negative if word A < word B,
X * zero for A==B, and larger than zero for A>B.
X */
X
LONG CompareWordCountRecords (SkipNodePointer A, SkipNodePointer B)
{
X  WordCountPointer WordA, WordB;
X
X  WordA = (WordCountPointer) A;
X  WordB = (WordCountPointer) B;
X
X  return strcmp (WordA->word, WordB->word);
}
X
X
X
/******************************************************************************
X * This is a different callback function that the skip list routines use to
X * compare two nodes in the sorted-by-count list.  Returns negative if the
X * count of word A < count of word B, zero for A==B, and larger than zero for
X * A>B.  If two entries have the same count, the alphabetical order of the
X * associated words is used to break the tie.
X */
X
LONG CompareSortByCountRecords (SkipNodePointer A, SkipNodePointer B)
{
X  SortByCountPointer SortA, SortB;
X  long  CountDelta;
X
X  SortA = (SortByCountPointer) A;
X  SortB = (SortByCountPointer) B;
X
X  CountDelta = SortA->wordPntr->count - SortB->wordPntr->count;
X
X  if (CountDelta != 0)
X    return CountDelta;
X
X  return strcmp (SortA->wordPntr->word, SortB->wordPntr->word);
}
X
X
X
/******************************************************************************
X * Go through the input file parsing words and storing them in the given list.
X * Stops at end of file or when an IO error happens or when it runs out of
X * memory.
X */
X
void CountWords (SkipListPointer WordList, FILE *InputFile)
{
X  WordCountPointer  ExistingWordNode;
X  int               Letter;
X  WordCountPointer  NewWordNode;
X  int               WordSize;
X
X  /* Create a search node record on the stack, with space for the longest
X     possible word.  Also make a constant pointer to the Word string for easy
X     access. */
X
X  const int MAXWORDLENGTH = 511;
X  struct
X  {
X    WordCountRecord countRecord;
X    char spaceHolder [MAXWORDLENGTH];
X  } SearchNode;
X  char * const Word = SearchNode.countRecord.word;
X
X  while (TRUE)
X  {
X    /* Read a word.  Skip over nonalphabetic characters, read alphabetic
X       characters and stop when first nonalpha is hit. */
X
X    WordSize = 0;
X
X    while ((Letter = getc (InputFile)) != EOF && !ferror (InputFile))
X    {
X      Letter = tolower (Letter);
X      if (isalpha (Letter))
X      {
X        if (WordSize < MAXWORDLENGTH)
X          Word [WordSize++] = Letter;
X      }
X      else
X      {
X        /* Nonalphabetic, treat as word separators.  Skip over if no word yet,
X           stop if there is a word. */
X
X        if (WordSize > 0)
X          break; /* This one signals end of the word. */
X      }
X    }
X
X    if (WordSize == 0)
X      return; /* Must have hit end of file, or an error. */
X
X    Word [WordSize] = 0; /* End of string marker. */
X
X    /* Is that word already in the list? */
X
X    ExistingWordNode = (WordCountPointer) FindSkipNode (WordList,
X    &SearchNode.countRecord.skipNode);
X
X    if (ExistingWordNode != NULL)
X      ExistingWordNode->count++;
X    else
X    {
X      /* Allocate a list node with extra space past the end for the word
X         string.  Note that the WordCountRecord already includes 1 character
X         for the string size, which accounts for the NUL character at the end
X         of the string. */
X
X      NewWordNode = (WordCountPointer) AllocateSkipNode (WordList,
X      sizeof (WordCountRecord) + WordSize, 0 /* Any memory type */);
X
X      if (NewWordNode == NULL)
X      {
X        fprintf (stderr, "Ran out of memory while adding words.\n");
X        return;
X      }
X
X      strcpy (NewWordNode->word, Word);
X      NewWordNode->count = 1;
X
X      InsertSkipNode (WordList, &NewWordNode->skipNode);
X    }
X  }
}
X
X
X
/******************************************************************************
X * Make a shadow list that has an entry for every word, except that the
X * entries are sorted by count, not word.
X */
X
void SortCounts (SkipListPointer WordList, SkipListPointer CountList)
{
X  SortByCountPointer  CountNode;
X  WordCountPointer    WordNode;
X
X  WordNode = (WordCountPointer) WordList->levelPointers [SKIPLISTLEVELCAP-1];
X
X  while (WordNode != NULL)
X  {
X    CountNode = (SortByCountPointer) AllocateSkipNode (CountList,
X    sizeof (SortByCountRecord), 0 /* Any memory type */);
X
X    if (CountNode == NULL)
X    {
X      fprintf (stderr, "Ran out of memory while sorting counts.\n");
X      return;
X    }
X
X    CountNode->wordPntr = WordNode;
X
X    InsertSkipNode (CountList, &CountNode->skipNode);
X
X    WordNode = (WordCountPointer) WordNode->skipNode.next;
X  }
}
X
X
X
/******************************************************************************
X * Print the list of words and their counts.  Also print the list of
X * sorted-by-counts words in a second column.
X */
X
void PrintWordsAndCounts (SkipListPointer WordList, SkipListPointer CountList)
{
X  WordCountPointer WordNode;
X  SortByCountPointer CountNode;
X
X  WordNode = (WordCountPointer) WordList->levelPointers [SKIPLISTLEVELCAP-1];
X  CountNode = (SortByCountPointer) CountList->levelPointers [SKIPLISTLEVELCAP-1];
X
X  printf ("Sorted by Word                         Sorted by Count\n");
X  printf ("=====================================  =====================================\n");
X
X  while (WordNode != NULL && CountNode != NULL)
X  {
X    printf ("%-32s %4ld  %-32s %4ld\n", WordNode->word, WordNode->count,
X    CountNode->wordPntr->word, CountNode->wordPntr->count);
X
X    WordNode = (WordCountPointer) WordNode->skipNode.next;
X    CountNode = (SortByCountPointer) CountNode->skipNode.next;
X  }
}
X
X
X
int main (int argc, char *argv[])
{
X  SkipListRecord CountList;
X  FILE *InputFile;
X  BOOL Success;
X  SkipListRecord WordList;
X
X  InputFile = NULL;
X  Success = TRUE;
X
X  SkipListBase = OpenLibrary (SKIPLISTLIBRARYNAME, 0 /* version */);
X  if (SkipListBase == NULL)
X  {
X    Success = FALSE;
X    fprintf (stderr, "Unable to open " SKIPLISTLIBRARYNAME "\n");
X  }
X
X  if (Success)
X  {
X    if (argc >= 2)
X    {
X      fprintf (stderr,
X      "Opening file \"%s\" for input text to be word counted.\n", argv[1]);
X
X      InputFile = fopen (argv[1], "r");
X
X      if (InputFile == NULL)
X      {
X        Success = FALSE;
X        fprintf (stderr, "Unable to open input file!\n");
X      }
X    }
X    else /* No file name. */
X    {
X      Success = FALSE;
X      fprintf (stderr, "Usage: %s filename\n"
X      "Counts the number of times each word appears in the file.\n"
X      "By Alexander G. M. Smith, 1996.  Public Domain.\n",
X      argv[0]);
X    }
X  }
X
X  if (Success)
X  {
X    InitSkipList (&WordList);
X    WordList.compareUserData = CompareWordCountRecords;
X
X    CountWords (&WordList, InputFile);
X
X    InitSkipList (&CountList);
X    CountList.compareUserData = CompareSortByCountRecords;
X
X    SortCounts (&WordList, &CountList);
X
X    PrintWordsAndCounts (&WordList, &CountList);
X
X    fprintf (stderr, "Please wait, deallocating count list...\n");
X    DeleteAllSkipNodes (&CountList);
X
X    fprintf (stderr, "Please wait, deallocating word list...\n");
X    DeleteAllSkipNodes (&WordList);
X  }
X
X  if (InputFile != NULL)
X    fclose (InputFile);
X
X  if (SkipListBase != NULL)
X    CloseLibrary (SkipListBase);
}
SHAR_EOF
echo 'File SkipListLib/Examples/WordCounter.c is complete' &&
chmod 0600 SkipListLib/Examples/WordCounter.c ||
echo 'restore of SkipListLib/Examples/WordCounter.c failed'
Wc_c="`wc -c < 'SkipListLib/Examples/WordCounter.c'`"
test 9107 -eq "$Wc_c" ||
	echo 'SkipListLib/Examples/WordCounter.c: original size 9107, current size' "$Wc_c"
rm -f _shar_wnt_.tmp
fi
# ============= SkipListLib/Libs/random250.library ==============
if test ! -d 'SkipListLib/Libs'; then
    echo 'x - creating directory SkipListLib/Libs'
    mkdir 'SkipListLib/Libs'
fi
if test -f 'SkipListLib/Libs/random250.library' -a X"$1" != X"-c"; then
	echo 'x - skipping SkipListLib/Libs/random250.library (File already exists)'
	rm -f _shar_wnt_.tmp
else
> _shar_wnt_.tmp
echo 'x - extracting SkipListLib/Libs/random250.library (Binary)'
sed 's/^X//' << 'SHAR_EOF' > _shar_tmp_.tmp &&
begin 600 SkipListLib/Libs/random250.library
M```#\P`````````!``````````````$?```#Z0```1]P_TYU2OP````$```$
M>H`!"0`````>````,````9AR86YD;VTR-3`N;&EB<F%R>0!R86YD;VTR-3`@
M,2XP("@Q-BXV+CDV*0T*`"1615(Z(')A;F1O;3(U,"`Q+C`@*#$V+C8N,3DY
M-BD@*&)Y($%L97AA;F1E<B!'+B!-+B!3;6ET:"D`"@HD260Z(%)A;F1O;3(U
M,"YA<VTL=B`Q+C$Q(#$Y.38O,#8O,S`@,38Z-3(Z-38@04=-4R!%>'`@)`I0
M=6)L:6,@9&]M86EN(#$Y.38@8GD@06QE>&%N9&5R($<N($TN(%-M:71H+"!A
M;&P@<FEG:'1S('5N<F5S97)V960N"E-E;F0@<75E<W1I;VYS('1O(&%G;7-M
M:71H0&%C:&EL;&5S+FYE="P@86=M<VUI=&A`8FEX+F-O;2P*874X,CE`9G)E
M96YE="YC87)L971O;BYC82!A;F0@-S$S,S`N,S$W,T!#;VUP=5-E<G9E+F-O
M;0H*`&5X96,N;&EB<F%R>0!I;G1U:71I;VXN;&EB<F%R>0````1,```!J```
M`<0```)$```#<@```X````.:```#R````\P```/Z_____Z`("0"`"@```!Z@
M#@8`D!0``9`6``"`&````#`````````````0``\````````"#```````````
M``8``P````````(]`````%)A;F1O;3(U,"YL:6)R87)Y(')E<75I<F5S($%M
M:6=A1$]3('8R+C`K("A6,S8K*0!#86YC96P`2.<_/BI`*T@`(D/Z_S9P`$ZN
M_=@K0``J9P``V$/Z_Q=P)$ZN_=@K0``F9BAP`"!`0_K_;B1`1_K_?"(`)#P`
M``%`=D@H3BQM`"I.KOZD+$Q@``"@+$!![0`N3J[]TB!M`"8P/`"90^T`7"M)
M!$@B&.&Y(L%1R/_X</\BP.*(9OI!^OTZ<#<B&.&Y(L%1R/_X0>D`!"1)+&T`
M*DZN_ZQ#Z@`((!KAF"+`X9@BP.&8(L`@&N&8(L#AF"+`X9@BP#`\`/E![0!<
M0^@!G#(\`)(D&;684<G_^D/M`%PR/`!F)!FUF%')__I1R/_:(`U,WWS\3G5A
M"$S??/QP`$YU("T`*F<*(D!.KOYB0JT`*B`M`"9G"B)`3J[^8D*M`"9P`")-
M,"T`$)/`T&T`$D[N_RY2;@`@"*X``P`.(`Y.=3`N`"!G!E-`/4``(&8(""X`
M`P`.9@1P`$YU2FX`(&<*".X``P`.<`!.=4CG(`8J3BQM`"8D+0`B(DU.KO\$
M88`@`DS?8`1.=7``3G4B3BQI`"9!Z0`N3J[]S"Q)0>X$1'`!818@+@1$(DXL
M:0`F0>D`+DZN_<8L24YU2.<@/B1()``J3BQM`"9![0`N3J[]S$/M!$1![0!<
M)FT$2$GK`9RYR64>F/P#Z"()DHODB;*"8C*4@6`&(!RQDR3;4<G_^"9((@F2
MC.2)LH)B&)2!8`8@'+&3)-M1R?_X*$A@RB`<L9,DVU'*__@K2P1(0>T`+DZN
M_<9,WWP$3G5.<0```^P````2``````````8````*````$@```!8````:```!
MG````:````&D```!J````:P```&P```!M````;@```&\```!R@```=P```'P
,```"!`````````/R
`
end
SHAR_EOF
echo 'uudecoding file SkipListLib/Libs/random250.library' &&
uudecode < _shar_tmp_.tmp && rm -f _shar_tmp_.tmp &&
chmod 0600 SkipListLib/Libs/random250.library ||
echo 'restore of SkipListLib/Libs/random250.library failed'
Wc_c="`wc -c < 'SkipListLib/Libs/random250.library'`"
test 1272 -eq "$Wc_c" ||
	echo 'SkipListLib/Libs/random250.library: original size 1272, current size' "$Wc_c"
rm -f _shar_wnt_.tmp
fi
# ============= SkipListLib/Libs/skiplist.library ==============
if test -f 'SkipListLib/Libs/skiplist.library' -a X"$1" != X"-c"; then
	echo 'x - skipping SkipListLib/Libs/skiplist.library (File already exists)'
	rm -f _shar_wnt_.tmp
else
> _shar_wnt_.tmp
echo 'x - extracting SkipListLib/Libs/skiplist.library (Binary)'
sed 's/^X//' << 'SHAR_EOF' > _shar_tmp_.tmp &&
begin 600 SkipListLib/Libs/skiplist.library
M```#\P`````````!``````````````1P```#Z0``!'!P_TYU3G%S:VEP;&ES
M="YL:6)R87)Y`'-K:7!L:7-T(#$N,"`H075G(#(Y(#$Y.38I("A$96)U9RD@
M*%9E<F)O<V4I("A">2!!1TU3;6ET:"D-"@`*"B1)9#H@4VMI<$QI<W0N8RQV
M(#$N-B`Q.3DV+S`X+S$Y(#$U.C`X.C$U($%'35,@17AP("0*4'5B;&EC(&1O
M;6%I;B`Q.3DV(&)Y($%L97AA;F1E<B!'+B!-+B!3;6ET:"P@86QL(')I9VAT
M<R!U;G)E<V5R=F5D+@I!;&=O<FET:&T@8GD@5VEL;&EA;2!0=6=H(&%T('1H
M92!5;FEV97)S:71Y(&]F($UA<GEL86YD(%5302X*4V5N9"!Q=65S=&EO;G,@
M=&\@86=M<VUI=&A`86-H:6QL97,N;F5T+"!A9VUS;6ET:$!B:7@N8V]M+`IA
M=3@R.4!F<F5E;F5T+F-A<FQE=&]N+F-A(&%N9"`W,3,S,"XS,3<S0$-O;7!U
M4V5R=F4N8V]M"@H`4V]R<GDL('-K:7!L:7-T+FQI8G)A<GD@8V%N)W0@;W!E
M;B!R86YD;VTR-3`N;&EB<F%R>0```0$```8`!0````````&!`````%-O<G)Y
M+"!S:VEP;&ES="YL:6)R87)Y(&-A;B=T(&]P96X@=71I;&ET>2YL:6)R87)Y
M(%8S-P````$!```&``4````````!R@````!#86YC96P````!`0``!@`#````
M`````A8`````3TL````!`0``!@`#`````````C(````````$+```!#X```1@
M```$E```!9@```94```'3@``"A0```O6```,\@``#:P```Z6```/P@``$,@`
M`!%:```1L@``$;C_____````.````DH````````#9DK\```"H@``$;Z``0D`
M````!@```!<```*2+PXO"B1O``PL>``$("H`*F<*(D!.KOYB0JH`*B`J`"YG
M"B)`3J[^8D*J`"X@*@`R9PHB0$ZN_F)"J@`R("H`)F<*(D!.KOYB0JH`)D*`
M,"H`$$*!,BH`$B)*D\#0@4ZN_RXD7RQ?3G5I;G1U:71I;VXN;&EB<F%R>0!U
M=&EL:71Y+FQI8G)A<GD`<F%N9&]M,C4P+FQI8G)A<GD`97AE8RYL:6)R87)Y
M``!(YS`Z*$`I2``B&7P`"0`(*7P````&``H9?``&``XY?``!`!1";``6*7P`
M```7`!@Y?``!`#8D#D/Y```#)'``3J[]V"E``"IG7$/Y```#-G`E3J[]V"E`
M`#)G5D/Y```#1G``3J[]V"E``"YG%D/Y```#6'``3J[]V"E``"9G)B`,8#PL
M;``J($!#^0```;:5RD?Y```"'G(`)#P```(`=CQ.KOZD+PQA`/ZL<`!83V`.
M+&P`*B!`0_D```("8-!,WUP,3G4O#E)N`"`"+@#W``X@#BQ?3G4O#C`N`"!G
M"%-`/4``(&8,""X``P`.9P1A"&`"<``L7TYU2.<@(B1.2FH`(&8:)"H`(BQJ
M`"8B2DZN_P0O"F$`_CX@`EA/8`@`*@`(``YP`$S?1`1.=7``3G5.<4-O;G1I
M;G5E('-H;W=I;F<@<VMI<&QI<W0N;&EB<F%R>2!E<G)O<B!M97-S86=E<S\`
MWOS_U$CG.#HH+P!0*$1*;``V9P``C$(O`#`??``!`#$??``!`#(_?``&`#0_
M?``%`#9"KP`X+V\`3``\2>\`'"],`$!"+P`<'WP``0`='WP``0`>/WP`!@`@
M/WP`$0`B0J\`)"]\```$F@`H0J\`+"A$+&P`*I'(0^\`,$7Y```"-D?Y```"
M'G``<@`D/````@!V4$ZN_J1*0&8$.4``-DS?7!S>_``L3G54:&5,:7-T(&ES
M($Y53$P@:6X@26YI=%-K:7!,:7-T+@``2.<@(B1.L/P``&80+PY(>0``!79A
M`/\>4$]@2'`/0^@`/$*164E1R/_Z0D!3@&3R$7P``0!`0F@`0D*H`$1T!"%"
M`$A"J`!,0J@`4$*H`%01?``'`$$L:@`N<`C0_`!83J[_W$S?1`1.=55S97)2
M96-O<F13:7IE(&ES(&)A9"!I;B!!;&QO8V%T95-K:7!.;V1E+@!286X@;W5T
M(&]F(&UE;6]R>2!I;B!!;&QO8V%T95-K:7!.;V1E+@!(YS@Z)`@F0"8!)$Y!
MZ__XL?P`___W8PHO#DAY```&`F`L($(L2DZN_Z8D`.6`+&H`)DGS"/P@#"(#
M3J[_.B!`L/P``&82+PI(>0``!BUA`/XH<`!03V`L(`+E@$/P"/P@27``M(!O
M"D*064A2@+2`;O8@`N%`2$!"0"@+B(`C1``$(`E,WUP<3G5.54Q,(%1H94QI
M<W0@;W(@5&AE3F]D92!I;B!$96%L;&]C871E4VMI<$YO9&4N`%1H94YO9&4@
M:7,@8V]R<G5P="`H86QR96%D>2!D96%L;&]C871E9#\I(&EN($1E86QL;V-A
M=&53:VEP3F]D92X`2.<\.B1))DZP_```9P:R_```9@HO#DAY```&WF`H*"H`
M!`*$`/___T*"%"H`!"8"4X-Z#[J#909Z![J$91`O#DAY```'#6$`_3903V`T
M(&@`4+#\``!G"B\)3I!83TJ`9R!"J@`$(@/E@2`"Y8`L:P`F(DJ3P2A`2?1(
M_"`,3J[_+DS?7#Q.=2\.(&\`"")O``PL;P`0(#P`____(B@`!,*`P*D`!+*`
M;P(B`$J!;@1P`&`.+&X`,E!(4$D@`4ZN_U@L7TYU0V]R<G5P="!L:7-T(&AE
M861E<B!I;B!5<&1A=&5,:7-T06-T:79E3&5V96QS+@!-87AI;75M(&QE=F5L
M(')E86-H960@*&QI<W0@=VEL;"!B92!I;F5F9FEC:65N="D@:6X@57!D871E
M3&ES=$%C=&EV94QE=F5L<RX`0G5G/R`@5V%N="!T;R!G;R!U<"!M;W)E('1H
M86X@;VYE(&QE=F5L(&EN(%5P9&%T94QI<W1!8W1I=F5,979E;',N`$CG/"`D
M;P`8*"\`'$*#%BH`0"`#4X!Z#[J`9!(O!$AY```(%&$`^]103V```+IR`"`J
M`$1G!E*!Y(AF^DJ!;@)R`7H0NH%L$"\$2'D```A#80#[J'(04$\D`U*"M(%L
M$"\$2'D```B/80#[D"("4$^T@69$<!"0@>6`0_((`'`0D(/E@"!R"`"P_```
M9RAT`"`!Y8`H`%F$(`-$@.6`%"@`!+*";@8BB")(D\0@<`@$L/P``&;H0I$5
M00!`(`'0@70!*@+AI2`%9@)P_R5``$@@`5.`T(#AHB`">@&Z@&8"<``E0`!,
M3-\$/$YU3E5,3"!4:&5,:7-T(&]R(%1H94YO9&4@:6X@26YS97)T4VMI<$YO
M9&4N`$-O<G)U<'0@5&AE3&ES="!H96%D97(@:6X@26YS97)T4VMI<$YO9&4N
M``#>_/^\2.<X.B9(*`DF#K;\``!G!K+\``!F"B\.2'D```F^8!00*P!`9P8,
M```08Q0O#DAY```)Z6$`^GYP`%!/8``!($7K`#P"@````/_E@#0`1$)J/EA"
M+'(@`+S\``!G*B!K`%2P_```9A`O`R\$+PYA`/U.WOP`#&`(+P0O#DZ04$]*
M@&P$)$Y@S"^*(%A*0FW")%*T_```9V0@:P!4L/P``&80+P,O!"\*80#]%-[\
M``Q@""\$+PI.D%!/2H!F/A`J``02*P!`L`%C`A`!`H````#_Y8`T`$1":A)8
M0C!"(G#X6"&PJ`"8`$I";>Y3JP!$0I(@2R)*+$-.KO_6*$00+``$$BL`0+`!
M8P(0`0*`````_^6`-`!$0FH66$(P0B)P^%@AL)@`2``AA)@`2D)MZB!K`$1)
MZ``!)TP`1%)(L>L`2&4*+P,O"V$`_7!03R)O`%A!ZP`\<`"QR6<"(`E,WUP<
MWOP`1$YU3E5,3"!4:&5,:7-T(&]R(%1H94YO9&4@:6X@4F5M;W9E4VMI<$YO
M9&4N`$-O<G)U<'0@5&AE3&ES="!H96%D97(@:6X@4F5M;W9E4VMI<$YO9&4N
M``#>_/^\2.<\.B9()@DH#K;\``!G!K+\``!F"B\.2'D```N`8!00*P!`9P8,
M```08Q0O#DAY```+JV$`^+QP`%!/8```T$7K`#P"@````/_E@$1`/$!J.EA.
M)#+@`&<J(&L`5+#\``!F$"\$+P,O`F$`^Y#>_``,8`@O`R\"3I!03TJ`;`0D
M0F#0+XK@7#H.;<8D4K3\``!G>"!K`%2P_```9A`O!"\#+PIA`/M6WOP`#&`(
M+P,O"DZ04$]*@&90$"H`!!(K`$"P`6,"$`$"@````/_E@$1`/$!J$EA.,$XB
M</A<(;"H`)@`.@YM[B!K`$1)Z/__)TP`1%-(L>L`3&0*+P0O"V$`^_903T*2
M8`*5RB`*3-]</-[\`$1.=4CG.`(D""8.3J[_RB@`9P@@0B)`3J[_UDJ$5L!(
M@#!`(`A$@$S?0!Q.=4Y53$P@5&AE3&ES="!I;B!$96QE=&5!;&Q3:VEP3F]D
M97,N`$-O<G)U<'0@5&AE3&ES="!H96%D97(@:6X@1&5L971E06QL4VMI<$YO
M9&5S+@!4:&5,:7-T+3YS:7IE(&1O97-N)W0@;6%T8V@@;F]D92!C;W5N="!I
M;B!$96QE=&5!;&Q3:VEP3F]D97,N`$CG.#(F2"8.MOP``&8*+PY(>0``#1Q@
M%!`K`$!G!@P``!!C$"\.2'D```U`80#V\E!/8%XD:P`\=`"T_```9Q8B2B12
M4H)"D2!++$-.KO_6M/P``&;JM*L`1&<.+P-(>0``#6YA`/:Z4$]P#T'K`#Q"
MD%E(4<C_^D)`4X!D\A=\``$`0$*K`$1X!"=$`$A"JP!,3-],'$YU3E5,3"!4
M:&5,:7-T(&]R(%1H94YO9&4@:6X@1FEN9%-K:7!.;V1E+@!#;W)R=7!T(%1H
M94QI<W0@:&5A9&5R(&EN($9I;F13:VEP3F]D92X``$CG.#HH2"0))@ZX_```
M9P:R_```9@HO#DAY```.1&`4$"P`0&<&#```$&,4+PY(>0``#FUA`/8`<`!0
M3V```(Q'[``\`H````#_Y8!$0#1`:CY82BQSH`"\_```9RX@;`!4L/P``&82
M+P,O`B\.80#XT"(`WOP`#&`*+P(O#DZ0(@!03TJ!;`0F3F#(.`IMPB93MOP`
M`&8$<`!@+B!L`%2P_```9A(O`R\"+PMA`/B2(@#>_``,8`HO`B\+3I`B`%!/
M(`M*@6<"<`!,WUP<3G5.54Q,(%1H94QI<W0@;W(@5&AE3F]D92!I;B!&:6YD
M0F5L;W=3:VEP3F]D92X`0V]R<G5P="!4:&5,:7-T(&AE861E<B!I;B!&:6YD
M0F5L;W=3:VEP3F]D92X``$CG,#HH2"0))@ZX_```9P:R_```9@HO#DAY```/
M9F`4$"P`0&<&#```$&,2+PY(>0``#Y1A`/34<`!03V!81^P`/`*`````_^6`
M1$`T0&HZ6$HL<Z``O/P``&<J(&P`5+#\``!F$"\#+P(O#F$`]Z;>_``,8`@O
M`B\.3I!03TJ`;`0F3F#,,@IMQD'L`#QP`+'+9P(@"TS?7`Q.=4Y53$P@5&AE
M3&ES="!O<B!4:&5.;V1E(&EN($9I;F1!8F]V94]R17%U86Q3:VEP3F]D92X`
M0V]R<G5P="!4:&5,:7-T(&AE861E<B!I;B!&:6YD06)O=F5/<D5Q=6%L4VMI
M<$YO9&4N``!(YS`Z*$@D"28.N/P``&<&LOP``&8*+PY(>0``$%Y@%!`L`$!G
M!@P``!!C$B\.2'D``!"380#SSG``4$]@3D?L`#P"@````/_E@$1`-$!J.EA*
M+'.@`+S\``!G*B!L`%2P_```9A`O`R\"+PYA`/:@WOP`#&`(+P(O#DZ04$]*
M@&P$)DY@S#(*;<8@$TS?7`Q.=4CG,"(D2+3\``!F#"QN`"Y.KO_B)`!@)D*!
M$BH`02`!Y8`D,@A84X%J$"QN`"YP"$'J`%A.KO_<<@<500!!<@%P`\""9@KD
MBE*!=@^V@6SP(`%,WT0,3G5P"$YU3G%P$$YU3G%.=0```^P````]````````
M`<(```(.```"*@```D(```)*```"3@```E(```)6```"6@```EX```)B```"
M9@```FH```)N```"<@```G8```)Z```"?@```H(```*&```"B@```I8```*>
M```"I````J@```*P```"M````K@```-X```#D````Z````.R```#Q````]8`
M``/R```#^@``!"````4R```%2@``!5````6H```&<```!IX```=F```'D```
M"/(```D>```)-@``"C(```I(```+]```#`H```V^```-U```#@P```ZP```.
MQ@``#]P```_R```0X@``$/@````````#\`````5?7U]G;G5?8V]M<&EL961?
M8P`````````````$7T1U;6UY4W1A<G1U<``````````````#7TQI8G)A<GE.
M86UE````!@````-?3&EB<F%R>4E$```````7````!%]!=71H;W)3=')I;F<`
M``````!4````!5]-:7-S:6YG4C(U,%-T<FEN9P`````!@0````5?36ES<VEN
M9U(R-3!)5&5X=````````;8````&7TUI<W-I;F=5=&EL:71Y4W1R:6YG````
M```!R@````5?36ES<VEN9U5T:6QI='E)5&5X=````@(````$7T-A;F-E;%-T
M<FEN9P```````A8````#7T-A;F-E;$E497AT```"'@````-?3TM3=')I;F<`
M``````(R`````E]/2TE497AT```"-@````9?3&EB<F%R>49U;F-T:6]N<TQI
M<W0```````)*````!5],:6)R87)Y26YI=%1A8FQE```````"D@````1?4VMI
M<$QI<W123TU486<````"H@````1?1&5A;&QO8V%T95-T=69F```"O`````=?
M26YI=&EA;&ES95-K:7!,:7-T3&EB<F%R>0`````#9@````5?3W!E;E-K:7!,
M:7-T3&EB<F%R>0``!"P````&7T-L;W-E4VMI<$QI<W1,:6)R87)Y```````$
M/@````9?17AP=6YG95-K:7!,:7-T3&EB<F%R>0````1@````!5]297-E<G9E
M9$9U;F-T:6]N```````$E`````5?1&ES<&QA>45R<F]R365S<V%G90``!,P`
M```$7TEN:713:VEP3&ES=```````!9@````%7T%L;&]C871E4VMI<$YO9&4`
M``````94````!5]$96%L;&]C871E4VMI<$YO9&4````'3@````9?0V]M<&%R
M94YO9&5S07-3=')I;F=S``````?6````!E]5<&1A=&5,:7-T06-T:79E3&5V
M96QS````"-(````$7TEN<V5R=%-K:7!.;V1E````"A0````$7U)E;6]V95-K
M:7!.;V1E````"]8````$7T1E;&5T95-K:7!.;V1E````#/(````%7T1E;&5T
M94%L;%-K:7!.;V1E<P````VL````!%]&:6YD4VMI<$YO9&4```````Z6````
M!5]&:6YD0F5L;W=3:VEP3F]D90`````/P@````=?1FEN9$%B;W9E3W)%<75A
M;%-K:7!.;V1E```````0R`````=?1V5N97)A=&5286YD;VU,979E;$YU;6)E
M<@`````16@````5?1V5T4D%.1$]-0T%#2$5325I%````$;(````%7T=E=%-+
M25!,25-43$5614Q#05```!&X`````U]%;F1/9D-O9&4`````$;X````"7U]E
A=&5X=````!'``````E]E=&5X=``````1P`````````/R
`
end
SHAR_EOF
echo 'uudecoding file SkipListLib/Libs/skiplist.library' &&
uudecode < _shar_tmp_.tmp && rm -f _shar_tmp_.tmp &&
chmod 0600 SkipListLib/Libs/skiplist.library ||
echo 'restore of SkipListLib/Libs/skiplist.library failed'
Wc_c="`wc -c < 'SkipListLib/Libs/skiplist.library'`"
test 5928 -eq "$Wc_c" ||
	echo 'SkipListLib/Libs/skiplist.library: original size 5928, current size' "$Wc_c"
rm -f _shar_wnt_.tmp
fi
# ============= SkipListLib/SkipListLib.readme ==============
if test -f 'SkipListLib/SkipListLib.readme' -a X"$1" != X"-c"; then
	echo 'x - skipping SkipListLib/SkipListLib.readme (File already exists)'
	rm -f _shar_wnt_.tmp
else
> _shar_wnt_.tmp
echo 'x - extracting SkipListLib/SkipListLib.readme (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'SkipListLib/SkipListLib.readme' &&
Short: Fast sorted linked list library & source
Uploader: agmsmith@achilles.net
Author: agmsmith@bix.com
Type: dev/c
Requires: AmigaDOS 2.04 (V37) or later, random250.library.
Version: 1.0
X
This is an implementation of William Pugh's Skip List algorithm as an
Amiga shared library, skiplist.library.  It lets you have the
flexiblity of linked lists with the sorting ability of arrays, without
the fixed size problems of arrays or slow (linear) sorting speed of
lists.
X
The GNU C source code for the library is included.  Examples of using
it in GNU C are also available (including a unique words counting
program).  You can easily add it to other languages just like you add
other Amiga libraries.  Read SkipList.h for heavily commented data
structures and functions, or just play around with WordCount.c to get
started quickly.
X
Skiplist.library and the included examples are released to the public
domain.  That means you can hack it up or do whatever you want to it.
That also means I'm not responsible for it running amuck.  But if you
do find bugs, or add some interfaces to other compilers, please let me
know so that I can update it.
X
- Alex
SHAR_EOF
chmod 0600 SkipListLib/SkipListLib.readme ||
echo 'restore of SkipListLib/SkipListLib.readme failed'
Wc_c="`wc -c < 'SkipListLib/SkipListLib.readme'`"
test 1149 -eq "$Wc_c" ||
	echo 'SkipListLib/SkipListLib.readme: original size 1149, current size' "$Wc_c"
rm -f _shar_wnt_.tmp
fi
# ============= SkipListLib/Source/SkipList.c ==============
if test ! -d 'SkipListLib/Source'; then
    echo 'x - creating directory SkipListLib/Source'
    mkdir 'SkipListLib/Source'
fi
if test -f 'SkipListLib/Source/SkipList.c' -a X"$1" != X"-c"; then
	echo 'x - skipping SkipListLib/Source/SkipList.c (File already exists)'
	rm -f _shar_wnt_.tmp
else
> _shar_wnt_.tmp
echo 'x - extracting SkipListLib/Source/SkipList.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'SkipListLib/Source/SkipList.c' &&
/******************************************************************************
X * SkipList.library - an Amiga shared library for fast random and sequential
X * access sorted lists.  Needs Random250.library for random numbers, needs
X * AmigaDOS 2.04 or later for assorted system libraries.
X *
X * $Header: Big:Programming/C/SkipLists/RCS/SkipList.c,v 1.6 1996/08/19 15:08:15 AGMS Exp $
X *
X * Implemented by Alexander G. M. Smith, Ottawa Canada, agmsmith@achilles.net,
X * agmsmith@bix.com, 71330.3173@compuserve.com, and various other places
X * 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.
X *
X * Compile with the GNU C compiler, gcc version 2.7.0, use the command line:
X *    gcc -v -O2 -Wall -nostdlib SkipList.c
X * then rename the a.out file to "skiplist.library".
X *
X * The algorithm was created by, I believe, William Pugh at the University
X * of Maryland USA.  You can read about the algorithm and an analysis of its
X * performance in: William Pugh, Skip Lists: A Probabilistic Alternative to
X * Balanced Trees, Volume 382 of Lecture Notes in Computer Science
X * (proceedings of the Workshop on Algorithms and Data Structures (WADS '89 -
X * I was there as a student volunteer)), pages 437-449, 1989, published by
X * Springer-Verlag, ISBN 3-540-51542-9 or ISBN 0-387-51542-9.
X *
X * He has also published some tech reports at the University of Maryland
X * describing skip lists and there is a note in the bibliography saying he is
X * working on a book called A Skip List Cookbook.
X *
X * $Log: SkipList.c,v $
X * Revision 1.6  1996/08/19  15:08:15  AGMS
X * Added functions for finding and deleting.
X *
X * Revision 1.5  1996/08/17  13:00:24  AGMS
X * Insert is working, but not fully tested.
X *
X * Revision 1.4  1996/08/14  14:35:50  AGMS
X * Init and allocation functions in, ready to start with the guts
X * of the algorithm.  Also added an error display function.
X *
X * Revision 1.3  1996/08/11  13:15:17  AGMS
X * Added prototypes for newly defined library functions, open
X * utility.library as part of initialisation.
X *
X * Revision 1.2  1996/07/30  14:40:08  AGMS
X * Library framework now seems to work.
X *
X * Revision 1.1  1996/07/30  13:27:48  AGMS
X * Initial revision
X */
X
#define __NOLIBBASE__
#define COMPILE_FOR_SKIPLIST_LIBRARY
#define LIBCALL_DECLARATION extern __inline
#define VERBOSE_CODE 1 /* True for run time error messages. */
#define DEBUGMODE 1 /* True to turn on sanity checking code. */
X
#ifndef EXEC_LIBRARIES_H
#include "exec/libraries.h"
#endif /* EXEC_LIBRARIES_H */
X
#ifndef EXEC_RESIDENT_H
#include <exec/resident.h>
#endif /* EXEC_RESIDENT_H */
X
#include "SkipList.h"
X
X
#define VERSION 1     /* Feature set / API version, also library version. */
#define VERSIONQ "1"
#define REVISION 0    /* Bug fix version. */
#define REVISIONQ "0"
X
X
X
/******************************************************************************
X * Special dummy function at the start of the code segment that just returns
X * -1 so that this program doesn't do anything when run, the -1 Makes the CLI
X * return a not-a-program error if you try.  This must come before all the
X * other code and constant data in this file!
X */
X
LONG DummyStartup (void)
{
X  return -1L;
}
X
X
X
/******************************************************************************
X * This is our library base record.  The system will allocate a jump table
X * just before it in memory as well as allocating this record and initialising
X * it to zero.  However, the library pointer still points to the start of this
X * record, meaning that the jump table is accessed with negative offsets.
X */
X
struct SkipListBaseStruct
{
X  struct Library  standardLibrary;  /* The usual standard library fields. */
X  APTR            segmentList;      /* So we can unload our code when done. */
X  APTR            execBase;         /* For memory allocations etc. */
X  APTR            intuitionBase;    /* For error messages etc. */
X  APTR            random250Base;    /* For random numbers. */
X  APTR            utilityBase;      /* For international string comparisons. */
X  BOOL            displayErrors;    /* TRUE if errors are being shown. */
};
X
typedef struct SkipListBaseStruct SkipListBaseRecord, *SkipListBasePointer;
X
X
X
/******************************************************************************
X * Some structure declataions, copied here and simplified rather than using
X * include files, for extra compile speed (GNU on an A2000 isn't speedy).
X */
X
struct IntuiText
{
X    UBYTE FrontPen, BackPen;    /* the pen numbers for the rendering */
X    UBYTE DrawMode;             /* the mode for rendering the text */
X    WORD LeftEdge;              /* relative start location for the text */
X    WORD TopEdge;               /* relative start location for the text */
X    APTR ITextFont;             /* if NULL, you accept the default */
X    const UBYTE *IText;         /* pointer to null-terminated text */
X    struct IntuiText *NextText; /* pointer to another IntuiText to render */
};
X
/* drawing modes */
#define JAM1        0         /* jam 1 color into raster */
#define JAM2        1         /* jam 2 colors into raster */
#define COMPLEMENT  2         /* XOR bits into raster */
#define INVERSVID   4         /* inverse video for drawing modes */
X
/* When you're defining IntuiText for the Positive and Negative Gadgets
X * created by a call to AutoRequest(), these defines will get you
X * reasonable-looking text.  The only field without a define is the IText
X * field; you decide what text goes with the Gadget
X */
X
#define AUTOFRONTPEN    0
#define AUTOBACKPEN     1
#define AUTODRAWMODE    JAM2
#define AUTOLEFTEDGE    6
#define AUTOTOPEDGE     3
#define AUTOITEXTFONT   NULL
#define AUTONEXTTEXT    NULL
X
/* Similar values for the body text. */
X
#define BODYLEFTEDGE    6
#define BODYTOPEDGE     5
X
X
X
/******************************************************************************
X * Here are some library call declarations that have explicit library base
X * pointers, since this program doesn't have normal global variables where the
X * library base pointer would normally go.  You can make these extern if you
X * always compile with the O2 optimise option, then it won't actually have a
X * copy of these stubs in the code since they would be used only inline.
X */
X
LIBCALL_DECLARATION APTR
AllocMemA6 (unsigned long byteSize, unsigned long requirements, APTR ExecAddr)
{
X  register APTR  _res  __asm("d0");
X  register APTR a6 __asm("a6") = ExecAddr;
X  register unsigned long d0 __asm("d0") = byteSize;
X  register unsigned long d1 __asm("d1") = requirements;
X  __asm __volatile ("jsr a6@(-0xc6)"
X  : "=r" (_res)
X  : "r" (a6), "r" (d0), "r" (d1)
X  : "a0","a1","d0","d1", "memory");
X  return _res;
}
X
LIBCALL_DECLARATION BOOL
AutoRequestA6 (APTR window, const struct IntuiText *body,
const struct IntuiText *posText, const struct IntuiText *negText,
unsigned long pFlag, unsigned long nFlag, unsigned long width,
unsigned long height, APTR ExecAddr)
{
X  register BOOL  _res  __asm("d0");
X  register APTR a6 __asm("a6") = ExecAddr;
X  register APTR a0 __asm("a0") = window;
X  register const struct IntuiText *a1 __asm("a1") = body;
X  register const struct IntuiText *a2 __asm("a2") = posText;
X  register const struct IntuiText *a3 __asm("a3") = negText;
X  register unsigned long d0 __asm("d0") = pFlag;
X  register unsigned long d1 __asm("d1") = nFlag;
X  register unsigned long d2 __asm("d2") = width;
X  register unsigned long d3 __asm("d3") = height;
X  __asm __volatile ("jsr a6@(-0x15c)"
X  : "=r" (_res)
X  : "r" (a6), "r" (a0), "r" (a1), "r" (a2), "r" (a3), "r" (d0), "r" (d1), "r" (d2), "r" (d3)
X  : "a0","a1","a2","a3","d0","d1","d2","d3", "memory");
X  return _res;
}
X
LIBCALL_DECLARATION void
CloseLibraryA6 (struct Library *library, APTR ExecAddr)
{
X  register APTR a6 __asm("a6") = ExecAddr;
X  register struct Library *a1 __asm("a1") = library;
X  __asm __volatile ("jsr a6@(-0x19e)"
X  : /* no output */
X  : "r" (a6), "r" (a1)
X  : "a0","a1","d0","d1", "memory");
}
X
LIBCALL_DECLARATION void DeallocateSkipNodeA6 (SkipListPointer TheList,
SkipNodePointer TheNode, APTR SkipBase)
{
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register SkipNodePointer a1 __asm("a1") = TheNode;
X  register APTR a6 __asm("a6") = SkipBase;
X  __asm __volatile ("jsr a6@(-42)"
X  :                                 /* Outputs. */
X  : "r" (a6), "r" (a0), "r" (a1)    /* Inputs. */
X  : "a0","a1","d0","d1", "memory"); /* Changed. */
}
X
LIBCALL_DECLARATION void
FreeMemA6 (APTR memoryBlock, unsigned long byteSize, APTR ExecAddr)
{
X  register APTR a6 __asm("a6") = ExecAddr;
X  register APTR a1 __asm("a1") = memoryBlock;
X  register unsigned long d0 __asm("d0") = byteSize;
X  __asm __volatile ("jsr a6@(-0xd2)"
X  : /* no output */
X  : "r" (a6), "r" (a1), "r" (d0)
X  : "a0","a1","d0","d1", "memory");
}
X
LIBCALL_DECLARATION ULONG
GenerateRandomLevelNumberA6 (SkipListPointer TheList, APTR SkipBase)
{
X  register ULONG _res __asm("d0");
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register APTR a6 __asm("a6") = SkipBase;
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;
}
X
LIBCALL_DECLARATION void InitSkipListA6 (SkipListPointer TheList, APTR SkipBase)
{
X  register SkipListPointer a0 __asm("a0") = TheList;
X  register APTR a6 __asm("a6") = SkipBase;
X  __asm __volatile ("jsr a6@(-30)"
X  :                                 /* Outputs. */
X  : "r" (a6), "r" (a0)              /* Inputs. */
X  : "a0","a1","d0","d1", "memory"   /* Changed things. */);
}
X
LIBCALL_DECLARATION struct Library *
OpenLibraryA6 (UBYTE *libName, unsigned long version, APTR ExecAddr)
{
X  register struct Library * _res  __asm("d0");
X  register APTR a6 __asm("a6") = ExecAddr;
X  register UBYTE *a1 __asm("a1") = libName;
X  register unsigned long d0 __asm("d0") = version;
X  __asm __volatile ("jsr a6@(-0x228)"
X  : "=r" (_res)
X  : "r" (a6), "r" (a1), "r" (d0)
X  : "a0","a1","d0","d1", "memory");
X  return _res;
}
X
LIBCALL_DECLARATION void
Random250ArrayA6 (unsigned long ArrayLongWordSize,
unsigned long *ArrayPointer, APTR R250Base)
{
X  register APTR a6 __asm("a6") = R250Base;
X  register unsigned long d0 __asm("d0") = ArrayLongWordSize;
X  register unsigned long *a0 __asm("a0") = ArrayPointer;
X  __asm __volatile ("jsr a6@(-36)"
X  : /* no output */
X  : "r" (a6), "r" (a0), "r" (d0)
X  : "a0","a1","d0","d1","memory");
}
X
LIBCALL_DECLARATION unsigned long
Random250LongA6 (APTR R250Base)
{
X  register LONG _res __asm("d0");
X  register APTR a6 __asm("a6") = R250Base;
X  __asm __volatile ("jsr a6@(-30)"
X  : "=r" (_res)
X  : "r" (a6)
X  : "a0","a1","d0","d1", "memory");
X  return _res;
}
X
LIBCALL_DECLARATION void
RemoveA6 (struct Node *node, APTR ExecAddr)
{
X  register APTR a6 __asm("a6") = ExecAddr;
X  register struct Node *a1 __asm("a1") = node;
X  __asm __volatile ("jsr a6@(-0xfc)"
X  : /* no output */
X  : "r" (a6), "r" (a1)
X  : "a0","a1","d0","d1", "memory");
}
X
LIBCALL_DECLARATION SkipNodePointer RemoveSkipNodeA6 (SkipListPointer TheList,
SkipNodePointer TheNode, APTR SkipBase)
{
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") = SkipBase;
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;
}
X
LIBCALL_DECLARATION LONG
StrnicmpA6 (STRPTR string1, STRPTR string2, long length, APTR UtilityAddr)
{
X  register LONG  _res  __asm("d0");
X  register APTR a6 __asm("a6") = UtilityAddr;
X  register STRPTR a0 __asm("a0") = string1;
X  register STRPTR a1 __asm("a1") = string2;
X  register long d0 __asm("d0") = length;
X  __asm __volatile ("jsr a6@(-0xa8)"
X  : "=r" (_res)
X  : "r" (a6), "r" (a0), "r" (a1), "r" (d0)
X  : "a0","a1","d0","d1", "memory");
X  return _res;
}
X
X
X
/******************************************************************************
X * Forward declarations.
X */
X
static SkipListBasePointer InitialiseSkipListLibrary (void);
static SkipListBasePointer OpenSkipListLibrary (void);
static APTR CloseSkipListLibrary (void);
static APTR ExpungeSkipListLibrary (void);
static LONG ReservedFunction (void);
static void InitSkipList (void);
static SkipNodePointer AllocateSkipNode (void);
static void DeallocateSkipNode (void);
static SkipNodePointer InsertSkipNode (void);
static SkipNodePointer RemoveSkipNode (void);
static ULONG DeleteSkipNode (void);
static void DeleteAllSkipNodes (void);
static SkipNodePointer FindSkipNode (void);
static SkipNodePointer FindBelowSkipNode (void);
static SkipNodePointer FindAboveOrEqualSkipNode (void);
static ULONG GenerateRandomLevelNumber (void);
static ULONG GetRANDOMCACHESIZE (void);
static ULONG GetSKIPLISTLEVELCAP (void);
static void EndOfCode (void);
X
X
X
/******************************************************************************
X * Version strings, here since they need to be before the ROMTag.
X */
X
static const char LibraryName [] = "skiplist.library";
X
static const char LibraryID [] = "skiplist " VERSIONQ "." REVISIONQ " ("
__DATE__ ") "
#if DEBUGMODE
X  "(Debug) "
#else
X  "(Fast) "
#endif
#if VERBOSE_CODE
"(Verbose) "
#else
"(Silent) "
#endif
"(By AGMSmith)\r\n";
X
#if VERBOSE_CODE
static const char AuthorString [] =
"\n\n$Id: SkipList.c,v 1.6 1996/08/19 15:08:15 AGMS Exp $\n"
"Public domain 1996 by Alexander G. M. Smith, all rights unreserved.\n"
"Algorithm by William Pugh at the University of Maryland USA.\n"
"Send questions to agmsmith@achilles.net, agmsmith@bix.com,\n"
"au829@freenet.carleton.ca and 71330.3173@CompuServe.com\n\n";
#endif
X
X
X
/******************************************************************************
X * Various error messages.
X */
X
static const char MissingR250String [] =
"Sorry, skiplist.library can't open random250.library";
X
static const struct IntuiText MissingR250IText =
{
X  AUTOFRONTPEN,
X  AUTOBACKPEN,
X  AUTODRAWMODE,
X  BODYLEFTEDGE,
X  BODYTOPEDGE,
X  AUTOITEXTFONT,
X  MissingR250String, /* Message string */
X  AUTONEXTTEXT
};
X
X
static const char MissingUtilityString [] =
"Sorry, skiplist.library can't open utility.library V37";
X
static const struct IntuiText MissingUtilityIText =
{
X  AUTOFRONTPEN,
X  AUTOBACKPEN,
X  AUTODRAWMODE,
X  BODYLEFTEDGE,
X  BODYTOPEDGE,
X  AUTOITEXTFONT,
X  MissingUtilityString, /* Message string */
X  AUTONEXTTEXT
};
X
X
static const char CancelString [] = "Cancel";
X
static const struct IntuiText CancelIText =
{
X  AUTOFRONTPEN,
X  AUTOBACKPEN,
X  AUTODRAWMODE,
X  AUTOLEFTEDGE,
X  AUTOTOPEDGE,
X  AUTOITEXTFONT,
X  CancelString, /* Message string */
X  AUTONEXTTEXT
};
X
X
static const char OKString [] = "OK";
X
static const struct IntuiText OKIText =
{
X  AUTOFRONTPEN,
X  AUTOBACKPEN,
X  AUTODRAWMODE,
X  AUTOLEFTEDGE,
X  AUTOTOPEDGE,
X  AUTOITEXTFONT,
X  OKString, /* Message string */
X  AUTONEXTTEXT
};
X
X
X
/******************************************************************************
X * List of the functions that the OS will place into the jump table.
X */
X
static void * const LibraryFunctionsList [] =
{                               /* Library offset decimal value */
X  OpenSkipListLibrary,
X  CloseSkipListLibrary,
X  ExpungeSkipListLibrary,
X  ReservedFunction,
X  InitSkipList,                 /*  -30 */
X  AllocateSkipNode,             /*  -36 */
X  DeallocateSkipNode,           /*  -42 */
X  InsertSkipNode,               /*  -48 */
X  RemoveSkipNode,               /*  -54 */
X  DeleteSkipNode,               /*  -60 */
X  DeleteAllSkipNodes,           /*  -66 */
X  FindSkipNode,                 /*  -72 */
X  FindBelowSkipNode,            /*  -78 */
X  FindAboveOrEqualSkipNode,     /*  -84 */
X  GenerateRandomLevelNumber,    /*  -90 */
X  GetRANDOMCACHESIZE,           /*  -96 */
X  GetSKIPLISTLEVELCAP,          /* -102 */
X  (void *) -1  /* Marks end of list. */
};
X
X
X
/******************************************************************************
X * Library initialisation table, used by the OS to build the library base
X * record.
X */
X
static void * const LibraryInitTable [4] =
{
X  (void *) sizeof (SkipListBaseRecord), /* Library base structure size. */
X  (void *) LibraryFunctionsList,/* Function list for making jump table from. */
X  NULL,                         /* No special InitStruct data, */
X  InitialiseSkipListLibrary     /* instead our init function does it all. */
};
X
X
X
/******************************************************************************
X * Here we have the famous ROMTag structure that the library loader will
X * search through the code segment to find and will use to initialise the
X * library.
X */
X
static const struct Resident SkipListROMTag =
{
X  RTC_MATCHWORD,        /* Magic number identifying a ROMTag. */
X  (struct Resident *) &SkipListROMTag, /* Pointer to self, magic ID stuff. */
X  EndOfCode,            /* Pointer to end of this ROM section.  For CRC? */
X  RTF_AUTOINIT,         /* Various flags. */
X  VERSION,              /* Main version number.  API version in essence. */
X  NT_LIBRARY,           /* This is a library kind of thing. */
X  0,                    /* Priority in system library list? */
X  (char *) LibraryName, /* Points to name string. */
X  (char *) LibraryID,   /* Points to ID (readable version) string. */
X  (APTR) LibraryInitTable /* Table of pointers to init code and data sizes. */
};
X
X
X
/******************************************************************************
X * Deallocate the stuff allocated by this library and close sublibraries.
X * Assumes that the library base record isn't linked into any system lists,
X * since it is freed here.
X */
X
static void DeallocateStuff (SkipListBasePointer OurBase)
{
X  register APTR TempExecBase __asm("a6");
X
X  TempExecBase = *((void **) 4); /* Get standard execbase address. */
X
X  if (OurBase->intuitionBase != NULL)
X  {
X    CloseLibraryA6 (OurBase->intuitionBase, TempExecBase);
X    OurBase->intuitionBase = NULL;
X  }
X
X  if (OurBase->random250Base != NULL)
X  {
X    CloseLibraryA6 (OurBase->random250Base, TempExecBase);
X    OurBase->random250Base = NULL;
X  }
X
X  if (OurBase->utilityBase != NULL)
X  {
X    CloseLibraryA6 (OurBase->utilityBase, TempExecBase);
X    OurBase->utilityBase = NULL;
X  }
X
X  if (OurBase->execBase != NULL)
X  {
X    CloseLibraryA6 (OurBase->execBase, TempExecBase);
X    OurBase->execBase = NULL;
X  }
X
X  /* Finally free our library base record. */
X
X  FreeMemA6 (((UBYTE *) OurBase) - OurBase->standardLibrary.lib_NegSize,
X  OurBase->standardLibrary.lib_NegSize + OurBase->standardLibrary.lib_PosSize,
X  TempExecBase);
}
X
X
X
/******************************************************************************
X * Library has just been allocated, library base pointer in D0, segment list
X * pointer in A0, execbase in A6.  System is in a Forbid (non-multitasking)
X * state.  Returns zero in D0 on failure, returns library base address if
X * successful (will make system add the library to the loaded libraries list).
X */
X
static SkipListBasePointer InitialiseSkipListLibrary (void)
{
X  register ULONG  d0 __asm("d0");
X  register APTR   a0 __asm("a0");
X  register APTR   a6 __asm("a6");
X
X  APTR SegmentList = a0;
X  SkipListBasePointer NewBase = (void *) d0;
X
X  NewBase->segmentList = SegmentList;
X  NewBase->standardLibrary.lib_Node.ln_Type = NT_LIBRARY;
X  NewBase->standardLibrary.lib_Node.ln_Name = (char *) LibraryName;
X  NewBase->standardLibrary.lib_Flags = LIBF_SUMUSED | LIBF_CHANGED;
X  NewBase->standardLibrary.lib_Version = VERSION;
X  NewBase->standardLibrary.lib_Revision = REVISION;
X  NewBase->standardLibrary.lib_IdString = (APTR) LibraryID;
X  NewBase->displayErrors = TRUE;
X
X  while (TRUE)
X  {
X    /* Open intuition.library (any version, so it works under AmigaDOS 1.3
X       too), just in case we need to display error messages. */
X
X    NewBase->intuitionBase = OpenLibraryA6 ("intuition.library", 0, a6);
X    if (NewBase->intuitionBase == NULL)
X      break;
X
X    /* We need the utility library for string comparisons.  Version 37 is the
X       earliest one that has them. */
X
X    NewBase->utilityBase = OpenLibraryA6 ("utility.library", 37, a6);
X    if (NewBase->utilityBase == NULL)
X    {
X      /* Display an error message. */
X
X      AutoRequestA6 (NULL, &MissingUtilityIText, NULL,
X      &CancelIText, 0, 0, 512 /* width */, 60 /* height */,
X      NewBase->intuitionBase);
X
X      break;
X    }
X
X    /* We need the random number library. */
X
X    NewBase->random250Base = OpenLibraryA6 ("random250.library", 0, a6);
X    if (NewBase->random250Base == NULL)
X    {
X      /* Display an error message. */
X
X      AutoRequestA6 (NULL, &MissingR250IText, NULL,
X      &CancelIText, 0, 0, 512 /* width */, 60 /* height */,
X      NewBase->intuitionBase);
X
X      break;
X    }
X
X    /* And our copy of Execbase. */
X
X    NewBase->execBase = OpenLibraryA6 ("exec.library", 0, a6);
X    if (NewBase->execBase == NULL)
X      break;
X
X    return NewBase;  /* Success! */
X  }
X
X  DeallocateStuff (NewBase);
X  return 0;  /* Failure. */
}
X
X
X
/******************************************************************************
X * Our library base is in A6.  Return 0 if we can't handle another instance of
X * this library being opened, else return the library base if successful.  The
X * system is in a forbid state.  Turns off the delayed expunge state.
X */
X
static SkipListBasePointer OpenSkipListLibrary (void)
{
X  register APTR a6 __asm("a6");
X
X  SkipListBasePointer OurBase = a6;
X
X  OurBase->standardLibrary.lib_OpenCnt++;
X  OurBase->standardLibrary.lib_Flags &= ~LIBF_DELEXP;
X
X  return OurBase;
}
X
X
X
/******************************************************************************
X * Close the library.  Decrement the open count, but never let it go below
X * zero (unsigned int).  Returns the segment list if the library is expunged
X * as a side effect of the close, otherwise just returns zero.
X */
X
static APTR CloseSkipListLibrary (void)
{
X  register APTR a6 __asm("a6");
X
X  SkipListBasePointer OurBase = a6;
X
X  if (OurBase->standardLibrary.lib_OpenCnt > 0)
X    OurBase->standardLibrary.lib_OpenCnt -= 1;
X
X  if (OurBase->standardLibrary.lib_OpenCnt == 0 &&
X  (OurBase->standardLibrary.lib_Flags & LIBF_DELEXP))
X  {
X    /* A delayed expunge has been requested. */
X
X    a6 = OurBase;
X    return ExpungeSkipListLibrary ();
X  }
X
X  return NULL;
}
X
X
X
/******************************************************************************
X * Deallocate this library's data if nobody is using it.  If it is in use, do
X * a delayed expunge later when nobody is using the library.  Returns the
X * segment list if the library was deallocated, zero if still in use.  The
X * usual Forbid is in progress, and this can also be called by the OS memory
X * routines so don't do Wait or other things.  This can also be called by
X * RemLibrary so that call can't be used.
X */
X
static APTR ExpungeSkipListLibrary (void)
{
X  register APTR a6 __asm("a6");
X
X  APTR                ExecBase;
X  SkipListBasePointer OurBase = a6;
X  APTR                SegmentList;
X
X  if (OurBase->standardLibrary.lib_OpenCnt > 0)
X  {
X    /* If can't do an expunge now, do it later when the last user
X       has exited from the library. */
X
X    OurBase->standardLibrary.lib_Flags |= LIBF_DELEXP;
X    return NULL;
X  }
X
X  SegmentList = OurBase->segmentList;
X
X  /* Remove this library's node from the system library list. */
X
X  ExecBase = OurBase->execBase;
X  RemoveA6 (&OurBase->standardLibrary.lib_Node, ExecBase);
X
X  DeallocateStuff (OurBase);
X
X  return SegmentList;
}
X
X
X
/******************************************************************************
X * A special function that just returns zero.  Used for a reserved-for-future-
X * use function entry in the library jump table.
X */
X
static LONG ReservedFunction (void)
{
X  return 0;
}
X
X
X
#if VERBOSE_CODE
/******************************************************************************
X * Our runtime error message display function.  If the user hits Cancel, no
X * more messages will be displayed until the library is flushed from memory.
X */
X
static void DisplayErrorMessage (const char *ErrorMessage,
SkipListBasePointer OurBase)
{
X  struct IntuiText ErrorIText;
X  struct IntuiText ExplainingIText;
X  BOOL OKHit;
X
X  if (OurBase->displayErrors)
X  {
X    ErrorIText.FrontPen = AUTOFRONTPEN;
X    ErrorIText.BackPen = AUTOBACKPEN;
X    ErrorIText.DrawMode = AUTODRAWMODE;
X    ErrorIText.LeftEdge = BODYLEFTEDGE;
X    ErrorIText.TopEdge = BODYTOPEDGE;
X    ErrorIText.ITextFont = AUTOITEXTFONT;
X    ErrorIText.IText = ErrorMessage;
X    ErrorIText.NextText = &ExplainingIText;
X
X    ExplainingIText.FrontPen = AUTOFRONTPEN;
X    ExplainingIText.BackPen = AUTOBACKPEN;
X    ExplainingIText.DrawMode = AUTODRAWMODE;
X    ExplainingIText.LeftEdge = BODYLEFTEDGE;
X    ExplainingIText.TopEdge = BODYTOPEDGE + 12;
X    ExplainingIText.ITextFont = AUTOITEXTFONT;
X    ExplainingIText.IText = "Continue showing skiplist.library error messages?";
X    ExplainingIText.NextText = NULL;
X
X    OKHit = AutoRequestA6 (NULL, &ErrorIText, &OKIText, &CancelIText, 0, 0,
X    512 /* width */, 80 /* height */, OurBase->intuitionBase);
X
X    if (!OKHit) /* Cancel selected.  Stop showing errors. */
X      OurBase->displayErrors = FALSE;
X  }
}
#endif
X
X
X
/******************************************************************************
X * This function initialises a skip list record (you provide a pointer to an
X * allocated SkipListRecord) to an empty list state.  It is always successful.
X * Don't do it to an already initialised skip list, otherwise you'll lose the
X * memory that was allocated for its nodes.  You must call this function
X * before using the other skip list functions on that list.  Remember to set
X * the function pointer fields (usually compareUserData and maybe
X * destroyUserData) immediately after calling this function.
X */
X
static void InitSkipList (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  SkipListBasePointer OurBase = a6;
X
X  int i;
X
#if DEBUGMODE
X  if (TheList == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("TheList is NULL in InitSkipList.", OurBase);
X    #endif
X    return;
X  }
#endif
X
X  for (i = SKIPLISTLEVELCAP - 1; i >= 0; i--)
X    TheList->levelPointers [i] = NULL;
X
X  TheList->activeLevels = 1;
X  TheList->filler = 0;
X  TheList->size = 0;
X  TheList->nextSizeUp = 4;
X  TheList->nextSizeDown = 0;
X  TheList->destroyUserData = NULL;
X  TheList->compareUserData = NULL;
X  TheList->randomIndex = RANDOMCACHESIZE-1;
X  Random250ArrayA6 (RANDOMCACHESIZE, TheList->randomCache,
X  OurBase->random250Base);
}
X
X
X
/******************************************************************************
X * Allocate a new SkipNode record, returns a pointer to the record or NULL if
X * it fails.  The UserRecordSize is the size of your record (structure in C
X * talk), which includes a SkipNodeRecord at the very front.  Maximum size is
X * almost 16 megabytes.  The actual memory allocated is a bit larger, for a
X * randomly sized hidden array of pointers before your record in memory.
X * TheList is an existing list which is only used for its cache of random
X * numbers (so it doesn't have to be the same as the list the new SkipNode
X * will be eventually added to).  TheList can also be NULL, which makes it
X * slightly slower.  MemoryFlags specify which kind of memory to allocate, see
X * exec/memory.h for the various types (or just use MEMF_ANY or 0 if you don't
X * care). Your new record will have its SkipNode fields initialised.  If you
X * include the MEMF_CLEAR flag then the user data area will be cleared to
X * zero.
X */
X
static SkipNodePointer AllocateSkipNode (void)
{
X  register SkipListPointer a0 __asm("a0");
X  register ULONG d0 __asm("d0");
X  register ULONG d1 __asm("d1");
X  register APTR a6 __asm("a6");
X  SkipListPointer TheList = a0;
X  ULONG UserRecordSize = d0;
X  ULONG MemoryFlags = d1;
X  SkipListBasePointer OurBase = a6;
X
X  int i;
X  int Levels;
X  UBYTE *MemoryBytePointer;
X  SkipNodePointer NewNode;
X  SkipNodePointerPointer NewPointerArray;
X
#if DEBUGMODE
X  /* The user's record size has to contain at least a SkipNodeRecord and fit
X     within 24 bits.  Note that we don't care if TheList is NULL, it will just
X     be slower without the random number cache from it. */
X
X  if (UserRecordSize < sizeof (SkipNodeRecord) || UserRecordSize >= 0x1000000)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("UserRecordSize is bad in AllocateSkipNode.",
X    OurBase);
X    #endif
X    return NULL;
X  }
#endif
X
X  /* Generate the number of level pointers this node will have. */
X
X  Levels = GenerateRandomLevelNumberA6 (TheList, OurBase);
X
X  /* Allocate memory for the hidden array combined with the user's record. */
X
X  MemoryBytePointer = AllocMemA6 (UserRecordSize + (Levels - 1) * sizeof
X  (SkipNodePointer), MemoryFlags, OurBase->execBase);
X
X  if (MemoryBytePointer == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Ran out of memory in AllocateSkipNode.", OurBase);
X    #endif
X    return NULL;
X  }
X
X  NewNode = (SkipNodePointer) (MemoryBytePointer +
X  (Levels - 1) * sizeof (SkipNodePointer));
X
X  /* Zero out the variable sized pointer array. */
X
X  NewPointerArray = &NewNode->next;
X  for (i = 0; i < Levels; i++)
X    *NewPointerArray-- = NULL;
X
X  /* Set composite size field.  Assumes this is running on a big endian
X     processor so that the high byte comes first and falls into the nodeLevel
X     field. */
X
X  NewNode->size.asLong = (Levels << 24) | UserRecordSize;
X
X  return NewNode;
}
X
X
X
/******************************************************************************
X * This function deallocates the memory used by a SkipNode.  If the
X * destroyUserData function in TheList is NULL or it returns non-zero
X * (preferably 1) when called, then the memory is deallocated (including the
X * hidden array before the SkipNode).  If destroyUserData returns zero, no
X * deallocation is done (useful for situations where you are allocating memory
X * in a nonstandard way).
X */
X
static void DeallocateSkipNode (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  int Levels;
X  UBYTE *MemoryBytePointer;
X  int UserRecordSize;
X
#if DEBUGMODE
X  if (TheList == NULL || TheNode == NULL)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("NULL TheList or TheNode in DeallocateSkipNode.",
X    OurBase);
X    #endif
X    return;
X  }
#endif
X
X  /* Assume big endian byte ordering here. */
X
X  UserRecordSize = TheNode->size.asLong & 0xFFFFFF;
X
X  Levels = TheNode->size.asBytes.nodeLevel;
X
#if DEBUGMODE
X  if (Levels < 1 || Levels > SKIPLISTLEVELCAP ||
X  UserRecordSize < sizeof (SkipNodeRecord))
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage (
X    "TheNode is corrupt (already deallocated?) in DeallocateSkipNode.",
X    OurBase);
X    #endif
X    return; /* This isn't a valid node. */
X  }
#endif
X
X  /* Do the user provided cleanup function. */
X
X  if (TheList->destroyUserData != NULL &&
X  TheList->destroyUserData (TheNode) == 0)
X    return;  /* The user doesn't want this node deallocated by us. */
X
#if DEBUGMODE
X  /* Mark node as invalid so that future attempts to deallocate it are
X     detected and reported as a corrupt node.  Well, actually FreeMem writes
X    over this with something that looks like the size of the freed block,
X    which is also detected as invalid if it is <16M.  Well, at least for level
X    1 nodes.  It also puts a pointer in the next field of level 1 blocks.  See
X    the MemChunk structure in exec/memory.h for a clue. */
X
X  TheNode->size.asLong = 0;
#endif
X
X  /* Finally, deallocate the memory used by the node. */
X
X  MemoryBytePointer = (void *) TheNode;
X  MemoryBytePointer -= (Levels - 1) * sizeof (SkipNodePointer);
X
X  FreeMemA6 (MemoryBytePointer, UserRecordSize +
X  (Levels - 1) * sizeof (SkipNodePointer), OurBase->execBase);
}
X
X
X
/******************************************************************************
X * A little internal function for comparing two SkipNodes as strings.  Uses
X * the utility.library string comparison function to handle international
X * character sets.  Returns <0 if A<B, returns 0 if A==B, returns >0 if A>B.
X */
X
static LONG CompareNodesAsStrings (SkipNodePointer A, SkipNodePointer B,
SkipListBasePointer OurBase)
{
X  LONG ComparisonResult;
X  int ShortestLength;
X  int TempLength;
X  ULONG TwentyFourBitMask = 0xFFFFFF;
X
X  ShortestLength = A->size.asLong & TwentyFourBitMask;
X  TempLength = B->size.asLong & TwentyFourBitMask;
X  if (TempLength < ShortestLength)
X    ShortestLength = TempLength;
X
X  if (ShortestLength <= 0)
X    ComparisonResult = 0;
X  else /* Compare the data immediately after the SkipNodeRecord core. */
X    ComparisonResult = StrnicmpA6 (
X    ((char *) A) + sizeof (SkipNodeRecord),
X    ((char *) B) + sizeof (SkipNodeRecord),
X    ShortestLength, OurBase->utilityBase);
X
X  return ComparisonResult;
}
X
X
X
/******************************************************************************
X * An internal function that bumps up or down the number of active levels in a
X * list.  It also has to rethread the nodes that use a newly activated level.
X */
X
static void UpdateListActiveLevels (SkipListPointer TheList,
SkipListBasePointer OurBase)
{
X  SkipNodePointer CurrentNode;
X  int NewLevel;
X  int PreviousLevel;
X  SkipNodePointerPointer PointerToUpdate;
X  ULONG TempULong;
X
X  PreviousLevel = TheList->activeLevels;
X
#if DEBUGMODE
X  if (PreviousLevel <= 0 || PreviousLevel > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Corrupt list header in UpdateListActiveLevels.",
X    OurBase);
X    #endif
X    return;
X  }
#endif
X
X  /* Compute the desired level based on the current list size.  Essentially do
X     logarithm base 4 of the size, but not quite. */
X
X  NewLevel = 0;
X  TempULong = TheList->size;
X  while (TempULong != 0)
X  {
X    ++NewLevel;
X    TempULong >>= 2;
X  }
X  if (NewLevel <= 0)
X    NewLevel = 1; /* Special case for size zero lists. */
X
X  if (NewLevel > SKIPLISTLEVELCAP)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Maximum level reached "
X    "(list will be inefficient) in UpdateListActiveLevels.", OurBase);
X    #endif
X    NewLevel = SKIPLISTLEVELCAP;
X  }
X
#if DEBUGMODE
X  /* Can only go up one level at a time. */
X
X  if (NewLevel > PreviousLevel + 1)
X  {
X    #if VERBOSE_CODE
X    DisplayErrorMessage ("Bug?  Want to go up more than one level "
X    "in UpdateListActiveLevels.", OurBase);
X    #endif
X    NewLevel = PreviousLevel + 1;
X  }
#endif
X
X  if (NewLevel == PreviousLevel + 1)  /* If actually going up. */
X  {
X    /* Do the rethreading on the new level, iterating through the previous
X       level the old highest level) of pointers to find nodes that protude
X       into the new level (about 1 in 4 should). */
X
X    PointerToUpdate =
X    &TheList->levelPointers [SKIPLISTLEVELCAP - NewLevel];
X
X    CurrentNode = TheList->levelPointers [SKIPLISTLEVELCAP - PreviousLevel];
X
X    while (CurrentNode != NULL)
X    {
X      if (CurrentNode->size.asBytes.nodeLevel >= NewLevel)
X      {
X        *PointerToUpdate = CurrentNode;
X        PointerToUpdate = (&CurrentNode->next) + 1 - NewLevel;
X      }
X      CurrentNode = ((&CurrentNode->next) + 1) [-PreviousLevel];
SHAR_EOF
true || echo 'restore of SkipListLib/Source/SkipList.c failed'
fi
echo 'End of libs/SkipListLib-1.0 part 2'
echo 'File SkipListLib/Source/SkipList.c is continued in part 3'
echo 3 > _shar_seq_.tmp
exit 0
-- 
Bill Zimmer - zim@ibx.com


