M*LIB: Generic type-safe Container Library for C language

1. Overview
2. Components
3. Build & Installation
4. How to use
5. Performance
6. OPLIST
7. Memory Allocation
8. Emplace construction
9. Errors & compilers
10. External Reference
11. API Documentation
    1. Common Interface
    2. Sequence containers
       1. Array
       2. List
       3. Intrusive list
       4. Double end queue
       5. Fixed size queue / stack
    3. Associative containers
       1. Dictionary
       2. Red/Black Tree
       3. B+ Tree
    4. Misc containers
       1. Priority queue
       2. Generic Tree
       3. Tuple
       4. Variant
    5. Thread containers
       1. Shared Fixed size queue
       2. Atomic Shared Register
       3. Shared pointers
       4. Worker threads
    6. Dataset
       1. String
       2. Byte String
       3. Bitset
    7. Algorithms
       1. Generic algorithms
       2. Function objects
    8. Serialization
       1. JSON Serialization
       2. Binary Serialization
    9. Uniform interface
    10. Core preprocessing
    11. C11 compatibility headers
        1. Thread
        2. Atomic
12. Global User Customization
    1. Exception handling
    2. Memory context Customization
13. License

Overview

M*LIB (M star lib) is a C library enabling to define and to use generic and type safe container in C, aka handling generic containers in pure C language. The encapsulated objects can have their own constructor, destructor, operators or can be basic C type like the C type 'int': both are fully supported. This makes it possible to construct fully recursive container objects (container-of[...]-container-of-type-T) while keeping compile time type checking.

This is an equivalent of the C++ Standard Library, providing vector, deque, forward_list, set, map, multiset, multimap, unordered_set, unordered_map, stack, queue, shared_ptr, string, variant, option to standard ISO C99 / C11. There is not a strict mapping as both the STL and M*LIB have their exclusive containers:

See here for details. M*LIB provides also additional concurrent containers to design properly multi-threaded programs: shared register, communication queue, ...

M*LIB is portable to any systems that support ISO C99. Some optional features need at least ISO C11.

M*LIB is only composed of a set of headers. There is no C file, and as such, the installation is quite simple: you just have to put the header in the search path of your compiler, and it will work. There is no dependency (except some other headers of M*LIB and the LIBC).

One of M*LIB design key is to ensure safety. This is done by multiple means:

• in debug mode, defensive programming is extensively used: the contracts of the function are checked, ensuring that the data are not corrupted. For example, strict Buffer overflow are checked in this mode through bound checking or the intrinsic properties of a Red-Black tree (for example) are verified. Buffer overflow checks can still be kept in release mode if needed.
• as few cast as possible are used within the library (casts are the evil of safety). Still the library can be used with the greatest level of warnings by a C compiler without any aliasing warning.
• the genericity is not done directly by macro (which usually prevent type safety), but indirectly by making them define inline functions with the proper prototypes: this enables the user calls to have proper error and warning checks.
• extensive testing: the library is tested on the main targets using Continuous Integration with a coverage of the test suite of more than 99%. The test suite itself is run through the multiple sanitizers defined by GCC/CLANG (Address, undefined, leak, thread). The test suite also includes a comparison of equivalent behaviors of M*LIB with the C++ STL using random testing or fuzzer testing.
• static analysis: multiple static analyzer (like scan-build or GCC fanalyzer or CodeQL) are run on the generated code, and the results analyzed.

Other key designs are:

• do not rewrite the C library and just wrap around it (for example don't rewrite sort but stable sort),
• do not make users pay the cost of what they don't need.

Due to the unfortunate weak nature of the C language for pointers, type safe means that at least a warning is generated by the compiler in case of wrong type passed as container arguments to the functions.

M*LIB is still quite-efficient: there is no overhead in using this library rather than using direct C low-level access as the compiler is able to fully optimize the library usage and the library is carefully designed. In fact, M*LIB is one of the fastest generic C/C++ library you can find.

M*LIB uses internally the malloc, realloc and free functions to handle the memory pool. This behavior can be overridden at different level. Its default policy is to abort the program if there is a memory error. However, this behavior can also be customized globally. M*LIB supports also the exception error model by providing its own implementation of the try / catch mechanism. This mechanism is compatible with RAII programming: when an exception is thrown, the destructors of the constructed objects are called (See m-try for more details).

M*LIB may use a lot of assertions in its implementation to ensure safety: it is highly recommended to properly define NDEBUG for released programs.

M*LIB provides automatically several serialization methods for each containers. You can read or write your full and complex data structure into JSON format in a few lines.

M*LIB is distributed under BSD-2 simplified license.

It is strongly advised not to read the source to know how to use the library as the code is quite complex and uses a lot of tricks but rather read the examples.

In this documentation, * shall will be used to indicate a user constraint that is mandatory to follow under penalty of undefined behavior. * should will be used to indicate a recommendation to the user.

All pointers expected by the functions of the library shall expect non-null argument except if indicated.

Components

The following headers define containers that don't require the user structure to be modified:

• m-array.h: header for creating dynamic array of generic type,
• m-list.h: header for creating singly-linked list of generic type,
• m-deque.h: header for creating dynamic double-ended queue of generic type,
• m-queue.h: header for creating static queue or stack of generic type,
• m-prioqueue.h: header for creating dynamic priority queue of generic type.
• m-dict.h: header for creating unordered associative array (through hashmap) or unordered set of generic type,
• m-rbtree.h: header for creating ordered set (through Red/Black binary sorted tree) of generic type,
• m-bptree.h: header for creating ordered map/set/multimap/multiset (through sorted B+TREE) of generic type,
• m-tree.h: header for creating arbitrary tree of generic type,
• m-tuple.h: header for creating arbitrary tuple of generic types,
• m-variant.h: header for creating arbitrary variant of generic type,

The available containers of M*LIB for thread synchronization are in the following headers:

• m-buffer.h: header for creating fixed-size queue (or stack) of generic type (multiple producer / multiple consumer) used for transferring data from a thread to another,
• m-snapshot: header for creating 'atomic buffer' (through triple buffer) for sharing synchronously big data (thread safe),
• m-shared-ptr.h: header for creating shared pointer of generic type,

The following containers are intrusive (You need to modify your structure to add fields needed by the container) and are defined in:

• m-i-list.h: header for creating doubly-linked intrusive list of generic type,

Other headers offering other functionality are:

• m-string.h: header for creating dynamic string of characters (UTF-8 support),
• m-bstring.h: header for creating dynamic string of BYTE,
• m-bitset.h: header for creating dynamic bitset (or "packed array of bool"),
• m-algo.h: header for providing various generic algorithms to the previous containers,
• m-funcobj.h: header for creating function object (used by algorithm generation),
• m-try.h: header for handling errors by throwing exceptions,
• m-worker.h: header for providing an easy pool of workers on separated threads to handle work orders (used for parallel tasks),
• m-serial-json.h: header for importing / exporting the containers in JSON format,
• m-serial-bin.h: header for importing / exporting the containers in an adhoc fast binary format,
• m-generic.h: header for using a common interface for all registered types,
• m-genint.h: internal header for generating unique integers in a concurrent context,
• m-core.h: header for meta-programming with the C preprocessor (used by all other headers).

Finally, headers for compatibility with non C11 compilers:

• m-atomic.h: header for ensuring compatibility between C's stdatomic.h and C++'s atomic header (provide also its own implementation if nothing is available),
• m-thread.h: header for providing a very thin layer across multiple implementation of mutex/threads (C11/PTHREAD/WIN32).

Each containers define their iterators (if it is meaningful).

All containers try to expose the same common interface: if the method name is the same, then it does the same thing and is used in the same way. In some rare case, the method is adapted to the container needs.

Each header can be used separately from others: dependency between headers have been kept to the minimum.

Build & Installation

M*LIB is only composed of a set of headers, as such there is no build for the library. The library doesn't depend on any other library than the LIBC.

To run the test suite, run:

make check

You can also override the compiler CC or its flags CFLAGS if needed:

make check CC="gcc" CFLAGS="-O3"

To generate the documentation, run:

make doc

To install the headers, run:

make install PREFIX=/my/directory/where/to/install [DESTDIR=...]

Other targets exist. Mainly for development purpose.

How to use

To use these data structures, you first include the desired header, instantiate the definition of the structure and its associated methods by using a macro _DEF for the needed container. Then you use the defined types and functions. Let's see a first simple example that creates a list of unsigned int:

#include <stdio.h>
#include "m-list.h"

LIST_DEF(list_uint, unsigned int) /* Define struct list_uint_t and its methods */

int main(void) {
   list_uint_t list ;             /* list_uint_t has been define above */
   list_uint_init(list);          /* All type needs to be initialized */
   list_uint_push_back(list, 42); /* Push 42 in the list */
   list_uint_push_back(list, 17); /* Push 17 in the list */
   list_uint_it_t it;             /* Define an iterator to scan each one */
   for(list_uint_it(it, list)     /* Start iterator on first element */
       ; !list_uint_end_p(it)     /* Until the end is not reached */
       ; list_uint_next(it)) {    /* Set the iterator to the next element*/
          printf("%d\n",          /* Get a reference to the underlying */
            *list_uint_cref(it)); /* data and print it */
   }
   list_uint_clear(list);         /* Clear all the list (destroying the object list)*/
}

[!NOTE] Do not forget to add -std=c99 (or c11) to your compile command to request a C99 compatible build

This looks like a typical C program except the line with LIST_DEF that doesn't have any semi-colon at the end. And in fact, except this line, everything is typical C program and even macro free! The only macro is in fact LIST_DEF: this macro expands to the good type for the list of the defined type and to all the necessary functions needed to handle such type. It is heavily context dependent and can generate different code depending on it. You