A C++17 Lock-Free Data Structure Library

Documentation is currently outdated and invalid.

This is a library for lock-free data structures with the following features.

Written purely in standard C++17 with no platform-dependent code.
Header-only.
Designed for low worst-case latency.
Designed for exception safety.
Provides first-class support, like emplace construction, for aggregate types.

Requirements
Repository Structure
Build
Unit Test
Reference Doc

Requirements

A decent C++17 implementation. Tested:
- MacPorts clang 6.0.0
- MacPorts gcc 7.3.0
64-bit pointer to avoid padding atomic.
Lock-free 128-bit atomic.

Repository Structure

doc.............Reference doc
lf..............Library headers
test
  unit_test

Build

The C++ standard does not require atomics, other than std::atomic_flag, to be lock-free. Lock-free 128-bit atomic, in particular, demands both CPU and C++ implementation support, plus proper build setup.

All modern x86-64 CPUs provide support^[r].
C++ implementation supportability
- MacPorts clang 6.0.0 is verified to provide support.
- Supportability is unclear for MacPorts gcc 7.3.0.
- It is said that MSVC does not provide support.
For clang/gcc, compile with -mcx16.

Here are some notes for verifying a genuine lock-free build. That said, is_lock_free() test is unreliable in practice.

Unit Test

Build all source files in test/unit_test to get the unit test executable. For example, using MacPorts clang 6.0.0, the following command line builds the test executable bin/unit_test.

clang++-mp-6.0 test/unit_test/*.cpp -o bin/unit_test -std=c++17 -mcx16

Note that gcc may additionally need -latomic.

The test executable uses Catch2 and supports various command line arguments. There is a dedicated test case named foo bar for each header lf/foo/bar.hpp. Executing with no argument runs all test cases.

Reference Doc

The library is still under early development. Reference for finished components can be found here.

Planned lock-free structures: