M*LIB is a library of generic and type safe containers / data structures in pure C language (C99 / C11) for a wide collection of container (comparable to the C++ STL).
C
1,157
4,017 commits
updated Jul 22, 2026
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 / copy / move / 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:
Other key designs are:
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.
The containers have exclusive ownership of the objects they encapsulate. The objects can be pushed in the container:
INIT_SET),INIT_MOVE),EMPLACE)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.
By default, M*LIB uses the malloc, realloc and free functions to handle
the memory pool.
This behavior can be customized to your heart content (fully supporting arena allocator).
Its default policy is to abort the program if there is a memory error: 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 and contract checking in its implementation to ensure robustness:
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.
You can look at the commented examples to get along with how to use the library. You'll see by yourself how easy is to write code using it. Even if writing the library itself is hard (as the code is quite complex and uses a lot of tricks - pretty much like the STL itself), I can ensure you that using it is very natural and simple, and the learning curve low.
In this documentation,
All pointers expected by the functions of the library shall expect non-null argument except if indicated.
The following headers define containers that don't require the user structure to be modified:
The available containers of M*LIB for thread synchronization are in the following headers:
The following containers are intrusive (You need to modify your structure to add fields needed by the container) and are defined in:
Other headers offering other functionality are:
Finally, headers for compatibility with non C11 compilers:
stdatomic.h and C++'s atomic header (provide also its own implementation if nothing is available),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.
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 on the host, run:
make check
You can also override the compiler CC, its flags CFLAGS and LDFLAGS if needed, to select which compiler you want to use:
make check CC="gcc" CFLAGS="-O3"
The dependencies of the test suite are computed automatically by the C compiler using the depend target,
which assumes a GCC compiler (or compatible). If you use another compiler, you can just
build the depend target using GCC or generate an empty file touch tests/depend before running the
check target.
You can also cross-compile if you want using LOG_COMPILER to pass the interpreter. For example:
make check CC=arm-linux-gnueabihf-gcc LOG_COMPILER="qemu-arm -L /usr/arm-linux-gnueabihf/
To generate the documentation, run:
make doc
Finally, to install the headers, run:
make install PREFIX=/my/directory/where/to/install [DESTDIR=...] [INSTALL_DOCS=yes|no]
it assumes PREFIX is the target directory (default /usr/local/) and DESTDIR is the rootfs (default /).
It installs headers in 'include/m-lib' directory and documentation in 'share/doc/m-lib'. Once it is installed, you can use pkg-config to get the include directory using:
[PKG_CONFIG_PATH=...] pkg-config --cflags m-lib
Note: It is called
m-libinstead ofm*libto avoid some potential issues with a directory name with '*' on Unix.
Other targets exist for development purpose.
This is the Quickstart section of the documentation!
M*LIB enables you to generate quickly custom type data structures and their methods. For this, it uses macro to generate content depending on the provided context.
So 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("%u\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 higher) 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 which takes as argument
the prefix of the container and its basic type. Then it expands and generates
the type of the container (by concatenating the prefix and the suffix _t) which is a list of unsigned int
and also other types (like the iterator of the list which uses the suffis _it_t)
and all the necessary methods needed to handle such container by concatenating the prefix and the suffix of the methods.
For example,
_init : the constructor of an empty list,_clear: the destructor of the list,_push_back: the method to push an object in the list (here an unsigned int)_it: the method to initialize the iterator to the first element of the list,_end_p: the method to test if the iterator as reaches the end of the list,_next: the method to move the iterator to the next element,_cref: the method to get a pointer to the data referenced by the iterator.The generation is heavily context dependent and can generate different code depending on it. You can use it as many times as needed to defined as many lists (of the same or different types) as you want provided that you use a different prefix.
The first argument of the macro is the name to use, e.g. the prefix that is added to all generated functions and types. The second argument of the macro is the type to embed within the container. It can be any C type. The third argument of the macro is optional and is the oplist to use. See below for more information.
Notice you call the function ending with _clear to clear the object.
Clearing for the library means drop (or free or destruct) the container's allocated memory.
It is its destructor.
You could replace LIST_DEF by ARRAY_DEF to change
the kind of container (an array instead of a linked list)
without changing the code below: the generated interface
of a list or of an array is very similar.
Yet the performance remains the same as hand-written code
for both the list variant and the array variant.
This is equivalent to this C++ program using the STL:
#include <iostream>
#include <list>
typedef std::list<unsigned int> list_uint_t;
typedef std::list<unsigned int>::iterator list_uint_it_t;
int main(void) {
list_uint_t list ; /* list_uint_t has been define above */
list.push_back(42); /* Push 42 in the list */
list.push_back(17); /* Push 17 in the list */
for(list_uint_it_t it = list.begin() /* Iterator is first element*/
; it != list.end() /* Until the end is not reached */
; ++it) { /* Set the iterator to the next element*/
std::cout << *it << '\n'; /* Print the underlying data */
}
}
As you can see, this is rather equivalent with the following remarks:
Note: M*LIB defines its own container as an array of a structure of size 1. This has the following advantages:
All M*LIB containers fully own their data. The user is only responsible for initialization and clearing the container (constructor/destructor).
The container returns borrowed pointers to the data within the container, theses borrowed pointers remain valid until modification of the container.
M*LIB offers also the possibility to condense further your code, so that it is more high level:
by using the M_EACH & M_LET macros (if you are not afraid of using syntactic macros):
#include <stdio.h>
#include "m-list.h"
LIST_DEF(list_uint, unsigned int) /* Define struct list_uint_t and its methods */
int main(void) {
M_LET(list, LIST_OPLIST(uint)) { /* Define & init list as list_uint_t */
list_uint_push_back(list, 42); /* Push 42 in the list */
list_uint_push_back(list, 17); /* Push 17 in the list */
for M_EACH(item, list, LIST_OPLIST(uint)) {
printf("%u\n", *item); /* Print the item */
}
} /* Clear of list will be done now */
}
Note: M*LIB macros are in upper cases and look like macros, normal functions are in lower cases.
You have just seen a new word you don't know: LIST_OPLIST
What is an oplist? To understand what it is, let's another example with a more complete type (with proper initialization & clear function) by using the GMP library:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
ARRAY_DEF(array_mpz, mpz_t, (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ)) )
int main(void) {
array_mpz_t array ; /* array_mpz_t has been define above */
array_mpz_init(array); /* All type needs to be initialized */
mpz_t z; /* Define a mpz_t type */
mpz_init(z); /* Initialize the z variable */
mpz_set_ui (z, 42);
array_mpz_push_back(array, z); /* Push 42 in the array */
mpz_set_ui (z, 17);
array_mpz_push_back(array, z); /* Push 17 in the array */
array_mpz_it_t it; /* Define an iterator to scan each one */
for(array_mpz_it(it, array) /* Start iterator on first element */
; !array_mpz_end_p(it) /* Until the end is not reached */
; array_mpz_next(it)) { /* Set the iterator to the next element*/
gmp_printf("%Zd\n", /* Get a reference to the underlying */
*array_mpz_cref(it)); /* data and print it */
}
mpz_clear(z); /* Clear the z variable */
array_mpz_clear(array); /* Clear all the array */
}
As the mpz_t type needs proper initialization, copy and destroy functions
we need to tell to the container how to handle such a type.
This is done by giving it the oplist associated to the type.
An oplist is an associative array where an operator is associated to its associated method.
In the example, we tell to the container to use:
mpz_init function for the INIT operator of the type (aka constructor),mpz_clear function for the CLEAR operator of the type (aka destructor),mpz_set function for the SET operator of the type (aka copy),mpz_init_set function for the INIT_SET operator of the type (aka copy constructor).M_COPY_A1OBJ is used for the INIT_MOVE operator (good for all objects using the [1] trick).The all pattern (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ))
is the oplist of the `mpz_t type. It starts with a parenthesis and end with a parenthesis.
Each association is done by giving the operator in upper case, and its method just after in parenthesis.
This associative array only exists in the preprocessing step of the compilation,
resulting in no runtime cost and strict aliasing check.
The LIST_OPLIST seen in the previous chapter is just a macro that define the oplist
for a list container giving its name.
See OPLIST chapter for more detailed information.
With oplists, behavior becomes modular, reusable and even inheritable: You define semantics once, reuse everywhere.
We can also write the same example shorter by using the ability of M*LIB to register oplists:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
// Register the oplist of a mpz_t.
#define M_OPL_mpz_t() (INIT(mpz_init), INIT_SET(mpz_init_set), \
SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ))
// Define an instance of an array of mpz_t (both type and function)
ARRAY_DEF(array_mpz, mpz_t)
// Register the oplist of the created instance of array of mpz_t
#define M_OPL_array_mpz_t() ARRAY_OPLIST(array_mpz, M_OPL_mpz_t())
int main(void) {
// Let's define `array` as an 'array_mpz_t' & initialize it.
M_LET(array, array_mpz_t)
// Let's define 'z1' and 'z2' to be 'mpz_t' & initialize it
M_LET (z1, z2, mpz_t) {
mpz_set_ui (z1, 42);
array_mpz_push_back(array, z1); /* Push 42 in the array */
mpz_set_ui (z2, 17);
array_mpz_push_back(array, z2); /* Push 17 in the array */
// Let's iterate over all items of the container
for M_EACH(item, array, array_mpz_t) {
gmp_printf("%Zd\n", *item);
}
} // All variables are cleared with the proper method beyond this point.
return 0;
}
To register an oplist, you need to define the macro M_OPL_+type that expands into its oplist.
It shall be a macro function that take no argument.
Or even shorter when you're comfortable enough with the library by using its advanced constructor features:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
// Register the oplist of a mpz_t. It is a classic oplist.
#define M_OPL_mpz_t() M_OPEXTEND(M_CLASSIC_OPLIST(mpz), \
INIT_WITH(mpz_init_set_ui), EMPLACE_TYPE(unsigned int))
// Define an instance of an array of mpz_t (both type and function)
ARRAY_DEF(array_mpz, mpz_t)
// Register the oplist of the created instance of array of mpz_t
#define M_OPL_array_mpz_t() ARRAY_OPLIST(array_mpz, M_OPL_mpz_t())
int main(void) {
// Let's define `array` as an 'array_mpz_t' with mpz_t(17) and mpz_t(42)
M_LET((array,(17),(42)), array_mpz_t) {
// Let's iterate over all items of the container
for M_EACH(item, array, array_mpz_t) {
gmp_printf("%Zd\n", *item);
}
} // All variables are cleared with the proper method beyond this point.
return 0;
}
There are two ways a container can known which oplist is to be used for the type:
M_LET and M_EACH macros,M_OPL_ and finishing with the name of type (don't forget the parenthesis and the suffix _t if needed). The macros performing the definition of container and the M_LET and M_EACH will test if such macro is defined. If it is defined, it will be used. Otherwise, default methods are used.Here we can see that we register the mpz_t type into the container with
the minimum information of its interface needed, and another one to initialize a mpz_t from an unsigned integer.
We can also see in this example so the container ARRAY provides also a macro to define the oplist of the array itself. This is true for all containers and this enables to define proper recursive container like in this example which reads from a text file a definition of sections:
#include <stdio.h>
#include "m-array.h"
#include "m-tuple.h"
#include "m-dict.h"
#include "m-string.h"
TUPLE_DEF2(symbol, (offset, long), (value, long))
#define M_OPL_symbol_t() TUPLE_OPLIST(symbol, M_BASIC_OPLIST, M_BASIC_OPLIST)
ARRAY_DEF(array_symbol, symbol_t)
#define M_OPL_array_symbol_t() ARRAY_OPLIST(array_symbol, M_OPL_symbol_t())
DICT_DEF2(sections, string_t, array_symbol_t)
#define M_OPL_sections_t() DICT_OPLIST(sections, STRING_OPLIST, M_OPL_array_symbol_t())
int main(int argc, const char *argv[])
{
if (argc < 2) abort();
FILE *f = fopen(argv[1], "rt");
if (!f) abort();
M_LET(sc, sections_t) {
sections_in_str(sc, f);
array_symbol_t *a = sections_get(sc, STRING_CTE(".text"));
if (a == NULL) {
printf("There is no .text section.");
} else {
printf("Section .text is :");
array_symbol_out_str(stdout, *a);
printf("\n");
}
}
return 0;
}
This example reads the data from a file and outputs the .text section if it finds it on the terminal.
Other examples are available in the example folder.
Internal fields of the structure are subject to change even for small revision of the library.
The final goal of the library is to be able to write code like this in pure C while keeping type safety and compile time name resolution:
let(list, list_uint_t) {
push(list, 42);
push(list, 17);
for each (item, list) {
print(*item, "\n");
}
}
And it works! See the example and m-generic header for details.
( ) or double level of ( ) around the oplist,BASIC_OPLIST instead of M_BASIC_OPLIST),name parameter given to the oplist is not the same as the one used to expand the methods,M*LIB performance is compared to the one of GNU C++ STL (v10.2) in the following graphs. Each graph is presented first in linear scale and then in logarithmic scale to better realize the differences. M*LIB is on par with the STL or even faster.
All used bench codes are available in this repository The results for several different libraries are also available in a separate page.
An OPLIST is a fundamental notion of M*LIB that hasn't be seen in any other library.
In order to know how to operate on a type, M*LIB needs additional information
as the compiler doesn't know how to handle properly any type (contrary to C++).
This is done by giving an operator list (or oplist in short) to any macro that
needs to handle the type. As such, an oplist has only meaning within a macro.
Fundamentally, this is the exposed interface of a type:
that is to say the association of the operators defined by the library to the
effective methods provided by the type, including their call interface.
This association is done only with the C preprocessor.
Therefore, an oplist is an associative array of operators to methods in the following format:
(OPERATOR1(method1), OPERATOR2(method2), ...)
It starts with a parenthesis and ends with a parenthesis. Each association is separated by a comma. Each association is composed of a predefined operator (as defined below) a method (in parentheses), and an optional API interface (see below).
In the given example,
the function method1 is used to handle OPERATOR1.
The function method2 is used to handle OPERATOR2, etc.
In case the same operator appears multiple times in the list, the first apparition of the operator has priority, and its associated method will be used. This enables overloading of operators in oplist in case you want to inherit oplists.
The associated method in the oplist is a preprocessor expression that shall not contain a comma as first level.
An oplist has no real form from the C language point of view. It is just an abstraction that disappears after the macro expansion step of the preprocessing. If an oplist remains unprocessed after the C preprocessing, a compiler error will be generated.
For basic C type, you can even omit the oplist definition, and the library will know how to handle it. For more complex type, you don't often have to define stub code to specify how elements are compared, copied, or destroyed by matching what is expected by the library: you can request conversion on the fly from what is provided to what is expected by using an adaptor. It allows very powerful binding while keeping it very simple to use and as error prone as possible.
When you define an instance of a new container for a given type, you give the type OPLIST
alongside the type for building the container.
Some functions of the container may not be available in function of the provided interface of the OPLIST
(for optional operators).
Of if some mandatory operators are missing, a compiler error is generated.
The generated container will also provide its own oplist, which will depends on all the oplists used to generate it. This oplist can also be used to generate new containers.
You can therefore use the oplist of the container to chain this new interface
with another container, creating container-of-container.
[!NOTE] An operator shall fail only on abnormal error and if it is marked as potentially raising asynchronous errors. In this case it shall throw exceptions only if exceptions are configured. Otherwise, the program shall be terminated.
In this case, the objects remain initialized and valid but in an unspecified state. In case of in constructors, the object is not constructed and the destructor of the object has not to be called.
[!NOTE] If an operator is not marked as raising asynchronous errors, it shall not fail or throw any exceptions in any cases.
Not all operators are needed for an oplist to handle a container. If some operator is missing, the associated default method of the operator is used if it exists.
The following classic operators are usually expected for an object:
INIT(obj): initialize the object obj into a valid state (constructor). It may raise asynchronous error.INIT_SET(obj, org): initialize the object obj into the same state as the object org (copy constructor). It may raise asynchronous error.SET(obj, org): set the initialized object obj into the same state as the initialized object org (copy operator). It may raise asynchronous error.CLEAR(obj): destroy the initialized object obj, releasing any attached memory (destructor).Other documented operators are:
NAME() --> prefix: Return the base name prefix used to construct the container.FIELD() --> field name: Return the name of the field used when constructing the upper container.TYPE() --> type: Return the base type associated to this oplist.SUBTYPE() --> type: Return the type of the element stored in the container (used to iterate over the container).GENTYPE() --> type: Return the type representing TYPE but suitable for a _Generic statement.OPLIST() --> oplist: Return the oplist of the type of the elements stored in the container.KEY_TYPE() --> key_t: Return the key type for associative containers.VALUE_TYPE() --> value_t: Return the value type for associative containers.KEY_OPLIST() --> oplist: Return the oplist of the key type for associative containers.VALUE_OPLIST() --> oplist: Return the oplist of the value type for associative containers.NEW(context, type) --> type pointer: allocate a new object (with suitable alignment and size) and return a pointer to it. The returned object is not initialized (a constructor operator shall be called afterward). The default method is M_MEMORY_ALLOC (that allocates from the heap). It returns NULL in case of failure.DEL(context, &obj): free the allocated uninitialized object obj. The destructor of the pointed object shall be called before freeing the memory by calling this method. The object shall have been allocated by the associated NEW method. sizeof obj is the size of the allocated object. The default method is M_MEMORY_DEL (that frees to the heap). obj shall not be NULL and shall be of the proper type.REALLOC(context, type, pointer, previous_number, new_number) --> pointer: reallocate the given array of previous_number elements of type type referenced by pointer (either a NULL pointer or a pointer returned by a previous call to REALLOC) to an array of new_number objects of type type and return a pointer to this new array. Previously objects pointed by the pointer are kept up to the minimum of the new size and old one but may have moved from their original positions (if the array is reallocated otherwhere). New objects are not initialized (a constructor operator shall be called afterward). Freed objects are not cleared (A destructor operator shall be called before). The default is M_MEMORY_REALLOC (that allocates from the heap). It returns NULL in case of failure in which case the original array is not modified. If pointer is NULL, then previous_number should be 0.FREE(context, type, pointer, number): free the allocated uninitialized array of number elements of type type referenced by pointer. The destructor of the pointed objects shall be called before freeing the memory. The memory of the objects shall have been allocated by the associated REALLOC method. The default is M_MEMORY_FREE (that frees to the heap). If pointer is NULL, then the function shall do nothing.INC_ALLOC(size_t s) --> size_t: Define the growing policy of an array (or equivalent structure). It returns a new allocation size based on the old allocation size (s). Default policy is to get the maximum between 2*s and 16. In case of overflow, it shall return a number less or equal than the original size.[!NOTE] It doesn't check for overflow: if the returned value is lower than the old one, the user shall raise an overflow error (memory error).
INIT_MOVE(objd, objc): Initialize objd to the same state than objc by stealing as many resources as possible from objc, and then clear objc (constructor of objd + destructor of objc). It is semantically equivalent to calling INIT_SET(objd,objc) then CLEAR(objc) but is usually way faster. Contrary to the C++ choice of using "conservative move" semantic (you still need to call the destructor of a moved object in C++) M*LIB implements a "destructive move" semantic (this enables better optimization). By default, all objects are assumed to be trivially movable (i.e. using memcpy to move an object is safe). Most C objects (even complex structure) are trivially movable and it is a very nice property to have (enabling better optimization). A notable exception are intrusive objects. If an object is not trivially movable, it shall provide an INIT_MOVE method or disable the INIT_MOVE method entirely[!NOTE] Some containers may assume that the objects are always trivially movable (like array). Moved objects shall use the same memory allocator.
MOVE(objd, objc): Set objd to the same state than objc by stealing as resources as possible from objc and then clear objc (destructor of objc). It is equivalent to calling SET(objd,objc) then CLEAR(objc) or CLEAR(objd) and then INIT_MOVE(objd, objc). See INIT_MOVE for details and constraints. TBC if this operator is really needed as calling CLEAR then INIT_MOVE is what do all known implementation, and is efficient.INIT_WITH(obj, ...): Initialize the object obj with the given variable set of arguments (constructor). The arguments are variable and can be of different types. It is up to the method of the object to decide how to initialize the object based on this initialization array. This operator is used by the M_LET macro to initialize objects with their given values and this operator defines what the M_LET macro supports. It may raise asynchronous error.[!NOTE] In C11, you can use
API_1(M_INIT_WITH_THROUGH_EMPLACE_TYPE)as a method forINIT_WITHto automatically use the different emplace functions defined inEMPLACE_TYPEthrough a _Generic switch case. The providedEMPLACE_TYPEshall use the LIST format. See emplace chapter.
SWAP(objd, objc): Swap the states of the object objc and the object objd.[!NOTE] The swapped objects shall use the same allocator.
RESET(obj): Reset the object to its initialized state (Emptying the object if it is a container object).EMPTY_P(obj) --> bool: Test if the container object is empty (true) or not.FULL_P(obj) --> bool: Test if the container object is full (true) or not. Default if not defined is to be not full.GET_SIZE (container) --> size_t: Return the number of elements in the container object.HASH (obj) --> size_t: return a hash of the object (not a secure hash but one that is usable for a hash table). Default is performing a hash of the memory representation of the object. This default implementation is invalid if the object holds pointer to other objects or has spare fields.EQUAL(obj1, obj2) --> bool: Compare the two objects for equality. Return true if both objects are equal, false otherwise. Default is using the C comparison operator. 'obj1' may be an OOR object (Out of Representation) for the Open Addressing dictionary (see OOR_* operators): in such cases, it shall return false.CMP(obj1, obj2) --> int: Provide a complete order the objects. return a negative integer if obj1 < obj2, 0 if obj1 = obj2, a positive integer otherwise. Default is C comparison operator.[!NOTE] The equivalence between
EQUAL(a, b)andCMP(a, b) == 0is not required, but is usually welcome.
ADD(obj1, obj2, obj3): Set obj1 to the sum of obj2 and obj3. Default is + C operator. It may raise asynchronous error.SUB(obj1, obj2, obj3): Set obj1 to the difference of obj2 and obj3. Default is - C operator. It may raise asynchronous error.MUL(obj1, obj2, obj3): Set obj1 to the product of obj2 and obj3. Default is * C operator. It may raise asynchronous error.DIV(obj1, obj2, obj3): Set obj1 to the division of obj2 and obj3. Default is / C operator. It may raise asynchronous error.GET_KEY (container, key) --> &value: Return a pointer to the value object within the container associated to the key key if an object is associated to this key. Otherwise it may return NULL or terminate the program with a logic error (depending on the container). The pointer to the value object remains valid until any modification of the container.SET_KEY (container, key, value): Associate the key object key to the value object value in the given container. It may raise asynchronous error.SAFE_GET_KEY (container, key) --> &value: return a pointer to the value object within the container associated to the key key if it exists, or create a new entry in the container and associate it to the key key with the default initialization before returning its pointer. The pointer to the object remains valid until any modification of the container. The returned pointer is therefore never NULL. It may raise asynchronous error.ERASE_KEY (container, key) --> bool: Erase the object associated to the key key within the container. Return true if successful, false if the key is not found (nothing is done).PUSH(container, obj): Push obj (of type SUBTYPE()) into the container container. How and where it is pushed is container dependent. It may raise asynchronous error.POP(&obj, container): Pop an object from the container container and set it in the initialized object *obj (of type SUBTYPE()) if the pointer obj is not NULL. Which object is popped is container dependent. It may raise asynchronous error.PUSH_MOVE(container, &obj): Push and move the object *obj (of type SUBTYPE()) into the container container (*obj destructor). How it is pushed is container dependent. *obj is cleared afterward and shall not be used anymore. See INIT_MOVE for more details and constraints. It may raise asynchronous error.POP_MOVE(&obj, container): Pop an object from the container container and init & move it in the uninitialized object *obj (aka constructor). Which object is popped is container dependent. *obj shall be uninitialized. See INIT_MOVE for more details and constraints.[!NOTE] When using a
POPoperator (or any derived operator) on a container, this container shall have at least one object.
The iterator operators are:
IT_TYPE() --> type: Return the type of the iterator object of this container.IT_FIRST(it_obj, obj): Set the iterator it_obj to the first sub-element of the container obj. What is the first element is container dependent (it may be front or back, or something else). However, iterating from FIRST to LAST (included) or END (excluded) through IT_NEXT ensures going through all elements of the container. If there is no sub-element in the container, it references an end of the container.IT_LAST(it_obj, obj): Set the iterator it_obj to the last sub-element of the container obj. What is the last element is container dependent (it may be front or back, or something else). However, iterating from LAST to FIRST (included) or END (excluded) through IT_PREVIOUS ensures going through all elements of the container. If there is no sub-element in the container, it references an end of the container.IT_END(it_obj, obj): Set the iterator it_obj to an end of the container obj. Once an iterator has reached an end, it can't use PREVIOUS or NEXT operators. If an iterator has reached an END, it means that there is no object referenced by the iterator (kind of NULL pointer). There can be multiple representation of the end of a container, but all of then share the same properties.IT_SET(it_obj, it_obj2): Set the iterator it_obj to reference the same sub-element as it_obj2.IT_END_P(it_obj) --> bool: Return true if the iterator it_obj references an end of the container, false otherwise.IT_LAST_P(it_obj) --> bool: Return true if the iterator it_obj references the last element of the container (just before reaching an end) or has reached an end of the container, false otherwise.IT_EQUAL_P(it_obj, it_obj2) --> bool: Return true if both iterators reference the same element, false otherwise.IT_NEXT(it_obj): Move the iterator to the next sub-element or an end of the container if there is no more sub-element. The direction of IT_NEXT is container dependent. it_obj shall not be an end of the container.IT_PREVIOUS(it_obj): Move the iterator to the previous sub-element or an end of the container if there is no more sub-element. The direction of PREVIOUS is container dependent, but it is the reverse of the IT_NEXT operator. it_obj shall not be an end of the container.IT_CREF(it_obj) --> &subobj: Return a constant pointer to the object referenced by the iterator (of type const SUBTYPE()). This pointer remains valid until any modifying operation on the container, or until another reference is taken from this container through an iterator (some containers may reduce theses constraints, for example a list). The iterator shall not be an end of the container.IT_REF(it_obj) --> &subobj: Same as IT_CREF, but return a modifiable pointer to the object referenced by the iterator.IT_INSERT(obj, it_obj, subobj): Insert subobj after 'it_obj' in the container obj and update it_obj to point to the inserted object (as per IT_NEXT semantics). All other iterators of the same container become invalidated. If 'it_obj' is an end of the container, it inserts the object as the first one.IT_REMOVE(obj, it_obj): Remove it_obj from the container obj (clearing the associated object) and update it_obj to point to the next object (as per IT_NEXT semantics). As it modifies the container, all other iterators of the same container become invalidated. it_obj shall not be an end of the container.SPLICE_BACK(objd, objs, it_obj): Move the object of the container objs referenced by the iterator 'it_obj' to the container objd. Where it is moved is container dependent (it is recommended however to be like the PUSH method). Afterward 'it_obj' references the next item in 'containerSrc' (as per IT_NEXT semantics). 'it_obj' shall not be an end of the container. Both objects shall use the same allocator. It may raise asynchronous error.SPLICE_AT(objd, id_objd, objs, it_objs): Move the object referenced by the iterator it_objs from the container objs just after the object referenced by the iterator it_objd in the container objd. If it_objd references an end of the container, it is inserted as the first item of the container (See operator IT_INSERT). Afterward it_objs references the next item in the container objs, and it_objd references the moved item in the container objd. it_objs shall not be an end of the container. Both objects shall use the same allocator. It may raise asynchronous error.[!NOTE] An iterator doesn't have a constructor nor destructor methods. Therefore, it cannot not allocate any memory.
[!NOTE] A reference to an object through the pointer get from the iterator is only valid until another reference is taken from the same container (potentially through another iterator), or the iterator is modified or the container itself is modified. This reference is therefore extremely local and should not be stored anywhere else. Some containers may lessen this constraint (for example list or RB-Tree).
[!NOTE] If the container is modified, all iterators of this container become invalid and shall not be used anymore except if the modifying operator provided itself an updated iterator. Some containers may lessen this constraint.
The I/O operators are:
OUT_STR(FILE* f, obj): Output obj as a custom formatted string into the FILE* stream f. Format is container dependent, but is human readable.IN_STR(obj, FILE* f) --> bool: Set obj to the value associated to the formatted string representation of the object in the FILE* stream f. Return true in case of success (in that case the stream f has been advanced to the end of the parsing of the object), false otherwise (in that case, the stream f is in an undetermined position but is likely where the parsing fails). It ensures that an object which is output in a FILE through OUT_STR, and an object which is read from this FILE through IN_STR are considered as equal. It may raise asynchronous error.GET_STR(string_t str, obj, bool append): Set str to a formatted string representation of the object obj. Append to the string if append is true, set it otherwise. This operator requires the module m-string. It may raise asynchronous error.PARSE_STR(obj, const char *str, const char **endp) --> bool: Set obj to the value associated to the formatted string representation of the object in the char stream str. Return true in case of success (in that case if endp is not NULL, it points to the end of the parsing of the object), false otherwise (in that case, if endp is not NULL, it points to an undetermined position but likely to be where the parsing fails). It ensures that an object which is written in a string through GET_STR, and an object which is read from this string through PARSE_STR are considered as equal. It may raise asynchronous error.OUT_SERIAL(m_serial_write_t *serial, obj) --> m_serial_return_code_t: Output obj into the configurable serialization stream serial (See m-serial-json.h for details and example) as per the serial object semantics. Return M_SERIAL_OK_DONE in case of success, or M_SERIAL_FAIL otherwise. It may raise asynchronous error.IN_SERIAL(obj, m_serial_read_t *serial) --> m_serial_return_code_t: Set obj to its representation from the configurable serialization stream serial (See m-serial-json.h for details and example) as per the serial object semantics. M_SERIAL_OK_DONE in case of success (in that case the stream serial has been advanced up to the complete parsing of the object), or M_SERIAL_FAIL otherwise (in that case, the stream serial is in an undetermined position but usually around the next characters after the first failure). It may raise asynchronous error.The final operators are:
OOR_SET(obj, int_value): Some containers want to store some information within the uninitialized objects (for example Open Addressing Hash Table). This method stores the integer value 'int_value' into an uninitialized object obj. It shall be able to differentiate between uninitialized object and initialized object (How is type dependent). The way to store this information is fully object dependent. In general, you use out-of-range value for detecting such values. The object remains uninitialized but sets to of out-of-range value (OOR). int_value can be 0 or 1.OOR_EQUAL(obj, int_value): This method compares the object obj (initialized or uninitialized) to the out-of-range value (OOR) representation associated to 'int_value' and returns true if both objects are equal, false otherwise. See OOR_SET.REVERSE(obj): Reverse the order of the items in the container obj. It may raise asynchronous error.SEPARATOR() --> character: Return the character used to separate items for I/O methods (default is ',') (for internal use only).EXT_ALGO(name, container oplist, object oplist): Define additional algorithms functions specialized for the containers (for internal use only).PROPERTIES() --> ( properties): Return internal properties of a container in a recursive oplist format. Use M_GET_PROPERTY to get the property.EMPLACE_TYPE( ... ): Specify the types usable for "emplacing" the object (initializing the object in-place, constructor). See chapter Emplace construction. THe referenced initializing functions may raise asynchronous error.[!NOTE] The operator names listed above shall not be defined as macro.
More operators are expected.
Properties can be stored in a sub-oplist format in the PROPERTIES operator.
The following properties are defined:
LET_AS_INIT_WITH(1) — Defined if the macro M_LET shall always initialize the object with INIT_WITH regardless of the given input. The value of the property is 1 (enabled) or 0 (disabled/default).NOCLEAR(1) — Defined if the object CLEAR operator can be omitted (like for basic types or POD data). The value of the property is 1 (enabled) or 0 (disabled/default).[!NOTE] The properties names listed above shall not be defined as macro.
More properties are expected.
Let's take the interface of the MPZ library:
void mpz_init(mpz_t z); // Constructor of the object z
void mpz_init_set(mpz_t z, const mpz_t s); // Copy Constructor of the object z
void mpz_set(mpz_t z, const mpz_t s); // Copy operator of the object z
void mpz_clear(mpz_t z); // Destructor of the object z
A basic oplist will be:
(INIT(mpz_init),SET(mpz_set),INIT_SET(mpz_init_set),CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ),TYPE(mpz_t))
Much more complete oplist can be built for this type however, enabling much more powerful generation: See in the example
Oplist can be registered globally by defining, for the type type, a macro named
M_OPL_ ## type () that expands to the oplist of the type.
Only type without any space in their name can be registered. A typedef of the type
can be used instead, but this typedef shall be used everywhere.
Example:
#define M_OPL_mpz_t() (INIT(mpz_init),SET(mpz_set), \
INIT_SET(mpz_init_set),CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ),TYPE(mpz_t))
[!NOTE] Registering globaly the oplist when defining its type simplify a lot the
OPLISTusage and it is highly recommended.
Then each times a macro expects an oplist, you can give instead its type. This make the code much easier to read and understand.
There is one exception however: the macros that are used to build oplist
(like ARRAY_OPLIST) don't perform this simplification and the oplist of
the type shall be explictely given instead
(This is due to limitation in the C preprocessing).
Within an OPLIST, you can also specify the needed low-level transformation to perform for calling your method.
This is called API Interface Adaptation: it enables to transform the API requirements of the selected operator
(which is very basic in general) to the API provided by the given method.
Assuming that the method to call is called 'method' and the first argument of the operator is 'output',
which interface is OPERATOR(output, ...)
then the following predefined adaptation are available:
| API | Method | Description |
|---|---|---|
| API_0 | method(output, ...) | No adaptation |
| API_1 | method(oplist, output, ...) | No adaptation but gives the oplist to the method |
| API_2 | method(&output, ...) | Pass by address the first argument (like with M_IPTR) |
| API_3 | method(oplist, &output, ...) | Pass by address the first argument (like with M_IPTR) and give the oplist of the type |
| API_4 | output = method(...) | Pass by return value the first argument |
| API_5 | output = method(oplist, ...) | Pass by return value the first argument and give the oplist of the type |
| API_6 | method(&output, &...) | Pass by address the two first arguments |
| API_7 | method(oplist, &output, &...) | Pass by address the two first argument and give the oplist of the type |
The API Adaptation to use shall be embedded in the OPLIST definition.
For example:
(INIT(API_0(mpz_init)), SET(API_0(mpz_set)), INIT_SET(API_0(mpz_init_set)), CLEAR(API_0(mpz_clear)), INIT_MOVE(M_COPY_A1OBJ))
The default adaptation is API_0 (i.e. no adaptation between operator interface and method interface). If an adaptation gives an oplist to the method, the method shall be implemented as macro.
Let's take the interface of a pseudo library:
typedef struct { ... } obj_t;
obj_t *obj_init(void); // Constructor of the object z
obj_t *obj_init_str(const char *str); // Constructor of the object z
obj_t *obj_clone(const obj_t *s); // Copy Constructor of the object z
void obj_clear(obj_t *z); // Destructor of the object z
The library returns a pointer to the object, so we need API_4 for these methods.
There is no method for the SET operator available. However, we can use the macro M_SET_THROUGH_INIT_SET
to emulate a SET semantics by using a combination of CLEAR + INIT_SET. This enables to support
the type for array containers in particular. Or we can avoid this definition if we don't need it.
A basic oplist will be:
(INIT(API_4(obj_init)),SET(API_1(M_SET_THROUGH_INIT_SET)),INIT_SET(API_4(obj_clone)),CLEAR(obj_clear),TYPE(obj_t *))
To work, M_SET_THROUGH_INIT_SET needs to have the oplist of the type to perform a call to its
CLEAR and INIT_SET operator, thus using the API_1 convention.
You can also describe the exact transformation to perform for calling the method: this is called Generic API Interface Adaptation (or GAIA). With this, you can add constant values to parameter of the method, reorder the parameters as you wish, pass then by pointers, or even change the return value.
The API adaptation is also described in the operator mapping with the method name by using the API keyword. Usage in oplist:
, OPERATOR( API( method, returncode, args...) ) ,
Within the API keyword,
returncode is the transformation to perform of the return code.returncode can be
NONE — no transformation,VOID — cast to void,NEG — inverse the result,EQ(val)/NEQ(val)/LT(val)/GT(val)/LE(val)/GE(val) — compare the return code to the given valueARG[1-9] — set the associated argument number of the operator to the return codeAn argument can be:
ID( constant or variable) — if the constant or variable is not a valid token,ARG[1-9] — the associated argument number of the operator,ARGPTR[1-9] — the pointer of the associated argument number of the operator,OPLIST — the oplistTherefore, it supports at most 9 arguments.
Example:
, EQUAL( API(mpz_cmp, EQ(0), ARG1, ARG2) ) ,
This will transform a return value of 0 by the mpz_cmp method into a boolean for the EQUAL operator.
Another Example:
, OUT_STR( API(mpz_out_str, VOID, ARG1, 10, ARG2) ) ,
This will serialize the mpz_t value in base 10 using the mpz_out_str method, and discarding the return value.
An operator OP can be defined, omitted or disabled:
( OP(f) ): the function f is the method of the operator OP( OP(API_N(f)) ): the function f is the method of the operator OP with the API transformation number N,( ): the operator OP is omitted, and the default global operation for OP is used (if it exists).( OP(0) ): the operator OP is disabled, and it can never be used.This can be useful to disable an operator in an inherited oplist.
OPLIST to use?My type is:
M_BOOL_OPLIST (M_BASIC_OPLIST also works partially),M_BASIC_OPLIST (it can also be omitted),M_ENUM_OPLIST,M_PTR_OPLIST,M_POD_OPLIST,memset, memcpy, memcmp: M_A1_OPLIST,name_init, name_init_set, name_set, name_clear methods: M_CLASSIC_OPLIST,const char *) that is neither freed nor moved: M_CSTR_OPLIST,STRING_OPLIST,OPLIST of the used container,OPLIST to your type.[!NOTE] The precise exported methods of the OPLIST depend on the version of the used C language. Typically, in C11 mode, the
M_BASIC_OPLISTexports all needed methods to handle generic input/output of int/floats (using_Generickeyword) whereas it is not possible in C99 mode.
This explains why JSON import/export is only available in C11 mode (See below chapter).
Basic usage of oplist is available in the example
Oplist can inherit from another one.
This is useful when you want to customize some specific operators while keeping other ones by default.
For example, internally M_BOOL_OPLIST inherits from M_BASIC_OPLIST.
A typical example is if you want to provide the OOR_SET and OOR_EQUAL operators to a type
so that it can be used in an OA dict.
To do it, you use the M_OPEXTEND macro. It takes as first argument the oplist you want to inherit with,
and then you provide the additional associations between operators to methods you want to add
or override in the inherited oplist. For example:
int my_int_oor_set(char c) { return INT_MIN + c; }
bool my_int_oor_equal(int i1, int i2) { return i1 == i2; }
#define MY_INT_OPLIST \
M_OPEXTEND(M_BASIC_OPLIST, OOR_SET(API_4(my_int_oor_set)), \
OOR_EQUAL(my_int_oor_equal))
You can even inherit from another oplist to disable some operators in your new oplist. For example:
#define MY_INT_OPLIST \
M_OPEXTEND(M_BASIC_OPLIST, HASH(0), CMP(0), EQUAL(0))
MY_INT_OPLIST is a new oplist that handles integers but has disabled the operators HASH, CMP and EQUAL.
The main interest is to disable the generation of optional methods of a container (since they are only
expanded if the oplist provides some methods).
Usage of inheritance and oplist is available in the int example and the cstr example
Let's take a look at the interface of the FILE* interface:
FILE *fopen(const char *filename, const char *mode);
fclose(FILE *f);
There is no INIT operator (an argument is mandatory), no INIT_SET operator.
It is only possible to open a file from a filename.
FILE* contains some space, so an alias is needed.
There is an optional mode argument, which is a constant string, and isn't a valid preprocessing token.
An oplist can therefore be:
typedef FILE *m_file_t;
#define M_OPL_m_file_t() (INIT_WITH(API(fopen, ARG1, ARG2, ID("wt"))), \
SET(0),INIT_SET(0),CLEAR(fclose),TYPE(m_file_t))
Since there is no INIT_SET operator available, pretty much no container can work.
However, you'll be able to use a writing text FILE* using a M_LET:
M_LET( (f, ("tmp.txt")), m_file_t) {
fprintf(f, "This is a tmp file.");
}
This is pretty useless, except if you enable exceptions... In which case, this enables you to close the file even if an exception is thrown.
Memory Allocation functions can be globally set by overriding the following macros before using the definition _DEF macros:
M_MEMORY_ALLOC (context, type) --> ptr: return a pointer to a new object of type type.M_MEMORY_DEL (context, ptr): free the single object pointed by ptr.M_MEMORY_REALLOC (context, type, ptr, old_number, new_number) --> ptr: return a pointer to an array of new_number objects of type type, reusing the old array pointed by ptr of old_number objects. ptr can be NULL, in which case the array will be created.M_MEMORY_FREE (context, type, ptr, number): free the array of number objects of type type pointed by ptr.[!NOTE] You can use
sizeof (type)andalignof (type)to get the size and the alignment of the object.
[!NOTE] For
M_MEMORY_DEL,sizeof *ptralways identifies the size of the object.
ALLOC and DEL operators are supposed to allocate fixed size single element object (no array).
These objects are not expected to grow.
REALLOC and FREE operators deal with allocated memory for growing objects.
Do not mix pointers between both: a pointer allocated by ALLOC (resp. REALLOC) is supposed
to be only freed by DEL (resp. FREE). There are separated 'free' operators to enable
specialization in the allocator (a good allocator can take this hint into account).
context is a local user context used to identify the memory context to use for the allocation.
This parameter only exists if the library is compiled with the M_USE_CONTEXT customization parameter enabled globally.
Otherwise this parameter identifies a non existing symbol m_context.
This parameter shall be discarded if M_USE_CONTEXT is not defined (it shall not exist anymore after preprocessing step).
For that, you can define the macros to ignore the first parameter
or you can use GAIA to adapt the call to what your function expects.
[!NOTE] If you get error on
m_contextbeing undefined it is likely because one of your memory is trying to evaluate the memory context without definingM_USE_CONTEXT.
M_MEMORY_ALLOC and M_MEMORY_REALLOC are supposed to return NULL in case of memory allocation failure.
The defaults are malloc, free, realloc and free.
You can also override the methods NEW, DEL, REALLOC and DEL in the oplist given to a container
so that only the container will use these memory allocation functions instead of the global ones.
When a memory exhaustion is reached, the global macro M_MEMORY_FULL is called.
It is supposed to terminate the execution flow of the function.
The object remains in a valid (if previously valid) and unchanged state in this case.
By default, the macro prints an error message and aborts the program: handling non-trivial memory errors can be hard, testing them is even harder but still mandatory to avoid security holes. So the default behavior is rather conservative.
It can however be overloaded to handle other policy for error handling like: throwing an error (which is automatically done by including header m-try ).
This function takes the type and the number of elements of this type that has been tried to be allocated.
If needed, this macro shall be defined prior to instantiate the structure.
## Error Classification
[!NOTE] A good design should handle a process entire failure (using for examples multiple processes for doing the job) so that even if a process stops, it should be recovered. See here for more information about why abandonment is good software practice.
In M*LIB, the kind of errors are classified according to this model:
M_MEMORY_FULL macro).ferror) in the data structure.For M*LIB, 'emplace' means pushing a new object in the container,
while not giving it a copy of the new object, but the parameters needed
to construct this object.
This is a shortcut to the pattern of creating the object with the arguments,
pushing it in the container, and deleting the created object
(even if using PUSH_MOVE could simplify the design).
The containers defining an emplace like method generate the emplace functions
based on the provided EMPLACE_TYPE of the oplist. If EMPLACE_TYPE doesn't exist or is disabled, no emplace function is generated. Otherwise EMPLACE_TYPE identifies
which types can be used to construct the object and which methods to use to construct then:
EMPLACE_TYPE( typeA ), means that the object can be constructed from typeA using the method of the INIT_WITH operator. An emplace function without suffix will be generated.EMPLACE_TYPE( (typeA, typeB, ...) ), means that the object can be constructed from the lists of types typeA, typeB, ... using the method of the INIT_WITH operator. An emplace function without suffix will be generated.EMPLACE_TYPE( LIST( (suffix, function, typeA, typeB, ...), (suffix, function, typeA, typeB, ...) means that the object can be constructed from all the provided lists of types typeA, typeB, ... using the provided method function. The function is the method to call to construct the object from the list of types. It supports API transformation if needed. As many emplace function will be generated as there are constructor function. Each generated function will be generated by suffixing it with the provided suffix (if suffix is empty, no suffix will be added).For example, for an ARRAY definition named vec, if there is such a definition of EMPLACE_TYPE(const char *), it will generate a function vec_emplace_back(const char *). This function will take a const char* parameter, construct the object from it (for example a string_t) then push the result back on the array.
Another example, for an ARRAY definition named vec, if there is such a definition of EMPLACE_TYPE( LIST( (_ui, mpz_init_set_ui, unsigned int), (_si, mpz_init_set_si, int) ) ), it will generate two functions vec_emplace_back_ui(unsigned int) and vec_emplace_back_si(int). These functions will take the (unsigned) int parameter, construct the object from it then push the result back on the array.
If the container is an associative array, the name will be constructed as follows:
name_emplace[_key_keysuffix][_val_valsuffix]
where keysuffix (resp. valsuffix) is the emplace suffix of the key (resp. value) oplist.
If you take once again the example of the FILE*, a more complete oplist can be:
typedef FILE *m_file_t;
#define M_OPL_m_file_t() (INIT_WITH(API_1(M_INIT_WITH_THROUGH_EMPLACE_TYPE)), \
SET(0),INIT_SET(0),CLEAR(fclose),TYPE(m_file_t), \
EMPLACE_TYPE(LIST((_str, API(fopen, ARG1, ARG2, ID("wb")), char *))))
The INIT_WITH operator will use the provided init methods in the EMPLACE_TYPE.
EMPLACE_TYPE defines a _str suffix method with a GAIA for fopen, and accepts a char* as argument.
The GAIA specifies that the output (ARG1) is set as return value,
ARG2 is given as the first argument, and a third constant argument is used.
M*LIB implements internally some controls to reduce the list of errors/warnings generated by a compiler when it detects some violation in the use of oplist by use of static assertion. It can also transform some type warnings into proper errors. In C99 mode, it will produce illegal code with the name of the error as attribute. In C11 mode, it will use static assert and produce a detailed error message.
The list of errors it can generate:
M_LIB_NOT_AN_OPLIST: something has been given (directly or indirectly) and it doesn't reduce as a proper oplist. You need to give an oplist for this definition.M_LIB_ERROR(ARGUMENT_OF_*_OPLIST_IS_NOT_AN_OPLIST, name, oplist): sub error of the previous error one, identifying the root cause. The error is in the oplist construction of the given macro. You need to give an oplist for this oplist construction.M_LIB_MISSING_METHOD: a required operator doesn't define any method in the given oplist. You need to complete the oplist with the missing method.M_LIB_TYPE_MISMATCH: the given oplist and the type do not match each other. You need to give the right oplist for this type.M_LIB_NOT_A_BASIC_TYPE: The oplist M_BASIC_OPLIST (directly or indirectly) has been used with the given type, but the given type is not a basic C type (int/float). You need to give the right oplist for this type.M_LIB_DIMENSION_ERROR: a macro expects a number of arguments and doesn't get it.Compilers can be very verbose on the error message:
You should focus mainly on the first reported error/warning
even if the link between what the compiler report and what the error is
is not immediate. The error is likely in one of the oplist definition.
Use of the flag -Wfatal-errors to stop on the first reported error.
Examples of typical errors:
NEW, DEL, INIT, OPLIST, ...),( ) or double level of ( ) around the oplist,BASIC_OPLIST instead of M_BASIC_OPLIST),name parameter given to the oplist is not the same as the one used to expand the methods,OPLIST definition (there is no registered type using M_OPL_ or the registered type doesn't match the name of the type),OPLIST definition.A good way to avoid these errors is to register the oplist of the type globally as soon as you define the container (to associated its oplist to the type).
In case of difficulties, debugging can be done by generating the preprocessed file
(by usually calling the compiler with the -E option instead of -c)
and check what's wrong in the preprocessed file:
cc -std=c99 -E test-file.c |grep -v '^#' > test-file.i
perl -i -e 's/;/;\n/g' test-file.i
cc -std=c99 -c -Wall test-file.i
Or you can use the cc.sh script in the doc folder instead of your Unix compiler
(it will automate theses steps, allowing you to see exactly the preprocessed code and
why the compiler reports an error).
You can define SUB_CC as an environement variable to define the sub compiler to
use for this script.
If you get the error "assignment to expression with array type", it means that the library
tries using the default '=' operator to set an object which is not compatible:
give the right method to the needed operator (usually INIT_MOVE or INIT_SET) in its oplist
or use the proper oplist of the type.
If there is a warning reported by the compiler in the generated code, then there is definitely an error you should fix (except if it reports shadowed variables), in particular cast evolving pointers.
You should also turn off the macro expansion of the errors reported by your compiler. There are often completely useless and misleading:
-ftrack-macro-expansion=0-fmacro-backtrace-limit=1Due to the unfortunate weak nature of the C language for pointers,
you should turn incompatible pointer type warning into an error in your compiler.
For GCC / CLANG, uses -Werror=incompatible-pointer-types or compile in C23 mode.
For MS Visual C++ compiler , you need the following options:
/Zc:__cplusplus /Zc:preprocessor /D__STDC_WANT_LIB_EXT1__ /EHsc
The M*LIB reference card is available here.
The generated containers tries to generate and provide a consistent interface: their methods would behave the same for all generated containers. This chapter will explain the common generated interface. In case of difference, it will be explained in the specific container.
In the following description:
name is the prefix used for the container generation,name_t refers to the type of the container,name_it_t refers to the iterator type of the container,type_t refers to the type of the object stored in the container,key_type_t refers to the type of the key object used to associate an element to,value_type_t refers to the type of the value object used to associate an element to.name_itref_t refers to a pair of key and value for associative arrays.An object shall be initialized (aka constructor) before being used by other methods. It shall be cleared (aka destructor) after being used and before program termination. An iterator has not destructor but shall be set before being used.
A container takes as input the
name — it is a mandatory argument that is the prefix used to generate all functions and types,type — it is a mandatory argument that the basic element of the container,oplist — it is an optional argument that defines the methods associated to the type. The provided oplist (if provided) shall be the one that is associated to the type, otherwise it won't generate compilable code. If there is no oplist parameter provided, a globally registered oplist associated to the type is used if possible, or the basic oplist for basic C types is used. This oplist will be used to handle internally the objects of the container.The type given to any templating macro can be either
an integer, a float, a boolean, an enum, a named structure, a named union, a pointer to such types,
or a typedef alias of any C type:
in fact, the only constraint is that the preprocessing concatenation between type and variable into
'type variable' shall be a valid C expression.
Therefore the type cannot be a C array or a function pointer
and you shall use a typedef as an intermediary named type for such types.
The output parameters are listed first, then the input/output parameters and finally the input parameters.
The oplist shall also provide the INIT_MOVE operator if the default instance (aka '=' operator) is not working for this type (for example for array of size 1, in which case the method M_COPY_A1OBJ is likely to work), or you need to disable the operator.
This common interface is specified as follow:
void name_init(name_t container)Initialize the container container (aka constructor) to an empty container.
Also called the default constructor of the container.
container shall be not initialized
void name_init_set(name_t container, const name_t ref)Initialize the container container (aka constructor) and set it to a copy of ref.
This method is only created if the INIT_SET & SET methods are provided.
Also called the copy constructor of the container.
container shall be not initialized
void name_set(name_t container, const name_t ref)Set the container container to the copy of ref.
This method is only created if the INIT_SET and SET methods are provided.
void name_init_move(name_t container, name_t ref)Initialize the container container (aka constructor)
by stealing as many resources from ref as possible.
After-wise ref is cleared and can no longer be used (aka destructor).
container shall be not initialized
void name_move(name_t container, name_t ref)Set the container container (aka constructor)
by stealing as many resources from ref as possible.
After-wise ref is cleared and can no longer be used (aka destructor).
container shall not be the same object as ref
void name_clear(name_t container)Clear the container container (aka destructor),
calling the CLEAR method of all the objects of the container and freeing memory.
The object can't be used anymore, except to be reinitialized with a constructor.
void name_reset(name_t container)Reset the container clearing and freeing all objects stored in it. The container becomes empty but remains initialized.
type_t *name_back(const name_t container)Return a pointer to the data stored in the back of the container.
This pointer should not be stored in a global variable.
container shall be not empty.
type_t *name_front(const name_t container)Return a pointer to the data stored in the front of the container.
This pointer should not be stored in a global variable.
container shall be not empty.
void name_push(name_t container, const type_t value)void name_push_back(name_t container, const type_t value)void name_push_front(name_t container, const type_t value)Push a new element in the container container as a copy of the object value.
This method is created only if the INIT_SET operator is provided.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
type_t *name_push_back_raw(name_t container)type_t *name_push_front_raw(name_t container)Push a new element in the container container
without initializing it and returns a borrowed pointer to the non-initialized data.
The first thing to do after calling this function shall be to initialize the data
using the proper constructor of the object of type type_t.
This enables using more specialized constructor than the generic copy one.
The user should use other _push functions if possible rather than this one
as it is low level and error prone.
This pointer should not be stored in a global variable.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
type_t *name_push_new(name_t container)type_t *name_push_back_new(name_t container)type_t *name_push_front_new(name_t container)Push a new element in the container container
and initialize it with the default constructor associated to the type type_t.
Return a borrowed pointer to the initialized object.
This pointer should not be stored in a global variable.
This method is only created if the INIT method is provided.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
void name_push_move(name_t container, type_t *value)void name_push_back_move(name_t container, type_t *value)void name_push_front_move(name_t container, type_t *value)Push a new element in the container container
as a move from the object *value:
it will therefore steal as much resources from *value as possible.
Afterward *value is cleared and cannot longer be used (aka. destructor).
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
void name_emplace[suffix](name_t container, args...)void name_emplace_back[suffix](name_t container, args...)void name_emplace_front[suffix](name_t container, args...)Push a new element in the container container
by initializing it with the provided arguments.
The provided arguments shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator.
There is one generated method per suffix defined in the EMPLACE_TYPE operator,
and the suffix in the generated method name corresponds to the suffix defined
in the EMPLACE_TYPE operator (it can be empty).
This method is created only if the EMPLACE_TYPE operator is provided.
See emplace chapter for more details.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
void name_pop(type_t *data, name_t container)void name_pop_back(type_t *data, name_t container)void name_pop_front(type_t *data, name_t container)Pop a element from the container container;
and set *data to this value if data is not the NULL pointer,
otherwise it only pops the data.
This method is created if the SET or INIT_MOVE operator is provided.
The _back suffixed method will pop it from the back of the container.
The _front suffixed method will pop it from the front of the container.
void name_pop_move(type_t *data, name_t container)void name_pop_move_back(type_t *data, name_t container)void name_pop_move_front(type_t *data, name_t container)Pop a element from the container container
and initialize and set *data to this value (aka. constructor)
by stealing as much resources from the container as possible.
data shall not be a NULL pointer.
The _back suffixed method will pop it from the back of the container.
The _front suffixed method will pop it from the front of the container.
bool name_empty_p(const name_t container)Return true if the container is empty, false otherwise.
void name_swap(name_t container1, name_t container2)Swap the container container1 and container2.
void name_set_at(name_t container, size_t key, type_t value)void name_set_at(name_t container, key_type_t key, value_type_t value) [for associative array]Set the element associated to key of the container container to value.
If the container is sequence-like (like array), the key is an integer.
The selected element is the key-th element of the container,
The index key shall be within the size of the container.
This method is created if the INIT_SET operator is provided.
If the container is associative-array like,
the selected element is the value object associated to the key object in the container.
It is created if it doesn't exist, overwritten otherwise.
void name_emplace_key[keysuffix](name_t container, keyargs..., value_type_t value) [for associative array]void name_emplace_val[valsuffix](name_t container, key_type_t key, valargs...) [for associative array]void name_emplace_key[keysuffix]_val[valsuffix](name_t container, keyargs..., valargs...) [for associative array]Set the element associated to key of the container container to value.
key (resp. value) is constructed from the provided args keyargs (resp. valargs) if not provided.
keyargs (resp. valargs) shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator of the key (resp. the value).
There is:
EMPLACE_TYPE operator of the key,EMPLACE_TYPE operator of the value,EMPLACE_TYPE operators of the key and value,The suffix in the generated method name corresponds to the suffix defined in
in the EMPLACE_TYPE operator (it can be empty).
This method is created only if one EMPLACE_TYPE operator is provided.
See emplace chapter for more details.
type_t *name_get(const name_t container, size_t key) [for sequence-like]const type_t *name_cget(const name_t container, size_t key) [for sequence-like]type_t *name_get(const name_t container, const type_t key) [for set-like]const type_t *name_cget(const name_t container, const type_t key) [for set-like]value_type_t *name_get(const name_t container, const key_type_t key) [for associative array]const value_type_t *name_cget(const name_t container, const key_type_t key) [for associative array]Return a modifiable (resp. constant) borrowed pointer to
the element associated to key in the container.
If the container is sequence-like, the key is an integer.
The selected element is the key-th element of the container,
the front being at the index 0, the last at the index (size-1).
The index key shall be within the size of the container.
Therefore, it will never return NULL in this case.
If the container is associative array like,
the selected element is the value object associated to the key object in the container.
If the key is not found, it returns NULL.
If the container is set-like,
the selected element is the value object which is equal to the key object in the container.
If the key is not found, it returns NULL.
This pointer remains valid until the container is modified by another method. This pointer should not be stored in a global variable.
type_t *name_get_emplace[suffix](const name_t container, args...) [for set-like]value_type_t * name_get_emplace[suffix](name_t container, args...) [for associative array]Return a modifiable (resp. constant) borrowed pointer to
the element associated to the key constructed from args in the container.
The selected element is the value object associated to the key object in the container
for an associative array, or the element itself for a set.
If the key is not found, it returns NULL.
This pointer remains valid until the container is modified by another method. This pointer should not be stored in a global variable.
type_t *name_safe_get(name_t container, size_t key) [for sequence]type_t *name_safe_get(name_t container, const type_t key) [for set]value_type_t *name_safe_get(name_t container, const key_type_t key) [for associative array]Return a modifiable borrowed pointer to
the element associated to key in the container,
creating a new element if it doesn't exist (ensuring therefore a safe get operation).
If the container is sequence-like, key_type_t is an alias for size_t and key an integer,
the selected element is the key-th element of the container.
If the element doesn't exist, the container size will be increased
if needed (creating new elements with the INIT operator),
which might increase the container to much in some cases.
The returned pointer cannot be NULL.
This method is only created if the INIT method is provided.
This pointer remains valid until the array is modified by another method.
This pointer should not be stored in a global variable.
bool name_erase(name_t container, const size_t key)bool name_erase(name_t container, const type_t key) [for set]bool name_erase(name_t container, const key_type_t key) [for associative array]Remove the element referenced by the key key in the container container.
Do nothing if key is no present in the container.
Return true if the key was present and erased, false otherwise.
size_t name_size(const name_t container)Return the number elements of the container (its size). Return 0 if there is no element.
size_t name_capacity(const name_t container)Return the capacity of the container, i.e. the maximum number of elements supported by the container before a reserve operation is needed to accommodate new elements.
void name_resize(name_t container, size_t size)Resize the container container to the size size,
increasing or decreasing the size of the container
by initializing new elements or clearing existing ones.
This method is only created if the INIT method is provided.
void name_reserve(name_t container, size_t capacity)Extend or reduce the capacity of the container to a rounded value based on capacity.
If the given capacity is below the current size of the container,
the capacity is set to a rounded value based on the size of the container.
Therefore a capacity of 0 is used to perform a shrink-to-fit operation on the container,
i.e. reducing the container usage to the minimum possible allocation.
void name_it(name_it_t it, const name_t container)Set the iterator it to the first element of the container container.
There is no destructor associated to this initialization.
void name_it_set(name_it_t it, const name_it_t ref)Set the iterator it to the iterator ref.
There is no destructor associated to this initialization.
void name_it_end(name_it_t it, const name_t container)Set the iterator it to a non valid element of the container.
There is no destructor associated to this initialization.
void name_it_last(name_it_t it, const name_t container)Set the iterator it to the last element of the container.
There is no destructor associated to this initialization.
bool name_end_p(const name_it_t it)Return true if the iterator doesn't reference a valid element anymore.
bool name_last_p(const name_it_t it)Return true if the iterator references the last element of the container or if the iterator doesn't reference a valid element anymore.
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)Return true if the iterator it1 references the same element than the iterator it2.
void name_next(name_it_t it)Move the iterator to the next element of the container. Afterwards, the moved iterator may reference an invalid element.
void name_previous(name_it_t it)Move the iterator it to the previous element of the container.
Afterwards, the moved iterator may reference an invalid element.
type_t *name_ref(name_it_t it)const type_t *name_cref(const name_it_t it)name_itref_t *name_ref(name_it_t it) [for associative array]const name_itref_t *name_cref(name_it_t it) [for associative array]Return a modifiable (resp. constant) borrowed pointer to the element pointed by the iterator.
For associative-array like container, this element is the pair composed of
the key (key field) and the associated value (value field);
otherwise this element is simply the basic type of the container (type_t).
The iterator shall reference a valid element. This pointer should not be stored in a global variable. This pointer remains valid until the container is modified by another method.
void name_insert(name_t container, const name_it_t it, const type_t x)Insert the object x after the position referenced by the iterator it in the container container
or if the iterator it doesn't reference anymore to a valid element of the container,
it is added as the first element of the container.
it shall be an iterator of the container container.
void name_remove(name_t container, name_it_t it)Remove the element referenced by the iterator it from the container container.
it shall be an iterator of the container container.
Afterwards, it references the next element of the container if it exists,
or not a valid element otherwise.
bool name_equal_p(const name_t container1, const name_t container2)Return true if both containers container1 and container2 are considered equal.
This method is only created if the EQUAL method is provided.
size_t name_hash(const name_t container)Return a fast hash value of the container container,
suitable to be used by a dictionary.
This method is only created if the HASH method is provided.
void name_get_str(string_t str, const name_t container, bool append)Set str to the formatted string representation of the container container if append is false
or append str with this representation if append is true.
This method is only created if the GET_STR method is provided.
bool name_parse_str(name_t container, const char str[], const char **endp)Parse the formatted string str,
that is assumed to be a string representation of a container,
and set container to this representation.
It returns true if success, false otherwise.
If endp is not NULL, it sets *endp to the pointer of the first character not
decoded by the function (or where the parsing fails).
This method is only created if the PARSE_STR & INIT methods are provided.
It is ensured that the container gets from parsing a formatted string representation
gets from name_get_str and the original container are equal.
void name_out_str(FILE *file, const name_t container)Generate a formatted string representation of the container container
and outputs it into the file FILE*.
The file FILE* shall be opened in write text mode and without error.
This method is only created if the OUT_STR methods is provided.
bool name_in_str(name_t container, FILE *file)Read from the file FILE* a formatted string representation of a container
and set container to this representation.
It returns true if success, false otherwise.
This method is only created if the IN_STR & INIT methods are provided.
It is ensured that the container gets from parsing a formatted string representation gets from name_out_str and the original container are equal.
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)Output the container container into the serializing object serial.
How and where it is output depends on the serializing object.
It returns M_SERIAL_OK_DONE in case of success,
or M_SERIAL_FAILURE in case of failure.
In case of failure, the serializing object is in an unspecified but valid state.
This method is only created if the OUT_SERIAL methods is provided.
m_serial_return_code_t name_in_serial(name_t container, m_serial_read_t serial)Read from the serializing object serial a representation of a container
and set container to this representation.
It returns M_SERIAL_OK_DONE in case of success,
or M_SERIAL_FAILURE in case of failure.
In case of failure, the serializing object is in an unspecified but valid state.
This method is only created if the IN_SERIAL & INIT methods are provided.
It is ensured that the container gets from parsing a representation gets from name_out_serial and the original container are equal (using the same type of serialization object).
This header is for creating singly linked list.
A linked list is a linear collection of elements, in which each element points to the next, all of then representing a sequence.
A fundamental property of a list is that the objects created within the list will remain at their initialized address, and won't moved due to operations done on the list (except if it is removed). Therefore a returned pointer to an element of the container remains valid until this element is destroyed in the container.
LIST_DEF(name, type [, oplist])LIST_DEF_AS(name, name_t, name_it_t, type [, oplist])LIST_DEF defines the singly linked list named name_t
that contains objects of type type and their associated methods as static inline functions.
name shall be a C identifier that will be used to identify the list.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
For this container, the back is always the first element, and the front is the last element: the list grows from the back. Therefore, the iteration of this container using iterator objects will go from the back element to the front element (contrary to an array).
Even if it provides random access functions, theses access are slow and should be avoided: it iterates linearly over all the elements of the container until it reaches the requested element. The size method has the same drawback.
The push/pop methods of the container always operate on the back of the container.
LIST_DEF_AS is the same as LIST_DEF
except the name of the types name_t, name_it_t are provided by the user,
and not computed from the name prefix.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-list.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
LIST_DEF(list_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), \
CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ), OUT_STR(MPZ_OUT_STR)))
int main(void) {
list_mpz_t a;
list_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
list_mpz_push_back (a, x);
mpz_set_ui(x, 45);
list_mpz_push_back (a, x);
mpz_clear(x);
printf ("LIST is: ");
list_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *list_mpz_back(a));
printf ("\n");
list_mpz_clear(a);
}
LIST_OPLIST(name [, oplist])Return the oplist of the list defined by calling LIST_DEF and LIST_DUALB_DEF with name & oplist.
The list behaves list a stack (First In, Last Out).
If there is no given oplist, the basic oplist for basic C types is used.
There is no globally registered oplist support.
LIST_DUALF_OPLIST(name [, oplist])Return the oplist of the list defined by calling LIST_DUALF_DEF with name & oplist.
The list behaves list a fifo (First In, First Out).
If there is no given oplist, the basic oplist for basic C types is used.
There is no globally registered oplist support.
LIST_INIT_VALUE()Define an initial value that is suitable to initialize global variable(s)
of type list as created by LIST_DEF or LIST_DEF_AS.
It enables to create a list as a global variable and to initialize it.
The list shall still be cleared manually to avoid leaking memory.
Example:
LIST_DEF(list_int, int)
list_int_t my_list = LIST_INIT_VALUE();
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the list of type objects.
name_it_tType of an iterator over this list.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t list)
void name_init_set(name_t list, const name_t ref)
void name_set(name_t list, const name_t ref)
void name_init_move(name_t list, name_t ref)
void name_move(name_t list, name_t ref)
void name_clear(name_t list)
void name_reset(name_t list)
type *name_back(const name_t list)
void name_push_back(name_t list, const type value)
type *name_push_back_raw(name_t list)
type *name_push_new(name_t list)
void name_push_move(name_t list, type *value)
void name_emplace_back[suffix](name_t list, args...)
void name_pop_back(type *data, name_t list)
void name_pop_move(type *data, name_t list)
bool name_empty_p(const name_t list)
void name_swap(name_t list1, name_t list2)
void name_it(name_it_t it, const name_t list)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, const name_t list)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
type *name_get(const name_t list, size_t i)
const type *name_cget(const name_t list, size_t i)
size_t name_size(const name_t list)
void name_insert(name_t list, const name_it_t it, const type x)
void name_remove(name_t list, name_it_t it)
void name_get_str(string_t str, const name_t list, bool append)
bool name_parse_str(name_t list, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t list)
bool name_in_str(name_t list, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t list1, const name_t list2)
size_t name_hash(const name_t list)
The following specialized methods are automatically created by the previous definition macro:
void name_splice_back(name_t list1, name_t list2, name_it_t it)Move the element referenced by the iterator it
from the list list2 to the back position of the list list1.
it shall be an iterator of list2.
Afterwards, it references the next element of the list if it exists,
or not a valid element otherwise.
void name_splice_at(name_t list1, name_it_t it1, name_t list2, name_it_t it2)Move the element referenced by the iterator it2 from the list list2
to the position just after it1 in the list list1.
(If it1 is not a valid position, it inserts it at the back just like name_insert).
it1 shall be an iterator of list1.
it2 shall be an iterator of list2.
Afterwards, it2 references the next element of the list if it exists,
or not a valid element otherwise,
and it1 references the inserted element in list1.
void name_splice(name_t list1, name_t list2)Move all the element of the list list2 into the list list1,
moving the last element of list2 after the first element of list1.
Afterwards, list2 remains initialized but is emptied.
list1 and list2 shall reference different objects.
void name_reverse(name_t list)Reverse the order of the list.
LIST_DUALB_DEF(name, type[, oplist])LIST_DUALB_DEF_AS(name, name_t, name_it_t, type [, oplist])LIST_DUALB_DEF defines the singly linked list named name_t
that contains the objects of type type and their associated methods as static inline functions.
The only difference with the list defined by LIST_DEF is
the support of the method for PUSH_FRONT in addition to the one for PUSH_BACK
(therefore both BI Pushes and the pop Back methods are provided - so the BIB name).
However, there is still only POP method (associated to POP_BACK).
The list is a bit bigger to be able to handle such method to work, but not the nodes.
This list is therefore able to represent:
PUSH_BACK + POP_BACK) - which is the default -PUSH_FRONT + POP_BACK).LIST_DUALB_DEF_AS is the same as LIST_DUALB_DEF except the name of the types name_t, name_it_t are provided by the user.
See LIST_DEF for more details and constraints.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-list.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
LIST_DUALB_DEF(list_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), \
CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ), OUT_STR(MPZ_OUT_STR)))
int main(void) {
list_mpz_t a;
list_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
list_mpz_push_back (a, x);
mpz_set_ui(x, 45);
list_mpz_push_back (a, x);
mpz_clear(x);
printf ("LIST is: ");
list_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *list_mpz_back(a));
printf ("\n");
list_mpz_clear(a);
}
The methods follow closely the methods defined by LIST_DEF.
LIST_DUALF_DEF(name, type[, oplist])LIST_DUALF_DEF_AS(name, name_t, name_it_t, type [, oplist])LIST_DUALF_DEF defines the singly linked list named name_t
that contains the objects of type type and their associated methods as static inline functions.
The only difference with the list defined by LIST_DUALB_DEF is POP_BACK is replaced by POP_FRONT.
(therefore both BI Pushes and the pop Forward methods are provided - so the BIF name)
and the list first element is the front, and the last element is the back.
The list is a bit bigger to be able to handle such method to work, but not the nodes.
This list is therefore able to represent:
PUSH_FRONT + POP_FRONT)PUSH_BACK + POP_FRONT) - which is the default -.LIST_DUALF_DEF_AS is the same as LIST_DUALF_DEF except the name of the types name_t, name_it_t are provided by the user.
See LIST_DEF for more details and constraints.
The methods follow closely the methods defined by LIST_DEF.
LIST_DUAL_PUSH_INIT_VALUE()Define an initial value that is suitable to initialize global variable(s)
of type list as created by LIST_DUALB_DEF or LIST_DUALB_DEF_AS or LIST_DUALF_DEF or LIST_DUALF_DEF_AS.
It enables to create a list as a global variable and to initialize it.
The list should still be cleared manually to avoid leaking memory.
Example:
LIST_DUALB_DEF(list_int, int)
list_int_t my_list = LIST_DUAL_PUSH_INIT_VALUE();
The following types are automatically defined by the previous definition macros if not provided by the user:
name_tType of the list of type.
name_it_tType of an iterator over this list.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t list)
void name_init_set(name_t list, const name_t ref)
void name_set(name_t list, const name_t ref)
void name_init_move(name_t list, name_t ref)
void name_move(name_t list, name_t ref)
void name_clear(name_t list)
void name_reset(name_t list)
type *name_back(const name_t list)
void name_push_back(name_t list, type value)
type *name_push_back_raw(name_t list)
type *name_push_back_new(name_t list)
void name_push_back_move(name_t list, type *value)
void name_emplace_back[suffix](name_t list, args...)
const type *name_front(const name_t list)
void name_push_front(name_t list, type value)
type *name_push_front_raw(name_t list)
type *name_push_front_new(name_t list)
void name_push_front_move(name_t list, type *value)
void name_emplace_front[suffix](name_t list, args...)
void name_pop_back(type *data, name_t list) /* For BIB list */
void name_pop_front(type *data, name_t list) /* For BIF list */
void name_pop_move(type *data, name_t list)
bool name_empty_p(const name_t list)
void name_swap(name_t list1, name_t list2)
void name_it(name_it_t it, name_t list)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, const name_t list)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
size_t name_size(const name_t list)
void name_insert(name_t list, const name_it_t it, const type x)
void name_remove(name_t list, name_it_t it)
void name_get_str(string_t str, const name_t list, bool append)
bool name_parse_str(name_t list, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t list)
bool name_in_str(name_t list, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t list1, const name_t list2)
size_t name_hash(const name_t list)
The following specialized methods are automatically created by the previous definition macro:
void name_splice_back(name_t list1, name_t list2, name_it_t it) /* for BIB list */void name_splice_front(name_t list1, name_t list2, name_it_t it) /* for BIF list */Move the element pointed by it
from the list list2 to the back position of the list list1.
it shall be an iterator of list2.
Afterwards, it points to the next element of list2.
void name_splice(name_t list1, name_t list2)Move all the element of the list list2 into the list list1,
moving the last element of list2 after the first element of list1.
Afterwards, list2 is emptied.
list1 and list2 shall reference different objects.
void name_reverse(name_t list)Reverse the order of the list.
An array is a growable collection of element that are individually indexable.
ARRAY_DEF(name, type [, oplist])ARRAY_DEF_AS(name, name_t, name_it_t, type [, oplist])ARRAY_DEF defines the array name_t that contains the objects of type type
in a sequence
and its associated methods as static inline functions.
Compared to C arrays, the created methods handle automatically the size (aka growable array).
name shall be a C identifier that will be used to identify the container.
It will be used to create all the types (including the iterator)
and functions to handle the container.
The provided oplist shall have at least the following operators (CLEAR).
It should also provide the following operators (INIT, INIT_SET, SET),
so that at least some methods are defined for the array!
The object of type type shall be trivially movable.
The push / pop methods of the container always operate on the back of the container, acting like a stack-like container.
ARRAY_DEF_AS is the same as ARRAY_DEF except the name of the types name_t, name_it_t
are provided by the user.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
ARRAY_DEF(array_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), \
CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ), OUT_STR(MPZ_OUT_STR)))
int main(void) {
array_mpz_t a;
array_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
array_mpz_push_back (a, x);
mpz_set_ui(x, 45);
array_mpz_push_back (a, x);
mpz_clear(x);
printf ("ARRAY is: ");
array_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *array_mpz_get(a, 0));
printf ("\n");
array_mpz_clear(a);
}
ARRAY_OPLIST(name [, oplist])Return the oplist of the array defined by calling ARRAY_DEF with name & oplist.
If there is no given oplist, the basic oplist for basic C types is used.
ARRAY_INIT_VALUE()Define an initial value that is suitable to initialize global variable(s)
of type array as created by ARRAY_DEF or ARRAY_DEF_AS.
It enables to create an array as a global variable and to initialize it.
The array should still be cleared manually to avoid leaking memory.
Example:
ARRAY_DEF(array_int_t, int)
array_int_t my_array = ARRAY_INIT_VALUE();
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the array of type.
name_it_tType of an iterator over this array.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t array)
void name_init_set(name_t array, const name_t ref)
void name_set(name_t array, const name_t ref)
void name_init_move(name_t array, name_t ref)
void name_move(name_t array, name_t ref)
void name_clear(name_t array)
void name_reset(name_t array)
type *name_push_back_raw(name_t array)
void name_push_back(name_t array, const type value)
type *name_push_new(name_t array)
void name_push_move(name_t array, type *val)
void name_emplace_back[suffix](name_t array, args...)
void name_pop_back(type *data, name_t array)
void name_pop_move(type *data, name_t array)
type *name_front(const name_t array)
type *name_back(const name_t array)
void name_set_at(name_t array, size_t i, type value)
type *name_get(name_t array, size_t i)
const type *name_cget(const name_t it, size_t i)
type *name_safe_get(name_t array, size_t i)
bool name_empty_p(const name_t array)
size_t name_size(const name_t array)
size_t name_capacity(const name_t array)
void name_resize(name_t array, size_t size)
void name_reserve(name_t array, size_t capacity)
void name_swap(name_t array1, name_t array2)
void name_it(name_it_t it, name_t array)
void name_it_last(name_it_t it, name_t array)
void name_it_end(name_it_t it, name_t array)
void name_it_set(name_it_t it1, name_it_t it2)
bool name_end_p(name_it_t it)
bool name_last_p(name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
void name_previous(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
void name_remove(name_t array, name_it_t it)
void name_insert(name_t array, name_it_t it, const type x)
void name_get_str(string_t str, const name_t array, bool append)
bool name_parse_str(name_t array, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t array)
bool name_in_str(name_t array, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t array1, const name_t array2)
size_t name_hash(const name_t array)
The following specialized methods are automatically created by the previous definition macro:
void name_push_at(name_t array, size_t key, const type x)Push a new element into the position key of the array array
with the value value.
All elements after the position key (included) will be moved in the array towards the back,
and the array will have one more element.
key shall be a valid position of the array: from 0 to the size of array (included).
This method is created only if the INIT_SET operator is provided.
void name_pop_until(name_t array, array_it_t position)Pop all elements of the array array from 'position' to the back of the array,
while clearing them.
This method is created only if the INIT operator is provided.
void name_pop_at(type *dest, name_t array, size_t key)Set *dest to the value the element key if dest is not NULL,
then remove the element key from the array (decreasing the array size).
key shall be within the size of the array.
This method is created only if the SET or INIT_MOVE operator is provided.
void name_remove_v(name_t array, size_t i, size_t j)Remove the element i (included) to the element j (excluded)
from the array.
i and j shall be within the size of the array, and i < j.
void name_insert_v(name_t array, size_t i, size_t num)Insert from the element i (included) num new empty elements to the array.
i shall be within the size of the array.
This method is only defined if the type of the element defines an INIT method.
void name_insert_n(name_t array, size_t i, size_t num, type array_value[num])Insert from the element i (included) num new elements to the array initialized to the values of the array array_value.
i shall be within the size of the array.
void name_swap_at(name_t array, size_t i, size_t j)Swap the elements i and j of the array array.
i and j shall reference valid elements of the array.
This method is created if the INIT_SET or INIT_MOVE operator is provided.
void name_special_sort(name_t array, int (*func_type) (type const *a, type const *b))Sort the array array.
This method uses the qsort function of the C library using func_type.
void name_special_stable_sort(name_t array)Sort the array array using a stable sort.
This method is defined if the type of the element defines CMP and SWAP and SET methods.
This method provides an ad-hoc implementation of the stable sort.
In practice, it is faster than the _sort method for small types and fast
comparisons.
void name_splice(name_t array1, name_t array2)Move all the elements of the array array2 to the end of the array array1.
Afterwards, array2 is empty.
array1 and array2 shall reference different objects.
This header is for creating double-ended queue (or deque). A deque is an abstract data type that generalizes a queue, for that elements can be added to or removed from either the front (head) or back (tail)
DEQUE_DEF(name, type [, oplist])DEQUE_DEF_AS(name, name_t, name_it_t, type [, oplist])DEQUE_DEF defines the deque name_t that contains the objects of type type and its associated methods as static inline functions.
name shall be a C identifier that will be used to identify the deque.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The oplist shall have at least the following operators (INIT, INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The algorithm complexity to access random elements is in O(ln(n)). Removing an element may unbalance the deque, which breaks the promise of algorithm complexity for the _get method.
DEQUE_DEF_AS is the same as DEQUE_DEF
except the name of the types name_t, name_it_t are provided.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-deque.h"
DEQUE_DEF(deque_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ)))
int main(void) {
deque_mpz_t a;
deque_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
deque_mpz_push_back (a, x);
mpz_set_ui(x, 45);
deque_mpz_push_front (a, x);
deque_mpz_pop_back(&x, a);
mpz_set_ui(x, 5);
deque_mpz_push_back (a, x);
mpz_clear(x);
printf ("First element is: ");
mpz_out_str(stdout, 0, *deque_mpz_front(a));
printf ("\n");
printf ("Last element is: ");
mpz_out_str(stdout, 0, *deque_mpz_back(a));
printf ("\n");
deque_mpz_clear(a);
}
DEQUE_OPLIST(name [, oplist])Return the oplist of the deque defined by calling DEQUE_DEF with name oplist.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the deque of type.
name_it_tType of an iterator over this deque.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t deque)
void name_init_set(name_t deque, const name_t ref) /* If INIT_SET operator is defined */
void name_set(name_t deque, const name_t ref) /* If INIT_SET operator is defined */
void name_init_move(name_t deque, name_t ref)
void name_move(name_t deque, name_t ref)
void name_clear(name_t deque)
void name_reset(name_t deque)
type *name_back(const name_t deque)
void name_push_back(name_t deque, type value) /* If INIT_SET operator is defined */
type *name_push_back_raw(name_t deque)
type *name_push_back_new(name_t deque)
void name_emplace_back[suffix](name_t list, args...)
void name_pop_back(type *data, name_t deque)
type *name_front(const name_t deque)
void name_push_front(name_t deque, type value) /* If INIT_SET operator is defined */
type *name_push_front_raw(name_t deque)
type *name_push_front_new(name_t deque)
void name_emplace_front[suffix](name_t list, args...)
void name_pop_front(type *data, name_t deque)
bool name_empty_p(const name_t deque)
void name_swap(name_t deque1, name_t deque2)
void name_it(name_it_t it, name_t deque)
void name_it_set(name_it_t it, const name_it_t ref)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
void name_previous(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
void name_remove(name_t deque, name_it_t it)
type *name_get(const name_t deque, size_t i)
const type *name_cget(const name_t deque, size_t i)
void name_set_at(name_t deque, size_t i, type const value) /* If SET operator is defined */
size_t name_size(const name_t deque)
void name_get_str(string_t str, const name_t deque, bool append)
bool name_parse_str(name_t deque, const char str[], const char **endp) /* If INIT, INIT_SET, PARSE_STR operator are defined */
void name_out_str(FILE *file, const name_t deque)
bool name_in_str(name_t deque, FILE *file) /* If INIT, INIT_SET, PARSE_STR operator are defined */
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial) /* If INIT, INIT_SET, PARSE_STR operator are defined */
bool name_equal_p(const name_t deque1, const name_t deque2)
size_t name_hash(const name_t deque)
void name_swap_at(name_t deque, size_t i, size_t j)
A dictionary (or associative array, map, symbol table) is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection, and is associated to only one value. It is possible to search for a key in the dictionary and get back its value.
Several dictionaries are proposed. The "best" to use depends on the data type
and in particular the size of the data.
For very small, fast types (integer, or floats, or pair of such types),
DICT_OA_DEF2 may be the best to use (but slightly more complex to instantiate).
However DICT_DEF2 should be good enough for all scenarios.
DICT_DEF2(name, key_type[, key_oplist], value_type[, value_oplist])DICT_DEF2_AS(name, name_t, name_it_t, name_itref_t, key_type[, key_oplist], value_type[, value_oplist])DICT_DEF2 defines the dictionary name_t and its associated methods as static inline functions as an associative array of key_type to value_type.
name shall be a C identifier that will be used to identify the dictionary.
It will be used to create all the types (including the iterator and the iterated object type)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
Both oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The key_oplist shall also define the additional operators (HASH and EQUAL).
[!NOTE] You can either call this macro with only
key_typeandvalue_typeor with their type+oplistskey_type,key_oplist,value_typeandvalue_oplist. You cannot call it with an oplist for a type and not for the other (Otherwise it won't be able to identify reliably what is the third argument - avalue_typeor akey_oplist?) Failure to respect this rule so will result in a too few argument error forM_D1CT_DEF2_P2internal macro.
Elements in the dictionary are unordered. On insertion of a new element, contained objects may moved. Maximum number of elements of this dictionary is 3'006'477'107 elements.
The _set_at method overwrites the already existing value if key is already present in the dictionary
(contrary to C++).
The iterated object type name##_itref_t is a pair of key_type and value_type.
What is exactly the "first" element for the iteration is not specified. It is only ensured that all elements of the dictionary are explored by going from "first" to "end".
DICT_DEF2_AS is the same as DICT_DEF2
except the name of the types name_t, name_it_t, name_itref_t are provided.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-dict.h"
DICT_DEF2(dict_string, string_t, unsigned)
int main(void) {
dict_string_t a;
dict_string_init(a);
string_t x;
string_init_set_str(x, "This is an example");
dict_string_set_at (a, x, 1);
string_set_str(x, "This is an another example");
dict_string_set_at (a, x, 2);
string_set_str(x, "This is an example");
unsigned *val = dict_string_get(a, x);
printf ("Value of %s is %u\n", string_get_cstr(x), *val);
string_clear(x);
printf ("Dictionary is: ");
dict_string_out_str(stdout, a);
printf ("\n");
dict_string_clear(a);
}
DICT_OA_DEF2(name, key_type[, key_oplist], value_type[, value_oplist])DICT_OA_DEF2_AS(name, name_t, name_it_t, name_itref_t, key_type[, key_oplist], value_type[, value_oplist])DICT_OA_DEF2 defines the dictionary name_t and its associated methods
as static inline functions much like DICT_DEF2.
The difference is that it uses an Open Addressing Hash-Table as container
that stores the data with the table.
The key_oplist shall also define the additional operators:
OOR_EQUAL and OOR_SET
The Out-Of-Range operators (OOR_EQUAL and OOR_SET) are used to store uninitialized keys
in the dictionary and be able to detect it. This enables avoiding a separate bit-field
to know the state of the entry in the dictionary (which increases memory
usage and is cache unfriendly).
The elements may move when inserting / deleting other elements (and not just the iterators).
This implementation is in general faster for small types of keys (like integer or float) but are slower for larger types.
[!NOTE] You can either call this macro with only
key_typeandvalue_typeor with their type+oplistskey_type,key_oplist,value_typeandvalue_oplist. You cannot call it with an oplist for a type and not for the other (Otherwise it won't be able to identify reliably what is the third argument - avalue_typeor akey_oplist?) Failure to respect this rule so will result in a too few argument error forM_D1CT_DEF2_P2internal macro.
DICT_OA_DEF2_AS is the same as DICT_OA_DEF2
except the name of the types name_t, name_it_t, name_itref_t are provided.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-dict.h"
// Define an Out Of Range equal function
static inline bool oor_equal_p(unsigned k, unsigned char n) {
return k == (unsigned)(-n-1);
}
// Define an Out Of Range function
static inline void oor_set(unsigned *k, unsigned char n) {
*k = (unsigned)(-n-1);
}
DICT_OA_DEF2(dict_unsigned, unsigned, M_OPEXTEND(M_BASIC_OPLIST,
OOR_EQUAL(oor_equal_p), OOR_SET(API_2(oor_set))), long long, M_BASIC_OPLIST)
unsigned main(void) {
dict_unsigned_t a;
dict_unsigned_init(a);
dict_unsigned_set_at (a, 13566, 14890943049);
dict_unsigned_set_at (a, 656, -2);
long long *val = dict_unsigned_get(a, 458);
printf ("Value of %d is %p\n", 458, val); // Not found value
val = dict_unsigned_get(a, 656);
printf ("Value of %d is %lld\n", 656, *val);
dict_unsigned_clear(a);
}
DICT_OPLIST(name[, key_oplist, value_oplist])Return the oplist of the dictionary defined by calling any DICT_*_DEF2 with name, key_oplist, value_oplist.
DICT_SET_DEF(name, key_type[, key_oplist])DICT_SET_DEF_AS(name, name_t, name_it_t, key_type[, key_oplist])DICT_SET_DEF defines the dictionary set name_t and its associated methods as static inline functions.
A dictionary set is a specialized version of a dictionary with no value (only keys).
name shall be a C identifier that will be used to identify the dictionary.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The oplist shall have at least the following operators (INIT_SET, SET, CLEAR, HASH and EQUAL),
otherwise it won't generate compilable code.
The _push method will overwrite the already existing value if key is already present in the dictionary (contrary to C++).
What is exactly the "first" element for the iteration is not specified. It is only ensured that all elements of the dictionary are explored by going from "first" to "end".
DICT_SET_DEF_AS is the same as DICT_SET_DEF
except the name of the types name_t, name_it_t are provided.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-dict.h"
DICT_SET_DEF(set_string, double)
unsigned main(void) {
set_string_t a;
set_string_init(a);
set_string_push (a, 13566);
set_string_push (a, 656);
double *val = set_string_get(a, 458);
printf ("Value of %d is %p\n", 458, val); // Not found value
val = set_string_get(a, 656);
printf ("Value of %d is %f\n", 656, *val);
printf("Set is ");
set_string_out_str(stdout, a);
printf("\n");
set_string_clear(a);
}
DICT_OASET_DEF(name, key_type[, key_oplist])DICT_OASET_DEF_AS(name, name_t, name_it_t, key_type[, key_oplist])DICT_OASET_DEF defines the dictionary set name_t and its associated methods as static inline functions just like DICT_SET_DEF.
The difference is that it uses an Open Addressing Hash-Table as container.
The key_oplist shall also define the additional operators:
OOR_EQUAL and OOR_SET
The elements may move when inserting / deleting other elements (and not just the iterators).
This implementation is in general faster for small types of keys (like integer) but slower for larger types.
DICT_OASET_DEF_AS is the same as DICT_OASET_DEF
except the name of the types name_t, name_it_t are provided.
DICT_SET_OPLIST(name[, key_oplist])Return the oplist of the set defined by calling DICT_SET_DEF (or DICT_OASET_DEF) with name and key_oplist.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the dictionary which
key_type to value_type,key_type.name_it_tType of an iterator over this dictionary.
name_itref_t [only for associative array]Type of one item referenced in the dictionary for associative array.
It is a structure composed of the key (field key) and the value (field value).
This type is created only for associative arrays (_DEF2 suffix) and not for sets.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t dict)
void name_clear(name_t dict)
void name_init_set(name_t dict, const name_t ref)
void name_set(name_t dict, const name_t ref)
void name_init_move(name_t dict, name_t ref)
void name_move(name_t dict, name_t ref)
void name_reset(name_t dict)
size_t name_size(const name_t dict)
bool name_empty_p(const name_t dict)
value_type *name_get(const name_t dict, const key_type key)
value_type_t * name_get_emplace[suffix](name_t container, args...)
value_type *name_safe_get(name_t dict, const key_type key)
void name_set_at(name_t dict, const key_type key, const value_type value) /* for associative array */
void name_push(name_t dict, const key_type key) /* for dictionary set */
bool name_erase(name_t dict, const key_type key)
void name_it(name_it_t it, name_t dict)
void name_it_set(name_it_t it, const name_it_t ref)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
void name_next(name_it_t it)
name_itref_t *name_ref(name_it_t it) /* for associative array */
key_type *name_ref(name_it_t it) /* for dictionary set */
const name_itref_t *name_cref(name_it_t it) /* for associative array */
const key_type *name_cref(name_it_t it) /* for dictionary set */
void name_get_str(string_t str, const name_t dict, bool append)
bool name_parse_str(name_t dict, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t dict)
bool name_in_str(name_t dict, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t dict1, const name_t dict2)
void name_emplace[suffix](name_t container, keyargs...) [for dictionary set */
void name_emplace_key[keysuffix]_val[valsuffix](name_t container, keyargs..., valargs...) /* for associative array */
void name_reserve(name_t dict, size_t capacity)
The following specialized methods are automatically created by the previous definition macro:
void name_splice(name_t dict1, name_t dict2)Move all items from dict2 into dict1.
If there is the same key between dict2 into dict1,
then their values are added (as per the ADD method of the value type).
Afterward dict2 is reset (i.e. empty).
This method is only defined if the value type defines an ADD method.
dict1 and dict2 shall reference different objects.
A tuple is a finite ordered list of elements of different types.
TUPLE_DEF2(name, (element1, type1[, oplist1]) [, ...])TUPLE_DEF2_AS(name, name_t, (element1, type1[, oplist1]) [, ...])TUPLE_DEF2 defines the tuple name_t and its associated methods as static inline functions.
Each parameter of the macro is expected to be an element of the tuple.
Each element is defined by three parameters within parenthesis:
name and element shall be C identifiers that will be used to identify the container and the fields.
It will be used to create all the types (including the iterator) and functions to handle the container. This definition shall be done once per name and per compilation unit.
This is more or less a C structure. The main added value compared to using a C struct is that it generates also all the basic methods to handle it which is quite handy.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
In general, an optional method of the tuple will only be created if all oplists define the needed optional methods for the underlying type.
The _hash (resp. _equal_p and _cmp) method is an exception.
This method is created only if at least one oplist of the tuple defines the HASH (resp. EQUAL) method.
You can disable the use of a specific field for the hash computation of the tuple
by disabling the HASH operator of such field (with HASH(0) in its oplist),
in which case it is coherent to also disable the EQUAL operator too.
Resp., you can disable the use of a field for the equality of the tuple
by disabling the EQUAL operator of such field (with EQUAL(0) in its oplist)
The comparison of two tuples uses lexicographic order of the fields defining the CMP method.
It is created only if at least one oplist of the tuple define CMP method.
You can disable the use of a field for the comparison of the tuple
by disabling the CMP operator of such field (with CMP(0) in its oplist)
TUPLE_DEF2_AS is the same as TUPLE_DEF2 except the name of the type name_t is provided.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-string.h"
#include "m-tuple.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
TUPLE_DEF2(pair, (key_field, string_t, STRING_OPLIST), \
(value_field, mpz_t, M_OPEXTEND(M_CLASSIC_OPLIST(mpz), \
OUT_STR(MPZ_OUT_STR))))
int main(void) {
pair_t p1;
pair_init (p1);
string_set_str(p1->key_field, "HELLO");
mpz_set_str(p1->value_field, "1742", 10);
printf("The pair is ");
pair_out_str(stdout, p1);
printf("\n");
pair_clear(p1);
}
TUPLE_OPLIST(name, oplist1[, ...] )Return the oplist of the tuple defined by calling TUPLE_DEF2 with the given name and the oplist.
The following type is automatically defined by the previous definition macro if not provided by the user:
name_tType of the defined tuple.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t tuple)
void name_init_set(name_t tuple, const name_t ref)
void name_set(name_t tuple, const name_t ref)
void name_init_move(name_t tuple, name_t ref)
void name_move(name_t tuple, name_t ref)
void name_clear(name_t tuple)
void name_reset(name_t tuple)
void name_get_str(string_t str, const name_t tuple, bool append)
bool name_parse_str(name_t tuple, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t tuple)
bool name_in_str(name_t tuple, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
size_t name_hash(const name_t tuple)
int name_equal_p(const name_t tuple1, const name_t tuple2)
int name_cmp(const name_t tuple1, const name_t tuple2)
The following specialized methods are automatically created by the previous definition macro:
void name_init_emplace(name_t tuple, const type1 element1[, ...])Initialize the tuple tuple (aka constructor) and set it to the value of the constructed tuple (element1[, ...]).
void name_emplace(name_t tuple, const type1 element1[, ...])Set the tuple tuple to the value of the tuple constructed with (element1[, ...]).
const type1 *name_cget_at_element1(const name_t tuple)Return a constant borrowed pointer to the element element1 of the tuple.
There is as many methods as there are elements.
type1 *name_get_at_element1(const name_t tuple)Return a borrowed pointer to the element element1 of the tuple.
There is as many methods as there are elements.
void name_set_element1(name_t tuple, type1 element1)Set the element of the tuple to element1
There is as many methods as there are elements.
int name_cmp_order(const name_t tuple1, const name_t tuple2, const int order[])Compare tuple1 to tuple2 using the given order.
order is a NULL terminated array of int that defines the order of comparison:
an order of {1, 4, 2, 0} indicates to compare first the first field,
if it is equal, to compare the fourth and so on. The third field is not
compared. A negative value indicates to revert the comparison.
This method is created only if all oplist of the tuple define CMP method.
int name_cmp_element1(const name_t tuple1, const name_t tuple2)Compare tuple1 to tuple2 using only the element element1 as reference.
This method is created only if the oplist of element1 defines the CMP method.
A variant is a finite exclusive list of elements of different types: the variant can only be equal to one element at a time.
VARIANT_DEF2(name, (element1, type1[, oplist1]) [, ...])VARIANT_DEF2_AS(name, name_t, (element1, type1[, oplist1]) [, ...])VARIANT_DEF2 defines the variant name_t and its associated methods as static inline functions.
Each parameter of the macro is expected to be an element of the variant.
Each element is defined by three parameters within parenthesis:
If an OPLIST is given, it shall be the one matching the associated type.
name and element<n> shall be C identifiers that will be used to identify the variant.
name will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
This is like a C union. The main added value compared to using a union
is that it generates all the basic methods to handle and it dynamically
identifies which element is stored within.
It is also able to store an EMPTY state for the variant, contrary to an union
(this is the state when default constructing it).
The oplists shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
In general, an optional method of the variant will only be created
if all oplists define the needed optional methods for the underlying type.
VARIANT_DEF2_AS is the same as VARIANT_DEF2 except the name of the type name_t
is provided.
name_parse_str and name_in_str depend also on the INIT operator.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-variant.h"
VARIANT_DEF2(item,
(name, string_t),
(age, long))
int main(void) {
item_t p1;
item_init (p1);
item_set_name(p1, STRING_CTE("HELLO"));
printf("The variant is ");
item_out_str(stdout, p1);
printf("\n");
item_set_age(p1, 43);
printf("The variant is now ");
item_out_str(stdout, p1);
printf("\n");
item_clear(p1);
}
VARIANT_OPLIST(name, oplist1[, ...] )Return the oplist of the variant defined by calling VARIANT_DEF2 with the given name and the oplists used to generate it.
The following type is automatically defined by the previous definition macro if not provided by the user:
name_tType of the defined variant.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t variant)
void name_init_set(name_t variant, const name_t ref)
void name_set(name_t variant, const name_t ref)
void name_init_move(name_t variant, name_t ref)
void name_move(name_t variant, name_t ref)
void name_clear(name_t variant)
void name_reset(name_t variant)
bool name_empty_p(const name_t variant)
size_t name_hash(const name_t variant)
bool name_equal_p(const name_t variant1, const name_t variant2)
void name_swap(name_t variant1, name_t variant2)
void name_get_str(string_t str, name_t variant, bool append)
bool name_parse_str(name_t variant, const char str[], const char **endp)
void name_out_str(FILE *file, name_t variant)
bool name_in_str(name_t variant, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
The following specialized methods are automatically created by the previous definition macro:
void name_init_elementN(name_t variant)Initialize the variant variant to the type of element1 [constructor]
using the default constructor of this element.
This method is defined if all methods define an INIT method.
void name_init_set_elementN(name_t variant, const typeN elementN)Initialize the variant variant and set it to the type and value of elementN [constructor]
void name_move_elementN(name_t variant, typeN ref)Set the variant variant by stealing as many resources from ref as possible.
Afterwards ref is cleared (destructor)
This method is created only if all oplist of the variant define MOVE method.
void name_set_elementN(name_t variant, const typeN elementN)Set the variant variant to the type and value of elementN.
const typeN *name_cget_at_elementN(name_t variant)Return a borrowed pointer to the variant viewed as of type typeN.
If the variant isn't an object of such type, it returns NULL.
typeN *name_get_at_elementN(name_t variant)Return a borrowed pointer to the variant viewed as of type typeN.
If the variant isn't an object of such type, it returns NULL.
bool name_elementN_p(const name_t variant)Return true if the variant is of the type of elementN.
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A node without any child is called a leaf. It can be seen as an ordered set.
A R-B Tree is a tree where all elements are also totally ordered, and the worst-case of any operation is in logarithm of the number of elements in the tree. The current implementation is RED-BLACK TREE which provides performance guarantee for both insertion and lockup operations. It has not to be confused with a B-TREE.
RBTREE_DEF(name, type[, oplist])RBTREE_DEF_AS(name, name_t, name_it_t, type[, oplist])RBTREE_DEF defines the binary ordered tree name_t and its associated methods as static inline functions.
name shall be a C identifier that will be used to identify the R-B Tree.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The CMP operator is used to perform the total ordering of the elements.
The oplist shall have at least the following operators (INIT, INIT_SET, SET, CLEAR & CMP),
otherwise it won't generate compilable code.
Some methods may return a modifiable pointer to the found element
(for example, _get). In this case, the user shall not modify the
key order of the element, as there is no reordering of the tree
in this case.
A push method on the tree will put the given key in its right place in the tree
by keeping the tree ordered.
It overwrites the already existing value if the key is already present in the dictionary (contrary to C++).
RBTREE_DEF_AS is the same as RBTREE_DEF2 except the name of the types name_t, name_it_t are provided by the user.
Example:
RBTREE_DEF(rbtree_uint, unsigned int)
void f(unsigned int num) {
rbtree_uint_t tree;
rbtree_uint_init(tree);
for(unsigned int i = 0; i < num; i++)
rbtree_uint_push(tree, i);
rbtree_uint_clear(tree);
}
RBTREE_OPLIST(name [, oplist])Return the oplist of the Red-Black tree defined by calling RBTREE_DEF with name and oplist.
If there is no given oplist, the basic oplist for basic C types is used.
The following types are automatically defined by the previous definition macro with name if not provided by the user:
name_tType of the Red Black Tree.
name_it_tType of an iterator over this Red Black Tree.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t rbtree)
void name_clear(name_t rbtree)
void name_init_set(name_t rbtree, const name_t ref)
void name_set(name_t rbtree, const name_t ref)
void name_init_move(name_t rbtree, name_t ref)
void name_move(name_t rbtree, name_t ref)
void name_reset(name_t rbtree)
size_t name_size(const name_t rbtree)
void name_push(name_t rbtree, const type data)
void name_emplace[suffix](name_t rbtree, args...)
type *name_get(const name_t rbtree, const type data)
const type *name_cget(const name_t rbtree, const type data)
void name_swap(name_t rbtree1, name_t rbtree2)
bool name_empty_p(const name_t rbtree)
void name_it(name_it_t it, name_t rbtree)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_last(name_it_t it, name_t rbtree)
void name_it_end(name_it_t it, name_t rbtree)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
void name_it_remove(name_t rbtree, name_it_t it)
void name_next(name_it_t it)
void name_previous(name_it_t it)
type *name_ref(name_it_t it)
const type *name_ref(name_it_t it)
void name_get_str(string_t str, const name_t rbtree, bool append)
bool name_parse_str(name_t tree, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t rbtree)
bool name_in_str(name_t rbtree, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t rbtree1, const name_t rbtree2)
size_t name_hash(const name_t rbtree)
The following specialized methods are automatically created by the previous definition macro:
void name_pop(type *dest, name_t rbtree, const type data)Pop data from the Red Black Tree rbtree
and save the popped value into dest if the pointer is not null
while keeping the tree balanced.
Do nothing if data is no present in the Red Black Tree.
type * name_min(const name_t rbtree)const type * name_cmin(const name_t rbtree)Return a borrowed pointer to the minimum element of the tree or NULL if there is no element.
type * name_max(const name_t rbtree)const type * name_cmax(const name_t rbtree)Return a borrowed pointer to the maximum element of the tree or NULL if there is no element.
void name_it_from(name_it_t it, const name_t rbtree, const type data)Set the iterator it to
the lowest element of the tree rbtree greater or equal than data
or an iterator to no element is there is none.
bool name_it_until_p(const name_it_t it, const type data)Return true if it references an element that is greater or equal than data
or if it references no longer a valid element, false otherwise.
bool name_it_while_p(const name_it_t it, const type data)Return true if it references an element that is lower or equal than data.
Otherwise (or if it references no longer a valid element) it returns false.
A B+TREE is a variant of BTREE that itself is a generalization of Binary Tree.
A B+TREE is an N-ary tree with a variable but often large number of children per node. It is mostly used for handling slow media by file system and database.
It provides a fully sorted container enabling fast access to individual item or range of items, and as such is concurrent to Red-Black Tree. On modern architecture, a B+TREE is typically faster than a red-black tree due to being more cache friendly (The RAM itself can be considered as a slow media nowadays!)
When defining a B+TREE it is necessary to give the type of the item within, but also
the maximum number of child per node (N). The best maximum number of child per node
depends on the type itself (its size, its compare cost) and the cache of the
processor.
BPTREE_DEF2(name, N, key_type, key_oplist, value_type, value_oplist)BPTREE_DEF2_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist, value_type, value_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an associative
array of the key_type to the value_type.
The CMP operator is used to perform the total ordering of the key elements.
N is the number of items per node and shall be greater or equal than 3.
It shall be done once per type and per compilation unit.
It also define the iterator name##_it_t and its associated methods as static inline functions.
The object of type key_type and value_type shall be trivially movable.
The object oplist shall have at least the operators (INIT, INIT_SET, SET, CLEAR and CMP).
BPTREE_DEF2_AS is the same as BPTREE_DEF2 except the name of the
container type name_t, the iterator type name_it_t, and the
iterated object type name_itref_t are provided by the user.
Example:
BPTREE_DEF2(tree_uint, 4, unsigned int, (), float, ())
void f(unsigned int num) {
tree_uint_t tree;
tree_uint_init(tree);
for(unsigned int i = 0; i < num; i++)
tree_uint_set_at(tree, i, (float) i);
tree_uint_clear(tree);
}
BPTREE_OPLIST2(name, key_oplist, value_oplist)Return the oplist of the BPTREE defined by calling BPTREE_DEF2 with name,
key_oplist and value_oplist.
BPTREE_DEF(name, N, key_type[, key_oplist])BPTREE_DEF_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an ordered set
of key_type.
The CMP operator is used to perform the total ordering of the key elements.
N is the number of items per node and shall be greater or equal than 2.
It shall be done once per type and per compilation unit.
It also define the iterator name##_it_t and its associated methods as static inline functions.
The object oplist shall have at least the operators (INIT, INIT_SET, SET, CLEAR and CMP).
BPTREE_DEF_AS is the same as BPTREE_DEF except the name of
the container type name_t, the iterator type name_it_t and the iterated object type name_itref_t
are provided by the user.
Example:
BPTREE_DEF(tree_uint, unsigned int)
void f(unsigned int num) {
tree_uint_t tree;
tree_uint_init(tree);
for(unsigned int i = 0; i < num; i++)
tree_uint_push(tree, i);
tree_uint_clear(tree);
}
BPTREE_OPLIST(name[, key_oplist])Return the oplist of the BPTREE defined by calling BPTREE_DEF with name and key_oplist.
If there is no given oplist, the basic oplist for basic C types is used.
BPTREE_MULTI_DEF2(name, N, key_type, key_oplist, value_type, value_oplist)BPTREE_MULTI_DEF2_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist, value_type, value_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an associative
array of the key_type to the value_type and allows multiple instance of
the same key in the tree (aka it is a multi-map: re-adding the same key in
the tree will add a new instance of the key in the tree rather than update
the value associated to the key).
See BPTREE_DEF2 for additional details and example.
BPTREE_MULTI_DEF2_AS is the same as BPTREE_MULTI_DEF2 except the name of the types name_t, name_it_t, name_itref_t are provided by the user.
BPTREE_MULTI_DEF(name, N, key_type[, key_oplist])BPTREE_MULTI_DEF_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an ordered set
of key_type and allows multiple instance of
the same key in the tree (aka it is a multi set: re-adding the same key in
the tree will add a new instance of the key in the tree rather than update
the key value).
See BPTREE_DEF for additional details and example.
BPTREE_MULTI_DEF_AS is the same as BPTREE_MULTI_DEF except the name of the types name_t, name_it_t, name_itref_t are provided by the user.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the B+Tree of type.
name_it_tType of an iterator over this B+Tree.
name_itref_tType of one item referenced in the B+Tree. It is either:
key_ptr) and a pointer to the value (field value_ptr) if the B+Tree is an associative array,The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t tree)
void name_clear(name_t tree)
void name_init_set(name_t tree, const name_t ref)
void name_set(name_t tree, const name_t ref)
void name_init_move(name_t tree, name_t ref)
void name_move(name_t tree, name_t ref)
void name_reset(name_t tree)
size_t name_size(const name_t tree)
void name_push(name_t tree, const key_type data) [for set definition only]
void name_set_at(name_t tree, const key_type data, const value_type val) /* for associative array definition only */
bool name_erase(name_t tree, const key_type data)
value_type *name_get(const name_t tree, const key_type data)
const value_type *name_cget(const name_t tree, const key_type data)
value_type *name_safe_get(name_t tree, const key_type data)
void name_swap(name_t tree1, name_t tree2)
bool name_empty_p(const name_t tree)
void name_it(name_it_t it, name_t tree)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, name_t tree)
void name_it_last(name_it_t it, name_t tree)
bool name_end_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it1)
void name_next(name_it_t it)
void name_previous(name_it_t it)
name_itref_t *name_ref(name_it_t it)
const name_itref_t *name_cref(name_it_t it)
void name_get_str(string_t str, const name_t tree, bool append)
bool name_parse_str(name_t tree, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t tree)
bool name_in_str(name_t tree, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t tree1, const name_t tree2)
size_t name_hash(const name_t tree)
void name_emplace[suffix](name_t container, keyargs...) [for dictionary set]
void name_emplace_key[keysuffix]_val[valsuffix](name_t container, keyargs..., valargs...) /* for associative array */
The following specialized methods are automatically created by the previous definition macro:
bool name_pop_at(value_type *dest, name_t tree, const key_type data)Pop data from the B+Tree tree
and save the popped value into *dest if dest is not NULL
while keeping the tree balanced.
Do nothing if data is no present in the B+Tree.
Return true if data has been erased, false otherwise.
value_type *name_min(const name_t tree)const value_type *name_cmin(const name_t tree)Return a borrowed pointer to the minimum element of the tree or NULL if there is no element in the B+Tree.
value_type *name_max(const name_t tree)const value_type *name_cmax(const name_t tree)Return a borrowed pointer to the maximum element of the tree or NULL if there is no element in the B+Tree.
void name_it_from(name_it_t it, const name_t tree, const type data)Set the iterator it to the lowest element of tree
greater or equal than data or the end iterator is there is none.
bool name_it_until_p(const name_it_t it, const type data)Return true if it references an element that is greater or equal than data.
Otherwise it returns false.
If it references no longer a valid element,
it returns true if the iterator has reached this state by going above the maximum of the tree,
false otherwise.
bool name_it_while_p(const name_it_t it, const type data)Return true if it references an element that is lower or equal than data.
Otherwise it returns false.
If it references no longer a valid element,
it returns true if the iterator has reached this state by going below the minimum of the tree,
false otherwise.
A tree is an abstract data type to represent the hierarchic nature of a structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent.
TREE_DEF(name, type [, oplist])TREE_DEF_AS(name, name_t, name_it_t, type [, oplist])Define the tree name_t and its associated methods as static inline functions.
The tree will be composed of object of type type, connected each other.
name shall be a C identifier that will be used to identify the tree.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
Any insert (resp. remove) in the tree shall specific the insertion point
(resp. deleting point). To construct a tree, you start by creating the
root node (using the _set_root method) and then insert new nodes from there.
Each insertion of node in the tree will return an iterator of the inserted
node. This can be used to construct quickly a full tree.
The oplist shall have at least the following operators (INIT_SET & CLEAR),
otherwise it won't generate compilable code.
The tree handles its own pool of nodes for the nodes.
It is called the capacity of the tree.
This pool of nodes will increase when needed by default.
However, in case of capacity increased, all the nodes of the tree may move in memory to accommodate the new need.
You may also request to reserve more capacity to avoid moving the items, and disable this auto-expand feature (in which a MEMORY_FAILURE is raised).
There are several ways to iterate over this container:
On insertion, all iterators remain valid. Except if it says otherwise, all functions accepting iterators expect a valid iterator (i.e. it references an existing node).
TRREE_DEF_AS is the same as TREE_DEF except the name of the types name_t, name_it_t are provided.
TREE_OPLIST(name, [, oplist])Define the oplist of the generic tree defined with name and potentially oplist.
If there is no given oplist, the basic oplist for basic C types is used.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the generic tree of type.
name_it_tType of an iterator over this generic tree.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t tree)
void name_init_set(name_t tree, const name_t ref)
void name_init_move(name_t tree, name_t ref)
void name_set(name_t tree, const name_t ref)
void name_move(name_t tree, name_t ref)
void name_clear(name_t tree)
void name_reset(name_t tree)
size_t name_size(const name_t tree)
size_t name_capacity(const name_t tree)
void name_reserve(name_t tree, size_t capacity)
bool name_empty_p(const name_t tree)
void name_swap(name_t tree1, name_t tree2)
bool name_equal_p(const name_t tree1, const name_t tree2)
bool name_end_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
const type *name_cref(name_it_t it)
type *name_ref(name_it_t it)
bool name_remove(it_t it)
void name_get_str(string_t str, const name_t tree, bool append)
bool name_parse_str(name_t tree, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t tree)
bool name_in_str(name_t tree, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
The following specialized methods are automatically created by the previous definition macro:
void name_lock(name_t tree, bool lock)Disable the auto-resize feature of the tree (if lock is true), or enable it otherwise. By default, the feature is enabled. Locking a tree shall be done after reserving the maximum number of nodes that can be added by your tree, so that the returned borrowed pointers to the internal types won't move on inserting a new node.
name_it_t name_set_root(name_t tree, const type value)Set the tree to a single root node and set this node to value.
name_it_t name_emplace_root[suffix](name_t tree, args...)Set the tree to a single root node and set this node to the value
initialized with the given args.
The provided arguments shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator.
See emplace chapter for more details.
it_t name_insert_up_raw(it_t ref)it_t name_insert_left_raw(it_t ref)it_t name_insert_right_raw(it_t ref)it_t name_insert_down_raw(it_t ref)it_t name_insert_child_raw(it_t ref)Insert a node up (resp. left, right, down and down) the given referenced iterator without initializing it.
It returns an iterator to the inserted node with non-initialized data.
The first thing to do after calling this function shall be to initialize the data
using the proper constructor of the object of type type (the pointer can be get through name_ref)
This enables using more specialized constructor than the generic copy one.
The user should use the non _raw function if possible rather than this one
as it is low level and error prone.
name_insert_down_raw will move all children of the referenced node as children of the inserted children,
whereas name_insert_child_raw will insert the node as the new first child of the referenced node.
it_t name_insert_up(it_t ref, const type value)it_t name_insert_left(it_t ref, const type value)it_t name_insert_right(it_t ref, const type value)it_t name_insert_down(it_t ref, const type value)it_t name_insert_child(it_t ref, const type value)Insert a node up (resp. left, right, down and down) the given referenced iterator and initialize it with a copy of value.
It returns an iterator to the inserted node.
name_insert_down will move all children of the referenced node as children of the inserted children,
whereas name_insert_child will insert the node as the new first child of the referenced node.
it_t name_move_up(it_t ref, type *value)it_t name_move_left(it_t ref, type *value)it_t name_move_right(it_t ref, type *value)it_t name_move_down(it_t ref, type *value)it_t name_move_child(it_t ref, type *value)Insert a node up (resp. left, right, down and down) the given referenced iterator and initialize it with value by stealing as much resource from value as possible (and destroy *value)
It returns an iterator to the inserted node.
name_move_down will move all children of the referenced node as children of the inserted children,
whereas name_move_child will insert the node as the new first child of the referenced node.
it_t name_emplace_up[suffix](it_t ref, args...)it_t name_emplace_left[suffix](it_t ref, args...)it_t name_emplace_right[suffix](it_t ref, args...)it_t name_emplace_down[suffix](it_t ref, args...)it_t name_emplace_child[suffix](it_t ref, args...)Insert a node up (resp. left, right, down and down) the given referenced iterator
and initialize this node to the value initialized with the given args.
The provided arguments shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator.
See emplace chapter for more details.
It returns an iterator to the inserted node.
name_emplace_down will move all children of the referenced node as children of the inserted children,
whereas name_emplace_child will insert the node as the new first child of the referenced node.
type *name_up_ref(name_it_t it)type *name_down_ref(name_it_t it)type *name_left_ref(name_it_t it)type *name_right_ref(name_it_t it)Return a borrowed pointer to the type of the node which is
respectively. It returns NULL if there is no such node.
it_t name_up(it_t it)it_t name_down(it_t it)it_t name_left(it_t it)it_t name_right(it_t it)Return an iterator to point to the node which is up (resp. down, left and right) the given iterator.
Return a valid iterator in case of success, an invalid one otherwise (see name_end_p)
bool name_it_up(it_t *it)bool name_it_down(it_t *it)bool name_it_left(it_t *it)bool name_it_right(it_t *it)Update the iterator to point to the node which is up (resp. down, left and right) the given iterator. Return true in case of success, false otherwise (as such node doesn't exist, the iterator remains unchanged).
bool name_root_p(const it_t it)Return true if it references the root node, false otherwise.
bool name_node_p(const it_t it)Return true if it references a non-leaf node, false otherwise.
bool name_leaf_p(const it_t it)Return true if it references a leaf node, false otherwise.
int32_t name_degree(const it_t it)Return the degree of the referenced node (aka the number of children). A leaf node has a degree of 0. This function is linear in the number of children of the node.
int32_t name_depth(const it_t it)Return the depth of the referenced node (aka the number of nodes until reaching the root node). The root node has a depth of 0. This function is linear in the depth of the node.
type *name_unlink(it_t it)Unlink the referenced node from the tree, so that the node is removed from the tree. All children of the removed node become children of the parent node. If the removed node is the root node, than the root node shall have only one child.
Return a reference to the internal type and give back ownership of the type:
you shall destroy the type (using CLEAR or MOVE methods) before calling any other tree functions
(as the memory area used by the node may be removed on inserting a new node)
You should use the remove service instead as it has the same semantics but it is safer as it perform the clear of the data.
void name_prune(name_it_t it)Remove the referenced node including all its children.
See name_remove for more details.
name_it_t name_it_end(name_t tree)Return an iterator that references no valid node.
void name_it_set(name_it_t *it, const name_it_t ref)Set the iterator *it to ref.
[!NOTE] You can use the
=affectation operator of the C language to copy tree iterators too.
name_it_t name_it(name_t tree)Return an iterator of the tree that will iterator on the tree in global pre-order walk (the root).
void name_next(name_it_t *it)Update the iterator of the tree so that it references the next node in a global pre-order walk, or set it to invalid if the walk is finished.
name_it_t name_it_post(name_t tree)Return an iterator of the tree that will iterator on the tree in global post-order walk
void name_next_post(name_it_t *it)Update the iterator of the tree so that it references the next node in a global post-order walk, or set it to invalid if the walk is finished.
name_it_t name_it_subpre(name_t tree, const name_it_t ref)Return an iterator of the tree that will iterator on the tree in pre-order walk of the child nodes of the referenced one.
void name_next_subpre(name_it_t it, const name_it_t ref)Update the iterator of the tree so that it references the next node in a local pre-order walk of the child nodes of the referenced one, or set it to invalid if the walk is finished (the sub tree is fully scanned).
The referenced iterator shall be the same as the one used to create the updated iterator (with name_it_subpre).
name_it_t name_it_subpost(name_t tree, const name_it_t ref)Return an iterator of the tree that will iterator on the tree in post-order walk of the child nodes of the referenced one.
void name_next_subpost(name_it_t it, const name_it_t ref)Update the iterator of the tree so that it references the next node in a local post-order walk of the child nodes of the referenced one, or set it to invalid if the walk is finished (the sub-tree is fully scanned).
The referenced iterator shall be the same as the one used to create the updated iterator (with name_it_subpost).
void name_lca(name_it_t it1, name_it_t it2)Compute the Lowest Common Ancestor of the two iterators. Both iterators shall belong to the same tree.
void name_swap_at(name_it_t it1, name_it_t it2, bool swapChild)Swap the node referenced by it1 and the node referenced by it2 in the tree.
If swapChild is true, the children nodes perform the swap with their parent.
Otherwise, only the referenced nodes are swapped.
void name_sort_child(name_it_t it1)Sort the child of the node referenced by it1 in the order of the type.
This method is constructed if the basic type exports the CMP type.
A priority queue is a queue where each element has a "priority" associated with it: an element with high priority is served before an element with low priority. It is currently implemented as a heap.
PRIOQUEUE_DEF(name, type [, oplist])PRIOQUEUE_DEF_AS(name, name_t, name_it_t, type [, oplist])Define the priority queue name_t and its associated methods
as static inline functions.
The queue will be composed of object of type type.
name shall be a C identifier that will be used to identify the queue.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The CMP operator is used to sort the queue so that the highest priority is the minimum.
The EQUAL operator is used to identify an item on update or remove operations.
It is uncorrelated with the CMP operator from the point of view of this container.
(i.e. EQUAL() == TRUE is not equivalent to CMP() == 0 for this container)
This queue will push the object at the right place in the queue in function of their priority. A pop from this queue will always return the minimum of all objects within the queue (contrary to C++ which returns the maximum), and the front method will reference this object.
The oplist shall have at least the following operators (INIT, INIT_SET, SET, CLEAR, CMP),
otherwise it won't generate compilable code.
The equal_p, update & erase methods have a complexity of O(n) due to the linear
search of the data and are only created if the EQUAL method is defined.
Iteration over this container won't iterate from minimum to maximum but in an implementation define way that ensures that all items are accessed.
PRIOQUEUE_DEF_AS is the same as PRIOQUEUE_DEF except the name of the types name_t, name_it_t are provided.
PRIOQUEUE_OPLIST(name, [, oplist])Define the oplist of the PRIOQUEUE defined with name and potentially oplist.
If there is no given oplist, the basic oplist for basic C types is used.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the priority queue of type.
name_it_tType of an iterator over this priority queue.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t queue)
void name_clear(name_t queue)
void name_init_set(name_t queue, const name_t ref)
void name_set(name_t queue, const name_t ref)
void name_init_move(name_t queue, name_t ref)
void name_move(name_t queue, name_t ref)
void name_reset(name_t queue)
size_t name_size(const name_t queue)
bool name_empty_p(const name_t queue)
void name_swap(name_t queue1, name_t queue2)
void name_push(name_t queue, const type x)
const type *name_front(name_t queue)
void name_pop(type *dest, name_t queue)
bool name_equal_p(const name_t queue1, const name_t queue2)
bool name_erase(name_t queue, const type_t val)
void name_it(name_it_t it, name_t queue)
void name_it_last(name_it_t it, name_t queue)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, name_t queue)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
void name_previous(name_it_t it)
const type *name_cref(name_it_t it)
void name_get_str(string_t str, const name_t queue, bool append)
bool name_parse_str(name_t queue, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t queue)
bool name_in_str(name_t queue, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
void name_emplace[suffix](name_t queue, args...)
The following specialized methods are automatically created by the previous definition macro:
void name_update(name_t queue, const type_t old_val, const type_t new_val)Change the priority of the data of the priority equals to old_val (in EQUAL sense)
to new_val (increase or decrease priority).
This method has a complexity of O(n) (due to linear search of the data).
This method is defined only if the EQUAL method is defined.
This header implements a fixed circular queue or stack.
A circular buffer (or ring buffer or circular queue) is a data structure using a single, bounded buffer as if its head was connected to its tail.
Define the circular queue name_t and its associated methods as static inline functions.
This queue is not thread-safe (See m-buffer header for a thread safe variant).
The order of the elements in the container is FIFO (First In, First Out).
name shall be a C identifier that will be used to identify the queue.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The size parameter defined the fixed size of the queue.
It can be 0. In this case, the fixed size is defined at initialization time only
and the needed objects to handle the queue are allocated at initialization time too.
Otherwise the needed objects are embedded within the structure, preventing
any other allocations.
The size of the queue shall be lower or equal than the maximum of the type unsigned int.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
QUEUE_DEF_AS is the same as QUEUE_DEF except the name of the type name_t is provided.
Example:
QUEUE_DEF(queue_uint, unsigned int, 10)
queue_uint_t g_buff;
void f(unsigned int i) {
queue_uint_init(g_buff, 10);
queue_uint_push(g_buff, i);
queue_uint_pop(&i, g_buff);
queue_uint_clear(g_buff);
}
Define the fixed size stack name_t and its associated methods as static inline functions.
This stack is not thread-safe (See m-buffer header for a thread safe variant).
The order of the elements in the container is FILO (First In, Last Out).
name shall be a C identifier that will be used to identify the stack.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The size parameter defined the fixed size of the stack.
It can be 0. In this case, the fixed size is defined at initialization time only
and the needed objects to handle the stack are allocated at initialization time too.
Otherwise the needed objects are embedded within the structure, preventing
any other allocations.
The size of the stack shall be lower or equal than the maximum of the type unsigned int.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
STACK_DEF_AS is the same as STACK_DEF except the name of the type name_t is provided.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the circular queue (or stack).
The following methods of the common interface are defined (See Common interface for details):
void name_clear(queue_t queue)
void name_reset(queue_t queue)
bool name_empty_p(const queue_t queue)
size_t name_size(const queue_t queue)
size_t name_capacity(const queue_t queue)
void name_push(queue_t queue, const type data)
void name_pop(type *data, queue_t queue)
The following specialized methods are automatically created by the previous definition macro:
void name_init(queue_t queue, size_t size)Initialize the queue (or stack) queue for size elements.
The size argument shall be the same as the one used to create the container, or the size used to create it was 0 (ie. runtime fixed size).
The size of the queue shall be lower or equal than UINT_MAX.
bool name_full_p(const queue_t queue)Return true if the queue (or stack) is full, false otherwise.
This header implements different kind of fixed circular buffer used for threading purpose.
A circular buffer (or ring buffer or circular queue) is a data structure using a single, bounded buffer as if its head was connected to its tail.
Define the buffer name_t and its associated methods as static inline functions.
A buffer is a fixed circular queue implementing a queue (or stack) interface.
It can be used to transfer message from multiple producer threads to multiple consumer threads.
This is done internally using a mutex and conditional waits
See m-queue for a non thread safe variant.
name shall be a C identifier that will be used to identify the buffer.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The size parameter defined the fixed size of the queue.
It can be 0. In this case, the fixed size is defined at initialization time only
and the needed objects to handle the buffer are allocated at initialization time too.
Otherwise the needed objects are embedded within the structure, preventing
any other allocations.
The size of the buffer shall be lower or equal than the maximum of the type unsigned int.
Multiple additional policy can be applied to the buffer by performing a logical or of the following properties:
BUFFER_QUEUE — define a FIFO queue (default),BUFFER_STACK — define a stack (exclusive with BUFFER_QUEUE),BUFFER_PUSH_OVERWRITE — PUSH overwrites the last entry if the queue is full instead of blocking,BUFFER_DEFERRED_POP — do not consider the object to be fully popped from the buffer by calling the pop method until the call to pop_deferred ; this enables to handle object that are in-progress of being consumed by the thread.This container is designed to be used for synchronization inter-threads of data (and the buffer variable should be a global shared one).
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The PUSH and POP methods operate like push_blocking and pop_blocking when the blocking parameter
is true.
BUFFER_DEF_AS is the same as BUFFER_DEF except the name of the type name_t is provided.
Example:
BUFFER_DEF(buffer_uint, unsigned int, 10, BUFFER_QUEUE|BUFFER_BLOCKING)
buffer_uint_t g_buff;
void f(unsigned int i) {
buffer_uint_init(g_buff, 10);
buffer_uint_push(g_buff, i);
buffer_uint_pop(&i, g_buff);
buffer_uint_clear(g_buff);
}
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the buffer.
The following methods of the common interface are defined (See Common interface for details):
void name_clear(buffer_t buffer) /* Not thread safe */
void name_reset(buffer_t buffer) /* Thread safe */
bool name_empty_p(const buffer_t buffer) /* Thread safe */
size_t name_size(const buffer_t buffer) /* Thread safe */
size_t name_capacity(const buffer_t buffer) /* Thread safe */
void name_push(buffer_t buffer, const type data)
void name_push_move(buffer_t buffer, type *data)
void name_pop(type *data, buffer_t buffer)
void name_pop_move(type *data, buffer_t buffer)
The following specialized methods are automatically created by the previous definition macro:
void name_init(buffer_t buffer, size_t size)Initialize the buffer buffer for size elements.
The size argument shall be the same as the one used to create the buffer
or the one used to create the buffer was 0.
The size of the buffer shall be lower or equal than UINT_MAX.
This function is not thread safe.
bool name_full_p(const buffer_t buffer)Return true if the buffer is full, false otherwise. This function is thread safe if the buffer was built thread safe.
size_t name_overwrite(const buffer_t buffer)If the buffer is built with the BUFFER_PUSH_OVERWRITE option,
this function returns the number of elements that have been overwritten
and thus discarded.
If the buffer was not built with the BUFFER_PUSH_OVERWRITE option,
it returns 0.
bool name_push_blocking(buffer_t buffer, const type data, bool blocking)Push the object data in the buffer buffer,
waiting for an empty room if blocking is true (performing a blocking wait)
Returns true if the data was pushed, false otherwise.
Always return true if the buffer is blocking.
This function is thread safe.
bool name_push_move_blocking(buffer_t buffer, type *data, bool blocking)Push the object *data in the buffer buffer
by stealing as much resource from it as possible,
clearing *data afterwards (destructor)
waiting for an empty room if blocking is true (performing a blocking wait)
Returns true if the data was pushed, false otherwise.
Always return true if the buffer is blocking.
This function is thread safe.
bool name_pop_blocking(type *data, buffer_t buffer, bool blocking)Pop from the buffer buffer into the object *data,
waiting for a data if blocking is true.
If the buffer is built with the BUFFER_DEFERRED_POP option,
the object is still considered being present in the queue until
a call to name_pop_release.
Returns true if a data was popped, false otherwise. Always return true if the buffer is blocking. This function is thread safe.
bool name_pop_move_blocking(type *data, buffer_t buffer, bool blocking)Pop from the buffer buffer into the uninitialized object *data,
waiting for a data if blocking is true (constructor).
If the buffer is built with the BUFFER_DEFERRED_POP option,
the object is still considered being present in the queue until
a call to name_pop_release.
Returns true if a data was popped, false otherwise. Always return true if the buffer is blocking. This function is thread safe.
bool name_pop_release(buffer_t buffer)If the buffer is built with the BUFFER_DEFERRED_POP option,
the object being popped is considered fully release (freeing a
space in the queue).
Otherwise it does nothing.
QUEUE_MPMC_DEF(name, type, policy[, oplist])QUEUE_MPMC_DEF_AS(name, name_t, type, policy[, oplist])Define the MPMC queue name_t and its associated methods as static inline functions.
A MPMC queue is a fixed circular queue implementing a queue (or stack) interface.
It can be used to transfer message from Multiple Producer threads to Multiple Consumer threads.
This queue is not strictly lock free but has
a lot of the properties of such algorithms.
The size is specified only at run-time and shall be a power of 2.
name shall be a C identifier that will be used to identify the queue.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
An additional policy can be applied to the buffer by performing a logical or of the following properties:
BUFFER_QUEUE — define a FIFO queue (default),This container is designed to be used for easy synchronization inter-threads in a context of very fast communication (the variable should be a global shared one). There should not have much more threads using this queue than they are available hardware cores due to the only partial protection on Context-switch Immunity of this structure (This can happen only if you abuse massively the number of threads vs the number of cores).
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The size method is thread safe but may return a size greater than
the size of the queue in some race condition.
QUEUE_MPMC_DEF_AS is the same as QUEUE_MPMC_DEF except the name of the type name_t
is provided.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the circular queue.
The following methods of the common interface are defined (See Common interface for details):
void name_clear(buffer_t buffer)
bool name_empty_p(const buffer_t buffer) /* Thread safe */
size_t name_size(const buffer_t buffer) /* Thread safe */
size_t name_capacity(const buffer_t buffer) /* Thread safe */
The following specialized methods are automatically created by the previous definition macro:
void name_init(buffer_t buffer, size_t size)Initialize the buffer buffer with size elements.
The size argument shall be a power of two greater than 0, and less than UINT_MAX.
This function is not thread safe.
##### bool name_full_p(const buffer_t buffer)
Return true if the buffer is full, false otherwise. This function is thread safe.
bool name_push(buffer_t buffer, const type data)Push the object data in the buffer buffer if possible.
Returns true if the data was pushed, false otherwise
(buffer full or unlikely data race).
This function is thread safe.
bool name_push_move(buffer_t buffer, type *data)Push the object *data in the buffer buffer if possible,
by stealing as much resources from it as possible,
clearing *data afterwards.
Returns true if the data was effectively pushed, false otherwise
(buffer full or unlikely data race), in which case *data is still initialized.
This function is thread safe.
bool name_pop(type *data, buffer_t buffer)Pop from the buffer buffer into the object *data if possible.
Returns true if a data was popped, false otherwise (buffer empty or unlikely data race). This function is thread safe.
bool name_pop_move(type *data, buffer_t buffer)Pop from the buffer buffer into the unin
Truncated — view the full README on GitHub.
(top 24 of 26)
M*LIB is a library of generic and type safe containers / data structures in pure C language (C99 / C11) for a wide collection of container (comparable to the C++ STL).
C
1,157
4,017 commits
updated Jul 22, 2026
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 / copy / move / 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:
Other key designs are:
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.
The containers have exclusive ownership of the objects they encapsulate. The objects can be pushed in the container:
INIT_SET),INIT_MOVE),EMPLACE)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.
By default, M*LIB uses the malloc, realloc and free functions to handle
the memory pool.
This behavior can be customized to your heart content (fully supporting arena allocator).
Its default policy is to abort the program if there is a memory error: 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 and contract checking in its implementation to ensure robustness:
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.
You can look at the commented examples to get along with how to use the library. You'll see by yourself how easy is to write code using it. Even if writing the library itself is hard (as the code is quite complex and uses a lot of tricks - pretty much like the STL itself), I can ensure you that using it is very natural and simple, and the learning curve low.
In this documentation,
All pointers expected by the functions of the library shall expect non-null argument except if indicated.
The following headers define containers that don't require the user structure to be modified:
The available containers of M*LIB for thread synchronization are in the following headers:
The following containers are intrusive (You need to modify your structure to add fields needed by the container) and are defined in:
Other headers offering other functionality are:
Finally, headers for compatibility with non C11 compilers:
stdatomic.h and C++'s atomic header (provide also its own implementation if nothing is available),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.
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 on the host, run:
make check
You can also override the compiler CC, its flags CFLAGS and LDFLAGS if needed, to select which compiler you want to use:
make check CC="gcc" CFLAGS="-O3"
The dependencies of the test suite are computed automatically by the C compiler using the depend target,
which assumes a GCC compiler (or compatible). If you use another compiler, you can just
build the depend target using GCC or generate an empty file touch tests/depend before running the
check target.
You can also cross-compile if you want using LOG_COMPILER to pass the interpreter. For example:
make check CC=arm-linux-gnueabihf-gcc LOG_COMPILER="qemu-arm -L /usr/arm-linux-gnueabihf/
To generate the documentation, run:
make doc
Finally, to install the headers, run:
make install PREFIX=/my/directory/where/to/install [DESTDIR=...] [INSTALL_DOCS=yes|no]
it assumes PREFIX is the target directory (default /usr/local/) and DESTDIR is the rootfs (default /).
It installs headers in 'include/m-lib' directory and documentation in 'share/doc/m-lib'. Once it is installed, you can use pkg-config to get the include directory using:
[PKG_CONFIG_PATH=...] pkg-config --cflags m-lib
Note: It is called
m-libinstead ofm*libto avoid some potential issues with a directory name with '*' on Unix.
Other targets exist for development purpose.
This is the Quickstart section of the documentation!
M*LIB enables you to generate quickly custom type data structures and their methods. For this, it uses macro to generate content depending on the provided context.
So 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("%u\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 higher) 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 which takes as argument
the prefix of the container and its basic type. Then it expands and generates
the type of the container (by concatenating the prefix and the suffix _t) which is a list of unsigned int
and also other types (like the iterator of the list which uses the suffis _it_t)
and all the necessary methods needed to handle such container by concatenating the prefix and the suffix of the methods.
For example,
_init : the constructor of an empty list,_clear: the destructor of the list,_push_back: the method to push an object in the list (here an unsigned int)_it: the method to initialize the iterator to the first element of the list,_end_p: the method to test if the iterator as reaches the end of the list,_next: the method to move the iterator to the next element,_cref: the method to get a pointer to the data referenced by the iterator.The generation is heavily context dependent and can generate different code depending on it. You can use it as many times as needed to defined as many lists (of the same or different types) as you want provided that you use a different prefix.
The first argument of the macro is the name to use, e.g. the prefix that is added to all generated functions and types. The second argument of the macro is the type to embed within the container. It can be any C type. The third argument of the macro is optional and is the oplist to use. See below for more information.
Notice you call the function ending with _clear to clear the object.
Clearing for the library means drop (or free or destruct) the container's allocated memory.
It is its destructor.
You could replace LIST_DEF by ARRAY_DEF to change
the kind of container (an array instead of a linked list)
without changing the code below: the generated interface
of a list or of an array is very similar.
Yet the performance remains the same as hand-written code
for both the list variant and the array variant.
This is equivalent to this C++ program using the STL:
#include <iostream>
#include <list>
typedef std::list<unsigned int> list_uint_t;
typedef std::list<unsigned int>::iterator list_uint_it_t;
int main(void) {
list_uint_t list ; /* list_uint_t has been define above */
list.push_back(42); /* Push 42 in the list */
list.push_back(17); /* Push 17 in the list */
for(list_uint_it_t it = list.begin() /* Iterator is first element*/
; it != list.end() /* Until the end is not reached */
; ++it) { /* Set the iterator to the next element*/
std::cout << *it << '\n'; /* Print the underlying data */
}
}
As you can see, this is rather equivalent with the following remarks:
Note: M*LIB defines its own container as an array of a structure of size 1. This has the following advantages:
All M*LIB containers fully own their data. The user is only responsible for initialization and clearing the container (constructor/destructor).
The container returns borrowed pointers to the data within the container, theses borrowed pointers remain valid until modification of the container.
M*LIB offers also the possibility to condense further your code, so that it is more high level:
by using the M_EACH & M_LET macros (if you are not afraid of using syntactic macros):
#include <stdio.h>
#include "m-list.h"
LIST_DEF(list_uint, unsigned int) /* Define struct list_uint_t and its methods */
int main(void) {
M_LET(list, LIST_OPLIST(uint)) { /* Define & init list as list_uint_t */
list_uint_push_back(list, 42); /* Push 42 in the list */
list_uint_push_back(list, 17); /* Push 17 in the list */
for M_EACH(item, list, LIST_OPLIST(uint)) {
printf("%u\n", *item); /* Print the item */
}
} /* Clear of list will be done now */
}
Note: M*LIB macros are in upper cases and look like macros, normal functions are in lower cases.
You have just seen a new word you don't know: LIST_OPLIST
What is an oplist? To understand what it is, let's another example with a more complete type (with proper initialization & clear function) by using the GMP library:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
ARRAY_DEF(array_mpz, mpz_t, (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ)) )
int main(void) {
array_mpz_t array ; /* array_mpz_t has been define above */
array_mpz_init(array); /* All type needs to be initialized */
mpz_t z; /* Define a mpz_t type */
mpz_init(z); /* Initialize the z variable */
mpz_set_ui (z, 42);
array_mpz_push_back(array, z); /* Push 42 in the array */
mpz_set_ui (z, 17);
array_mpz_push_back(array, z); /* Push 17 in the array */
array_mpz_it_t it; /* Define an iterator to scan each one */
for(array_mpz_it(it, array) /* Start iterator on first element */
; !array_mpz_end_p(it) /* Until the end is not reached */
; array_mpz_next(it)) { /* Set the iterator to the next element*/
gmp_printf("%Zd\n", /* Get a reference to the underlying */
*array_mpz_cref(it)); /* data and print it */
}
mpz_clear(z); /* Clear the z variable */
array_mpz_clear(array); /* Clear all the array */
}
As the mpz_t type needs proper initialization, copy and destroy functions
we need to tell to the container how to handle such a type.
This is done by giving it the oplist associated to the type.
An oplist is an associative array where an operator is associated to its associated method.
In the example, we tell to the container to use:
mpz_init function for the INIT operator of the type (aka constructor),mpz_clear function for the CLEAR operator of the type (aka destructor),mpz_set function for the SET operator of the type (aka copy),mpz_init_set function for the INIT_SET operator of the type (aka copy constructor).M_COPY_A1OBJ is used for the INIT_MOVE operator (good for all objects using the [1] trick).The all pattern (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ))
is the oplist of the `mpz_t type. It starts with a parenthesis and end with a parenthesis.
Each association is done by giving the operator in upper case, and its method just after in parenthesis.
This associative array only exists in the preprocessing step of the compilation,
resulting in no runtime cost and strict aliasing check.
The LIST_OPLIST seen in the previous chapter is just a macro that define the oplist
for a list container giving its name.
See OPLIST chapter for more detailed information.
With oplists, behavior becomes modular, reusable and even inheritable: You define semantics once, reuse everywhere.
We can also write the same example shorter by using the ability of M*LIB to register oplists:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
// Register the oplist of a mpz_t.
#define M_OPL_mpz_t() (INIT(mpz_init), INIT_SET(mpz_init_set), \
SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ))
// Define an instance of an array of mpz_t (both type and function)
ARRAY_DEF(array_mpz, mpz_t)
// Register the oplist of the created instance of array of mpz_t
#define M_OPL_array_mpz_t() ARRAY_OPLIST(array_mpz, M_OPL_mpz_t())
int main(void) {
// Let's define `array` as an 'array_mpz_t' & initialize it.
M_LET(array, array_mpz_t)
// Let's define 'z1' and 'z2' to be 'mpz_t' & initialize it
M_LET (z1, z2, mpz_t) {
mpz_set_ui (z1, 42);
array_mpz_push_back(array, z1); /* Push 42 in the array */
mpz_set_ui (z2, 17);
array_mpz_push_back(array, z2); /* Push 17 in the array */
// Let's iterate over all items of the container
for M_EACH(item, array, array_mpz_t) {
gmp_printf("%Zd\n", *item);
}
} // All variables are cleared with the proper method beyond this point.
return 0;
}
To register an oplist, you need to define the macro M_OPL_+type that expands into its oplist.
It shall be a macro function that take no argument.
Or even shorter when you're comfortable enough with the library by using its advanced constructor features:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
// Register the oplist of a mpz_t. It is a classic oplist.
#define M_OPL_mpz_t() M_OPEXTEND(M_CLASSIC_OPLIST(mpz), \
INIT_WITH(mpz_init_set_ui), EMPLACE_TYPE(unsigned int))
// Define an instance of an array of mpz_t (both type and function)
ARRAY_DEF(array_mpz, mpz_t)
// Register the oplist of the created instance of array of mpz_t
#define M_OPL_array_mpz_t() ARRAY_OPLIST(array_mpz, M_OPL_mpz_t())
int main(void) {
// Let's define `array` as an 'array_mpz_t' with mpz_t(17) and mpz_t(42)
M_LET((array,(17),(42)), array_mpz_t) {
// Let's iterate over all items of the container
for M_EACH(item, array, array_mpz_t) {
gmp_printf("%Zd\n", *item);
}
} // All variables are cleared with the proper method beyond this point.
return 0;
}
There are two ways a container can known which oplist is to be used for the type:
M_LET and M_EACH macros,M_OPL_ and finishing with the name of type (don't forget the parenthesis and the suffix _t if needed). The macros performing the definition of container and the M_LET and M_EACH will test if such macro is defined. If it is defined, it will be used. Otherwise, default methods are used.Here we can see that we register the mpz_t type into the container with
the minimum information of its interface needed, and another one to initialize a mpz_t from an unsigned integer.
We can also see in this example so the container ARRAY provides also a macro to define the oplist of the array itself. This is true for all containers and this enables to define proper recursive container like in this example which reads from a text file a definition of sections:
#include <stdio.h>
#include "m-array.h"
#include "m-tuple.h"
#include "m-dict.h"
#include "m-string.h"
TUPLE_DEF2(symbol, (offset, long), (value, long))
#define M_OPL_symbol_t() TUPLE_OPLIST(symbol, M_BASIC_OPLIST, M_BASIC_OPLIST)
ARRAY_DEF(array_symbol, symbol_t)
#define M_OPL_array_symbol_t() ARRAY_OPLIST(array_symbol, M_OPL_symbol_t())
DICT_DEF2(sections, string_t, array_symbol_t)
#define M_OPL_sections_t() DICT_OPLIST(sections, STRING_OPLIST, M_OPL_array_symbol_t())
int main(int argc, const char *argv[])
{
if (argc < 2) abort();
FILE *f = fopen(argv[1], "rt");
if (!f) abort();
M_LET(sc, sections_t) {
sections_in_str(sc, f);
array_symbol_t *a = sections_get(sc, STRING_CTE(".text"));
if (a == NULL) {
printf("There is no .text section.");
} else {
printf("Section .text is :");
array_symbol_out_str(stdout, *a);
printf("\n");
}
}
return 0;
}
This example reads the data from a file and outputs the .text section if it finds it on the terminal.
Other examples are available in the example folder.
Internal fields of the structure are subject to change even for small revision of the library.
The final goal of the library is to be able to write code like this in pure C while keeping type safety and compile time name resolution:
let(list, list_uint_t) {
push(list, 42);
push(list, 17);
for each (item, list) {
print(*item, "\n");
}
}
And it works! See the example and m-generic header for details.
( ) or double level of ( ) around the oplist,BASIC_OPLIST instead of M_BASIC_OPLIST),name parameter given to the oplist is not the same as the one used to expand the methods,M*LIB performance is compared to the one of GNU C++ STL (v10.2) in the following graphs. Each graph is presented first in linear scale and then in logarithmic scale to better realize the differences. M*LIB is on par with the STL or even faster.
All used bench codes are available in this repository The results for several different libraries are also available in a separate page.
An OPLIST is a fundamental notion of M*LIB that hasn't be seen in any other library.
In order to know how to operate on a type, M*LIB needs additional information
as the compiler doesn't know how to handle properly any type (contrary to C++).
This is done by giving an operator list (or oplist in short) to any macro that
needs to handle the type. As such, an oplist has only meaning within a macro.
Fundamentally, this is the exposed interface of a type:
that is to say the association of the operators defined by the library to the
effective methods provided by the type, including their call interface.
This association is done only with the C preprocessor.
Therefore, an oplist is an associative array of operators to methods in the following format:
(OPERATOR1(method1), OPERATOR2(method2), ...)
It starts with a parenthesis and ends with a parenthesis. Each association is separated by a comma. Each association is composed of a predefined operator (as defined below) a method (in parentheses), and an optional API interface (see below).
In the given example,
the function method1 is used to handle OPERATOR1.
The function method2 is used to handle OPERATOR2, etc.
In case the same operator appears multiple times in the list, the first apparition of the operator has priority, and its associated method will be used. This enables overloading of operators in oplist in case you want to inherit oplists.
The associated method in the oplist is a preprocessor expression that shall not contain a comma as first level.
An oplist has no real form from the C language point of view. It is just an abstraction that disappears after the macro expansion step of the preprocessing. If an oplist remains unprocessed after the C preprocessing, a compiler error will be generated.
For basic C type, you can even omit the oplist definition, and the library will know how to handle it. For more complex type, you don't often have to define stub code to specify how elements are compared, copied, or destroyed by matching what is expected by the library: you can request conversion on the fly from what is provided to what is expected by using an adaptor. It allows very powerful binding while keeping it very simple to use and as error prone as possible.
When you define an instance of a new container for a given type, you give the type OPLIST
alongside the type for building the container.
Some functions of the container may not be available in function of the provided interface of the OPLIST
(for optional operators).
Of if some mandatory operators are missing, a compiler error is generated.
The generated container will also provide its own oplist, which will depends on all the oplists used to generate it. This oplist can also be used to generate new containers.
You can therefore use the oplist of the container to chain this new interface
with another container, creating container-of-container.
[!NOTE] An operator shall fail only on abnormal error and if it is marked as potentially raising asynchronous errors. In this case it shall throw exceptions only if exceptions are configured. Otherwise, the program shall be terminated.
In this case, the objects remain initialized and valid but in an unspecified state. In case of in constructors, the object is not constructed and the destructor of the object has not to be called.
[!NOTE] If an operator is not marked as raising asynchronous errors, it shall not fail or throw any exceptions in any cases.
Not all operators are needed for an oplist to handle a container. If some operator is missing, the associated default method of the operator is used if it exists.
The following classic operators are usually expected for an object:
INIT(obj): initialize the object obj into a valid state (constructor). It may raise asynchronous error.INIT_SET(obj, org): initialize the object obj into the same state as the object org (copy constructor). It may raise asynchronous error.SET(obj, org): set the initialized object obj into the same state as the initialized object org (copy operator). It may raise asynchronous error.CLEAR(obj): destroy the initialized object obj, releasing any attached memory (destructor).Other documented operators are:
NAME() --> prefix: Return the base name prefix used to construct the container.FIELD() --> field name: Return the name of the field used when constructing the upper container.TYPE() --> type: Return the base type associated to this oplist.SUBTYPE() --> type: Return the type of the element stored in the container (used to iterate over the container).GENTYPE() --> type: Return the type representing TYPE but suitable for a _Generic statement.OPLIST() --> oplist: Return the oplist of the type of the elements stored in the container.KEY_TYPE() --> key_t: Return the key type for associative containers.VALUE_TYPE() --> value_t: Return the value type for associative containers.KEY_OPLIST() --> oplist: Return the oplist of the key type for associative containers.VALUE_OPLIST() --> oplist: Return the oplist of the value type for associative containers.NEW(context, type) --> type pointer: allocate a new object (with suitable alignment and size) and return a pointer to it. The returned object is not initialized (a constructor operator shall be called afterward). The default method is M_MEMORY_ALLOC (that allocates from the heap). It returns NULL in case of failure.DEL(context, &obj): free the allocated uninitialized object obj. The destructor of the pointed object shall be called before freeing the memory by calling this method. The object shall have been allocated by the associated NEW method. sizeof obj is the size of the allocated object. The default method is M_MEMORY_DEL (that frees to the heap). obj shall not be NULL and shall be of the proper type.REALLOC(context, type, pointer, previous_number, new_number) --> pointer: reallocate the given array of previous_number elements of type type referenced by pointer (either a NULL pointer or a pointer returned by a previous call to REALLOC) to an array of new_number objects of type type and return a pointer to this new array. Previously objects pointed by the pointer are kept up to the minimum of the new size and old one but may have moved from their original positions (if the array is reallocated otherwhere). New objects are not initialized (a constructor operator shall be called afterward). Freed objects are not cleared (A destructor operator shall be called before). The default is M_MEMORY_REALLOC (that allocates from the heap). It returns NULL in case of failure in which case the original array is not modified. If pointer is NULL, then previous_number should be 0.FREE(context, type, pointer, number): free the allocated uninitialized array of number elements of type type referenced by pointer. The destructor of the pointed objects shall be called before freeing the memory. The memory of the objects shall have been allocated by the associated REALLOC method. The default is M_MEMORY_FREE (that frees to the heap). If pointer is NULL, then the function shall do nothing.INC_ALLOC(size_t s) --> size_t: Define the growing policy of an array (or equivalent structure). It returns a new allocation size based on the old allocation size (s). Default policy is to get the maximum between 2*s and 16. In case of overflow, it shall return a number less or equal than the original size.[!NOTE] It doesn't check for overflow: if the returned value is lower than the old one, the user shall raise an overflow error (memory error).
INIT_MOVE(objd, objc): Initialize objd to the same state than objc by stealing as many resources as possible from objc, and then clear objc (constructor of objd + destructor of objc). It is semantically equivalent to calling INIT_SET(objd,objc) then CLEAR(objc) but is usually way faster. Contrary to the C++ choice of using "conservative move" semantic (you still need to call the destructor of a moved object in C++) M*LIB implements a "destructive move" semantic (this enables better optimization). By default, all objects are assumed to be trivially movable (i.e. using memcpy to move an object is safe). Most C objects (even complex structure) are trivially movable and it is a very nice property to have (enabling better optimization). A notable exception are intrusive objects. If an object is not trivially movable, it shall provide an INIT_MOVE method or disable the INIT_MOVE method entirely[!NOTE] Some containers may assume that the objects are always trivially movable (like array). Moved objects shall use the same memory allocator.
MOVE(objd, objc): Set objd to the same state than objc by stealing as resources as possible from objc and then clear objc (destructor of objc). It is equivalent to calling SET(objd,objc) then CLEAR(objc) or CLEAR(objd) and then INIT_MOVE(objd, objc). See INIT_MOVE for details and constraints. TBC if this operator is really needed as calling CLEAR then INIT_MOVE is what do all known implementation, and is efficient.INIT_WITH(obj, ...): Initialize the object obj with the given variable set of arguments (constructor). The arguments are variable and can be of different types. It is up to the method of the object to decide how to initialize the object based on this initialization array. This operator is used by the M_LET macro to initialize objects with their given values and this operator defines what the M_LET macro supports. It may raise asynchronous error.[!NOTE] In C11, you can use
API_1(M_INIT_WITH_THROUGH_EMPLACE_TYPE)as a method forINIT_WITHto automatically use the different emplace functions defined inEMPLACE_TYPEthrough a _Generic switch case. The providedEMPLACE_TYPEshall use the LIST format. See emplace chapter.
SWAP(objd, objc): Swap the states of the object objc and the object objd.[!NOTE] The swapped objects shall use the same allocator.
RESET(obj): Reset the object to its initialized state (Emptying the object if it is a container object).EMPTY_P(obj) --> bool: Test if the container object is empty (true) or not.FULL_P(obj) --> bool: Test if the container object is full (true) or not. Default if not defined is to be not full.GET_SIZE (container) --> size_t: Return the number of elements in the container object.HASH (obj) --> size_t: return a hash of the object (not a secure hash but one that is usable for a hash table). Default is performing a hash of the memory representation of the object. This default implementation is invalid if the object holds pointer to other objects or has spare fields.EQUAL(obj1, obj2) --> bool: Compare the two objects for equality. Return true if both objects are equal, false otherwise. Default is using the C comparison operator. 'obj1' may be an OOR object (Out of Representation) for the Open Addressing dictionary (see OOR_* operators): in such cases, it shall return false.CMP(obj1, obj2) --> int: Provide a complete order the objects. return a negative integer if obj1 < obj2, 0 if obj1 = obj2, a positive integer otherwise. Default is C comparison operator.[!NOTE] The equivalence between
EQUAL(a, b)andCMP(a, b) == 0is not required, but is usually welcome.
ADD(obj1, obj2, obj3): Set obj1 to the sum of obj2 and obj3. Default is + C operator. It may raise asynchronous error.SUB(obj1, obj2, obj3): Set obj1 to the difference of obj2 and obj3. Default is - C operator. It may raise asynchronous error.MUL(obj1, obj2, obj3): Set obj1 to the product of obj2 and obj3. Default is * C operator. It may raise asynchronous error.DIV(obj1, obj2, obj3): Set obj1 to the division of obj2 and obj3. Default is / C operator. It may raise asynchronous error.GET_KEY (container, key) --> &value: Return a pointer to the value object within the container associated to the key key if an object is associated to this key. Otherwise it may return NULL or terminate the program with a logic error (depending on the container). The pointer to the value object remains valid until any modification of the container.SET_KEY (container, key, value): Associate the key object key to the value object value in the given container. It may raise asynchronous error.SAFE_GET_KEY (container, key) --> &value: return a pointer to the value object within the container associated to the key key if it exists, or create a new entry in the container and associate it to the key key with the default initialization before returning its pointer. The pointer to the object remains valid until any modification of the container. The returned pointer is therefore never NULL. It may raise asynchronous error.ERASE_KEY (container, key) --> bool: Erase the object associated to the key key within the container. Return true if successful, false if the key is not found (nothing is done).PUSH(container, obj): Push obj (of type SUBTYPE()) into the container container. How and where it is pushed is container dependent. It may raise asynchronous error.POP(&obj, container): Pop an object from the container container and set it in the initialized object *obj (of type SUBTYPE()) if the pointer obj is not NULL. Which object is popped is container dependent. It may raise asynchronous error.PUSH_MOVE(container, &obj): Push and move the object *obj (of type SUBTYPE()) into the container container (*obj destructor). How it is pushed is container dependent. *obj is cleared afterward and shall not be used anymore. See INIT_MOVE for more details and constraints. It may raise asynchronous error.POP_MOVE(&obj, container): Pop an object from the container container and init & move it in the uninitialized object *obj (aka constructor). Which object is popped is container dependent. *obj shall be uninitialized. See INIT_MOVE for more details and constraints.[!NOTE] When using a
POPoperator (or any derived operator) on a container, this container shall have at least one object.
The iterator operators are:
IT_TYPE() --> type: Return the type of the iterator object of this container.IT_FIRST(it_obj, obj): Set the iterator it_obj to the first sub-element of the container obj. What is the first element is container dependent (it may be front or back, or something else). However, iterating from FIRST to LAST (included) or END (excluded) through IT_NEXT ensures going through all elements of the container. If there is no sub-element in the container, it references an end of the container.IT_LAST(it_obj, obj): Set the iterator it_obj to the last sub-element of the container obj. What is the last element is container dependent (it may be front or back, or something else). However, iterating from LAST to FIRST (included) or END (excluded) through IT_PREVIOUS ensures going through all elements of the container. If there is no sub-element in the container, it references an end of the container.IT_END(it_obj, obj): Set the iterator it_obj to an end of the container obj. Once an iterator has reached an end, it can't use PREVIOUS or NEXT operators. If an iterator has reached an END, it means that there is no object referenced by the iterator (kind of NULL pointer). There can be multiple representation of the end of a container, but all of then share the same properties.IT_SET(it_obj, it_obj2): Set the iterator it_obj to reference the same sub-element as it_obj2.IT_END_P(it_obj) --> bool: Return true if the iterator it_obj references an end of the container, false otherwise.IT_LAST_P(it_obj) --> bool: Return true if the iterator it_obj references the last element of the container (just before reaching an end) or has reached an end of the container, false otherwise.IT_EQUAL_P(it_obj, it_obj2) --> bool: Return true if both iterators reference the same element, false otherwise.IT_NEXT(it_obj): Move the iterator to the next sub-element or an end of the container if there is no more sub-element. The direction of IT_NEXT is container dependent. it_obj shall not be an end of the container.IT_PREVIOUS(it_obj): Move the iterator to the previous sub-element or an end of the container if there is no more sub-element. The direction of PREVIOUS is container dependent, but it is the reverse of the IT_NEXT operator. it_obj shall not be an end of the container.IT_CREF(it_obj) --> &subobj: Return a constant pointer to the object referenced by the iterator (of type const SUBTYPE()). This pointer remains valid until any modifying operation on the container, or until another reference is taken from this container through an iterator (some containers may reduce theses constraints, for example a list). The iterator shall not be an end of the container.IT_REF(it_obj) --> &subobj: Same as IT_CREF, but return a modifiable pointer to the object referenced by the iterator.IT_INSERT(obj, it_obj, subobj): Insert subobj after 'it_obj' in the container obj and update it_obj to point to the inserted object (as per IT_NEXT semantics). All other iterators of the same container become invalidated. If 'it_obj' is an end of the container, it inserts the object as the first one.IT_REMOVE(obj, it_obj): Remove it_obj from the container obj (clearing the associated object) and update it_obj to point to the next object (as per IT_NEXT semantics). As it modifies the container, all other iterators of the same container become invalidated. it_obj shall not be an end of the container.SPLICE_BACK(objd, objs, it_obj): Move the object of the container objs referenced by the iterator 'it_obj' to the container objd. Where it is moved is container dependent (it is recommended however to be like the PUSH method). Afterward 'it_obj' references the next item in 'containerSrc' (as per IT_NEXT semantics). 'it_obj' shall not be an end of the container. Both objects shall use the same allocator. It may raise asynchronous error.SPLICE_AT(objd, id_objd, objs, it_objs): Move the object referenced by the iterator it_objs from the container objs just after the object referenced by the iterator it_objd in the container objd. If it_objd references an end of the container, it is inserted as the first item of the container (See operator IT_INSERT). Afterward it_objs references the next item in the container objs, and it_objd references the moved item in the container objd. it_objs shall not be an end of the container. Both objects shall use the same allocator. It may raise asynchronous error.[!NOTE] An iterator doesn't have a constructor nor destructor methods. Therefore, it cannot not allocate any memory.
[!NOTE] A reference to an object through the pointer get from the iterator is only valid until another reference is taken from the same container (potentially through another iterator), or the iterator is modified or the container itself is modified. This reference is therefore extremely local and should not be stored anywhere else. Some containers may lessen this constraint (for example list or RB-Tree).
[!NOTE] If the container is modified, all iterators of this container become invalid and shall not be used anymore except if the modifying operator provided itself an updated iterator. Some containers may lessen this constraint.
The I/O operators are:
OUT_STR(FILE* f, obj): Output obj as a custom formatted string into the FILE* stream f. Format is container dependent, but is human readable.IN_STR(obj, FILE* f) --> bool: Set obj to the value associated to the formatted string representation of the object in the FILE* stream f. Return true in case of success (in that case the stream f has been advanced to the end of the parsing of the object), false otherwise (in that case, the stream f is in an undetermined position but is likely where the parsing fails). It ensures that an object which is output in a FILE through OUT_STR, and an object which is read from this FILE through IN_STR are considered as equal. It may raise asynchronous error.GET_STR(string_t str, obj, bool append): Set str to a formatted string representation of the object obj. Append to the string if append is true, set it otherwise. This operator requires the module m-string. It may raise asynchronous error.PARSE_STR(obj, const char *str, const char **endp) --> bool: Set obj to the value associated to the formatted string representation of the object in the char stream str. Return true in case of success (in that case if endp is not NULL, it points to the end of the parsing of the object), false otherwise (in that case, if endp is not NULL, it points to an undetermined position but likely to be where the parsing fails). It ensures that an object which is written in a string through GET_STR, and an object which is read from this string through PARSE_STR are considered as equal. It may raise asynchronous error.OUT_SERIAL(m_serial_write_t *serial, obj) --> m_serial_return_code_t: Output obj into the configurable serialization stream serial (See m-serial-json.h for details and example) as per the serial object semantics. Return M_SERIAL_OK_DONE in case of success, or M_SERIAL_FAIL otherwise. It may raise asynchronous error.IN_SERIAL(obj, m_serial_read_t *serial) --> m_serial_return_code_t: Set obj to its representation from the configurable serialization stream serial (See m-serial-json.h for details and example) as per the serial object semantics. M_SERIAL_OK_DONE in case of success (in that case the stream serial has been advanced up to the complete parsing of the object), or M_SERIAL_FAIL otherwise (in that case, the stream serial is in an undetermined position but usually around the next characters after the first failure). It may raise asynchronous error.The final operators are:
OOR_SET(obj, int_value): Some containers want to store some information within the uninitialized objects (for example Open Addressing Hash Table). This method stores the integer value 'int_value' into an uninitialized object obj. It shall be able to differentiate between uninitialized object and initialized object (How is type dependent). The way to store this information is fully object dependent. In general, you use out-of-range value for detecting such values. The object remains uninitialized but sets to of out-of-range value (OOR). int_value can be 0 or 1.OOR_EQUAL(obj, int_value): This method compares the object obj (initialized or uninitialized) to the out-of-range value (OOR) representation associated to 'int_value' and returns true if both objects are equal, false otherwise. See OOR_SET.REVERSE(obj): Reverse the order of the items in the container obj. It may raise asynchronous error.SEPARATOR() --> character: Return the character used to separate items for I/O methods (default is ',') (for internal use only).EXT_ALGO(name, container oplist, object oplist): Define additional algorithms functions specialized for the containers (for internal use only).PROPERTIES() --> ( properties): Return internal properties of a container in a recursive oplist format. Use M_GET_PROPERTY to get the property.EMPLACE_TYPE( ... ): Specify the types usable for "emplacing" the object (initializing the object in-place, constructor). See chapter Emplace construction. THe referenced initializing functions may raise asynchronous error.[!NOTE] The operator names listed above shall not be defined as macro.
More operators are expected.
Properties can be stored in a sub-oplist format in the PROPERTIES operator.
The following properties are defined:
LET_AS_INIT_WITH(1) — Defined if the macro M_LET shall always initialize the object with INIT_WITH regardless of the given input. The value of the property is 1 (enabled) or 0 (disabled/default).NOCLEAR(1) — Defined if the object CLEAR operator can be omitted (like for basic types or POD data). The value of the property is 1 (enabled) or 0 (disabled/default).[!NOTE] The properties names listed above shall not be defined as macro.
More properties are expected.
Let's take the interface of the MPZ library:
void mpz_init(mpz_t z); // Constructor of the object z
void mpz_init_set(mpz_t z, const mpz_t s); // Copy Constructor of the object z
void mpz_set(mpz_t z, const mpz_t s); // Copy operator of the object z
void mpz_clear(mpz_t z); // Destructor of the object z
A basic oplist will be:
(INIT(mpz_init),SET(mpz_set),INIT_SET(mpz_init_set),CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ),TYPE(mpz_t))
Much more complete oplist can be built for this type however, enabling much more powerful generation: See in the example
Oplist can be registered globally by defining, for the type type, a macro named
M_OPL_ ## type () that expands to the oplist of the type.
Only type without any space in their name can be registered. A typedef of the type
can be used instead, but this typedef shall be used everywhere.
Example:
#define M_OPL_mpz_t() (INIT(mpz_init),SET(mpz_set), \
INIT_SET(mpz_init_set),CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ),TYPE(mpz_t))
[!NOTE] Registering globaly the oplist when defining its type simplify a lot the
OPLISTusage and it is highly recommended.
Then each times a macro expects an oplist, you can give instead its type. This make the code much easier to read and understand.
There is one exception however: the macros that are used to build oplist
(like ARRAY_OPLIST) don't perform this simplification and the oplist of
the type shall be explictely given instead
(This is due to limitation in the C preprocessing).
Within an OPLIST, you can also specify the needed low-level transformation to perform for calling your method.
This is called API Interface Adaptation: it enables to transform the API requirements of the selected operator
(which is very basic in general) to the API provided by the given method.
Assuming that the method to call is called 'method' and the first argument of the operator is 'output',
which interface is OPERATOR(output, ...)
then the following predefined adaptation are available:
| API | Method | Description |
|---|---|---|
| API_0 | method(output, ...) | No adaptation |
| API_1 | method(oplist, output, ...) | No adaptation but gives the oplist to the method |
| API_2 | method(&output, ...) | Pass by address the first argument (like with M_IPTR) |
| API_3 | method(oplist, &output, ...) | Pass by address the first argument (like with M_IPTR) and give the oplist of the type |
| API_4 | output = method(...) | Pass by return value the first argument |
| API_5 | output = method(oplist, ...) | Pass by return value the first argument and give the oplist of the type |
| API_6 | method(&output, &...) | Pass by address the two first arguments |
| API_7 | method(oplist, &output, &...) | Pass by address the two first argument and give the oplist of the type |
The API Adaptation to use shall be embedded in the OPLIST definition.
For example:
(INIT(API_0(mpz_init)), SET(API_0(mpz_set)), INIT_SET(API_0(mpz_init_set)), CLEAR(API_0(mpz_clear)), INIT_MOVE(M_COPY_A1OBJ))
The default adaptation is API_0 (i.e. no adaptation between operator interface and method interface). If an adaptation gives an oplist to the method, the method shall be implemented as macro.
Let's take the interface of a pseudo library:
typedef struct { ... } obj_t;
obj_t *obj_init(void); // Constructor of the object z
obj_t *obj_init_str(const char *str); // Constructor of the object z
obj_t *obj_clone(const obj_t *s); // Copy Constructor of the object z
void obj_clear(obj_t *z); // Destructor of the object z
The library returns a pointer to the object, so we need API_4 for these methods.
There is no method for the SET operator available. However, we can use the macro M_SET_THROUGH_INIT_SET
to emulate a SET semantics by using a combination of CLEAR + INIT_SET. This enables to support
the type for array containers in particular. Or we can avoid this definition if we don't need it.
A basic oplist will be:
(INIT(API_4(obj_init)),SET(API_1(M_SET_THROUGH_INIT_SET)),INIT_SET(API_4(obj_clone)),CLEAR(obj_clear),TYPE(obj_t *))
To work, M_SET_THROUGH_INIT_SET needs to have the oplist of the type to perform a call to its
CLEAR and INIT_SET operator, thus using the API_1 convention.
You can also describe the exact transformation to perform for calling the method: this is called Generic API Interface Adaptation (or GAIA). With this, you can add constant values to parameter of the method, reorder the parameters as you wish, pass then by pointers, or even change the return value.
The API adaptation is also described in the operator mapping with the method name by using the API keyword. Usage in oplist:
, OPERATOR( API( method, returncode, args...) ) ,
Within the API keyword,
returncode is the transformation to perform of the return code.returncode can be
NONE — no transformation,VOID — cast to void,NEG — inverse the result,EQ(val)/NEQ(val)/LT(val)/GT(val)/LE(val)/GE(val) — compare the return code to the given valueARG[1-9] — set the associated argument number of the operator to the return codeAn argument can be:
ID( constant or variable) — if the constant or variable is not a valid token,ARG[1-9] — the associated argument number of the operator,ARGPTR[1-9] — the pointer of the associated argument number of the operator,OPLIST — the oplistTherefore, it supports at most 9 arguments.
Example:
, EQUAL( API(mpz_cmp, EQ(0), ARG1, ARG2) ) ,
This will transform a return value of 0 by the mpz_cmp method into a boolean for the EQUAL operator.
Another Example:
, OUT_STR( API(mpz_out_str, VOID, ARG1, 10, ARG2) ) ,
This will serialize the mpz_t value in base 10 using the mpz_out_str method, and discarding the return value.
An operator OP can be defined, omitted or disabled:
( OP(f) ): the function f is the method of the operator OP( OP(API_N(f)) ): the function f is the method of the operator OP with the API transformation number N,( ): the operator OP is omitted, and the default global operation for OP is used (if it exists).( OP(0) ): the operator OP is disabled, and it can never be used.This can be useful to disable an operator in an inherited oplist.
OPLIST to use?My type is:
M_BOOL_OPLIST (M_BASIC_OPLIST also works partially),M_BASIC_OPLIST (it can also be omitted),M_ENUM_OPLIST,M_PTR_OPLIST,M_POD_OPLIST,memset, memcpy, memcmp: M_A1_OPLIST,name_init, name_init_set, name_set, name_clear methods: M_CLASSIC_OPLIST,const char *) that is neither freed nor moved: M_CSTR_OPLIST,STRING_OPLIST,OPLIST of the used container,OPLIST to your type.[!NOTE] The precise exported methods of the OPLIST depend on the version of the used C language. Typically, in C11 mode, the
M_BASIC_OPLISTexports all needed methods to handle generic input/output of int/floats (using_Generickeyword) whereas it is not possible in C99 mode.
This explains why JSON import/export is only available in C11 mode (See below chapter).
Basic usage of oplist is available in the example
Oplist can inherit from another one.
This is useful when you want to customize some specific operators while keeping other ones by default.
For example, internally M_BOOL_OPLIST inherits from M_BASIC_OPLIST.
A typical example is if you want to provide the OOR_SET and OOR_EQUAL operators to a type
so that it can be used in an OA dict.
To do it, you use the M_OPEXTEND macro. It takes as first argument the oplist you want to inherit with,
and then you provide the additional associations between operators to methods you want to add
or override in the inherited oplist. For example:
int my_int_oor_set(char c) { return INT_MIN + c; }
bool my_int_oor_equal(int i1, int i2) { return i1 == i2; }
#define MY_INT_OPLIST \
M_OPEXTEND(M_BASIC_OPLIST, OOR_SET(API_4(my_int_oor_set)), \
OOR_EQUAL(my_int_oor_equal))
You can even inherit from another oplist to disable some operators in your new oplist. For example:
#define MY_INT_OPLIST \
M_OPEXTEND(M_BASIC_OPLIST, HASH(0), CMP(0), EQUAL(0))
MY_INT_OPLIST is a new oplist that handles integers but has disabled the operators HASH, CMP and EQUAL.
The main interest is to disable the generation of optional methods of a container (since they are only
expanded if the oplist provides some methods).
Usage of inheritance and oplist is available in the int example and the cstr example
Let's take a look at the interface of the FILE* interface:
FILE *fopen(const char *filename, const char *mode);
fclose(FILE *f);
There is no INIT operator (an argument is mandatory), no INIT_SET operator.
It is only possible to open a file from a filename.
FILE* contains some space, so an alias is needed.
There is an optional mode argument, which is a constant string, and isn't a valid preprocessing token.
An oplist can therefore be:
typedef FILE *m_file_t;
#define M_OPL_m_file_t() (INIT_WITH(API(fopen, ARG1, ARG2, ID("wt"))), \
SET(0),INIT_SET(0),CLEAR(fclose),TYPE(m_file_t))
Since there is no INIT_SET operator available, pretty much no container can work.
However, you'll be able to use a writing text FILE* using a M_LET:
M_LET( (f, ("tmp.txt")), m_file_t) {
fprintf(f, "This is a tmp file.");
}
This is pretty useless, except if you enable exceptions... In which case, this enables you to close the file even if an exception is thrown.
Memory Allocation functions can be globally set by overriding the following macros before using the definition _DEF macros:
M_MEMORY_ALLOC (context, type) --> ptr: return a pointer to a new object of type type.M_MEMORY_DEL (context, ptr): free the single object pointed by ptr.M_MEMORY_REALLOC (context, type, ptr, old_number, new_number) --> ptr: return a pointer to an array of new_number objects of type type, reusing the old array pointed by ptr of old_number objects. ptr can be NULL, in which case the array will be created.M_MEMORY_FREE (context, type, ptr, number): free the array of number objects of type type pointed by ptr.[!NOTE] You can use
sizeof (type)andalignof (type)to get the size and the alignment of the object.
[!NOTE] For
M_MEMORY_DEL,sizeof *ptralways identifies the size of the object.
ALLOC and DEL operators are supposed to allocate fixed size single element object (no array).
These objects are not expected to grow.
REALLOC and FREE operators deal with allocated memory for growing objects.
Do not mix pointers between both: a pointer allocated by ALLOC (resp. REALLOC) is supposed
to be only freed by DEL (resp. FREE). There are separated 'free' operators to enable
specialization in the allocator (a good allocator can take this hint into account).
context is a local user context used to identify the memory context to use for the allocation.
This parameter only exists if the library is compiled with the M_USE_CONTEXT customization parameter enabled globally.
Otherwise this parameter identifies a non existing symbol m_context.
This parameter shall be discarded if M_USE_CONTEXT is not defined (it shall not exist anymore after preprocessing step).
For that, you can define the macros to ignore the first parameter
or you can use GAIA to adapt the call to what your function expects.
[!NOTE] If you get error on
m_contextbeing undefined it is likely because one of your memory is trying to evaluate the memory context without definingM_USE_CONTEXT.
M_MEMORY_ALLOC and M_MEMORY_REALLOC are supposed to return NULL in case of memory allocation failure.
The defaults are malloc, free, realloc and free.
You can also override the methods NEW, DEL, REALLOC and DEL in the oplist given to a container
so that only the container will use these memory allocation functions instead of the global ones.
When a memory exhaustion is reached, the global macro M_MEMORY_FULL is called.
It is supposed to terminate the execution flow of the function.
The object remains in a valid (if previously valid) and unchanged state in this case.
By default, the macro prints an error message and aborts the program: handling non-trivial memory errors can be hard, testing them is even harder but still mandatory to avoid security holes. So the default behavior is rather conservative.
It can however be overloaded to handle other policy for error handling like: throwing an error (which is automatically done by including header m-try ).
This function takes the type and the number of elements of this type that has been tried to be allocated.
If needed, this macro shall be defined prior to instantiate the structure.
## Error Classification
[!NOTE] A good design should handle a process entire failure (using for examples multiple processes for doing the job) so that even if a process stops, it should be recovered. See here for more information about why abandonment is good software practice.
In M*LIB, the kind of errors are classified according to this model:
M_MEMORY_FULL macro).ferror) in the data structure.For M*LIB, 'emplace' means pushing a new object in the container,
while not giving it a copy of the new object, but the parameters needed
to construct this object.
This is a shortcut to the pattern of creating the object with the arguments,
pushing it in the container, and deleting the created object
(even if using PUSH_MOVE could simplify the design).
The containers defining an emplace like method generate the emplace functions
based on the provided EMPLACE_TYPE of the oplist. If EMPLACE_TYPE doesn't exist or is disabled, no emplace function is generated. Otherwise EMPLACE_TYPE identifies
which types can be used to construct the object and which methods to use to construct then:
EMPLACE_TYPE( typeA ), means that the object can be constructed from typeA using the method of the INIT_WITH operator. An emplace function without suffix will be generated.EMPLACE_TYPE( (typeA, typeB, ...) ), means that the object can be constructed from the lists of types typeA, typeB, ... using the method of the INIT_WITH operator. An emplace function without suffix will be generated.EMPLACE_TYPE( LIST( (suffix, function, typeA, typeB, ...), (suffix, function, typeA, typeB, ...) means that the object can be constructed from all the provided lists of types typeA, typeB, ... using the provided method function. The function is the method to call to construct the object from the list of types. It supports API transformation if needed. As many emplace function will be generated as there are constructor function. Each generated function will be generated by suffixing it with the provided suffix (if suffix is empty, no suffix will be added).For example, for an ARRAY definition named vec, if there is such a definition of EMPLACE_TYPE(const char *), it will generate a function vec_emplace_back(const char *). This function will take a const char* parameter, construct the object from it (for example a string_t) then push the result back on the array.
Another example, for an ARRAY definition named vec, if there is such a definition of EMPLACE_TYPE( LIST( (_ui, mpz_init_set_ui, unsigned int), (_si, mpz_init_set_si, int) ) ), it will generate two functions vec_emplace_back_ui(unsigned int) and vec_emplace_back_si(int). These functions will take the (unsigned) int parameter, construct the object from it then push the result back on the array.
If the container is an associative array, the name will be constructed as follows:
name_emplace[_key_keysuffix][_val_valsuffix]
where keysuffix (resp. valsuffix) is the emplace suffix of the key (resp. value) oplist.
If you take once again the example of the FILE*, a more complete oplist can be:
typedef FILE *m_file_t;
#define M_OPL_m_file_t() (INIT_WITH(API_1(M_INIT_WITH_THROUGH_EMPLACE_TYPE)), \
SET(0),INIT_SET(0),CLEAR(fclose),TYPE(m_file_t), \
EMPLACE_TYPE(LIST((_str, API(fopen, ARG1, ARG2, ID("wb")), char *))))
The INIT_WITH operator will use the provided init methods in the EMPLACE_TYPE.
EMPLACE_TYPE defines a _str suffix method with a GAIA for fopen, and accepts a char* as argument.
The GAIA specifies that the output (ARG1) is set as return value,
ARG2 is given as the first argument, and a third constant argument is used.
M*LIB implements internally some controls to reduce the list of errors/warnings generated by a compiler when it detects some violation in the use of oplist by use of static assertion. It can also transform some type warnings into proper errors. In C99 mode, it will produce illegal code with the name of the error as attribute. In C11 mode, it will use static assert and produce a detailed error message.
The list of errors it can generate:
M_LIB_NOT_AN_OPLIST: something has been given (directly or indirectly) and it doesn't reduce as a proper oplist. You need to give an oplist for this definition.M_LIB_ERROR(ARGUMENT_OF_*_OPLIST_IS_NOT_AN_OPLIST, name, oplist): sub error of the previous error one, identifying the root cause. The error is in the oplist construction of the given macro. You need to give an oplist for this oplist construction.M_LIB_MISSING_METHOD: a required operator doesn't define any method in the given oplist. You need to complete the oplist with the missing method.M_LIB_TYPE_MISMATCH: the given oplist and the type do not match each other. You need to give the right oplist for this type.M_LIB_NOT_A_BASIC_TYPE: The oplist M_BASIC_OPLIST (directly or indirectly) has been used with the given type, but the given type is not a basic C type (int/float). You need to give the right oplist for this type.M_LIB_DIMENSION_ERROR: a macro expects a number of arguments and doesn't get it.Compilers can be very verbose on the error message:
You should focus mainly on the first reported error/warning
even if the link between what the compiler report and what the error is
is not immediate. The error is likely in one of the oplist definition.
Use of the flag -Wfatal-errors to stop on the first reported error.
Examples of typical errors:
NEW, DEL, INIT, OPLIST, ...),( ) or double level of ( ) around the oplist,BASIC_OPLIST instead of M_BASIC_OPLIST),name parameter given to the oplist is not the same as the one used to expand the methods,OPLIST definition (there is no registered type using M_OPL_ or the registered type doesn't match the name of the type),OPLIST definition.A good way to avoid these errors is to register the oplist of the type globally as soon as you define the container (to associated its oplist to the type).
In case of difficulties, debugging can be done by generating the preprocessed file
(by usually calling the compiler with the -E option instead of -c)
and check what's wrong in the preprocessed file:
cc -std=c99 -E test-file.c |grep -v '^#' > test-file.i
perl -i -e 's/;/;\n/g' test-file.i
cc -std=c99 -c -Wall test-file.i
Or you can use the cc.sh script in the doc folder instead of your Unix compiler
(it will automate theses steps, allowing you to see exactly the preprocessed code and
why the compiler reports an error).
You can define SUB_CC as an environement variable to define the sub compiler to
use for this script.
If you get the error "assignment to expression with array type", it means that the library
tries using the default '=' operator to set an object which is not compatible:
give the right method to the needed operator (usually INIT_MOVE or INIT_SET) in its oplist
or use the proper oplist of the type.
If there is a warning reported by the compiler in the generated code, then there is definitely an error you should fix (except if it reports shadowed variables), in particular cast evolving pointers.
You should also turn off the macro expansion of the errors reported by your compiler. There are often completely useless and misleading:
-ftrack-macro-expansion=0-fmacro-backtrace-limit=1Due to the unfortunate weak nature of the C language for pointers,
you should turn incompatible pointer type warning into an error in your compiler.
For GCC / CLANG, uses -Werror=incompatible-pointer-types or compile in C23 mode.
For MS Visual C++ compiler , you need the following options:
/Zc:__cplusplus /Zc:preprocessor /D__STDC_WANT_LIB_EXT1__ /EHsc
The M*LIB reference card is available here.
The generated containers tries to generate and provide a consistent interface: their methods would behave the same for all generated containers. This chapter will explain the common generated interface. In case of difference, it will be explained in the specific container.
In the following description:
name is the prefix used for the container generation,name_t refers to the type of the container,name_it_t refers to the iterator type of the container,type_t refers to the type of the object stored in the container,key_type_t refers to the type of the key object used to associate an element to,value_type_t refers to the type of the value object used to associate an element to.name_itref_t refers to a pair of key and value for associative arrays.An object shall be initialized (aka constructor) before being used by other methods. It shall be cleared (aka destructor) after being used and before program termination. An iterator has not destructor but shall be set before being used.
A container takes as input the
name — it is a mandatory argument that is the prefix used to generate all functions and types,type — it is a mandatory argument that the basic element of the container,oplist — it is an optional argument that defines the methods associated to the type. The provided oplist (if provided) shall be the one that is associated to the type, otherwise it won't generate compilable code. If there is no oplist parameter provided, a globally registered oplist associated to the type is used if possible, or the basic oplist for basic C types is used. This oplist will be used to handle internally the objects of the container.The type given to any templating macro can be either
an integer, a float, a boolean, an enum, a named structure, a named union, a pointer to such types,
or a typedef alias of any C type:
in fact, the only constraint is that the preprocessing concatenation between type and variable into
'type variable' shall be a valid C expression.
Therefore the type cannot be a C array or a function pointer
and you shall use a typedef as an intermediary named type for such types.
The output parameters are listed first, then the input/output parameters and finally the input parameters.
The oplist shall also provide the INIT_MOVE operator if the default instance (aka '=' operator) is not working for this type (for example for array of size 1, in which case the method M_COPY_A1OBJ is likely to work), or you need to disable the operator.
This common interface is specified as follow:
void name_init(name_t container)Initialize the container container (aka constructor) to an empty container.
Also called the default constructor of the container.
container shall be not initialized
void name_init_set(name_t container, const name_t ref)Initialize the container container (aka constructor) and set it to a copy of ref.
This method is only created if the INIT_SET & SET methods are provided.
Also called the copy constructor of the container.
container shall be not initialized
void name_set(name_t container, const name_t ref)Set the container container to the copy of ref.
This method is only created if the INIT_SET and SET methods are provided.
void name_init_move(name_t container, name_t ref)Initialize the container container (aka constructor)
by stealing as many resources from ref as possible.
After-wise ref is cleared and can no longer be used (aka destructor).
container shall be not initialized
void name_move(name_t container, name_t ref)Set the container container (aka constructor)
by stealing as many resources from ref as possible.
After-wise ref is cleared and can no longer be used (aka destructor).
container shall not be the same object as ref
void name_clear(name_t container)Clear the container container (aka destructor),
calling the CLEAR method of all the objects of the container and freeing memory.
The object can't be used anymore, except to be reinitialized with a constructor.
void name_reset(name_t container)Reset the container clearing and freeing all objects stored in it. The container becomes empty but remains initialized.
type_t *name_back(const name_t container)Return a pointer to the data stored in the back of the container.
This pointer should not be stored in a global variable.
container shall be not empty.
type_t *name_front(const name_t container)Return a pointer to the data stored in the front of the container.
This pointer should not be stored in a global variable.
container shall be not empty.
void name_push(name_t container, const type_t value)void name_push_back(name_t container, const type_t value)void name_push_front(name_t container, const type_t value)Push a new element in the container container as a copy of the object value.
This method is created only if the INIT_SET operator is provided.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
type_t *name_push_back_raw(name_t container)type_t *name_push_front_raw(name_t container)Push a new element in the container container
without initializing it and returns a borrowed pointer to the non-initialized data.
The first thing to do after calling this function shall be to initialize the data
using the proper constructor of the object of type type_t.
This enables using more specialized constructor than the generic copy one.
The user should use other _push functions if possible rather than this one
as it is low level and error prone.
This pointer should not be stored in a global variable.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
type_t *name_push_new(name_t container)type_t *name_push_back_new(name_t container)type_t *name_push_front_new(name_t container)Push a new element in the container container
and initialize it with the default constructor associated to the type type_t.
Return a borrowed pointer to the initialized object.
This pointer should not be stored in a global variable.
This method is only created if the INIT method is provided.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
void name_push_move(name_t container, type_t *value)void name_push_back_move(name_t container, type_t *value)void name_push_front_move(name_t container, type_t *value)Push a new element in the container container
as a move from the object *value:
it will therefore steal as much resources from *value as possible.
Afterward *value is cleared and cannot longer be used (aka. destructor).
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
void name_emplace[suffix](name_t container, args...)void name_emplace_back[suffix](name_t container, args...)void name_emplace_front[suffix](name_t container, args...)Push a new element in the container container
by initializing it with the provided arguments.
The provided arguments shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator.
There is one generated method per suffix defined in the EMPLACE_TYPE operator,
and the suffix in the generated method name corresponds to the suffix defined
in the EMPLACE_TYPE operator (it can be empty).
This method is created only if the EMPLACE_TYPE operator is provided.
See emplace chapter for more details.
The _back suffixed method will push it in the back of the container.
The _front suffixed method will push it in the front of the container.
void name_pop(type_t *data, name_t container)void name_pop_back(type_t *data, name_t container)void name_pop_front(type_t *data, name_t container)Pop a element from the container container;
and set *data to this value if data is not the NULL pointer,
otherwise it only pops the data.
This method is created if the SET or INIT_MOVE operator is provided.
The _back suffixed method will pop it from the back of the container.
The _front suffixed method will pop it from the front of the container.
void name_pop_move(type_t *data, name_t container)void name_pop_move_back(type_t *data, name_t container)void name_pop_move_front(type_t *data, name_t container)Pop a element from the container container
and initialize and set *data to this value (aka. constructor)
by stealing as much resources from the container as possible.
data shall not be a NULL pointer.
The _back suffixed method will pop it from the back of the container.
The _front suffixed method will pop it from the front of the container.
bool name_empty_p(const name_t container)Return true if the container is empty, false otherwise.
void name_swap(name_t container1, name_t container2)Swap the container container1 and container2.
void name_set_at(name_t container, size_t key, type_t value)void name_set_at(name_t container, key_type_t key, value_type_t value) [for associative array]Set the element associated to key of the container container to value.
If the container is sequence-like (like array), the key is an integer.
The selected element is the key-th element of the container,
The index key shall be within the size of the container.
This method is created if the INIT_SET operator is provided.
If the container is associative-array like,
the selected element is the value object associated to the key object in the container.
It is created if it doesn't exist, overwritten otherwise.
void name_emplace_key[keysuffix](name_t container, keyargs..., value_type_t value) [for associative array]void name_emplace_val[valsuffix](name_t container, key_type_t key, valargs...) [for associative array]void name_emplace_key[keysuffix]_val[valsuffix](name_t container, keyargs..., valargs...) [for associative array]Set the element associated to key of the container container to value.
key (resp. value) is constructed from the provided args keyargs (resp. valargs) if not provided.
keyargs (resp. valargs) shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator of the key (resp. the value).
There is:
EMPLACE_TYPE operator of the key,EMPLACE_TYPE operator of the value,EMPLACE_TYPE operators of the key and value,The suffix in the generated method name corresponds to the suffix defined in
in the EMPLACE_TYPE operator (it can be empty).
This method is created only if one EMPLACE_TYPE operator is provided.
See emplace chapter for more details.
type_t *name_get(const name_t container, size_t key) [for sequence-like]const type_t *name_cget(const name_t container, size_t key) [for sequence-like]type_t *name_get(const name_t container, const type_t key) [for set-like]const type_t *name_cget(const name_t container, const type_t key) [for set-like]value_type_t *name_get(const name_t container, const key_type_t key) [for associative array]const value_type_t *name_cget(const name_t container, const key_type_t key) [for associative array]Return a modifiable (resp. constant) borrowed pointer to
the element associated to key in the container.
If the container is sequence-like, the key is an integer.
The selected element is the key-th element of the container,
the front being at the index 0, the last at the index (size-1).
The index key shall be within the size of the container.
Therefore, it will never return NULL in this case.
If the container is associative array like,
the selected element is the value object associated to the key object in the container.
If the key is not found, it returns NULL.
If the container is set-like,
the selected element is the value object which is equal to the key object in the container.
If the key is not found, it returns NULL.
This pointer remains valid until the container is modified by another method. This pointer should not be stored in a global variable.
type_t *name_get_emplace[suffix](const name_t container, args...) [for set-like]value_type_t * name_get_emplace[suffix](name_t container, args...) [for associative array]Return a modifiable (resp. constant) borrowed pointer to
the element associated to the key constructed from args in the container.
The selected element is the value object associated to the key object in the container
for an associative array, or the element itself for a set.
If the key is not found, it returns NULL.
This pointer remains valid until the container is modified by another method. This pointer should not be stored in a global variable.
type_t *name_safe_get(name_t container, size_t key) [for sequence]type_t *name_safe_get(name_t container, const type_t key) [for set]value_type_t *name_safe_get(name_t container, const key_type_t key) [for associative array]Return a modifiable borrowed pointer to
the element associated to key in the container,
creating a new element if it doesn't exist (ensuring therefore a safe get operation).
If the container is sequence-like, key_type_t is an alias for size_t and key an integer,
the selected element is the key-th element of the container.
If the element doesn't exist, the container size will be increased
if needed (creating new elements with the INIT operator),
which might increase the container to much in some cases.
The returned pointer cannot be NULL.
This method is only created if the INIT method is provided.
This pointer remains valid until the array is modified by another method.
This pointer should not be stored in a global variable.
bool name_erase(name_t container, const size_t key)bool name_erase(name_t container, const type_t key) [for set]bool name_erase(name_t container, const key_type_t key) [for associative array]Remove the element referenced by the key key in the container container.
Do nothing if key is no present in the container.
Return true if the key was present and erased, false otherwise.
size_t name_size(const name_t container)Return the number elements of the container (its size). Return 0 if there is no element.
size_t name_capacity(const name_t container)Return the capacity of the container, i.e. the maximum number of elements supported by the container before a reserve operation is needed to accommodate new elements.
void name_resize(name_t container, size_t size)Resize the container container to the size size,
increasing or decreasing the size of the container
by initializing new elements or clearing existing ones.
This method is only created if the INIT method is provided.
void name_reserve(name_t container, size_t capacity)Extend or reduce the capacity of the container to a rounded value based on capacity.
If the given capacity is below the current size of the container,
the capacity is set to a rounded value based on the size of the container.
Therefore a capacity of 0 is used to perform a shrink-to-fit operation on the container,
i.e. reducing the container usage to the minimum possible allocation.
void name_it(name_it_t it, const name_t container)Set the iterator it to the first element of the container container.
There is no destructor associated to this initialization.
void name_it_set(name_it_t it, const name_it_t ref)Set the iterator it to the iterator ref.
There is no destructor associated to this initialization.
void name_it_end(name_it_t it, const name_t container)Set the iterator it to a non valid element of the container.
There is no destructor associated to this initialization.
void name_it_last(name_it_t it, const name_t container)Set the iterator it to the last element of the container.
There is no destructor associated to this initialization.
bool name_end_p(const name_it_t it)Return true if the iterator doesn't reference a valid element anymore.
bool name_last_p(const name_it_t it)Return true if the iterator references the last element of the container or if the iterator doesn't reference a valid element anymore.
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)Return true if the iterator it1 references the same element than the iterator it2.
void name_next(name_it_t it)Move the iterator to the next element of the container. Afterwards, the moved iterator may reference an invalid element.
void name_previous(name_it_t it)Move the iterator it to the previous element of the container.
Afterwards, the moved iterator may reference an invalid element.
type_t *name_ref(name_it_t it)const type_t *name_cref(const name_it_t it)name_itref_t *name_ref(name_it_t it) [for associative array]const name_itref_t *name_cref(name_it_t it) [for associative array]Return a modifiable (resp. constant) borrowed pointer to the element pointed by the iterator.
For associative-array like container, this element is the pair composed of
the key (key field) and the associated value (value field);
otherwise this element is simply the basic type of the container (type_t).
The iterator shall reference a valid element. This pointer should not be stored in a global variable. This pointer remains valid until the container is modified by another method.
void name_insert(name_t container, const name_it_t it, const type_t x)Insert the object x after the position referenced by the iterator it in the container container
or if the iterator it doesn't reference anymore to a valid element of the container,
it is added as the first element of the container.
it shall be an iterator of the container container.
void name_remove(name_t container, name_it_t it)Remove the element referenced by the iterator it from the container container.
it shall be an iterator of the container container.
Afterwards, it references the next element of the container if it exists,
or not a valid element otherwise.
bool name_equal_p(const name_t container1, const name_t container2)Return true if both containers container1 and container2 are considered equal.
This method is only created if the EQUAL method is provided.
size_t name_hash(const name_t container)Return a fast hash value of the container container,
suitable to be used by a dictionary.
This method is only created if the HASH method is provided.
void name_get_str(string_t str, const name_t container, bool append)Set str to the formatted string representation of the container container if append is false
or append str with this representation if append is true.
This method is only created if the GET_STR method is provided.
bool name_parse_str(name_t container, const char str[], const char **endp)Parse the formatted string str,
that is assumed to be a string representation of a container,
and set container to this representation.
It returns true if success, false otherwise.
If endp is not NULL, it sets *endp to the pointer of the first character not
decoded by the function (or where the parsing fails).
This method is only created if the PARSE_STR & INIT methods are provided.
It is ensured that the container gets from parsing a formatted string representation
gets from name_get_str and the original container are equal.
void name_out_str(FILE *file, const name_t container)Generate a formatted string representation of the container container
and outputs it into the file FILE*.
The file FILE* shall be opened in write text mode and without error.
This method is only created if the OUT_STR methods is provided.
bool name_in_str(name_t container, FILE *file)Read from the file FILE* a formatted string representation of a container
and set container to this representation.
It returns true if success, false otherwise.
This method is only created if the IN_STR & INIT methods are provided.
It is ensured that the container gets from parsing a formatted string representation gets from name_out_str and the original container are equal.
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)Output the container container into the serializing object serial.
How and where it is output depends on the serializing object.
It returns M_SERIAL_OK_DONE in case of success,
or M_SERIAL_FAILURE in case of failure.
In case of failure, the serializing object is in an unspecified but valid state.
This method is only created if the OUT_SERIAL methods is provided.
m_serial_return_code_t name_in_serial(name_t container, m_serial_read_t serial)Read from the serializing object serial a representation of a container
and set container to this representation.
It returns M_SERIAL_OK_DONE in case of success,
or M_SERIAL_FAILURE in case of failure.
In case of failure, the serializing object is in an unspecified but valid state.
This method is only created if the IN_SERIAL & INIT methods are provided.
It is ensured that the container gets from parsing a representation gets from name_out_serial and the original container are equal (using the same type of serialization object).
This header is for creating singly linked list.
A linked list is a linear collection of elements, in which each element points to the next, all of then representing a sequence.
A fundamental property of a list is that the objects created within the list will remain at their initialized address, and won't moved due to operations done on the list (except if it is removed). Therefore a returned pointer to an element of the container remains valid until this element is destroyed in the container.
LIST_DEF(name, type [, oplist])LIST_DEF_AS(name, name_t, name_it_t, type [, oplist])LIST_DEF defines the singly linked list named name_t
that contains objects of type type and their associated methods as static inline functions.
name shall be a C identifier that will be used to identify the list.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
For this container, the back is always the first element, and the front is the last element: the list grows from the back. Therefore, the iteration of this container using iterator objects will go from the back element to the front element (contrary to an array).
Even if it provides random access functions, theses access are slow and should be avoided: it iterates linearly over all the elements of the container until it reaches the requested element. The size method has the same drawback.
The push/pop methods of the container always operate on the back of the container.
LIST_DEF_AS is the same as LIST_DEF
except the name of the types name_t, name_it_t are provided by the user,
and not computed from the name prefix.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-list.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
LIST_DEF(list_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), \
CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ), OUT_STR(MPZ_OUT_STR)))
int main(void) {
list_mpz_t a;
list_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
list_mpz_push_back (a, x);
mpz_set_ui(x, 45);
list_mpz_push_back (a, x);
mpz_clear(x);
printf ("LIST is: ");
list_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *list_mpz_back(a));
printf ("\n");
list_mpz_clear(a);
}
LIST_OPLIST(name [, oplist])Return the oplist of the list defined by calling LIST_DEF and LIST_DUALB_DEF with name & oplist.
The list behaves list a stack (First In, Last Out).
If there is no given oplist, the basic oplist for basic C types is used.
There is no globally registered oplist support.
LIST_DUALF_OPLIST(name [, oplist])Return the oplist of the list defined by calling LIST_DUALF_DEF with name & oplist.
The list behaves list a fifo (First In, First Out).
If there is no given oplist, the basic oplist for basic C types is used.
There is no globally registered oplist support.
LIST_INIT_VALUE()Define an initial value that is suitable to initialize global variable(s)
of type list as created by LIST_DEF or LIST_DEF_AS.
It enables to create a list as a global variable and to initialize it.
The list shall still be cleared manually to avoid leaking memory.
Example:
LIST_DEF(list_int, int)
list_int_t my_list = LIST_INIT_VALUE();
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the list of type objects.
name_it_tType of an iterator over this list.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t list)
void name_init_set(name_t list, const name_t ref)
void name_set(name_t list, const name_t ref)
void name_init_move(name_t list, name_t ref)
void name_move(name_t list, name_t ref)
void name_clear(name_t list)
void name_reset(name_t list)
type *name_back(const name_t list)
void name_push_back(name_t list, const type value)
type *name_push_back_raw(name_t list)
type *name_push_new(name_t list)
void name_push_move(name_t list, type *value)
void name_emplace_back[suffix](name_t list, args...)
void name_pop_back(type *data, name_t list)
void name_pop_move(type *data, name_t list)
bool name_empty_p(const name_t list)
void name_swap(name_t list1, name_t list2)
void name_it(name_it_t it, const name_t list)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, const name_t list)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
type *name_get(const name_t list, size_t i)
const type *name_cget(const name_t list, size_t i)
size_t name_size(const name_t list)
void name_insert(name_t list, const name_it_t it, const type x)
void name_remove(name_t list, name_it_t it)
void name_get_str(string_t str, const name_t list, bool append)
bool name_parse_str(name_t list, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t list)
bool name_in_str(name_t list, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t list1, const name_t list2)
size_t name_hash(const name_t list)
The following specialized methods are automatically created by the previous definition macro:
void name_splice_back(name_t list1, name_t list2, name_it_t it)Move the element referenced by the iterator it
from the list list2 to the back position of the list list1.
it shall be an iterator of list2.
Afterwards, it references the next element of the list if it exists,
or not a valid element otherwise.
void name_splice_at(name_t list1, name_it_t it1, name_t list2, name_it_t it2)Move the element referenced by the iterator it2 from the list list2
to the position just after it1 in the list list1.
(If it1 is not a valid position, it inserts it at the back just like name_insert).
it1 shall be an iterator of list1.
it2 shall be an iterator of list2.
Afterwards, it2 references the next element of the list if it exists,
or not a valid element otherwise,
and it1 references the inserted element in list1.
void name_splice(name_t list1, name_t list2)Move all the element of the list list2 into the list list1,
moving the last element of list2 after the first element of list1.
Afterwards, list2 remains initialized but is emptied.
list1 and list2 shall reference different objects.
void name_reverse(name_t list)Reverse the order of the list.
LIST_DUALB_DEF(name, type[, oplist])LIST_DUALB_DEF_AS(name, name_t, name_it_t, type [, oplist])LIST_DUALB_DEF defines the singly linked list named name_t
that contains the objects of type type and their associated methods as static inline functions.
The only difference with the list defined by LIST_DEF is
the support of the method for PUSH_FRONT in addition to the one for PUSH_BACK
(therefore both BI Pushes and the pop Back methods are provided - so the BIB name).
However, there is still only POP method (associated to POP_BACK).
The list is a bit bigger to be able to handle such method to work, but not the nodes.
This list is therefore able to represent:
PUSH_BACK + POP_BACK) - which is the default -PUSH_FRONT + POP_BACK).LIST_DUALB_DEF_AS is the same as LIST_DUALB_DEF except the name of the types name_t, name_it_t are provided by the user.
See LIST_DEF for more details and constraints.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-list.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
LIST_DUALB_DEF(list_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), \
CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ), OUT_STR(MPZ_OUT_STR)))
int main(void) {
list_mpz_t a;
list_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
list_mpz_push_back (a, x);
mpz_set_ui(x, 45);
list_mpz_push_back (a, x);
mpz_clear(x);
printf ("LIST is: ");
list_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *list_mpz_back(a));
printf ("\n");
list_mpz_clear(a);
}
The methods follow closely the methods defined by LIST_DEF.
LIST_DUALF_DEF(name, type[, oplist])LIST_DUALF_DEF_AS(name, name_t, name_it_t, type [, oplist])LIST_DUALF_DEF defines the singly linked list named name_t
that contains the objects of type type and their associated methods as static inline functions.
The only difference with the list defined by LIST_DUALB_DEF is POP_BACK is replaced by POP_FRONT.
(therefore both BI Pushes and the pop Forward methods are provided - so the BIF name)
and the list first element is the front, and the last element is the back.
The list is a bit bigger to be able to handle such method to work, but not the nodes.
This list is therefore able to represent:
PUSH_FRONT + POP_FRONT)PUSH_BACK + POP_FRONT) - which is the default -.LIST_DUALF_DEF_AS is the same as LIST_DUALF_DEF except the name of the types name_t, name_it_t are provided by the user.
See LIST_DEF for more details and constraints.
The methods follow closely the methods defined by LIST_DEF.
LIST_DUAL_PUSH_INIT_VALUE()Define an initial value that is suitable to initialize global variable(s)
of type list as created by LIST_DUALB_DEF or LIST_DUALB_DEF_AS or LIST_DUALF_DEF or LIST_DUALF_DEF_AS.
It enables to create a list as a global variable and to initialize it.
The list should still be cleared manually to avoid leaking memory.
Example:
LIST_DUALB_DEF(list_int, int)
list_int_t my_list = LIST_DUAL_PUSH_INIT_VALUE();
The following types are automatically defined by the previous definition macros if not provided by the user:
name_tType of the list of type.
name_it_tType of an iterator over this list.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t list)
void name_init_set(name_t list, const name_t ref)
void name_set(name_t list, const name_t ref)
void name_init_move(name_t list, name_t ref)
void name_move(name_t list, name_t ref)
void name_clear(name_t list)
void name_reset(name_t list)
type *name_back(const name_t list)
void name_push_back(name_t list, type value)
type *name_push_back_raw(name_t list)
type *name_push_back_new(name_t list)
void name_push_back_move(name_t list, type *value)
void name_emplace_back[suffix](name_t list, args...)
const type *name_front(const name_t list)
void name_push_front(name_t list, type value)
type *name_push_front_raw(name_t list)
type *name_push_front_new(name_t list)
void name_push_front_move(name_t list, type *value)
void name_emplace_front[suffix](name_t list, args...)
void name_pop_back(type *data, name_t list) /* For BIB list */
void name_pop_front(type *data, name_t list) /* For BIF list */
void name_pop_move(type *data, name_t list)
bool name_empty_p(const name_t list)
void name_swap(name_t list1, name_t list2)
void name_it(name_it_t it, name_t list)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, const name_t list)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
size_t name_size(const name_t list)
void name_insert(name_t list, const name_it_t it, const type x)
void name_remove(name_t list, name_it_t it)
void name_get_str(string_t str, const name_t list, bool append)
bool name_parse_str(name_t list, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t list)
bool name_in_str(name_t list, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t list1, const name_t list2)
size_t name_hash(const name_t list)
The following specialized methods are automatically created by the previous definition macro:
void name_splice_back(name_t list1, name_t list2, name_it_t it) /* for BIB list */void name_splice_front(name_t list1, name_t list2, name_it_t it) /* for BIF list */Move the element pointed by it
from the list list2 to the back position of the list list1.
it shall be an iterator of list2.
Afterwards, it points to the next element of list2.
void name_splice(name_t list1, name_t list2)Move all the element of the list list2 into the list list1,
moving the last element of list2 after the first element of list1.
Afterwards, list2 is emptied.
list1 and list2 shall reference different objects.
void name_reverse(name_t list)Reverse the order of the list.
An array is a growable collection of element that are individually indexable.
ARRAY_DEF(name, type [, oplist])ARRAY_DEF_AS(name, name_t, name_it_t, type [, oplist])ARRAY_DEF defines the array name_t that contains the objects of type type
in a sequence
and its associated methods as static inline functions.
Compared to C arrays, the created methods handle automatically the size (aka growable array).
name shall be a C identifier that will be used to identify the container.
It will be used to create all the types (including the iterator)
and functions to handle the container.
The provided oplist shall have at least the following operators (CLEAR).
It should also provide the following operators (INIT, INIT_SET, SET),
so that at least some methods are defined for the array!
The object of type type shall be trivially movable.
The push / pop methods of the container always operate on the back of the container, acting like a stack-like container.
ARRAY_DEF_AS is the same as ARRAY_DEF except the name of the types name_t, name_it_t
are provided by the user.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
ARRAY_DEF(array_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), \
CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ), OUT_STR(MPZ_OUT_STR)))
int main(void) {
array_mpz_t a;
array_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
array_mpz_push_back (a, x);
mpz_set_ui(x, 45);
array_mpz_push_back (a, x);
mpz_clear(x);
printf ("ARRAY is: ");
array_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *array_mpz_get(a, 0));
printf ("\n");
array_mpz_clear(a);
}
ARRAY_OPLIST(name [, oplist])Return the oplist of the array defined by calling ARRAY_DEF with name & oplist.
If there is no given oplist, the basic oplist for basic C types is used.
ARRAY_INIT_VALUE()Define an initial value that is suitable to initialize global variable(s)
of type array as created by ARRAY_DEF or ARRAY_DEF_AS.
It enables to create an array as a global variable and to initialize it.
The array should still be cleared manually to avoid leaking memory.
Example:
ARRAY_DEF(array_int_t, int)
array_int_t my_array = ARRAY_INIT_VALUE();
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the array of type.
name_it_tType of an iterator over this array.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t array)
void name_init_set(name_t array, const name_t ref)
void name_set(name_t array, const name_t ref)
void name_init_move(name_t array, name_t ref)
void name_move(name_t array, name_t ref)
void name_clear(name_t array)
void name_reset(name_t array)
type *name_push_back_raw(name_t array)
void name_push_back(name_t array, const type value)
type *name_push_new(name_t array)
void name_push_move(name_t array, type *val)
void name_emplace_back[suffix](name_t array, args...)
void name_pop_back(type *data, name_t array)
void name_pop_move(type *data, name_t array)
type *name_front(const name_t array)
type *name_back(const name_t array)
void name_set_at(name_t array, size_t i, type value)
type *name_get(name_t array, size_t i)
const type *name_cget(const name_t it, size_t i)
type *name_safe_get(name_t array, size_t i)
bool name_empty_p(const name_t array)
size_t name_size(const name_t array)
size_t name_capacity(const name_t array)
void name_resize(name_t array, size_t size)
void name_reserve(name_t array, size_t capacity)
void name_swap(name_t array1, name_t array2)
void name_it(name_it_t it, name_t array)
void name_it_last(name_it_t it, name_t array)
void name_it_end(name_it_t it, name_t array)
void name_it_set(name_it_t it1, name_it_t it2)
bool name_end_p(name_it_t it)
bool name_last_p(name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
void name_previous(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
void name_remove(name_t array, name_it_t it)
void name_insert(name_t array, name_it_t it, const type x)
void name_get_str(string_t str, const name_t array, bool append)
bool name_parse_str(name_t array, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t array)
bool name_in_str(name_t array, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t array1, const name_t array2)
size_t name_hash(const name_t array)
The following specialized methods are automatically created by the previous definition macro:
void name_push_at(name_t array, size_t key, const type x)Push a new element into the position key of the array array
with the value value.
All elements after the position key (included) will be moved in the array towards the back,
and the array will have one more element.
key shall be a valid position of the array: from 0 to the size of array (included).
This method is created only if the INIT_SET operator is provided.
void name_pop_until(name_t array, array_it_t position)Pop all elements of the array array from 'position' to the back of the array,
while clearing them.
This method is created only if the INIT operator is provided.
void name_pop_at(type *dest, name_t array, size_t key)Set *dest to the value the element key if dest is not NULL,
then remove the element key from the array (decreasing the array size).
key shall be within the size of the array.
This method is created only if the SET or INIT_MOVE operator is provided.
void name_remove_v(name_t array, size_t i, size_t j)Remove the element i (included) to the element j (excluded)
from the array.
i and j shall be within the size of the array, and i < j.
void name_insert_v(name_t array, size_t i, size_t num)Insert from the element i (included) num new empty elements to the array.
i shall be within the size of the array.
This method is only defined if the type of the element defines an INIT method.
void name_insert_n(name_t array, size_t i, size_t num, type array_value[num])Insert from the element i (included) num new elements to the array initialized to the values of the array array_value.
i shall be within the size of the array.
void name_swap_at(name_t array, size_t i, size_t j)Swap the elements i and j of the array array.
i and j shall reference valid elements of the array.
This method is created if the INIT_SET or INIT_MOVE operator is provided.
void name_special_sort(name_t array, int (*func_type) (type const *a, type const *b))Sort the array array.
This method uses the qsort function of the C library using func_type.
void name_special_stable_sort(name_t array)Sort the array array using a stable sort.
This method is defined if the type of the element defines CMP and SWAP and SET methods.
This method provides an ad-hoc implementation of the stable sort.
In practice, it is faster than the _sort method for small types and fast
comparisons.
void name_splice(name_t array1, name_t array2)Move all the elements of the array array2 to the end of the array array1.
Afterwards, array2 is empty.
array1 and array2 shall reference different objects.
This header is for creating double-ended queue (or deque). A deque is an abstract data type that generalizes a queue, for that elements can be added to or removed from either the front (head) or back (tail)
DEQUE_DEF(name, type [, oplist])DEQUE_DEF_AS(name, name_t, name_it_t, type [, oplist])DEQUE_DEF defines the deque name_t that contains the objects of type type and its associated methods as static inline functions.
name shall be a C identifier that will be used to identify the deque.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The oplist shall have at least the following operators (INIT, INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The algorithm complexity to access random elements is in O(ln(n)). Removing an element may unbalance the deque, which breaks the promise of algorithm complexity for the _get method.
DEQUE_DEF_AS is the same as DEQUE_DEF
except the name of the types name_t, name_it_t are provided.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-deque.h"
DEQUE_DEF(deque_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), INIT_MOVE(M_COPY_A1OBJ)))
int main(void) {
deque_mpz_t a;
deque_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
deque_mpz_push_back (a, x);
mpz_set_ui(x, 45);
deque_mpz_push_front (a, x);
deque_mpz_pop_back(&x, a);
mpz_set_ui(x, 5);
deque_mpz_push_back (a, x);
mpz_clear(x);
printf ("First element is: ");
mpz_out_str(stdout, 0, *deque_mpz_front(a));
printf ("\n");
printf ("Last element is: ");
mpz_out_str(stdout, 0, *deque_mpz_back(a));
printf ("\n");
deque_mpz_clear(a);
}
DEQUE_OPLIST(name [, oplist])Return the oplist of the deque defined by calling DEQUE_DEF with name oplist.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the deque of type.
name_it_tType of an iterator over this deque.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t deque)
void name_init_set(name_t deque, const name_t ref) /* If INIT_SET operator is defined */
void name_set(name_t deque, const name_t ref) /* If INIT_SET operator is defined */
void name_init_move(name_t deque, name_t ref)
void name_move(name_t deque, name_t ref)
void name_clear(name_t deque)
void name_reset(name_t deque)
type *name_back(const name_t deque)
void name_push_back(name_t deque, type value) /* If INIT_SET operator is defined */
type *name_push_back_raw(name_t deque)
type *name_push_back_new(name_t deque)
void name_emplace_back[suffix](name_t list, args...)
void name_pop_back(type *data, name_t deque)
type *name_front(const name_t deque)
void name_push_front(name_t deque, type value) /* If INIT_SET operator is defined */
type *name_push_front_raw(name_t deque)
type *name_push_front_new(name_t deque)
void name_emplace_front[suffix](name_t list, args...)
void name_pop_front(type *data, name_t deque)
bool name_empty_p(const name_t deque)
void name_swap(name_t deque1, name_t deque2)
void name_it(name_it_t it, name_t deque)
void name_it_set(name_it_t it, const name_it_t ref)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
void name_previous(name_it_t it)
type *name_ref(name_it_t it)
const type *name_cref(const name_it_t it)
void name_remove(name_t deque, name_it_t it)
type *name_get(const name_t deque, size_t i)
const type *name_cget(const name_t deque, size_t i)
void name_set_at(name_t deque, size_t i, type const value) /* If SET operator is defined */
size_t name_size(const name_t deque)
void name_get_str(string_t str, const name_t deque, bool append)
bool name_parse_str(name_t deque, const char str[], const char **endp) /* If INIT, INIT_SET, PARSE_STR operator are defined */
void name_out_str(FILE *file, const name_t deque)
bool name_in_str(name_t deque, FILE *file) /* If INIT, INIT_SET, PARSE_STR operator are defined */
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial) /* If INIT, INIT_SET, PARSE_STR operator are defined */
bool name_equal_p(const name_t deque1, const name_t deque2)
size_t name_hash(const name_t deque)
void name_swap_at(name_t deque, size_t i, size_t j)
A dictionary (or associative array, map, symbol table) is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection, and is associated to only one value. It is possible to search for a key in the dictionary and get back its value.
Several dictionaries are proposed. The "best" to use depends on the data type
and in particular the size of the data.
For very small, fast types (integer, or floats, or pair of such types),
DICT_OA_DEF2 may be the best to use (but slightly more complex to instantiate).
However DICT_DEF2 should be good enough for all scenarios.
DICT_DEF2(name, key_type[, key_oplist], value_type[, value_oplist])DICT_DEF2_AS(name, name_t, name_it_t, name_itref_t, key_type[, key_oplist], value_type[, value_oplist])DICT_DEF2 defines the dictionary name_t and its associated methods as static inline functions as an associative array of key_type to value_type.
name shall be a C identifier that will be used to identify the dictionary.
It will be used to create all the types (including the iterator and the iterated object type)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
Both oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The key_oplist shall also define the additional operators (HASH and EQUAL).
[!NOTE] You can either call this macro with only
key_typeandvalue_typeor with their type+oplistskey_type,key_oplist,value_typeandvalue_oplist. You cannot call it with an oplist for a type and not for the other (Otherwise it won't be able to identify reliably what is the third argument - avalue_typeor akey_oplist?) Failure to respect this rule so will result in a too few argument error forM_D1CT_DEF2_P2internal macro.
Elements in the dictionary are unordered. On insertion of a new element, contained objects may moved. Maximum number of elements of this dictionary is 3'006'477'107 elements.
The _set_at method overwrites the already existing value if key is already present in the dictionary
(contrary to C++).
The iterated object type name##_itref_t is a pair of key_type and value_type.
What is exactly the "first" element for the iteration is not specified. It is only ensured that all elements of the dictionary are explored by going from "first" to "end".
DICT_DEF2_AS is the same as DICT_DEF2
except the name of the types name_t, name_it_t, name_itref_t are provided.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-dict.h"
DICT_DEF2(dict_string, string_t, unsigned)
int main(void) {
dict_string_t a;
dict_string_init(a);
string_t x;
string_init_set_str(x, "This is an example");
dict_string_set_at (a, x, 1);
string_set_str(x, "This is an another example");
dict_string_set_at (a, x, 2);
string_set_str(x, "This is an example");
unsigned *val = dict_string_get(a, x);
printf ("Value of %s is %u\n", string_get_cstr(x), *val);
string_clear(x);
printf ("Dictionary is: ");
dict_string_out_str(stdout, a);
printf ("\n");
dict_string_clear(a);
}
DICT_OA_DEF2(name, key_type[, key_oplist], value_type[, value_oplist])DICT_OA_DEF2_AS(name, name_t, name_it_t, name_itref_t, key_type[, key_oplist], value_type[, value_oplist])DICT_OA_DEF2 defines the dictionary name_t and its associated methods
as static inline functions much like DICT_DEF2.
The difference is that it uses an Open Addressing Hash-Table as container
that stores the data with the table.
The key_oplist shall also define the additional operators:
OOR_EQUAL and OOR_SET
The Out-Of-Range operators (OOR_EQUAL and OOR_SET) are used to store uninitialized keys
in the dictionary and be able to detect it. This enables avoiding a separate bit-field
to know the state of the entry in the dictionary (which increases memory
usage and is cache unfriendly).
The elements may move when inserting / deleting other elements (and not just the iterators).
This implementation is in general faster for small types of keys (like integer or float) but are slower for larger types.
[!NOTE] You can either call this macro with only
key_typeandvalue_typeor with their type+oplistskey_type,key_oplist,value_typeandvalue_oplist. You cannot call it with an oplist for a type and not for the other (Otherwise it won't be able to identify reliably what is the third argument - avalue_typeor akey_oplist?) Failure to respect this rule so will result in a too few argument error forM_D1CT_DEF2_P2internal macro.
DICT_OA_DEF2_AS is the same as DICT_OA_DEF2
except the name of the types name_t, name_it_t, name_itref_t are provided.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-dict.h"
// Define an Out Of Range equal function
static inline bool oor_equal_p(unsigned k, unsigned char n) {
return k == (unsigned)(-n-1);
}
// Define an Out Of Range function
static inline void oor_set(unsigned *k, unsigned char n) {
*k = (unsigned)(-n-1);
}
DICT_OA_DEF2(dict_unsigned, unsigned, M_OPEXTEND(M_BASIC_OPLIST,
OOR_EQUAL(oor_equal_p), OOR_SET(API_2(oor_set))), long long, M_BASIC_OPLIST)
unsigned main(void) {
dict_unsigned_t a;
dict_unsigned_init(a);
dict_unsigned_set_at (a, 13566, 14890943049);
dict_unsigned_set_at (a, 656, -2);
long long *val = dict_unsigned_get(a, 458);
printf ("Value of %d is %p\n", 458, val); // Not found value
val = dict_unsigned_get(a, 656);
printf ("Value of %d is %lld\n", 656, *val);
dict_unsigned_clear(a);
}
DICT_OPLIST(name[, key_oplist, value_oplist])Return the oplist of the dictionary defined by calling any DICT_*_DEF2 with name, key_oplist, value_oplist.
DICT_SET_DEF(name, key_type[, key_oplist])DICT_SET_DEF_AS(name, name_t, name_it_t, key_type[, key_oplist])DICT_SET_DEF defines the dictionary set name_t and its associated methods as static inline functions.
A dictionary set is a specialized version of a dictionary with no value (only keys).
name shall be a C identifier that will be used to identify the dictionary.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The oplist shall have at least the following operators (INIT_SET, SET, CLEAR, HASH and EQUAL),
otherwise it won't generate compilable code.
The _push method will overwrite the already existing value if key is already present in the dictionary (contrary to C++).
What is exactly the "first" element for the iteration is not specified. It is only ensured that all elements of the dictionary are explored by going from "first" to "end".
DICT_SET_DEF_AS is the same as DICT_SET_DEF
except the name of the types name_t, name_it_t are provided.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-dict.h"
DICT_SET_DEF(set_string, double)
unsigned main(void) {
set_string_t a;
set_string_init(a);
set_string_push (a, 13566);
set_string_push (a, 656);
double *val = set_string_get(a, 458);
printf ("Value of %d is %p\n", 458, val); // Not found value
val = set_string_get(a, 656);
printf ("Value of %d is %f\n", 656, *val);
printf("Set is ");
set_string_out_str(stdout, a);
printf("\n");
set_string_clear(a);
}
DICT_OASET_DEF(name, key_type[, key_oplist])DICT_OASET_DEF_AS(name, name_t, name_it_t, key_type[, key_oplist])DICT_OASET_DEF defines the dictionary set name_t and its associated methods as static inline functions just like DICT_SET_DEF.
The difference is that it uses an Open Addressing Hash-Table as container.
The key_oplist shall also define the additional operators:
OOR_EQUAL and OOR_SET
The elements may move when inserting / deleting other elements (and not just the iterators).
This implementation is in general faster for small types of keys (like integer) but slower for larger types.
DICT_OASET_DEF_AS is the same as DICT_OASET_DEF
except the name of the types name_t, name_it_t are provided.
DICT_SET_OPLIST(name[, key_oplist])Return the oplist of the set defined by calling DICT_SET_DEF (or DICT_OASET_DEF) with name and key_oplist.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the dictionary which
key_type to value_type,key_type.name_it_tType of an iterator over this dictionary.
name_itref_t [only for associative array]Type of one item referenced in the dictionary for associative array.
It is a structure composed of the key (field key) and the value (field value).
This type is created only for associative arrays (_DEF2 suffix) and not for sets.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t dict)
void name_clear(name_t dict)
void name_init_set(name_t dict, const name_t ref)
void name_set(name_t dict, const name_t ref)
void name_init_move(name_t dict, name_t ref)
void name_move(name_t dict, name_t ref)
void name_reset(name_t dict)
size_t name_size(const name_t dict)
bool name_empty_p(const name_t dict)
value_type *name_get(const name_t dict, const key_type key)
value_type_t * name_get_emplace[suffix](name_t container, args...)
value_type *name_safe_get(name_t dict, const key_type key)
void name_set_at(name_t dict, const key_type key, const value_type value) /* for associative array */
void name_push(name_t dict, const key_type key) /* for dictionary set */
bool name_erase(name_t dict, const key_type key)
void name_it(name_it_t it, name_t dict)
void name_it_set(name_it_t it, const name_it_t ref)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
void name_next(name_it_t it)
name_itref_t *name_ref(name_it_t it) /* for associative array */
key_type *name_ref(name_it_t it) /* for dictionary set */
const name_itref_t *name_cref(name_it_t it) /* for associative array */
const key_type *name_cref(name_it_t it) /* for dictionary set */
void name_get_str(string_t str, const name_t dict, bool append)
bool name_parse_str(name_t dict, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t dict)
bool name_in_str(name_t dict, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t dict1, const name_t dict2)
void name_emplace[suffix](name_t container, keyargs...) [for dictionary set */
void name_emplace_key[keysuffix]_val[valsuffix](name_t container, keyargs..., valargs...) /* for associative array */
void name_reserve(name_t dict, size_t capacity)
The following specialized methods are automatically created by the previous definition macro:
void name_splice(name_t dict1, name_t dict2)Move all items from dict2 into dict1.
If there is the same key between dict2 into dict1,
then their values are added (as per the ADD method of the value type).
Afterward dict2 is reset (i.e. empty).
This method is only defined if the value type defines an ADD method.
dict1 and dict2 shall reference different objects.
A tuple is a finite ordered list of elements of different types.
TUPLE_DEF2(name, (element1, type1[, oplist1]) [, ...])TUPLE_DEF2_AS(name, name_t, (element1, type1[, oplist1]) [, ...])TUPLE_DEF2 defines the tuple name_t and its associated methods as static inline functions.
Each parameter of the macro is expected to be an element of the tuple.
Each element is defined by three parameters within parenthesis:
name and element shall be C identifiers that will be used to identify the container and the fields.
It will be used to create all the types (including the iterator) and functions to handle the container. This definition shall be done once per name and per compilation unit.
This is more or less a C structure. The main added value compared to using a C struct is that it generates also all the basic methods to handle it which is quite handy.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
In general, an optional method of the tuple will only be created if all oplists define the needed optional methods for the underlying type.
The _hash (resp. _equal_p and _cmp) method is an exception.
This method is created only if at least one oplist of the tuple defines the HASH (resp. EQUAL) method.
You can disable the use of a specific field for the hash computation of the tuple
by disabling the HASH operator of such field (with HASH(0) in its oplist),
in which case it is coherent to also disable the EQUAL operator too.
Resp., you can disable the use of a field for the equality of the tuple
by disabling the EQUAL operator of such field (with EQUAL(0) in its oplist)
The comparison of two tuples uses lexicographic order of the fields defining the CMP method.
It is created only if at least one oplist of the tuple define CMP method.
You can disable the use of a field for the comparison of the tuple
by disabling the CMP operator of such field (with CMP(0) in its oplist)
TUPLE_DEF2_AS is the same as TUPLE_DEF2 except the name of the type name_t is provided.
Example:
#include <stdio.h>
#include <gmp.h>
#include "m-string.h"
#include "m-tuple.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
TUPLE_DEF2(pair, (key_field, string_t, STRING_OPLIST), \
(value_field, mpz_t, M_OPEXTEND(M_CLASSIC_OPLIST(mpz), \
OUT_STR(MPZ_OUT_STR))))
int main(void) {
pair_t p1;
pair_init (p1);
string_set_str(p1->key_field, "HELLO");
mpz_set_str(p1->value_field, "1742", 10);
printf("The pair is ");
pair_out_str(stdout, p1);
printf("\n");
pair_clear(p1);
}
TUPLE_OPLIST(name, oplist1[, ...] )Return the oplist of the tuple defined by calling TUPLE_DEF2 with the given name and the oplist.
The following type is automatically defined by the previous definition macro if not provided by the user:
name_tType of the defined tuple.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t tuple)
void name_init_set(name_t tuple, const name_t ref)
void name_set(name_t tuple, const name_t ref)
void name_init_move(name_t tuple, name_t ref)
void name_move(name_t tuple, name_t ref)
void name_clear(name_t tuple)
void name_reset(name_t tuple)
void name_get_str(string_t str, const name_t tuple, bool append)
bool name_parse_str(name_t tuple, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t tuple)
bool name_in_str(name_t tuple, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
size_t name_hash(const name_t tuple)
int name_equal_p(const name_t tuple1, const name_t tuple2)
int name_cmp(const name_t tuple1, const name_t tuple2)
The following specialized methods are automatically created by the previous definition macro:
void name_init_emplace(name_t tuple, const type1 element1[, ...])Initialize the tuple tuple (aka constructor) and set it to the value of the constructed tuple (element1[, ...]).
void name_emplace(name_t tuple, const type1 element1[, ...])Set the tuple tuple to the value of the tuple constructed with (element1[, ...]).
const type1 *name_cget_at_element1(const name_t tuple)Return a constant borrowed pointer to the element element1 of the tuple.
There is as many methods as there are elements.
type1 *name_get_at_element1(const name_t tuple)Return a borrowed pointer to the element element1 of the tuple.
There is as many methods as there are elements.
void name_set_element1(name_t tuple, type1 element1)Set the element of the tuple to element1
There is as many methods as there are elements.
int name_cmp_order(const name_t tuple1, const name_t tuple2, const int order[])Compare tuple1 to tuple2 using the given order.
order is a NULL terminated array of int that defines the order of comparison:
an order of {1, 4, 2, 0} indicates to compare first the first field,
if it is equal, to compare the fourth and so on. The third field is not
compared. A negative value indicates to revert the comparison.
This method is created only if all oplist of the tuple define CMP method.
int name_cmp_element1(const name_t tuple1, const name_t tuple2)Compare tuple1 to tuple2 using only the element element1 as reference.
This method is created only if the oplist of element1 defines the CMP method.
A variant is a finite exclusive list of elements of different types: the variant can only be equal to one element at a time.
VARIANT_DEF2(name, (element1, type1[, oplist1]) [, ...])VARIANT_DEF2_AS(name, name_t, (element1, type1[, oplist1]) [, ...])VARIANT_DEF2 defines the variant name_t and its associated methods as static inline functions.
Each parameter of the macro is expected to be an element of the variant.
Each element is defined by three parameters within parenthesis:
If an OPLIST is given, it shall be the one matching the associated type.
name and element<n> shall be C identifiers that will be used to identify the variant.
name will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
This is like a C union. The main added value compared to using a union
is that it generates all the basic methods to handle and it dynamically
identifies which element is stored within.
It is also able to store an EMPTY state for the variant, contrary to an union
(this is the state when default constructing it).
The oplists shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
In general, an optional method of the variant will only be created
if all oplists define the needed optional methods for the underlying type.
VARIANT_DEF2_AS is the same as VARIANT_DEF2 except the name of the type name_t
is provided.
name_parse_str and name_in_str depend also on the INIT operator.
Example:
#include <stdio.h>
#include "m-string.h"
#include "m-variant.h"
VARIANT_DEF2(item,
(name, string_t),
(age, long))
int main(void) {
item_t p1;
item_init (p1);
item_set_name(p1, STRING_CTE("HELLO"));
printf("The variant is ");
item_out_str(stdout, p1);
printf("\n");
item_set_age(p1, 43);
printf("The variant is now ");
item_out_str(stdout, p1);
printf("\n");
item_clear(p1);
}
VARIANT_OPLIST(name, oplist1[, ...] )Return the oplist of the variant defined by calling VARIANT_DEF2 with the given name and the oplists used to generate it.
The following type is automatically defined by the previous definition macro if not provided by the user:
name_tType of the defined variant.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t variant)
void name_init_set(name_t variant, const name_t ref)
void name_set(name_t variant, const name_t ref)
void name_init_move(name_t variant, name_t ref)
void name_move(name_t variant, name_t ref)
void name_clear(name_t variant)
void name_reset(name_t variant)
bool name_empty_p(const name_t variant)
size_t name_hash(const name_t variant)
bool name_equal_p(const name_t variant1, const name_t variant2)
void name_swap(name_t variant1, name_t variant2)
void name_get_str(string_t str, name_t variant, bool append)
bool name_parse_str(name_t variant, const char str[], const char **endp)
void name_out_str(FILE *file, name_t variant)
bool name_in_str(name_t variant, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
The following specialized methods are automatically created by the previous definition macro:
void name_init_elementN(name_t variant)Initialize the variant variant to the type of element1 [constructor]
using the default constructor of this element.
This method is defined if all methods define an INIT method.
void name_init_set_elementN(name_t variant, const typeN elementN)Initialize the variant variant and set it to the type and value of elementN [constructor]
void name_move_elementN(name_t variant, typeN ref)Set the variant variant by stealing as many resources from ref as possible.
Afterwards ref is cleared (destructor)
This method is created only if all oplist of the variant define MOVE method.
void name_set_elementN(name_t variant, const typeN elementN)Set the variant variant to the type and value of elementN.
const typeN *name_cget_at_elementN(name_t variant)Return a borrowed pointer to the variant viewed as of type typeN.
If the variant isn't an object of such type, it returns NULL.
typeN *name_get_at_elementN(name_t variant)Return a borrowed pointer to the variant viewed as of type typeN.
If the variant isn't an object of such type, it returns NULL.
bool name_elementN_p(const name_t variant)Return true if the variant is of the type of elementN.
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A node without any child is called a leaf. It can be seen as an ordered set.
A R-B Tree is a tree where all elements are also totally ordered, and the worst-case of any operation is in logarithm of the number of elements in the tree. The current implementation is RED-BLACK TREE which provides performance guarantee for both insertion and lockup operations. It has not to be confused with a B-TREE.
RBTREE_DEF(name, type[, oplist])RBTREE_DEF_AS(name, name_t, name_it_t, type[, oplist])RBTREE_DEF defines the binary ordered tree name_t and its associated methods as static inline functions.
name shall be a C identifier that will be used to identify the R-B Tree.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The CMP operator is used to perform the total ordering of the elements.
The oplist shall have at least the following operators (INIT, INIT_SET, SET, CLEAR & CMP),
otherwise it won't generate compilable code.
Some methods may return a modifiable pointer to the found element
(for example, _get). In this case, the user shall not modify the
key order of the element, as there is no reordering of the tree
in this case.
A push method on the tree will put the given key in its right place in the tree
by keeping the tree ordered.
It overwrites the already existing value if the key is already present in the dictionary (contrary to C++).
RBTREE_DEF_AS is the same as RBTREE_DEF2 except the name of the types name_t, name_it_t are provided by the user.
Example:
RBTREE_DEF(rbtree_uint, unsigned int)
void f(unsigned int num) {
rbtree_uint_t tree;
rbtree_uint_init(tree);
for(unsigned int i = 0; i < num; i++)
rbtree_uint_push(tree, i);
rbtree_uint_clear(tree);
}
RBTREE_OPLIST(name [, oplist])Return the oplist of the Red-Black tree defined by calling RBTREE_DEF with name and oplist.
If there is no given oplist, the basic oplist for basic C types is used.
The following types are automatically defined by the previous definition macro with name if not provided by the user:
name_tType of the Red Black Tree.
name_it_tType of an iterator over this Red Black Tree.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t rbtree)
void name_clear(name_t rbtree)
void name_init_set(name_t rbtree, const name_t ref)
void name_set(name_t rbtree, const name_t ref)
void name_init_move(name_t rbtree, name_t ref)
void name_move(name_t rbtree, name_t ref)
void name_reset(name_t rbtree)
size_t name_size(const name_t rbtree)
void name_push(name_t rbtree, const type data)
void name_emplace[suffix](name_t rbtree, args...)
type *name_get(const name_t rbtree, const type data)
const type *name_cget(const name_t rbtree, const type data)
void name_swap(name_t rbtree1, name_t rbtree2)
bool name_empty_p(const name_t rbtree)
void name_it(name_it_t it, name_t rbtree)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_last(name_it_t it, name_t rbtree)
void name_it_end(name_it_t it, name_t rbtree)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
void name_it_remove(name_t rbtree, name_it_t it)
void name_next(name_it_t it)
void name_previous(name_it_t it)
type *name_ref(name_it_t it)
const type *name_ref(name_it_t it)
void name_get_str(string_t str, const name_t rbtree, bool append)
bool name_parse_str(name_t tree, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t rbtree)
bool name_in_str(name_t rbtree, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t rbtree1, const name_t rbtree2)
size_t name_hash(const name_t rbtree)
The following specialized methods are automatically created by the previous definition macro:
void name_pop(type *dest, name_t rbtree, const type data)Pop data from the Red Black Tree rbtree
and save the popped value into dest if the pointer is not null
while keeping the tree balanced.
Do nothing if data is no present in the Red Black Tree.
type * name_min(const name_t rbtree)const type * name_cmin(const name_t rbtree)Return a borrowed pointer to the minimum element of the tree or NULL if there is no element.
type * name_max(const name_t rbtree)const type * name_cmax(const name_t rbtree)Return a borrowed pointer to the maximum element of the tree or NULL if there is no element.
void name_it_from(name_it_t it, const name_t rbtree, const type data)Set the iterator it to
the lowest element of the tree rbtree greater or equal than data
or an iterator to no element is there is none.
bool name_it_until_p(const name_it_t it, const type data)Return true if it references an element that is greater or equal than data
or if it references no longer a valid element, false otherwise.
bool name_it_while_p(const name_it_t it, const type data)Return true if it references an element that is lower or equal than data.
Otherwise (or if it references no longer a valid element) it returns false.
A B+TREE is a variant of BTREE that itself is a generalization of Binary Tree.
A B+TREE is an N-ary tree with a variable but often large number of children per node. It is mostly used for handling slow media by file system and database.
It provides a fully sorted container enabling fast access to individual item or range of items, and as such is concurrent to Red-Black Tree. On modern architecture, a B+TREE is typically faster than a red-black tree due to being more cache friendly (The RAM itself can be considered as a slow media nowadays!)
When defining a B+TREE it is necessary to give the type of the item within, but also
the maximum number of child per node (N). The best maximum number of child per node
depends on the type itself (its size, its compare cost) and the cache of the
processor.
BPTREE_DEF2(name, N, key_type, key_oplist, value_type, value_oplist)BPTREE_DEF2_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist, value_type, value_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an associative
array of the key_type to the value_type.
The CMP operator is used to perform the total ordering of the key elements.
N is the number of items per node and shall be greater or equal than 3.
It shall be done once per type and per compilation unit.
It also define the iterator name##_it_t and its associated methods as static inline functions.
The object of type key_type and value_type shall be trivially movable.
The object oplist shall have at least the operators (INIT, INIT_SET, SET, CLEAR and CMP).
BPTREE_DEF2_AS is the same as BPTREE_DEF2 except the name of the
container type name_t, the iterator type name_it_t, and the
iterated object type name_itref_t are provided by the user.
Example:
BPTREE_DEF2(tree_uint, 4, unsigned int, (), float, ())
void f(unsigned int num) {
tree_uint_t tree;
tree_uint_init(tree);
for(unsigned int i = 0; i < num; i++)
tree_uint_set_at(tree, i, (float) i);
tree_uint_clear(tree);
}
BPTREE_OPLIST2(name, key_oplist, value_oplist)Return the oplist of the BPTREE defined by calling BPTREE_DEF2 with name,
key_oplist and value_oplist.
BPTREE_DEF(name, N, key_type[, key_oplist])BPTREE_DEF_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an ordered set
of key_type.
The CMP operator is used to perform the total ordering of the key elements.
N is the number of items per node and shall be greater or equal than 2.
It shall be done once per type and per compilation unit.
It also define the iterator name##_it_t and its associated methods as static inline functions.
The object oplist shall have at least the operators (INIT, INIT_SET, SET, CLEAR and CMP).
BPTREE_DEF_AS is the same as BPTREE_DEF except the name of
the container type name_t, the iterator type name_it_t and the iterated object type name_itref_t
are provided by the user.
Example:
BPTREE_DEF(tree_uint, unsigned int)
void f(unsigned int num) {
tree_uint_t tree;
tree_uint_init(tree);
for(unsigned int i = 0; i < num; i++)
tree_uint_push(tree, i);
tree_uint_clear(tree);
}
BPTREE_OPLIST(name[, key_oplist])Return the oplist of the BPTREE defined by calling BPTREE_DEF with name and key_oplist.
If there is no given oplist, the basic oplist for basic C types is used.
BPTREE_MULTI_DEF2(name, N, key_type, key_oplist, value_type, value_oplist)BPTREE_MULTI_DEF2_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist, value_type, value_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an associative
array of the key_type to the value_type and allows multiple instance of
the same key in the tree (aka it is a multi-map: re-adding the same key in
the tree will add a new instance of the key in the tree rather than update
the value associated to the key).
See BPTREE_DEF2 for additional details and example.
BPTREE_MULTI_DEF2_AS is the same as BPTREE_MULTI_DEF2 except the name of the types name_t, name_it_t, name_itref_t are provided by the user.
BPTREE_MULTI_DEF(name, N, key_type[, key_oplist])BPTREE_MULTI_DEF_AS(name, name_t, name_it_t, name_itref_t, N, key_type, key_oplist)Define the B+TREE tree of rank N name_t and its associated methods as
static inline functions. This B+TREE will be created as an ordered set
of key_type and allows multiple instance of
the same key in the tree (aka it is a multi set: re-adding the same key in
the tree will add a new instance of the key in the tree rather than update
the key value).
See BPTREE_DEF for additional details and example.
BPTREE_MULTI_DEF_AS is the same as BPTREE_MULTI_DEF except the name of the types name_t, name_it_t, name_itref_t are provided by the user.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the B+Tree of type.
name_it_tType of an iterator over this B+Tree.
name_itref_tType of one item referenced in the B+Tree. It is either:
key_ptr) and a pointer to the value (field value_ptr) if the B+Tree is an associative array,The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t tree)
void name_clear(name_t tree)
void name_init_set(name_t tree, const name_t ref)
void name_set(name_t tree, const name_t ref)
void name_init_move(name_t tree, name_t ref)
void name_move(name_t tree, name_t ref)
void name_reset(name_t tree)
size_t name_size(const name_t tree)
void name_push(name_t tree, const key_type data) [for set definition only]
void name_set_at(name_t tree, const key_type data, const value_type val) /* for associative array definition only */
bool name_erase(name_t tree, const key_type data)
value_type *name_get(const name_t tree, const key_type data)
const value_type *name_cget(const name_t tree, const key_type data)
value_type *name_safe_get(name_t tree, const key_type data)
void name_swap(name_t tree1, name_t tree2)
bool name_empty_p(const name_t tree)
void name_it(name_it_t it, name_t tree)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, name_t tree)
void name_it_last(name_it_t it, name_t tree)
bool name_end_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it1)
void name_next(name_it_t it)
void name_previous(name_it_t it)
name_itref_t *name_ref(name_it_t it)
const name_itref_t *name_cref(name_it_t it)
void name_get_str(string_t str, const name_t tree, bool append)
bool name_parse_str(name_t tree, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t tree)
bool name_in_str(name_t tree, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
bool name_equal_p(const name_t tree1, const name_t tree2)
size_t name_hash(const name_t tree)
void name_emplace[suffix](name_t container, keyargs...) [for dictionary set]
void name_emplace_key[keysuffix]_val[valsuffix](name_t container, keyargs..., valargs...) /* for associative array */
The following specialized methods are automatically created by the previous definition macro:
bool name_pop_at(value_type *dest, name_t tree, const key_type data)Pop data from the B+Tree tree
and save the popped value into *dest if dest is not NULL
while keeping the tree balanced.
Do nothing if data is no present in the B+Tree.
Return true if data has been erased, false otherwise.
value_type *name_min(const name_t tree)const value_type *name_cmin(const name_t tree)Return a borrowed pointer to the minimum element of the tree or NULL if there is no element in the B+Tree.
value_type *name_max(const name_t tree)const value_type *name_cmax(const name_t tree)Return a borrowed pointer to the maximum element of the tree or NULL if there is no element in the B+Tree.
void name_it_from(name_it_t it, const name_t tree, const type data)Set the iterator it to the lowest element of tree
greater or equal than data or the end iterator is there is none.
bool name_it_until_p(const name_it_t it, const type data)Return true if it references an element that is greater or equal than data.
Otherwise it returns false.
If it references no longer a valid element,
it returns true if the iterator has reached this state by going above the maximum of the tree,
false otherwise.
bool name_it_while_p(const name_it_t it, const type data)Return true if it references an element that is lower or equal than data.
Otherwise it returns false.
If it references no longer a valid element,
it returns true if the iterator has reached this state by going below the minimum of the tree,
false otherwise.
A tree is an abstract data type to represent the hierarchic nature of a structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent.
TREE_DEF(name, type [, oplist])TREE_DEF_AS(name, name_t, name_it_t, type [, oplist])Define the tree name_t and its associated methods as static inline functions.
The tree will be composed of object of type type, connected each other.
name shall be a C identifier that will be used to identify the tree.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
Any insert (resp. remove) in the tree shall specific the insertion point
(resp. deleting point). To construct a tree, you start by creating the
root node (using the _set_root method) and then insert new nodes from there.
Each insertion of node in the tree will return an iterator of the inserted
node. This can be used to construct quickly a full tree.
The oplist shall have at least the following operators (INIT_SET & CLEAR),
otherwise it won't generate compilable code.
The tree handles its own pool of nodes for the nodes.
It is called the capacity of the tree.
This pool of nodes will increase when needed by default.
However, in case of capacity increased, all the nodes of the tree may move in memory to accommodate the new need.
You may also request to reserve more capacity to avoid moving the items, and disable this auto-expand feature (in which a MEMORY_FAILURE is raised).
There are several ways to iterate over this container:
On insertion, all iterators remain valid. Except if it says otherwise, all functions accepting iterators expect a valid iterator (i.e. it references an existing node).
TRREE_DEF_AS is the same as TREE_DEF except the name of the types name_t, name_it_t are provided.
TREE_OPLIST(name, [, oplist])Define the oplist of the generic tree defined with name and potentially oplist.
If there is no given oplist, the basic oplist for basic C types is used.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the generic tree of type.
name_it_tType of an iterator over this generic tree.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t tree)
void name_init_set(name_t tree, const name_t ref)
void name_init_move(name_t tree, name_t ref)
void name_set(name_t tree, const name_t ref)
void name_move(name_t tree, name_t ref)
void name_clear(name_t tree)
void name_reset(name_t tree)
size_t name_size(const name_t tree)
size_t name_capacity(const name_t tree)
void name_reserve(name_t tree, size_t capacity)
bool name_empty_p(const name_t tree)
void name_swap(name_t tree1, name_t tree2)
bool name_equal_p(const name_t tree1, const name_t tree2)
bool name_end_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
const type *name_cref(name_it_t it)
type *name_ref(name_it_t it)
bool name_remove(it_t it)
void name_get_str(string_t str, const name_t tree, bool append)
bool name_parse_str(name_t tree, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t tree)
bool name_in_str(name_t tree, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
The following specialized methods are automatically created by the previous definition macro:
void name_lock(name_t tree, bool lock)Disable the auto-resize feature of the tree (if lock is true), or enable it otherwise. By default, the feature is enabled. Locking a tree shall be done after reserving the maximum number of nodes that can be added by your tree, so that the returned borrowed pointers to the internal types won't move on inserting a new node.
name_it_t name_set_root(name_t tree, const type value)Set the tree to a single root node and set this node to value.
name_it_t name_emplace_root[suffix](name_t tree, args...)Set the tree to a single root node and set this node to the value
initialized with the given args.
The provided arguments shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator.
See emplace chapter for more details.
it_t name_insert_up_raw(it_t ref)it_t name_insert_left_raw(it_t ref)it_t name_insert_right_raw(it_t ref)it_t name_insert_down_raw(it_t ref)it_t name_insert_child_raw(it_t ref)Insert a node up (resp. left, right, down and down) the given referenced iterator without initializing it.
It returns an iterator to the inserted node with non-initialized data.
The first thing to do after calling this function shall be to initialize the data
using the proper constructor of the object of type type (the pointer can be get through name_ref)
This enables using more specialized constructor than the generic copy one.
The user should use the non _raw function if possible rather than this one
as it is low level and error prone.
name_insert_down_raw will move all children of the referenced node as children of the inserted children,
whereas name_insert_child_raw will insert the node as the new first child of the referenced node.
it_t name_insert_up(it_t ref, const type value)it_t name_insert_left(it_t ref, const type value)it_t name_insert_right(it_t ref, const type value)it_t name_insert_down(it_t ref, const type value)it_t name_insert_child(it_t ref, const type value)Insert a node up (resp. left, right, down and down) the given referenced iterator and initialize it with a copy of value.
It returns an iterator to the inserted node.
name_insert_down will move all children of the referenced node as children of the inserted children,
whereas name_insert_child will insert the node as the new first child of the referenced node.
it_t name_move_up(it_t ref, type *value)it_t name_move_left(it_t ref, type *value)it_t name_move_right(it_t ref, type *value)it_t name_move_down(it_t ref, type *value)it_t name_move_child(it_t ref, type *value)Insert a node up (resp. left, right, down and down) the given referenced iterator and initialize it with value by stealing as much resource from value as possible (and destroy *value)
It returns an iterator to the inserted node.
name_move_down will move all children of the referenced node as children of the inserted children,
whereas name_move_child will insert the node as the new first child of the referenced node.
it_t name_emplace_up[suffix](it_t ref, args...)it_t name_emplace_left[suffix](it_t ref, args...)it_t name_emplace_right[suffix](it_t ref, args...)it_t name_emplace_down[suffix](it_t ref, args...)it_t name_emplace_child[suffix](it_t ref, args...)Insert a node up (resp. left, right, down and down) the given referenced iterator
and initialize this node to the value initialized with the given args.
The provided arguments shall therefore match one of the constructor provided
by the EMPLACE_TYPE operator.
See emplace chapter for more details.
It returns an iterator to the inserted node.
name_emplace_down will move all children of the referenced node as children of the inserted children,
whereas name_emplace_child will insert the node as the new first child of the referenced node.
type *name_up_ref(name_it_t it)type *name_down_ref(name_it_t it)type *name_left_ref(name_it_t it)type *name_right_ref(name_it_t it)Return a borrowed pointer to the type of the node which is
respectively. It returns NULL if there is no such node.
it_t name_up(it_t it)it_t name_down(it_t it)it_t name_left(it_t it)it_t name_right(it_t it)Return an iterator to point to the node which is up (resp. down, left and right) the given iterator.
Return a valid iterator in case of success, an invalid one otherwise (see name_end_p)
bool name_it_up(it_t *it)bool name_it_down(it_t *it)bool name_it_left(it_t *it)bool name_it_right(it_t *it)Update the iterator to point to the node which is up (resp. down, left and right) the given iterator. Return true in case of success, false otherwise (as such node doesn't exist, the iterator remains unchanged).
bool name_root_p(const it_t it)Return true if it references the root node, false otherwise.
bool name_node_p(const it_t it)Return true if it references a non-leaf node, false otherwise.
bool name_leaf_p(const it_t it)Return true if it references a leaf node, false otherwise.
int32_t name_degree(const it_t it)Return the degree of the referenced node (aka the number of children). A leaf node has a degree of 0. This function is linear in the number of children of the node.
int32_t name_depth(const it_t it)Return the depth of the referenced node (aka the number of nodes until reaching the root node). The root node has a depth of 0. This function is linear in the depth of the node.
type *name_unlink(it_t it)Unlink the referenced node from the tree, so that the node is removed from the tree. All children of the removed node become children of the parent node. If the removed node is the root node, than the root node shall have only one child.
Return a reference to the internal type and give back ownership of the type:
you shall destroy the type (using CLEAR or MOVE methods) before calling any other tree functions
(as the memory area used by the node may be removed on inserting a new node)
You should use the remove service instead as it has the same semantics but it is safer as it perform the clear of the data.
void name_prune(name_it_t it)Remove the referenced node including all its children.
See name_remove for more details.
name_it_t name_it_end(name_t tree)Return an iterator that references no valid node.
void name_it_set(name_it_t *it, const name_it_t ref)Set the iterator *it to ref.
[!NOTE] You can use the
=affectation operator of the C language to copy tree iterators too.
name_it_t name_it(name_t tree)Return an iterator of the tree that will iterator on the tree in global pre-order walk (the root).
void name_next(name_it_t *it)Update the iterator of the tree so that it references the next node in a global pre-order walk, or set it to invalid if the walk is finished.
name_it_t name_it_post(name_t tree)Return an iterator of the tree that will iterator on the tree in global post-order walk
void name_next_post(name_it_t *it)Update the iterator of the tree so that it references the next node in a global post-order walk, or set it to invalid if the walk is finished.
name_it_t name_it_subpre(name_t tree, const name_it_t ref)Return an iterator of the tree that will iterator on the tree in pre-order walk of the child nodes of the referenced one.
void name_next_subpre(name_it_t it, const name_it_t ref)Update the iterator of the tree so that it references the next node in a local pre-order walk of the child nodes of the referenced one, or set it to invalid if the walk is finished (the sub tree is fully scanned).
The referenced iterator shall be the same as the one used to create the updated iterator (with name_it_subpre).
name_it_t name_it_subpost(name_t tree, const name_it_t ref)Return an iterator of the tree that will iterator on the tree in post-order walk of the child nodes of the referenced one.
void name_next_subpost(name_it_t it, const name_it_t ref)Update the iterator of the tree so that it references the next node in a local post-order walk of the child nodes of the referenced one, or set it to invalid if the walk is finished (the sub-tree is fully scanned).
The referenced iterator shall be the same as the one used to create the updated iterator (with name_it_subpost).
void name_lca(name_it_t it1, name_it_t it2)Compute the Lowest Common Ancestor of the two iterators. Both iterators shall belong to the same tree.
void name_swap_at(name_it_t it1, name_it_t it2, bool swapChild)Swap the node referenced by it1 and the node referenced by it2 in the tree.
If swapChild is true, the children nodes perform the swap with their parent.
Otherwise, only the referenced nodes are swapped.
void name_sort_child(name_it_t it1)Sort the child of the node referenced by it1 in the order of the type.
This method is constructed if the basic type exports the CMP type.
A priority queue is a queue where each element has a "priority" associated with it: an element with high priority is served before an element with low priority. It is currently implemented as a heap.
PRIOQUEUE_DEF(name, type [, oplist])PRIOQUEUE_DEF_AS(name, name_t, name_it_t, type [, oplist])Define the priority queue name_t and its associated methods
as static inline functions.
The queue will be composed of object of type type.
name shall be a C identifier that will be used to identify the queue.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The CMP operator is used to sort the queue so that the highest priority is the minimum.
The EQUAL operator is used to identify an item on update or remove operations.
It is uncorrelated with the CMP operator from the point of view of this container.
(i.e. EQUAL() == TRUE is not equivalent to CMP() == 0 for this container)
This queue will push the object at the right place in the queue in function of their priority. A pop from this queue will always return the minimum of all objects within the queue (contrary to C++ which returns the maximum), and the front method will reference this object.
The oplist shall have at least the following operators (INIT, INIT_SET, SET, CLEAR, CMP),
otherwise it won't generate compilable code.
The equal_p, update & erase methods have a complexity of O(n) due to the linear
search of the data and are only created if the EQUAL method is defined.
Iteration over this container won't iterate from minimum to maximum but in an implementation define way that ensures that all items are accessed.
PRIOQUEUE_DEF_AS is the same as PRIOQUEUE_DEF except the name of the types name_t, name_it_t are provided.
PRIOQUEUE_OPLIST(name, [, oplist])Define the oplist of the PRIOQUEUE defined with name and potentially oplist.
If there is no given oplist, the basic oplist for basic C types is used.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the priority queue of type.
name_it_tType of an iterator over this priority queue.
The following methods of the common interface are defined (See Common interface for details):
void name_init(name_t queue)
void name_clear(name_t queue)
void name_init_set(name_t queue, const name_t ref)
void name_set(name_t queue, const name_t ref)
void name_init_move(name_t queue, name_t ref)
void name_move(name_t queue, name_t ref)
void name_reset(name_t queue)
size_t name_size(const name_t queue)
bool name_empty_p(const name_t queue)
void name_swap(name_t queue1, name_t queue2)
void name_push(name_t queue, const type x)
const type *name_front(name_t queue)
void name_pop(type *dest, name_t queue)
bool name_equal_p(const name_t queue1, const name_t queue2)
bool name_erase(name_t queue, const type_t val)
void name_it(name_it_t it, name_t queue)
void name_it_last(name_it_t it, name_t queue)
void name_it_set(name_it_t it, const name_it_t ref)
void name_it_end(name_it_t it, name_t queue)
bool name_end_p(const name_it_t it)
bool name_last_p(const name_it_t it)
bool name_it_equal_p(const name_it_t it1, const name_it_t it2)
void name_next(name_it_t it)
void name_previous(name_it_t it)
const type *name_cref(name_it_t it)
void name_get_str(string_t str, const name_t queue, bool append)
bool name_parse_str(name_t queue, const char str[], const char **endp)
void name_out_str(FILE *file, const name_t queue)
bool name_in_str(name_t queue, FILE *file)
m_serial_return_code_t name_out_serial(m_serial_write_t serial, const name_t container)
m_serial_return_code_t name_in_str(name_t container, m_serial_read_t serial)
void name_emplace[suffix](name_t queue, args...)
The following specialized methods are automatically created by the previous definition macro:
void name_update(name_t queue, const type_t old_val, const type_t new_val)Change the priority of the data of the priority equals to old_val (in EQUAL sense)
to new_val (increase or decrease priority).
This method has a complexity of O(n) (due to linear search of the data).
This method is defined only if the EQUAL method is defined.
This header implements a fixed circular queue or stack.
A circular buffer (or ring buffer or circular queue) is a data structure using a single, bounded buffer as if its head was connected to its tail.
Define the circular queue name_t and its associated methods as static inline functions.
This queue is not thread-safe (See m-buffer header for a thread safe variant).
The order of the elements in the container is FIFO (First In, First Out).
name shall be a C identifier that will be used to identify the queue.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The size parameter defined the fixed size of the queue.
It can be 0. In this case, the fixed size is defined at initialization time only
and the needed objects to handle the queue are allocated at initialization time too.
Otherwise the needed objects are embedded within the structure, preventing
any other allocations.
The size of the queue shall be lower or equal than the maximum of the type unsigned int.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
QUEUE_DEF_AS is the same as QUEUE_DEF except the name of the type name_t is provided.
Example:
QUEUE_DEF(queue_uint, unsigned int, 10)
queue_uint_t g_buff;
void f(unsigned int i) {
queue_uint_init(g_buff, 10);
queue_uint_push(g_buff, i);
queue_uint_pop(&i, g_buff);
queue_uint_clear(g_buff);
}
Define the fixed size stack name_t and its associated methods as static inline functions.
This stack is not thread-safe (See m-buffer header for a thread safe variant).
The order of the elements in the container is FILO (First In, Last Out).
name shall be a C identifier that will be used to identify the stack.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The size parameter defined the fixed size of the stack.
It can be 0. In this case, the fixed size is defined at initialization time only
and the needed objects to handle the stack are allocated at initialization time too.
Otherwise the needed objects are embedded within the structure, preventing
any other allocations.
The size of the stack shall be lower or equal than the maximum of the type unsigned int.
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
STACK_DEF_AS is the same as STACK_DEF except the name of the type name_t is provided.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the circular queue (or stack).
The following methods of the common interface are defined (See Common interface for details):
void name_clear(queue_t queue)
void name_reset(queue_t queue)
bool name_empty_p(const queue_t queue)
size_t name_size(const queue_t queue)
size_t name_capacity(const queue_t queue)
void name_push(queue_t queue, const type data)
void name_pop(type *data, queue_t queue)
The following specialized methods are automatically created by the previous definition macro:
void name_init(queue_t queue, size_t size)Initialize the queue (or stack) queue for size elements.
The size argument shall be the same as the one used to create the container, or the size used to create it was 0 (ie. runtime fixed size).
The size of the queue shall be lower or equal than UINT_MAX.
bool name_full_p(const queue_t queue)Return true if the queue (or stack) is full, false otherwise.
This header implements different kind of fixed circular buffer used for threading purpose.
A circular buffer (or ring buffer or circular queue) is a data structure using a single, bounded buffer as if its head was connected to its tail.
Define the buffer name_t and its associated methods as static inline functions.
A buffer is a fixed circular queue implementing a queue (or stack) interface.
It can be used to transfer message from multiple producer threads to multiple consumer threads.
This is done internally using a mutex and conditional waits
See m-queue for a non thread safe variant.
name shall be a C identifier that will be used to identify the buffer.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
The size parameter defined the fixed size of the queue.
It can be 0. In this case, the fixed size is defined at initialization time only
and the needed objects to handle the buffer are allocated at initialization time too.
Otherwise the needed objects are embedded within the structure, preventing
any other allocations.
The size of the buffer shall be lower or equal than the maximum of the type unsigned int.
Multiple additional policy can be applied to the buffer by performing a logical or of the following properties:
BUFFER_QUEUE — define a FIFO queue (default),BUFFER_STACK — define a stack (exclusive with BUFFER_QUEUE),BUFFER_PUSH_OVERWRITE — PUSH overwrites the last entry if the queue is full instead of blocking,BUFFER_DEFERRED_POP — do not consider the object to be fully popped from the buffer by calling the pop method until the call to pop_deferred ; this enables to handle object that are in-progress of being consumed by the thread.This container is designed to be used for synchronization inter-threads of data (and the buffer variable should be a global shared one).
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The PUSH and POP methods operate like push_blocking and pop_blocking when the blocking parameter
is true.
BUFFER_DEF_AS is the same as BUFFER_DEF except the name of the type name_t is provided.
Example:
BUFFER_DEF(buffer_uint, unsigned int, 10, BUFFER_QUEUE|BUFFER_BLOCKING)
buffer_uint_t g_buff;
void f(unsigned int i) {
buffer_uint_init(g_buff, 10);
buffer_uint_push(g_buff, i);
buffer_uint_pop(&i, g_buff);
buffer_uint_clear(g_buff);
}
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the buffer.
The following methods of the common interface are defined (See Common interface for details):
void name_clear(buffer_t buffer) /* Not thread safe */
void name_reset(buffer_t buffer) /* Thread safe */
bool name_empty_p(const buffer_t buffer) /* Thread safe */
size_t name_size(const buffer_t buffer) /* Thread safe */
size_t name_capacity(const buffer_t buffer) /* Thread safe */
void name_push(buffer_t buffer, const type data)
void name_push_move(buffer_t buffer, type *data)
void name_pop(type *data, buffer_t buffer)
void name_pop_move(type *data, buffer_t buffer)
The following specialized methods are automatically created by the previous definition macro:
void name_init(buffer_t buffer, size_t size)Initialize the buffer buffer for size elements.
The size argument shall be the same as the one used to create the buffer
or the one used to create the buffer was 0.
The size of the buffer shall be lower or equal than UINT_MAX.
This function is not thread safe.
bool name_full_p(const buffer_t buffer)Return true if the buffer is full, false otherwise. This function is thread safe if the buffer was built thread safe.
size_t name_overwrite(const buffer_t buffer)If the buffer is built with the BUFFER_PUSH_OVERWRITE option,
this function returns the number of elements that have been overwritten
and thus discarded.
If the buffer was not built with the BUFFER_PUSH_OVERWRITE option,
it returns 0.
bool name_push_blocking(buffer_t buffer, const type data, bool blocking)Push the object data in the buffer buffer,
waiting for an empty room if blocking is true (performing a blocking wait)
Returns true if the data was pushed, false otherwise.
Always return true if the buffer is blocking.
This function is thread safe.
bool name_push_move_blocking(buffer_t buffer, type *data, bool blocking)Push the object *data in the buffer buffer
by stealing as much resource from it as possible,
clearing *data afterwards (destructor)
waiting for an empty room if blocking is true (performing a blocking wait)
Returns true if the data was pushed, false otherwise.
Always return true if the buffer is blocking.
This function is thread safe.
bool name_pop_blocking(type *data, buffer_t buffer, bool blocking)Pop from the buffer buffer into the object *data,
waiting for a data if blocking is true.
If the buffer is built with the BUFFER_DEFERRED_POP option,
the object is still considered being present in the queue until
a call to name_pop_release.
Returns true if a data was popped, false otherwise. Always return true if the buffer is blocking. This function is thread safe.
bool name_pop_move_blocking(type *data, buffer_t buffer, bool blocking)Pop from the buffer buffer into the uninitialized object *data,
waiting for a data if blocking is true (constructor).
If the buffer is built with the BUFFER_DEFERRED_POP option,
the object is still considered being present in the queue until
a call to name_pop_release.
Returns true if a data was popped, false otherwise. Always return true if the buffer is blocking. This function is thread safe.
bool name_pop_release(buffer_t buffer)If the buffer is built with the BUFFER_DEFERRED_POP option,
the object being popped is considered fully release (freeing a
space in the queue).
Otherwise it does nothing.
QUEUE_MPMC_DEF(name, type, policy[, oplist])QUEUE_MPMC_DEF_AS(name, name_t, type, policy[, oplist])Define the MPMC queue name_t and its associated methods as static inline functions.
A MPMC queue is a fixed circular queue implementing a queue (or stack) interface.
It can be used to transfer message from Multiple Producer threads to Multiple Consumer threads.
This queue is not strictly lock free but has
a lot of the properties of such algorithms.
The size is specified only at run-time and shall be a power of 2.
name shall be a C identifier that will be used to identify the queue.
It will be used to create all the types (including the iterator)
and functions to handle the container.
This definition shall be done once per name and per compilation unit.
An additional policy can be applied to the buffer by performing a logical or of the following properties:
BUFFER_QUEUE — define a FIFO queue (default),This container is designed to be used for easy synchronization inter-threads in a context of very fast communication (the variable should be a global shared one). There should not have much more threads using this queue than they are available hardware cores due to the only partial protection on Context-switch Immunity of this structure (This can happen only if you abuse massively the number of threads vs the number of cores).
The oplist shall have at least the following operators (INIT_SET, SET and CLEAR),
otherwise it won't generate compilable code.
The size method is thread safe but may return a size greater than
the size of the queue in some race condition.
QUEUE_MPMC_DEF_AS is the same as QUEUE_MPMC_DEF except the name of the type name_t
is provided.
The following types are automatically defined by the previous definition macro if not provided by the user:
name_tType of the circular queue.
The following methods of the common interface are defined (See Common interface for details):
void name_clear(buffer_t buffer)
bool name_empty_p(const buffer_t buffer) /* Thread safe */
size_t name_size(const buffer_t buffer) /* Thread safe */
size_t name_capacity(const buffer_t buffer) /* Thread safe */
The following specialized methods are automatically created by the previous definition macro:
void name_init(buffer_t buffer, size_t size)Initialize the buffer buffer with size elements.
The size argument shall be a power of two greater than 0, and less than UINT_MAX.
This function is not thread safe.
##### bool name_full_p(const buffer_t buffer)
Return true if the buffer is full, false otherwise. This function is thread safe.
bool name_push(buffer_t buffer, const type data)Push the object data in the buffer buffer if possible.
Returns true if the data was pushed, false otherwise
(buffer full or unlikely data race).
This function is thread safe.
bool name_push_move(buffer_t buffer, type *data)Push the object *data in the buffer buffer if possible,
by stealing as much resources from it as possible,
clearing *data afterwards.
Returns true if the data was effectively pushed, false otherwise
(buffer full or unlikely data race), in which case *data is still initialized.
This function is thread safe.
bool name_pop(type *data, buffer_t buffer)Pop from the buffer buffer into the object *data if possible.
Returns true if a data was popped, false otherwise (buffer empty or unlikely data race). This function is thread safe.
bool name_pop_move(type *data, buffer_t buffer)Pop from the buffer buffer into the unin
Truncated — view the full README on GitHub.
(top 24 of 26)