MySKL is a small library that implements a thread-safe skip list data structure (SKL) by means of that we can implement a fast kind of lists, much faster than simple linked lists (SLL). Besides, pretty much anything possible with SLL can be done as well using SKL. In a such data structure, primary operations such as insertion, deleting and searching, have almost the same complexity as in AVL trees, but the former is easier to implement and thus maintain.

Any advice or constructive criticism is greatly appreciated
Mail: ghangenit[AT]users.sourceforge.net

Short brief of MySKL - download here
================================

• I decided to publish this small standalone library - that is a tiny part of a more wide-breath project concerning Gis Data Structures - since could be useful to someone, maybe only as a didatic example: it uses a good and fast pseudo random number generator (Mersenne Twister), an internal tracing/debugging system - Fred Fish's debugging library (extended a bit to deal with threads) - etc.
• Library has been tested against a good red-black tree implementation (you can find it here) Benchmark results, as measured on a Intel 2.0 GHz dual core with 2 GB ram, are close: between 0m9.763s and 09.859s for this library and between 0m8.854s and 0m8.874s for the red-black implementation. These times are user times. It goes without saying that these benchmarks do not prove anything, but I reported them for completeness.
• It is written in C, compatible with C++ and compilable both under Linux and Windows. It can be either compiled as a shared or static library on Linux or as a DLL on Windows, by using MinGW (native compilation - since version 0.2.1) or Cygwin (not native compilation - since version 0.2.0). Library is also compilable using Sun studio compiler: tested with version 12.2.
• As far as the pseudo random number generator (PRNG), in a such data structure, it is used to assign a level to a node. An alternative implementation that may be used to accomplish this task and that does not rely on a PRNG is also provided by this library. It seems to be slightly faster, even though it consumes a greater amount of memory. It is not enabled by default.
• This library tries to guarantee thread safety by using the readers/writers technique. In this way if many read operations are performed in parallel, they can proceed freely, without waiting for the end of previous ones. On the contrary, if a writer has already gained the access to a critical section, readers have to wait in order to not working on unstable data.
• MySKL manages memory with care: no memory leaks found while using Valgrind to test it. This awesome tool was also used to test the library behavior in the presence of concurrent operations and no race conditions were reported.
• It can deal with generic data types and support double linked lists. By default, this kind of support is not enabled as the amount of memory requested would be greater compared to single linked lists and there would also be a slight decrease in performance.
• Since version 0.2.0 data are no longer contained (as pointers) within list nodes and are no more explicitly managed by the library. More precisely, each node of the list is contained within the associated user's data. This helps to reduce the data access overhead as it saves one pointer indirection per node and increases data locality.
• MySKL includes some executable files - created during compilation - that aim to show some examples of the MySKL usage and, besides, work as automatic tests for the correctness of the library - even though they can not guarantee from the absence of bugs :-(
• MySKL provides about 34 methods: two of these are also useful to check the result of some operations: one prints the skiplist in the form of memory addresses, the other displaies a list as it would be if we put it down on paper