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

Data Structures

The following data structures are as of the latest release (7.1.0) provided (but note support varies by processor, as atomic support varies by processor);

• Binary Tree (add-only, unbalanced)
• Freelist
• Hash (add-only)
• List (add-only, ordered, singly-linked)
• 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

Out-of-the-Box Support

In short, GCC 4.1.2 or greater for any UNIX (Linux, Android, etc) user-mode (all processors supported), and kernel-mode (kbuild) for Linux (all processors supported). MSVC 2008 (command line compilers with gnumake - no solution files) or greater for Windows user-mode (x64, x86 and ARM32), and WDK 7.1 for Window kernel-mode (IA64, x64, x86).

Note that not all data structures are supported on all processors, as atomic support varies by processor.

License

You are free to use this code 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 for convenience 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, this library (which is to say, the source code, build files, documentation, everything) is placed in the public domain.

Concurrent Use of Multiple Versions

Every version equal to or greater than 6.0.1 and 6.1.1 can be compiled and linked in the same build, i.e. you can use 6.0.1, 6.1.1 and 7.1.0 in the same code base. All public entities in the liblfds code base carry a version-unique prefix, so each version is effectively in its own 'namespace'.

The reason for this is to help with productivity and maintenance; when a new liblfds release is made, existing code does not have to be touched at all, and so does not have to be revalidated or retested.

Releases

Versioning from 6.0.0 onwards follows GCC style, "[major].[minor].[bugfix]". Prior to this versioning was simply an incrementing integer.

Versions 1 to 6 are depreciated and unsupported (they were released over a short period at the end of 2009, culminating in release 6, which was unchanged for three years.

Version 6.0.0 is a wholly unchanged copy of version 6, except with the version-unique prefix prepended to every public variable, define, etc, so that it can be compiled and linked in parallel with later releases (which cannot be done with releases 1 to 6 (six)).

Version 6.1.0 fixes a range of race-condition bugs in 6.0.0 (and, by implication in 6, as 6.0.0 is apart from name changes indentical to 6).

Versions 6.0.0 and 6.1.0 are depreciated, because one - ahhh! - public entity was overlooked and missed in testing and so they cannot in fact be used with other versions of the library. This issue was fixed in 6.0.1 and 6.1.1.

7.1.0 is the current release.

Porting

The library, benchmark and test programme each provide porting abstraction layers which acts to mask platform differences. Porting is the act of implementing the porting abstracton layer on your platform.

Usage

For 6.*.*, once built, there is a single header file, /inc/liblfds[version].h and a single library file /bin/liblfds[version].*.

For 7.0.0 and 7.1.0, once built, the header files are arranged as a single master file, /inc/liblfds.7nn.h, together with a directory of header files, /inc/liblfds7nn, one per data structure, which are included by the master header file, and the library file is /bin/liblfds7nn.*.

Testing

The library comes with a command line test program. This program requires threads. As such, it is only suitable for platforms providing thread support and which can execute a command line binary. Currently this means the test program works for Windows user-mode and platforms which support POSIX threads and provide a hosted implementation (e.g. Linux user-mode).

Benchmarking

The library comes with a command line benchmark program. This program requires threads. As such, it is only suitable for platforms providing thread support and which can execute a command line binary. Currently this means the test program works for Windows user-mode and platforms which support POSIX threads and provide a hosted implementation (e.g. Linux user-mode).