SimCList is a high quality C (C++ embeddable) library for handling lists. It exploits several advanced techniques for improving performance, including freelists, sentinels, automatic sort algorithm selection, sort randomization, mid pointer and optional multithreading.
SimCList takes about 12 kB and provides features such as automatic serialization/de-serialization, sorting, hashing, and element autocopy.
SimCList is available for free, under restrictions imposed by the BSD license.
SimCList is used projects ranging from Intrusion Detection to Embedded systems to Computer Vision.
SimCList has a gun on its head! Can you rescue it?
Assigned!
SimCList API is good because:
total
The library itself is very performant and makes a good compromise between performance in terms of time and space:
As a general rule, you don't want to implement your own linked list code whenever you need operations beyond the trivia. Linked lists involve complex pointer manipulation, which makes them hard to test and optimize. By using SimCList you leverage hours of optimization and testing from millions of runs of others.
Have a look at a sneak peak into the API for an example-driven introduction to SimCList.
The library header file simclist.h itself is fully documented.
An automatically generated html prospect of the API is also available.
The SimCList library is thread safe, meaning that many threads can run SimCList operators on different lists concurrently without hurt, or also read operations on the same list.
However, of course, no safety guarantee is made for performing concurrently write+write or read+write operations on the same list (eg: insertion, deletion, sorting, ...). For performance and portability reasons, protecting such operations from concurrency is left to the library adopter.
SimCList has been designed with ease of use and performance in mind. There is some example factors that have been taken into account, and against which the code has been optimized when implementing SimCList:
Many parts of SimCList's code have been deeply improved with profiling analysis.
Since version 1.4, SimCList decorates the interface with restrict specifiers to guide the compiler to do better optimization (as such, it requires the compiler to interpret C99 syntax -- -std=c99).
These are some results:
| description | time | code |
|---|---|---|
| 10 million insertions of one same element, without element copy | 0m1.153s | ins.c |
| insertion of 1M elements with autocopy, then extraction of 1k elements at random positions | 0m1.278s | ext.c |
| insertion of 1M random elements with autocopy, then sorting | 0m1.094s | sort.c |
| insertion of 1M random elements with autocopy, then sorting, with SimCList threading enabled | 0m0.897s | sort.c |
Test bench:
SimCList is licensed BSD. See the BSD license content for details.
You can embed simclist into your source code (because of the BSD
license) or use it as a dynamic link library.
For the former: just download simclist and include the
simclist.c and simclist.h files into your
package. Remind to compile with -std=c99 to enable C99
syntax parsing.
For the latter: there is a buildfile in the package that makes it
automatically.
Armando is developing a consistent regression test suite for SimCList. All releases of SimCList are thorougly tested against it before making it to public.
In previous history: one bug has been found in simclist-1.0 in
list_concat(), whose output could become inconsistent after element
deletion. One bug in simclist-1.1 in list_insert_at(), whose output
could become inconsistent when inserting in even-sized lists in
position 0. One in simclist-1.4.4 where clearing a list with assertions
enabled would trigger an assertion violation.
If you encounter
new bugs, or you have a comment or feature request, please report to mij@bitchx.it.
When reporting bugs like crashes, a core dump describing the the event in detail is desirable. For better tracking, debug symbols should be enabled in SimCList. They can be easily activated by uncommenting the apposite line in SimCList makefile and recompiling.
If you want to keep up with new releases and fixes, subscribe the SimCList freshmeat node or follow the SimCList release feed.