Introduction
Introduction
Welcome to liblfds, a portable, license-free, lock-free data structure library written in C.
Lock-free data structures are process, thread and interrupt safe (i.e. the same data structure instance can be safely used across processes, threads and both inside and outside of interrupt handlers), never sleep (and so are safe for kernel use when sleeping is not permitted), operate without context switches, cannot fail (no need to handle error cases, as there are none), perform and scale literally orders of magnitude better than locking data structures, and liblfds itself (as of release 7.1.1) is implemented such that it performs no allocations (and so can be used with the stack, heap or shared memory) and compiles not just on a freestanding C89 implementation, but on a bare C89 implementation.
Currently liblfds is composed of three components; the library itself, a test suite and a benchmark suite, where the test and benchmark suites are implemented as libraries (libtest and libbenchmark) so they can be used on arbitrary platforms, where both offer their complete functionality through a simple and minimal API, along with two thin command line veneers (test and benchmark) provided for convenience for the wide range of platforms which do offer hosted environments.
Out-of-the-Box Supported Data Structures and Platforms
The library ships with build files for a small range of popular toolchains and platforms. The library provides a porting abstraction layer to mask platform differences and the porting abstraction layer, for this small range of popular toolchains and platforms, has been fully implemented.
To use the library on unsupported platforms, the porting abstraction layer must be implemented. To use the library with unsupported toolchains, the build files must be provided.
Version 7.0.0 provided Microsoft Visual Studio solution files (2012 and 2013, with the respective WDK for each version), but the staggeringly high cost of creating these build files, and Microsoft's conduct pushing Windows 10 onto users, has led to their omission from this release.
Note not all processors support all data structures, due to atomic operation support varying by processor.
| Release 7.1.1 | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| GCC and gnumake | GCC, gnumake and kbuild1 | Microsoft C compiler and gnumake | WDK 7.12 | ||||||||||
| Alpha, IA64, MIPS64, POWERPC32/64, SPARC32/64 |
MIPS32 | ARM64 | x86 | ARM32, x64 | Alpha, IA64, MIPS32/64, POWERPC32/64, SPARC32/64 |
ARM64 | ARM32, x86 | x64 | x64 | x86 | IA64 | x64, x86 | |
| Binary Tree (add-only, unbalanced) |  |
 |
 |
|
|
|
|
|
 |
|
|
|
|
| Freelist |  |
|
|
|
|
|
|
|
|
|
|
|
|
| Hash (add-only) | |
|
|
|
|
|
|
|
|
|
|
|
|
| List (add-only, singly-linked, ordered) | |
|
|
|
|
|
|
|
|
|
|
|
|
| List (add-only, singly-linked, unordered) | |
|
|
|
|
|
|
|
|
|
|
|
|
| PRNG | |
|
|
|
|
|
|
|
|
|
|
|
|
| Queue (bounded, many producer, many consumer) | |
|
|
|
|
|
|
|
|
|
|
|
|
| Queue (bounded, single producer, single consumer) | |
|
|
|
|
|
|
|
|
|
|
|
|
| Queue (unbounded, many producer, many consumer) | |
|
|
|
|
|
|
|
|
|
|
|
|
| Ringbuffer | |
|
|
|
|
|
|
|
|
|
|
|
|
| Stack | |
|
|
|
|
|
|
|
|
|
|
|
|
1. This is the Linux kernel toolchain
2. This is a Windows kernel toolchain
| Key | |
|---|---|
|
supported, compiled and tested |
|
supported and compiled but not tested (test ought to pass, but it hasn't been run, so it won't) |
|
supported but not compiled or tested (so it ought to compile, but it hasn't been done, so it won't) |
|
not (yet) supported (never compiled, and expected not to compile successfully) |
|
cannot be implemented on this platform |
| GCC | GCC >= 4.1.21 and GNUmake >= 3.8.1 |
| Microsoft C compiler | Development uses Microsoft Windows SDK 7.1, but MSVC 2008 or later should be fine, and GNUmake 3.8.1 |
| WDK 7.1 | Windows Driver Kit 7.1.1 |
1. If GCC >= 4.7.3 is used, the new atomic intrinsics introduced with that version are used
License
You are free to use this library in any way. Go forth and create wealth!
If for legal reasons a specific, well-known licence is required, the license of your choice will be granted, and license is hereby granted up front for a range of popular licenses : the MIT license, the BSD license, the Apache license, the GPL and LPGL (all versions thereof) and the Creative Commons licenses (all of them). Additionally, everything is also placed in the public domain.
Porting
All liblfds components - liblfds itself, libtest, libbenchmark, libshared, test and benchmark - provide a porting abstraction layer which acts to mask platform differences. Porting is the act of implementing on your platform the defines, typesdefs and functions which make up a porting abstraction layer.
The porting abstraction layers are arranged in part as a set of three header files and in part as source files, which implement functions. The three header files consist of one each for the compiler, operating system and processor, where each file provided such parts of the porting abstraction layer as come from each source, with each file using the pre-processor #if directive with compiler and/or operating system defined macros to restrict each implementation to the correct platform.
As such, it's not possible to succinctly state exactly what ports are supported out-of-the-box, as an implementation can span many potential platforms - e.g. the compiler implementation which matches GCC provides the compiler part of the porting abstraction layer for GCC for all operating systems and all processors.
In general, out-of-the-box support consists of Windows user-mode and kernel-mode, and UNIX (Android, Linux, Solaris, etc) with GCC user-mode and kernel-mode.
For documentation, see the Porting Guide (liblfds), Porting Guide (testing) and Porting Guide (benchmarking)
Building
As of this release, all versions are released together. This is necessary for libbenchmark, which benchmarks earlier versions of liblfds as well as the current versions (although currently this only extends to release 7.0.0). Within the liblfds7.1.1 directory, there are two top-level directories, liblfds711 and test_and_benchmark. Each separate component has a directory called build, which in turns has one directory per supported platform, where that directory contains the build files (makefiles, MSVC solutions, etc) for that platform. The following tree omits the subdirectories in the src subtree, for brevity.
├── liblfds6.0.0
├── liblfds6.0.1
├── liblfds6.1.0
├── liblfds6.1.1
├── liblfds7.0.0
└── liblfds7.1.1
├── liblfds711
│ ├── bin
│ ├── build
│ │ ├── gcc_gnumake
│ │ ├── gcc_gnumake_kbuild
│ │ ├── msvc_gnumake
│ │ └── wdk_7.1
│ ├── inc
│ │ └── liblfds711
│ ├── obj
│ └── src
└── test_and_benchmark
├── benchmark
│ ├── bin
│ ├── build
│ │ ├── gcc_gnumake_hosted_liblfds711_liblfds700
│ │ ├── gcc_gnumake_hosted_liblfds711_liblfds700_libnuma
│ │ └── msvc_gnumake_liblfds711_liblfds700
│ ├── obj
│ └── src
├── libbenchmark
│ ├── bin
│ ├── build
│ │ ├── gcc_gnumake
│ │ ├── gcc_gnumake_kbuild
│ │ ├── msvc_gnumake
│ │ └── wdk_7.1
│ ├── inc
│ │ └── libbenchmark
│ ├── obj
│ └── src
├── libshared
│ ├── bin
│ ├── build
│ │ ├── gcc_gnumake
│ │ ├── gcc_gnumake_kbuild
│ │ ├── msvc_gnumake
│ │ └── wdk_7.1
│ ├── inc
│ │ └── libshared
│ ├── obj
│ └── src
├── libtest
│ ├── bin
│ ├── build
│ │ ├── gcc_gnumake_hosted
│ │ ├── gcc_gnumake_kbuild
│ │ ├── msvc_gnumake
│ │ └── wdk_7.1
│ ├── inc
│ │ └── libtest
│ ├── obj
│ └── src
└── test
├── bin
├── build
│ ├── gcc_gnumake_hosted
│ └── msvc_gnumake
├── obj
└── src
The libraries compiles to either a static or shared library, to their bin directories.
The test and benchmark programmes compile to command line binaries, to their bin directories.
For documentation, see the Building Guide (liblfds), Building Guide (testing) and Building Guide (benchmarking)
Usage
The liblfds library has a set of header files, one per data structure, found in liblfds711/inc/, but you only include liblfds711/inc/liblfds711.h. Include the header file as you would normally, link to the library as you would normally. Voilà!
The test and benchmark programmes are a command line binaries and are run by hand from the command line, where no arguments or "-h" will display help text.
For documentation, see the Usage Guide (liblfds), Usage Guide (testing) and Usage Guide (benchmarking)