Simple and fast C library implementing a thread-safe API to manage hash-tables, linked lists, lock-free ring buffers and queues

Overview

libhl

C library implementing a set of APIs to efficiently manage some basic data structures such as : hashtables, linked lists, queues, trees, ringbuffers, red-black trees, priority queues, skip lists

The provided APIs are :

  • hashtable.[ch] : A thread-safe hashtable implementation
  • linklist.[ch] : Thread-safe double linked lists (with also a tag-based API)
  • rbtree.[ch] : A generic red/black tree implementation
  • fbuf.[ch] : Dynamically-growing flat buffers
  • queue.[ch] : A lock-free thread-safe flat (dynamically growing) queue implementation
  • rqueue.[ch] : A lock-free thread-safe circular (fixed size) queue implementation (aka: vaule-oriented ringbuffers)
  • rbuf.[ch] : Byte-oriented ringbuffers
  • refcnt.[ch] : Reference-count memory manager
  • binheap.[ch] : A binomial heap implementation (building block for the priority queue implementation)
  • pqueue.[ch] : A priority queue implementation
  • skiplist.[ch] : A skip list implementation
  • graph.[ch] : A generic graph implementation which allow defining chooser functions to determine paths

Provided APIs typically don't depend on each other and can be simply included in an existing project by copying both the .c and the .h files plus, if necessary, bsd_queue.h and/or atomic_defs.h into the project sourcetree.

The only exceptions are:

  • queue => depending on: refcnt
  • pqueue => depending on: binheap
  • graph => depending on: hashtable
Comments
  • Completion of error handling

    Completion of error handling

    opened by elfring 25
  • Issues

    Issues

    Some quick initial review of libhl turned up some issues with it.

    • The use of __USE_UNIX98 is a non-standard feature-test macro which should be replaced with _POSIX_C_SOURCE.
    • There are a lot of identifiers that begin with double underscore, for instance __foo. These identifiers are reserved by the implementation (compiler and libc.) perhaps using an hl_ prefix would be better. This is also seen in headers a lot too; __BINOMIAL_HEAP_H__ for instance.
    • Failure to use extern "C" in headers for __cplusplus This makes it hard to actually use the library for C++ as the symbol names can be mangled, thus not finding them at link stage.
    • #pragma pack(push, ...) is seen a lot. I'm not sure why you're packing these structures, for doing so can only lead to access violations on systems where the read/write may be unaligned and therefor illegal (PPC for instance.)
    • Checking for NULL when calling free. This is just redundant as free is required to do this check. Doing this only leads to false-positives when running the code through static-analysis tools like coverity.
    • Linked list is not thread-safe. get_entry_position needs to hold a lock for a new list node can be inserted into the list in another thread causing the position to be wrong. This can cause a whole slew of problems.
    • Failure to check return value of malloc. It can fail, without checking and handling this case, this library is not usable for robust systems.
    opened by graphitemaster 16
  • reserved identifier violation

    reserved identifier violation

    opened by elfring 8
  • Consider using size_t to indicate size for tagged values in linked list

    Consider using size_t to indicate size for tagged values in linked list

    Currently the tagged value structure for linked lists assumes that the length of a value can fit inside uint32_t. While I'd agree that value types larger than 0xffffffff bytes are pathological; use of size_t instead is of no harm and does not blindly break the interface contract of strlen and would allow you to remove the cast on this line in particular newval->vlen = (uint32_t)strlen((char *)val);.

    When representing the size of something it's always best to use size_t which is specifically guaranteed to be large enough to hold the size of any represent-able allocation or object in memory. This is why allocation functions expect size_t, why strlen returns it and why the sizeof operator does as well.

    opened by graphitemaster 4
  • replace __sync_fetch_and_OP with __sync_OP_and_fetch

    replace __sync_fetch_and_OP with __sync_OP_and_fetch

    Hi,

    I know that this patch is a bit irritating and it will not make any difference at all. But I wanted to contribute to such a cool software and found low hanging fruit :-)

    Note that I changed op in ATOMIC_READ to OR.

    Also, it's quite possible that I'm stupid and you wrote this for very good and very smart reasons :-) If so, just disregard me (but explain, please :-))

    P.S. return value of REFCNT_ATOMIC_INCREMENT/DECREMENT is never checked

    opened by ikruglov 4
  • Queue issue

    Queue issue

    hi, author. I use create 5 thread to pop queue's arg, there are 10000 args that push to queue. But sometimes, the process will be crash. And from the crash log, i see that queue will call refcnt free and then process crash.

    opened by Pccccccc 3
  • Tons of key-value pairs.

    Tons of key-value pairs.

    Hello, I am looking for a hashtable which can hold millions or even more key-value pairs. Can this hashtable hold such payload, and give a good performance when there is some rebalance?

    opened by lxyscls 3
  • Dynamic determination of the library build version

    Dynamic determination of the library build version

    opened by elfring 2
  • Addition of a build system generator

    Addition of a build system generator

    opened by elfring 2
  • Possible memory leak in binheap.c

    Possible memory leak in binheap.c

    I'm currently unable to share the code that triggers this memory leak but I have traced it using valgrind through the following calls:

    ==77605== 4,811,032 (4,066,576 direct, 744,456 indirect) bytes in 187,682 blocks are definitely lost in loss record 10 of 10
    ==77605==    at 0x483DFAF: realloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==77605==    by 0x10E6F3: binomial_tree_merge (binheap.c:399)
    ==77605==    by 0x10E8B3: binheap_insert (binheap.c:427)
    ==77605==    by 0x10D12E: pqueue_insert (pqueue.c:78)
    

    This is one of ten leaks that valgrind detects over a relatively short span of inserting items into a priority queue. It seems like the realloc from binomial_tree_merge is not beeing freed.

    I am doing something funky in that I am passing size_t values and casting them as void* types in my priority queue but this seems to work. I don't know if there is an underlying assumption anywhere that the values must be pointers (for example, this approach doesn't work with hastable.c because the hash function accesses the pointers; I don't believe pqueue or binheap do this, though).

    opened by mattgallivan 1
  • Reuse of

    Reuse of "libtool"?

    opened by elfring 1
  • The lock-free circular queue currently requires one extra page in its internal ringbuffer to work properly

    The lock-free circular queue currently requires one extra page in its internal ringbuffer to work properly

    The number of successfully read from rqueue sometimes less than the number of successfully write to rqueue.

    Here is the test code. https://gist.github.com/mingpepe/9d6ec5f17bdb60094d7fc980df3437ce

    But i am not found the bug yet.

    opened by mingpepe 2
Releases(libhl-3.1)
  • libhl-3.1(Sep 17, 2015)

    • fixed get_entry_position() in linklist.c (was not retaining a lock)
    • gracefully handling OOM conditions
    • minor cleanings
    • using autoconf to manage the project
    Source code(tar.gz)
    Source code(zip)
  • libhl-3.0(Jul 17, 2015)

  • libhl-2.9(Apr 1, 2015)

  • libhl-2.8(Dec 16, 2014)

  • libhl-2.7(Nov 5, 2014)

  • libhl-2.6(Sep 4, 2014)

  • libhl-2.5(Jul 10, 2014)

  • libhl-2.4(Jun 13, 2014)

    • Introduced a skip list implementation
    • Fixed a major bug in the bin heap implementation (and hence in the priority queue as well)
    • Exported some macros to facilitate the use of the atomic builtins in atomic_defs.h (were previously exported by refcnt.h)
    Source code(tar.gz)
    Source code(zip)
  • libhl-2.3(Jun 10, 2014)

  • libhl-2.2(Jun 5, 2014)

    • Reviewed the implementation of queue.c to get rid of a memory leak triggered sporadically by a race condition
    • The position-based API exposed by queue.h has been dropped
    • Minor bugfixes and cleanings in hashtable.c
    Source code(tar.gz)
    Source code(zip)
  • libhl-2.1.1(Jun 3, 2014)

  • libhl-2.1(Jun 2, 2014)

  • libhl-2.0(May 23, 2014)

  • libhl-1.9.1(Apr 29, 2014)

  • libhl-1.9(Apr 16, 2014)

    • Introduced an AVL tree implementation (as alternative to the RB tree already included in the library)
    • Generalized the default number comparators which are now shared among all of the provided tree library implementations (binheap avltree and rbtree)
    Source code(tar.gz)
    Source code(zip)
  • libhl-1.8(Apr 15, 2014)

    • bugfix in queue_push_left() to ensure incrementing the count of queued items
    • allow to check if an rqueue is empty by using rqueue_isempty()
    Source code(tar.gz)
    Source code(zip)
  • libhl-1.7(Apr 11, 2014)

    • Extended the rbuf API
      • introduced: rbuf_copy(), rbuf_move(), rbuf_used() and rbuf_available()
      • deprecated: rbuf_len()
    • Provided a walker API for both the priority queue and the binomial heap implementations
    • Bugfixes
    Source code(tar.gz)
    Source code(zip)
  • libhl-1.6.1(Apr 4, 2014)

    • reduced the gc threshold used for the refcnt context used by the lock-free queue implementation (helps reducing the memory footprint which would otherwise risk to become quite big without any good reason)
    Source code(tar.gz)
    Source code(zip)
  • libhl-1.6(Apr 2, 2014)

  • libhl-1.5(Mar 27, 2014)

  • libhl-1.4.1(Mar 8, 2014)

  • libhl-1.4(Feb 21, 2014)

    • introduced a red/black tree implementation (rbtree.[ch])
    • bugfixes in the hashtable implementation (potential race conditions when setting new values while the table is being grown)
    • cleanings and minor fixes
    Source code(tar.gz)
    Source code(zip)
  • libhl-1.3(Feb 6, 2014)

  • libhl-1.2.2(Jan 20, 2014)

  • libhl-1.2.1(Jan 9, 2014)

    • fixed all the issues reported by the clang static analyzer NOTE: all the fixed issues were minor and unlikely to happen so it's not vital to upgrade from libhl-1.2
    Source code(tar.gz)
    Source code(zip)
  • libhl-1.2(Jan 8, 2014)

  • libhl-1.1(Jan 6, 2014)

    Renamed 'rbuf' API to 'rqueue' API , since it actually implements a lock-free queue using a ring buffer to implement the queue. But by itself allows to push/pop pointers out of the ring buffer but it doesn't allow writing/reading actual bytes. 'rqueue' represents an alternative to 'queue' which is still a lock-free queue implementation which instead uses a (dynamically growing) double-linked list instead of a ring buffer.

    Introduced a new ring buffer API 'rbuf' which is instead an actual circular buffer and allows writing/reading bytes. It's opposed to fbuf which instead implements a flat buffer which grows linearly.

    The documentation has been improved across the whole library.

    Source code(tar.gz)
    Source code(zip)
  • libhl-1.0(Jan 2, 2014)

Owner
Andrea Guzzo
Andrea Guzzo
Rpmalloc - Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C

rpmalloc - General Purpose Memory Allocator This library provides a public domain cross platform lock free thread caching 16-byte aligned memory alloc

Mattias Jansson 1.7k Jan 5, 2023
A bounded single-producer single-consumer wait-free and lock-free queue written in C++11

SPSCQueue.h A single producer single consumer wait-free and lock-free fixed size queue written in C++11. Example SPSCQueue<int> q(2); auto t = std::th

Erik Rigtorp 576 Dec 27, 2022
Awesome-lockfree - A collection of resources on wait-free and lock-free programming

Awesome Lock-Free A collection of resources on wait-free and lock-free programming. ?? ?? ?? Even better resource from MattPD: C++ links: atomics, loc

Erik Rigtorp 1.4k Jan 1, 2023
Forkpool - A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20

riften::Forkpool A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20. This project uses C++20's coroutines to implement c

Conor Williams 129 Dec 31, 2022
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 7.4k Jan 3, 2023
A fast single-producer, single-consumer lock-free queue for C++

A single-producer, single-consumer lock-free queue for C++ This mini-repository has my very own implementation of a lock-free queue (that I designed f

Cameron 2.9k Jan 5, 2023
Fast, generalized, implementation of the Chase-Lev lock-free work-stealing deque for C++17

riften::Deque A bleeding-edge lock-free, single-producer multi-consumer, Chase-Lev work stealing deque as presented in the paper "Dynamic Circular Wor

Conor Williams 120 Dec 22, 2022
C++11 thread safe, multi-producer, multi-consumer blocking queue, stack & priority queue class

BlockingCollection BlockingCollection is a C++11 thread safe collection class that provides the following features: Modeled after .NET BlockingCollect

Code Ex Machina LLC 50 Nov 23, 2022
Thread pool - Thread pool using std::* primitives from C++17, with optional priority queue/greenthreading for POSIX.

thread_pool Thread pool using std::* primitives from C++11. Also includes a class for a priority thread pool. Requires concepts and C++17, including c

Tyler Hardin 77 Dec 30, 2022
Thread-pool - Thread pool implementation using c++11 threads

Table of Contents Introduction Build instructions Thread pool Queue Submit function Thread worker Usage example Use case#1 Use case#2 Use case#3 Futur

Mariano Trebino 655 Dec 27, 2022
Thread-pool-cpp - High performance C++11 thread pool

thread-pool-cpp It is highly scalable and fast. It is header only. No external dependencies, only standard library needed. It implements both work-ste

Andrey Kubarkov 542 Dec 17, 2022
GECOS: A lock-free synchronization mechanism

GECOS GECOS is a lock-free synchronization mechanism, and this repository compares various well-known mechanisms such as RCU and HP (Hazard Pointers).

null 6 Sep 9, 2021
Bikeshed - Lock free hierarchical work scheduler

Branch OSX / Linux / Windows master master bikeshed Lock free hierarchical work scheduler Builds with MSVC, Clang and GCC, header only, C99 compliant,

Dan Engelbrecht 81 Dec 30, 2022
Concurrent-deque - Lock-free concurrent work stealing deque in C++

A lock-free work-stealing deque This is a C++ implementation of the Chase-Lev deque, a concurrent single-producer, multi-consumer queue presented in t

Shubham Lagwankar 30 Jan 7, 2023
Operating system project - implementing scheduling algorithms and some system calls for XV6 OS

About XV6 xv6 is a modern reimplementation of Sixth Edition Unix in ANSI C for multiprocessor x86 and RISC-V systems. It was created for pedagogical p

Amirhossein Rajabpour 22 Dec 22, 2022
An ultra-simple thread pool implementation for running void() functions in multiple worker threads

void_thread_pool.cpp © 2021 Dr Sebastien Sikora. [email protected] Updated 06/11/2021. What is it? void_thread_pool.cpp is an ultra-simple

Seb Sikora 1 Nov 19, 2021
ThreadPool - A simple C++11 Thread Pool implementation

ThreadPool A simple C++11 Thread Pool implementation. Basic usage: // create thread pool with 4 worker threads ThreadPool pool(4); // enqueue and sto

Jakob Progsch 6.1k Jan 7, 2023
CTPL - Modern and efficient C++ Thread Pool Library

CTPL Modern and efficient C++ Thread Pool Library A thread pool is a programming pattern for parallel execution of jobs, http://en.wikipedia.org/wiki/

null 1.1k Dec 22, 2022
A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

A easy to use multithreading thread pool library for C. It is a handy stream-like job scheduler with an automatic garbage collector for non I/O bound computation.

Hyoung Min Suh 12 Jun 4, 2022