Derived from: None
Declared in: PSkipList.h
This class is useful for storing items for later use. The skip list is highly optimized for inserting items into the list and removing items from the list. Moreover, the skip list is also highly optimized for getting and setting an existing item in the list. The reason is that the skip list simply "skips" a large amount of items, when searching for a specific item. The skip list does not function as an ordinary list, as it uses keys, and not indexes. That is, all items must be associated with a unique key before inserting it into the list. This key is used as a search key for getting, setting and removing a specific item from the list. The skip list cannot insert an item, if it has a key, that is already used for another item in the list. For more information about the skip list, you should visit the following page: http://www.csihq.com/CSI/pubs/skiplist.html.
The PSkipList class is a template class defined the following way:
template<class TYPE, class KEY_TYPE> class PSkipList;
The first template parameter specifies the type of the items to store in the list. The second template parameter specifies the type of the key, which each item should be associated with, when accessing items in the list.
Most of the operations on the skip list uses a key for accessing an item. If an operation tries to overwrite an item that already exist in the list, or an operation tries to access an item that do not exist in the list, an PKeyException will be thrown.
The PSkipList is not thread safe as it is. If you have more than one thread to access the list, you can use any of the synchronize classes to do that.
When construction a skip list an optional maxLevel parameter can be specified with the default constructor, which specifies the max level of the skip list. The more items that is stored into the list, the higher the internal level the skip list will obtain. This level depends on the number of items stored in the list. If e.g. 2^5 = 32 items is stored in the list, the internal level will be 5. The higher the level get, the more memory the skip list will need in order to guarantee that the skip list will remain extremely fast, even if many items is stored in the list. The maxLevel parameter ensure that the internal level of the skip list will not grow higher than the limit of maxLevel. This is useful, if the max number of items that will be stored in the list, is known in advantage. If e.g. max 1000 items at a time will be stored in the list, the maxLevel should be set to log2(1000) = 10. However, the maxLevel parameter DOES NOT restrict the number of items that can be stored in the list. It just means that the skip list will remain extremely fast, when 2^10 = 1024 or less items are stored in the list. If the maxLevel is set to 10, and 2000 items will be stored in the list, the skip list will not be as fast as it would be by setting the maxLevel to 11. By limiting the max level, memory will be saved due to the internal structure of the skip list.
PSkipList(uint8 maxLevel = 32);
The constructor creates an empty skip list, which is ready to be used. The maxLevel parameter is optional, and specifies the max level of the skip list. This parameter is described in further detail in the overview of this class.
~PSkipList()
~PSkipList(void);
The destructor will empty the list and destroy it.
CountItems()
int32 CountItems(void) const;
This function will return the number of items in the list.
GetAndRemoveItem()
TYPE GetAndRemoveItem(const KEY_TYPE key); throw(PKeyException);
This function will return an item from the list associated with the specified key. This item is removed from the list. If an item does not exist in the list with the specified key, a PKeyException will be thrown.
GetAndSetItem()
TYPE GetAndSetItem(const KEY_TYPE key, const TYPE newItem); throw(PKeyException);
This function will return an item from the list associated with the specified key. The item in the list will be replaced with the new item. If an item does not exist in the list with the specified key, a PKeyException will be thrown.
GetItem()
TYPE GetItem(const KEY_TYPE key) const; throw(PKeyException);
This function will return an item from the list associated with the specified key. If an item does not exist in the list with the specified key, a PKeyException will be thrown.
HasKey()
bool HasKey(KEY_TYPE key) const;
This function will test if the list has an item with the specified key. If an item do exist with the specified key, it will return true. Otherwise it will return false.
InsertItem()
void InsertItem(const KEY_TYPE key, const TYPE item); throw(PKeyException);
This function will insert an item into the list associated with the specifed key. If an item already exist in the list with the specified key, then a PKeyException will be thrown.
IsEmpty()
bool IsEmpty(void) const;
This function will test if the list is empty. If the list is empty, it will return true. Otherwise it will return false.
MakeEmpty()
void MakeEmpty(void);
This function removes all items from the list.
RemoveItem()
void RemoveItem(const KEY_TYPE key); throw(PKeyException);
This function will remove an item in the list associated with the specified key. If an item does not exist in the list with the specified key, a PKeyException will be thrown.
SetItem()
void SetItem(const KEY_TYPE key, const TYPE newItem); throw(PKeyException);
This function will replace an item in the list, associated with the specified key, with a new item. If an item does not exist in the list with the specified key, a PKeyException will be thrown.
operator =
const PSkipList<TYPE, KEY_TYPE, maxLevel>& operator = (const PSkipList<TYPE, KEY_TYPE, maxLevel> &skiplist);
Assigns the skip list with another skip list. All items in the assigned list is copied into the list.