#ifndef SKIPLIST_H #define SKIPLIST_H /*********************************************************************** * Exported functions from SkipList.library - an Amiga shared library * for fast random and sequential access sorted lists. * * $Header: Big:Programming/C/SkipLists/RCS/SkipList.h,v 1.6 1996/08/29 12:26:24 AGMS Exp $ * * Implemented by Alexander G. M. Smith, Ottawa Canada, * agmsmith@achilles.net, agmsmith@bix.com, 71330.3173@compuserve.com, * and various other places including the Ottawa Freenet. * * This code is put into the public domain by AGMS, so you can copy it, * hack it up, sell it, and do whatever you want to it. See SkipList.c * for algorithm credits and explanations. * * $Log: SkipList.h,v $ * Revision 1.6 1996/08/29 12:26:24 AGMS * Added comment for how to simulate duplicate keys. * * Revision 1.5 1996/08/19 15:05:10 AGMS * Changed FindBelowOrEqualSkipNode to FindBelowSkipNode. * * Revision 1.4 1996/08/17 13:01:36 AGMS * Documentation changes. * * Revision 1.3 1996/08/14 14:33:26 AGMS * Minor corrections. * * Revision 1.2 1996/08/11 13:17:00 AGMS * Defined the functions that skiplist library exports and wrote * up descriptions of what they do. * * Revision 1.1 1996/08/05 19:09:55 AGMS * Initial revision */ /* Define COMPILE_FOR_SKIPLIST_LIBRARY when making the library (so it doesn't have the library call declarations), leave it undefined if you are just using the library. */ #ifndef EXEC_TYPES_H #include #endif #define SKIPLISTLEVELCAP 16 /* A skip list has at most this many levels of pointers in use. List nodes are also allocated with at most this many levels. Some of the levels aren't used even though they are allocated, until the list size grows large enough. This value is related to the number of bits in a random number (for convenience 32 bits are generated per batch and we need 2 bits per level, thus 16 levels). This also means that the list can hold 4^16 = 4294967296 entries before becoming inefficient. If you change this value, you'll need to recompile the library and make sure that no programs written with the old value use your library (the list header sizes would be wrong). */ #define RANDOMCACHESIZE 8 /* A cache of pseudo-random numbers is stored in each skip list and used for generating the random sizes of new nodes. Whenever the cache is empty, it is refilled in one call to the random number generator. This is done because generating a single random number at a time has some overhead (locking semaphores in Random250, library function call overhead). The tradeoff is that some memory is used in each list. If you want to, you can define this to be 1 for minimal memory use. Use larger values if new node creation time is a concern. If you change this value, you'll need to recompile the library and make sure that no programs written with the old value use your library (the list header sizes would be wrong). */ #define SKIPLISTLIBRARYNAME "skiplist.library" /* So you don't have to type in the name of this library. Note that all letters are lower case. If you have a custom version of the library, it would be a good idea to give it a different name here. */ /* This structure contains a node in a skip list. It is a doubly variable size record so don't try to allocate it yourself, use the AllocateSkipNode function instead. There is a variable size array of pointers before the start of this record (number of entries specified by the "nodeLevel" field), with the very last element in the array overlapping with the "next" field. The variable size user data follows after this record in memory. Normally the user's record structure will have a SkipNodeRecord right at the front followed by user specified fields. */ typedef struct SkipNodeStruct SkipNodeRecord, *SkipNodePointer, **SkipNodePointerPointer; struct SkipNodeStruct { SkipNodePointer next; /* Points to the next node in the list. You can use it for iterating through the list, but don't change its value. This is also the last element in an array of pointers hidden before the start of this record. */ union { struct { UBYTE nodeLevel; UBYTE userSize [3]; } asBytes; ULONG asLong; } size; /* This 4 byte value contains the size of the node, which is set when the node is allocated and can't be changed. The nodeLevel field (first byte assuming it is running on a big-endien processor) contains the number of pointer levels that this node has. It is generated by GenerateRandomLevelNumber(). The userSize field (the next 3 bytes) contains the size of the user's record in bytes (includes the size of the user visible part of the SkipNodeRecord), thus allowing up to 16 megabytes of user data in a node. The actual size of the whole record including invisibles is: (levels - 1) * sizeof (SkipNodePointer) + sizeof (UserRecord). */ /****** UserData ******* follows after this, though you don't see it in this structure declaration. It is long word (4 byte) aligned. */ }; /* This structure contains a skip list. You need to allocate memory for this structure and call the InitSkipList function before using it. The fields are read only unless otherwise noted. It is not multitasking safe - it won't work properly if you have two tasks simultaneously trying to change the same list (OK for different lists). */ typedef struct SkipListStruct { SkipNodePointer levelPointers [SKIPLISTLEVELCAP]; /* Points to the various levels of linked list. The list of all the nodes is at index SKIPLISTLEVELCAP-1. The list with roughly every 4th node is at index SKIPLISTLEVELCAP-2, roughly every 16th is in the list at SKIPLISTLEVELCAP-3 and so on. This backwards array indexing corresponds to the order in the array hidden before each node record. Users can iterate through all the nodes using levelPointers [SKIPLISTLEVELCAP-1] to start, and the next pointers in the SkipNodes to continue on. */ UBYTE activeLevels; /* Current number of levels being used in this skip list. Equals one plus (integer portion of log base 4 of the list size). Can vary from 1 to SKIPLISTLEVELCAP. Set to 1 for the special case of an empty list (levelPointers [SKIPLISTLEVELCAP-1] will be NULL), stays 1 when there are 1 to 3 nodes, 2 when there are 4 to 15 nodes, 3 for 16 to 63 nodes and so on. Note that this field comes just after the level pointer array, the same as in the node record. That way the code can treat the list header a bit like a node. See also nextSizeUp and nextSizeDown, which are tied to this variable. */ UBYTE randomIndex; /* Next available number to use from the randomCache array field. Counts down to zero, then refills the array and resets to RANDOMCACHESIZE-1. */ UWORD filler; /* Pads the fields so the following 32 bit values are aligned on a 4 byte boundary for better speed on 32 bit processors. You can use this field for your own data if you want to. */ ULONG size; /* Number of nodes in this list. We assume that it never overflows, so don't try to add more than about four billion nodes :-). */ ULONG nextSizeUp; /* If the list size increases to this value just after adding a node, activeLevels will be incremented and the new higher level of pointers re-threaded and both nextSize fields recalculated. It is normally equal to 4^activeLevels. */ ULONG nextSizeDown; /* If the list size equals this value just before deleting a node, activeLevels will be decremented and thus the highest level of pointers won't be used any more until the size goes up again. Both nextSize fields are updated when activeLevels changes. It is normally equal to 4^(activeLevels-1). It doesn't have a useful value when the list is empty. */ ULONG (*destroyUserData) (SkipNodePointer UserData); /* A user provided (you can set this field) pointer to a cleanup function. This C style function (arguments on the stack, registers A2-A6, D2-D7 preserved, result returned in D0) will be called whenever a list node is going to be deallocated (not just removed). Deallocations happen during insert over an existing node and in calls to DeallocateSkipNode, DeleteSkipNode, DeleteAllSkipNodes, but not RemoveSkipNode. If you return zero then the memory used by the node won't be deallocated, this is useful if you allocated the memory using something other than AllocateSkipNode. Returning non-zero will deallocate the memory. For future compatability, please return a non-zero value of 1 to signal normal memory deallocation, other values could be useful for other special cases in the future. You should also set the node's size.asLong field to zero so that attempts to deallocate it twice can be detected by DeallocateSkipNode. If you allocated a resource of some sort (like an open file) as part of your user data, you might want to deallocate it in your destroyUserData function. If you are using C++, this would be a good place for a destructor function. This function is called after the destroyed node has been removed from the list, so its next pointer will be meaningless. The default value of NULL means that no function call will be done and the memory will be deallocated. */ LONG (*compareUserData) (SkipNodePointer A, SkipNodePointer B); /* A user provided pointer to a comparison function. You should set this field after initialisation and before adding any nodes. It is only safe to change it when the list is empty (otherwise your list will get out of sorted order). This C style function (arguments on the stack, etc) will be called whenever a comparison needs to be done between two nodes. It should return a value less than zero if A < B, zero if A = B, and greater than zero if A > B, if you want the list to be in ascending order. Return the opposite sign for descending order. If you want to have a list with nodes that have the same sort key value, you can't (by design). Instead, fake it with a secondary comparison that you use when the keys are equal (comparing node addresses works well). The default value of NULL means that the user data will be compared as if it is an international string, using Strnicmp from utility.library with the user data size as a limit to the string length (thus we need V37 (AmigaDOS 2.04) of the operating system for Strnicmp). */ ULONG randomCache [RANDOMCACHESIZE]; /* An array of previously computed pseudo-random numbers used for extra speed when creating large numbers of new nodes. RandomIndex specifies the next one to be used. */ } SkipListRecord, *SkipListPointer; #ifndef COMPILE_FOR_SKIPLIST_LIBRARY /*********************************************************************** * User's point of view library function declarations. */ extern APTR SkipListBase; /* A global variable you have to declare somewhere and put the result of OpenLibrary (SKIPLISTLIBRARYNAME, 0) into. Otherwise the following function calls will crash. */ #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. */ #ifndef LIBCALL_DECLARATION #define LIBCALL_DECLARATION extern __inline #endif /* The declaration for library call functions in GNU C. These ones are declared external inline so they will only work if you compile in optimised mode (where inlines work). Otherwise, you may have to remove the extern keyword to avoid missing function errors during linking. But then it may have other problems if more than one object file included these declarations. I normally compile in optimised mode. */ LIBCALL_DECLARATION void InitSkipList (SkipListPointer TheList) { register SkipListPointer a0 __asm("a0") = TheList; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-30)" : /* Outputs. */ : "r" (a6), "r" (a0) /* Inputs. */ : "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. */ LIBCALL_DECLARATION SkipNodePointer AllocateSkipNode (SkipListPointer TheList, ULONG UserRecordSize, ULONG MemoryFlags) { register SkipNodePointer _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register ULONG d0 __asm("d0") = UserRecordSize; register ULONG d1 __asm("d1") = MemoryFlags; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-36)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (d0), "r" (d1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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. */ LIBCALL_DECLARATION void DeallocateSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-42)" : /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "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). */ LIBCALL_DECLARATION SkipNodePointer InsertSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register SkipNodePointer _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-48)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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. 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). */ LIBCALL_DECLARATION SkipNodePointer RemoveSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register SkipNodePointer _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-54)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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). */ LIBCALL_DECLARATION ULONG DeleteSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register ULONG _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-60)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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. */ LIBCALL_DECLARATION void DeleteAllSkipNodes (SkipListPointer TheList) { register SkipListPointer a0 __asm("a0") = TheList; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-66)" : /* Outputs. */ : "r" (a6), "r" (a0) /* Inputs. */ : "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. */ LIBCALL_DECLARATION SkipNodePointer FindSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register SkipNodePointer _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-72)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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). */ LIBCALL_DECLARATION SkipNodePointer FindBelowSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register SkipNodePointer _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-78)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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). */ LIBCALL_DECLARATION SkipNodePointer FindAboveOrEqualSkipNode (SkipListPointer TheList, SkipNodePointer TheNode) { register SkipNodePointer _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register SkipNodePointer a1 __asm("a1") = TheNode; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-84)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0), "r" (a1) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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). */ LIBCALL_DECLARATION ULONG GenerateRandomLevelNumber (SkipListPointer TheList) { register ULONG _res __asm("d0"); register SkipListPointer a0 __asm("a0") = TheList; register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-90)" : "=r" (_res) /* Outputs. */ : "r" (a6), "r" (a0) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ 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. */ LIBCALL_DECLARATION ULONG GetRANDOMCACHESIZE (void) { register ULONG _res __asm("d0"); register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-96)" : "=r" (_res) /* Outputs. */ : "r" (a6) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ return _res; } /* Returns the value of RANDOMCACHESIZE used by the library. */ LIBCALL_DECLARATION ULONG GetSKIPLISTLEVELCAP (void) { register ULONG _res __asm("d0"); register APTR a6 __asm("a6") = SkipListBase; __asm __volatile ("jsr a6@(-102)" : "=r" (_res) /* Outputs. */ : "r" (a6) /* Inputs. */ : "a0","a1","d0","d1", "memory"); /* Changed. */ return _res; } /* Returns the value of SKIPLISTLEVELCAP used by the library. */ #endif /* ifdef __GNUC__ */ /* Put other compiler's library declarations here, with the appropriate #ifdef for that compiler around them. Please send me a copy if you do, so that I can update the main version on AmiNet. */ #endif /* ifndef COMPILE_FOR_SKIPLIST_LIBRARY */ #endif /* ifndef SKIPLIST_H */