SimCList – A C library for Lists

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!

The SimCList API

SimCList API is good because:

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.

Documentation

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.

Thread safety

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.

Performance

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:

License, Getting & Installing, Bugs

License

SimCList is licensed BSD. See the BSD license content for details.

Getting & Installing

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.

  1. download the latest SimCList package (version 1.5, see Changes)
  2. decompress it and get into its top dir
  3. run cmake . there (mind the dot). This generates Makefiles for your platform.
  4. run make there. This provides a libsimclist.so or libsimclist.dylib library file in the current dir.

Bugs and the rest

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.