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
Short brief of MySKL - download
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
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
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