DOCSEARCHbyAlgolia
Submit Docs

M*LIB Documentation

repository·master·Indexed 22 days ago

https://github.com/p-p-h-d/mlib

A generic, type-safe, header-only container library for C (C99/C11) providing functionality similar to the C++ Standard Library. It includes non-intrusive containers (vectors, deques, sets, maps, stacks, queues), intrusive containers, and thread synchronization tools. M*LIB features macro-based code generation for type safety, customizable memory allocators, built-in JSON and binary serialization, and a try/catch exception handling mechanism.

Tokens
58.4K
Snippets
93
Records
208
Agent score
78%

What's inside M*LIB

  1. Overview of M*LIB container types

    master

    M*LIB provides a variety of generic, type-safe containers categorized by their usage patterns and requirements:

    Non-intrusive Containers

    These containers do not require you to modify your existing data structures. They are defined in:

    • m-array.h: Dynamic array of a generic type.
    • m-list.h: Singly-linked list of a generic type.
    • m-deque.h: Dynamic double-ended queue of a generic type.
    • m-queue.h: Static queue or stack of a generic type.
    • m-prioqueue.h: Dynamic priority queue of a generic type.
    • m-dict.h: Unordered associative array (hashmap) or unordered set.
    • m-rbtree.h: Ordered set (Red/Black binary sorted tree).
    • m-bptree.h: Ordered map/set/multimap/multiset (sorted B+TREE).
    • m-tree.h: Arbitrary tree.
    • m-tuple.h: Arbitrary tuple of generic types.
    • m-variant.h: Arbitrary variant of generic types.

    Intrusive Containers

    These require you to modify your structure to include the fields necessary for the container:

    • m-i-list.h: Doubly-linked intrusive list.

    Thread Synchronization Containers

    Used for thread-safe data sharing and synchronization:

    • m-buffer.h: Fixed-size queue or stack (multiple producer / multiple consumer).
    • m-snapshot: Atomic buffer (triple buffer) for sharing large data synchronously.
    • m-shared-ptr.h: Shared pointer of a generic type.

  2. Overview of M*LIB

    master

    M*LIB (M star lib) is a generic, type-safe container library for the C language. It provides an equivalent to the C++ Standard Library (STL) for ISO C99 and C11, including containers like vectors, deques, sets, maps, stacks, queues, and more. It also includes concurrent containers for multi-threaded programming and built-in serialization (JSON and Binary).

    Key features include:

    • Type Safety: Uses macro-based code generation to define inline functions with proper prototypes, allowing the compiler to catch type mismatches.
    • Memory Management: Containers have exclusive ownership of encapsulated objects. Supports copy semantics (INIT_SET), move semantics (INIT_MOVE), and direct construction (EMPLACE).
    • Customizability: Fully customizable memory allocators (including arena allocators) and exception handling (try/catch mechanism compatible with RAII).
    • Performance: Designed for minimal runtime overhead in release mode; highly optimized for speed.
    • Safety: Extensive defensive programming and contract checking in debug mode (e.g., bounds checking for buffer overflows).

  3. M*LIB Performance Characteristics

    master
    MLIB is designed to be a high-performance, type-safe container library for C. Benchmarks comparing MLIB to the GNU C++ STL (v10.2) indicate that M*LIB performance is on par with or even faster than the STL across various data structures, including Singly Lists, Arrays, Unordered Maps, and Ordered Sets.

  4. What is an OPLIST and how to use it

    master

    An OPLIST (operator list) is a core MLIB abstraction used to define the interface of a type. Since C lacks native generics like C++, MLIB uses OPLISTs to tell macros how to operate on specific types (e.g., how to copy, destroy, or compare them).

    An OPLIST is an associative array of operators mapped to methods, formatted as:

    (OPERATOR1(method1), OPERATOR2(method2), ...)

    Key Characteristics:

    • Macro-based: It is a preprocessor abstraction that disappears after macro expansion.
    • Overloading: If an operator appears multiple times, the first occurrence takes priority. This allows for operator overloading when inheriting OPLISTs.
    • Method Constraints: The associated method must be a preprocessor expression that does not contain a comma at the first level.
    • Type Handling: For basic C types, you can often omit the OPLIST. For complex types, you can use an adaptor to convert existing methods into the format expected by the library.
    • Container Generation: When you define a container for a type, you provide its OPLIST. The resulting container will generate its own OPLIST, which can be used to create "container-of-container" structures.
    // Example format of an OPLIST
(INIT(my_init_func), CLEAR(my_clear_func), EQUAL(my_equal_func))

  5. Container constraints and type requirements

    master

    When using M*LIB macros to generate containers, the type argument must follow these rules:

    1. Valid C Expression: The concatenation of type and a variable name (e.g., type variable) must result in a valid C expression.
    2. Prohibited Types: You cannot pass a C array or a function pointer directly as the type.
    3. Workaround: For arrays or function pointers, you must use a typedef to create a named type first.
    4. Allowed Types: Integers, floats, booleans, enums, named structures, named unions, pointers to these, or typedef aliases.

    Oplist Requirement: If you provide an oplist, it must define all methods associated with the type. If omitted, the library attempts to use a globally registered oplist or basic C type oplist.

  6. M*LIB Safety and Debugging modes

    master

    M*LIB uses different strategies depending on the build mode:

    • Debug Mode: Extensive defensive programming is used. Function contracts are checked to prevent data corruption. For example, buffer overflows are checked via bounds checking, and internal properties (like Red-Black tree invariants) are verified.
    • Release Mode: To ensure maximum performance, most checks are removed. It is highly recommended to define NDEBUG for released programs to disable assertions and contract checking.

    Note: Buffer overflow checks can be kept in release mode if specifically required.

  7. Understand Generic Serialization in M*LIB

    master

    M*LIB supports generic serialization, allowing C objects (structs, arrays, lists, etc.) to be translated into formats like strings or FILE* streams and back.

    How it works

    Containers implement _out_serial and _in_serial methods if their underlying types define OUT_SERIAL and IN_SERIAL operators. The process is recursive: the container calls the serialization interface for its elements, which in turn call it for their elements.

    Input Serialization (m_serial_read_t)

    The input object is a structure containing:

    • m_interface: A pointer to a m_serial_read_interface_s structure defining the parsing methods.
    • data: A table of M_SERIAL_MAX_DATA_SIZE C types (Boolean, integer, size, or pointer) used to store state for the parsing methods.

  8. How Snapshots work in M*LIB

    master

    A Snapshot is an atomic shared register designed for high-concurrency scenarios where only the latest state is important. It acts like a global variable of a specific type but ensures data integrity and coherency across multiple threads using a lock-free implementation.

    There are two modes of operation:

    1. Single-Writer, Multiple-Reader (SPMC): Uses an N+2 buffer. Ideal for one producer and many consumers.
    2. Multi-Writer, Multi-Reader (MPMC): Uses an M+N+2 buffer. Supports multiple producers and multiple consumers.

    Snapshots are defined using macros that generate static inline functions and associated types. The oplist provided during definition must contain at least INIT, INIT_SET, SET, and CLEAR to ensure the code compiles.

    SNAPSHOT_SPMC_DEF(name, type, oplist)
SNAPSHOT_MPMC_DEF(name, type, oplist)

  9. Inherit and extend OPLISTs

    master

    You can create specialized OPLISTs by inheriting from existing ones using the M_OPEXTEND macro. This allows you to keep default behaviors while overriding or adding specific operators.

    Example usage: To add OOR_SET and OOR_EQUAL capabilities to a type by extending an existing oplist, use M_OPEXTEND(base_oplist, ...).

    // Example pattern for extending an oplist
#define M_MY_EXTENDED_OPLIST() M_OPEXTEND(M_BASIC_OPLIST, OOR_SET(my_oor_set_func), OOR_EQUAL(my_oor_equal_func))

  10. Define and use a Priority Queue (M-PRIOQUEUE)

    master

    A priority queue in M*LIB is implemented as a heap. It serves elements based on priority: the highest priority (defined by the minimum value according to the CMP operator) is served first.

    Definition

    Use PRIOQUEUE_DEF(name, type [, oplist]) to define the queue. This creates a name_t type and associated methods as static inline functions.

    • name: A C identifier used to prefix all generated types and functions.
    • type: The object type stored in the queue.
    • oplist: Must include INIT, INIT_SET, SET, CLEAR, and CMP.

    Key Behaviors

    • Priority: A pop operation always returns the minimum of all objects (unlike C++ which returns the maximum).
    • Complexity: equal_p, update, and erase have $O(n)$ complexity due to linear search.
    • Iteration: Iteration order is implementation-defined to ensure all items are accessed, but it does not necessarily go from minimum to maximum.

    Common API

    • void name_push(name_t queue, const type x): Adds an item.
    • const type *name_front(name_t queue): References the minimum item.
    • void name_pop(type *dest, name_t queue): Removes and returns the minimum item to dest.
    • void name_update(name_t queue, const type_t old_val, const type_t new_val): Changes the priority of an item (requires EQUAL operator).

  11. How M*LIB handles object ownership

    master

    M*LIB containers maintain exclusive ownership of the objects they encapsulate. When adding objects to a container, you can choose between three primary behaviors:

    1. Copying: Creates a copy of the data (default behavior, using INIT_SET).
    2. Moving: Steals resources from the source object (using INIT_MOVE).
    3. Emplacing: Constructs the object directly inside the container using its constructor (using EMPLACE methods).

    This allows for the construction of fully recursive container objects while maintaining compile-time type checking.

  12. How M*LIB Shared Pointers work

    master

    A Shared Pointer is a smart pointer that manages the shared ownership of an object, performing automatic destruction only when all owners release it. M*LIB shared pointers can transform standard containers (like LIST, ARRAY, etc.) into thread-safe versions by wrapping them with mutex locks.

    There are two main categories:

    1. Strong Shared Pointers: Support thread concurrency for both the reference counter and the data lock. Use SHARED_PTR_DECL macros. Ownership tracking is atomic and destruction is thread-safe.
    2. Weak Shared Pointers: Designed for single-threaded programs. They do not support thread concurrency (non-atomic ownership tracking) and do not provide a lock for the data. Use SHARED_WEAK_PTR_DECL macros.

    Implementation Pattern: To use shared pointers, you must follow a two-step process:

    1. Declare the pointer in a header file using _DECL macros (creates an opaque type and public API).
    2. Define the pointer in exactly one source file using _DEF_EXTERN macros (implements the logic).

    Oplists: The oplist is mandatory. It serves two purposes:

    • It identifies which methods to generate (e.g., name_new() is only created if INIT is in the oplist).
    • It provides type information (key types, value types, etc.) for the implementation.