overview

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 concurrently and simultaneously across cores, 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.0.0) is implemented such that it performs no allocations (and so works with NUMA, stack, heap and shared memory) and compiles not just on a freestanding C89 implementation, but on a bare C89 implementation.

The library is completely documented (every API, function, macro, struct, define, typedef and enum) and ships with a complete test suite and a partial benchmark suite.

Current users include AT&T, Red Hat and Xen.

resources

Home Blog Forum Mailing Lists Documentation Local Git GitHub Contact

license

You are free to use this library in any way. Go forth and create wealth!

If for legal reasons a custom 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.

data structures, processors and out-of-the-box toolchain support

The following matrix details out-of-the-box support, i.e. toolchains for which build files ship with the library and for those toolchains, which processors have been ported to. For other processors, the porting abstraction layer provides an easy-to-implement mechanism for adding support. For other toolchains you will need to provide your own build files.

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.2 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.0

benchmarking

btree (add-only, unbalanced)
ARM32	MIPS32	x64		Penny Arcade
Raspberry Pi 2 Model B	Ci20	AWS dedicated VM	Core i5	Bar

freelist
ARM32	x64
Raspberry Pi 2 Model B	AWS dedicated VM	Core i5

queue (unbounded, many producer, many consumer)
ARM32	x64
Raspberry Pi 2 Model B	AWS dedicated VM	Core i5

downloads

user provided downloads