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.
Home Blog Forum Mailing Lists Documentation Local Git GitHub Contact
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.
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 |
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 |
date | release | source | md5sum | release note | comment |
---|---|---|---|---|---|
25 Sep 09 | 1 | zip tar.bz2 |
726a344141ed486260e73d2e4cd2f822 e6573df1e2b4cb8818de826f4440858b |
here | Deprecated. |
05 Oct 09 | 2 | zip tar.bz2 |
7afc44da5e1d9fba45d34e2063cadb76 5afc460fb47ae206415c127bb72cd4c1 |
here | Deprecated. |
25 Oct 09 | 3 | zip tar.bz2 |
c5452a275e1c359b3e97bc281e3c3d8d e1cfbea18a28949ee17d5c1b84ed34d0 |
here | Deprecated. |
07 Dec 09 | 4 | zip tar.bz2 |
7be3eec9834be7f6603f0bb03490546a b11527ebaa25096dbccb380ab4d39004 |
here | Deprecated. |
19 Dec 09 | 5 | zip tar.bz2 |
5329a3348abd8d7b8d7cb44f796de393 dd1df6553b54ad3e342e545ce7b6f306 |
here | Deprecated. |
29 Dec 09 | 6 | zip tar.bz2 |
1bbb808f56082c7206efe2c9f3a36e47 cc9e07e8a7b972eb9fe4bbeb5db6eb7b |
here | Deprecated. |
18 Dec 12 | 6.0.0 | zip tar.bz2 github |
6eef0b2c8b56579d428a5d0d6d1d3bf5 a782de14d10a1d61c0423086f09107d9 |
here | Wholly identical to 6, except all public entities are prefixed with "lfds600_". This release is a stepping-stone from 6 into per-version 'namespaces'. |
31 Dec 12 | 6.1.0 | zip tar.bz2 github |
983d9eef3b0d2b123e0d27a7af4c90ad 5dc9ba7547b987bbbc3191224c301a16 |
here | Maintenance release. |
2 Jan 13 | 6.0.1 | zip tar.bz2 github |
fd9668a28d568156fb6a2b482f8d1856 bd331c6cb53f66ca8959dfceec840eed |
here | Bugfix release. |
2 Jan 13 | 6.1.1 | zip tar.bz2 github |
ec167c570cc0c5bc9a2b0d7c3424e4a3 ff3c5f1cb7805ab5b2d63c49d5e589e3 |
here | Bugfix release. |
29 Dec 15 | 7.0.0 | zip tar.bz2 github |
a320eb3bd77bbffabe02b665479006e3 552b613d454fc3e2aa6c54a4f86fca75 |
here | Finally. |
31 May 16 | 7.1.0 | zip tar.bz2 github |
e797b13362eadf9eb43cfab84bc8b2ff bad98e370d9a6035919f421b929ae22e |
here | New queue, PRNG, benchmark app, plus general performance improvements. |
20 Feb 17 | 7.1.1 | zip tar.bz2 github |
0bf8b2141062fc375c502dd5c85e828c 2a4cb6d64d8d9333b050059e4a1b7782 |
here | Bugfix release. |
date | release | source | md5sum | release note | comment |
---|---|---|---|---|---|
17 Aug 14 | 6.1.1 | patch file | 85353a6719ac6fc498aa904d0c329b47 | n/a | OSX patch kindly provided by Karl Yerkes |
4 Aug 15 | 6.1.1 | patch file | e9df09f41257d3c791988427c169c967 | n/a | OSX patch kindly provided by Ben Jolitz |