Skip to content
master
Switch branches/tags
Go to file
Code

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
doc
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

README.md

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

Overview

M*LIB (M star lib) is a C library enabling to use generic and type safe container in pure C language, aka handling generic containers. The objects within the containers can still have proper constructor, destructor (and other methods): this is handled by the library. This makes it possible to construct fully recursive objects (container-of[...]-container-of-type-T), without erasing type information (typically using void pointers or resorting to C macro to access the container).

This is an equivalent of the C++ Standard Library but for 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 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: 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's design key is to ensure safety. This is done by multiple means:

  • in debug mode, defensive programming is extensively used: the contracts of the function are checked, ensuring that the data are not corrupted. For example, Buffer overflow are checked in this mode through bound checking or the intrinsic properties of a Red-Black tree (for example) are verified.
  • as few cast as possible are used within the library (as cast are the evil of safety). Still the library can be used with the greatest level of warnings by a C compiler without any aliasing warning.
  • the genericity is not done directly by macro, but indirectly by making them define inline functions with the proper prototypes: this enables the user calls to have proper warning checks.

Other key designs are:

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

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

M*LIB is still be quite-efficient: even if the implementation may not always be state of the art, there is no overhead in using this library rather than using direct C low-level access: the compiler is able to fully optimize the library calls since all the functions are declared as inline. In fact, M*LIB is one of the fastest generic C library you can find.

M*LIB uses internally the 'malloc', 'realloc' and 'free' functions to handle the memory pool. This behavior can be overridden at different level. M*LIB default policy is to abort the program if there is a memory error. However, this behavior can also be customized globally.

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

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

It is strongly advised not to read the source to know how to use the library but rather read the examples or the tests.

In this documentation, 'shall' will be used to indicate a user constraint that is mandatory to follow under penalty of undefined behavior. 'should' will be used to indicate a recommendation to the user. All pointers expect non-null argument except if indicated.

Components

The available containers that doesn't require the user structure to be modified are:

  • m-array.h: header for creating array of generic type and of variable size,
  • m-list.h: header for creating singly-linked list of generic type,
  • m-deque.h: header for creating double-ended queue of generic type and of variable size,
  • m-dict.h: header for creating generic dictionary or set of generic type (and of variable kind),
  • m-rbtree.h: header for creating binary sorted tree of generic type,
  • m-bptree.h: header for creating B+TREE of generic type,
  • m-tuple.h: header for creating arbitrary tuple of generic type,
  • m-variant.h: header for creating arbitrary variant of generic type,
  • m-prioqueue.h: header for creating priority queue of generic type and of variable size,

The available containers of M*LIB for thread synchronization are:

  • m-buffer.h: header for creating fixed-size queue (or stack) of generic type (multiple producer / multiple consumer),
  • m-snapshot: header for creating 'snapshot' buffer for sharing synchronously big data (thread safe).
  • m-shared.h: header for creating shared pointer of generic type.
  • m-concurrent.h: header for transforming a container into a concurrent container.
  • [m-c-mempool.h]: WIP header for creating fast concurrent memory allocation.

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

  • m-i-list.h: header for creating doubly-linked intrusive list of generic type,
  • m-i-shared.h: header for creating intrusive shared pointer of generic type (Thread Safe),

Other headers offering other functionality are:

  • m-string.h: header for creating dynamic variable-length string,
  • m-bitset.h: header for creating bit set (or "packed array of bool"),
  • m-algo.h: header for providing various generic algorithms to the previous containers.
  • m-funcobj.h: header for creating function object (used by algorithm generation).
  • m-mempool.h: header for creating specialized & fast memory allocator.
  • m-worker.h: header for providing an easy pool of workers on separated threads to handle work orders, used for parallelism tasks.
  • m-serial-json.h: header for importing / exporting the containers in JSON format.
  • m-serial-bin.h: header for importing / exporting the containers in an adhoc fast binary format.
  • [m-genint.h]: internal header for generating unique integers in a concurrent context.
  • m-core.h: header for meta-programming with the C preprocessor (used by all other headers).

Finally headers for compatibility with non C11 compilers:

  • m-atomic.h: header for ensuring compatibility between C's stdatomic.h and C++'s atomic header. Provide also an implementation over mutex if none is available.
  • m-mutex.h: header for providing a very thin layer across multiple implementation of mutex/threads (C11/PTHREAD/WIN32).

Each containers define their iterators.

All containers try to expose the same 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 has to be adapted to the container.

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

Dependence between headers

Build & Installation

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

To run the test suite, run:

   make check

To generate the documentation, run:

   make doc

To install the headers, run:

   make install PREFIX=/my/directory/where/to/install

Other targets exist. Mainly for development purpose.

How to use

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

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

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

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

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

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

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:

  • M*LIB requires an explicit definition of the instance of the list,
  • M*LIB code is more verbose in the method name,
  • M*LIB needs explicit construction and destruction (as plain old C requests),
  • M*LIB doesn't return a value to the underlying data but a pointer to this value:
    • this was done for performance (it avoids copying all the data within the stack)
    • and for generality reasons (some structure may not allow copying data).

Note: list_uint_t is internally defined as an array of structure of size 1. This has the following advantages:

  • you effectively reserve the data whenever you declare a variable,
  • you pass automatically the variable per reference for function calls,
  • you can not copy the variable by an affectation (you have to use the API instead).

You can also condense the M*LIB code 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("%d\n", *item);       /* Print the item */
     }
   }                                /* Clear of list will be done now */
}

Here is another example with a 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)) )

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_it_mpz_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 the operators are associated to methods. In the example, we tell to the container to use the mpz_init function for the INIT operator of the type, the mpz_clear function for the CLEAR operator of the type, the mpz_set function for the SET operator of the type, the mpz_init_set function for the INIT_SET operator of the type. See oplist chapter for more information.

We can also write the same example shorter:

#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_CLASSIC_OPLIST(mpz)
// 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;
}

Or even shorter when you're comfortable enough with the library:

    #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) )
    // 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 & init 'z1=42' and 'z2=17' to be 'mpz_t'
      M_LET ((z1,42), (z2,17), mpz_t)
        // Let's define 'array' as an 'array_mpz_t' with 'z1' and 'z2'
        M_LET((array,z1,z2), 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 what is the oplist of a type:

  • either the oplist is passed explicitly for each definition of container and for the LET & EACH macros,
  • or the oplist is registered globally by defining a new macro starting with the prefix M_OPL_ and finishing with the name of type (don't forget the parenthesis). The macros performing the definition of container and the LET & 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.

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_DEFAULT_OPLIST, M_DEFAULT_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");
      }
    }

OPLIST

An OPLIST is a fundamental notion of M*LIB that hasn't be used 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 as only meaning within a macro expansion. Fundamentally, this is the exposed interface of a type with documented operators using an associative array implemented with the only C preprocessor where the operators are the predefined keys and the methods are the values.

An oplist is an associative array of operator over methods in the following format:

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

The function 'method1' is used to handle 'OPERATOR1'. The function 'method2' is used to handle 'OPERATOR2'. etc. The order of the operator in this list is the priority order: in case the same operator appear multiple times in the list, the first one is the priority.

The method of an operator in an oplist is a preprocessor expression that shall not contain a comma.

It is used to perform the association between the operation on a type and the function that performs this operation. Without an oplist, M*LIB has no way to known how to deal with your type and will deal with it like a classic C type.

When you define an instance of a new container, you give the type oplist you want to use as the base of the container. This type oplist performs the association between the operators and the methods for the type. In function of the available interface of the oplist, the container definition macro function generates the interface of the container. You can then use this interface directly. You can also use the oplist of the container to chain this new interface with another container, creating container-of-container. oplist and definition

A function name can be followed by the token M_IPTR in the oplist (for example: (INIT(init_func M_IPTR)) ) to specify that the function accept as its first argument a pointer to the type rather than the type itself (aka the prototype is init_func(type *) instead of init_func(type)). If you use the '[1]' trick (see below), you won't need this. See also the API_* transformation call below for further transformation means of the calls.

An oplist has no real form from a C language point of view. It is just an abstraction that disappears after the macro expansion step of the preprocessing.

For each object / container, an oplist is needed. The following operators are usually expected for an object:

  • INIT(obj): initialize the object 'obj' into a valid state (constructor).
  • INIT_SET(obj, org): initialize the object 'obj' into the same state as the object 'org' (constructor).
  • SET(obj, org): set the initialized object 'obj' into the same state as the initialized object org (operator).
  • CLEAR(obj): destroy the initialized object 'obj', releasing any attached memory (destructor). This method shall never fail.

INIT, INIT_SET & SET methods shall only fail due to memory errors.

Not all operators are needed within an oplist to handle a container. If some operator is missing, the associated default operator of the function is used. To use C integer or float types, the default constructors are perfectly fine: you may use M_DEFAULT_OPLIST to define the operator list of such types or you can just omit it.

NOTE: An iterator doesn't have a constructor nor destructor methods. It should not allocate any memory. A reference to an object through an iterator is only valid until another reference is taken from the same container (potentially through another iterator), the iterator is moved. 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 these constraints.

Other documented operators are:

  • NAME() --> prefix: Return the base name (prefix) used to construct the 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).
  • 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 (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 (&obj): free the allocated uninitialized object 'obj'. The object is not cleared before being free (A destructor operator shall be called before). The object shall have been allocated by the associated NEW method. The default method is M_MEMORY_DEL (that frees to the heap).
  • REALLOC(type, type pointer, number) --> type pointer: realloc the given array referenced by type pointer (either a NULL pointer or a pointer returned by the associated REALLOC method itself) to an array of the number of objects of this 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. 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.
  • FREE (&obj) : free the allocated uninitialized array object 'obj'. The objects are not cleared before being free (CLEAR operator has to be called before). The object shall have been allocated by the associated REALLOC method. The default is M_MEMORY_FREE (that frees to the heap).
  • 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. NOTE: It doesn't check for overflow: if the returned value is lower than the old one, the user shall raise an overflow error.
  • INIT_MOVE(objd, objc): Initialize 'objd' to the same state than 'objc' by stealing as much 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. 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. 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 always assume that the objects are trivially movable). An INIT_MOVE operator shall not fail.
  • 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). TBC if this operator is really needed as calling CLEAR then INIT_MOVE is what do all known implementation, and is efficient. A MOVE operator shall not fail.
  • INIT_WITH(obj, ...): Initialize the object 'obj' with the given variable set of arguments (constructor). Arguments can be of different types. It is up to the method of the objet to decide how to initialize the object based on this initialization array. This operator is used in the M_LET macro to initialize objects with their given values.
  • SWAP(objd, objc): Swap the states of the object 'objc' and the object 'objd'.
  • CLEAN(obj): Empty the container from all its objects. Nearly like CLEAR except that the container 'obj' remains initialized (but empty).
  • EMPTY_P(obj) --> bool: Test if the container object is empty (true) or not.
  • 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.
  • 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) and CMP(a,b)==0 is not required, but usually welcome.
  • ADD(obj1, obj2, obj3) : Set obj1 to the sum of obj2 and obj3. Default is '+' C operator.
  • SUB(obj1, obj2, obj3) : Set obj1 to the difference of obj2 and obj3. Default is '-' C operator.
  • MUL(obj1, obj2, obj3) : Set obj1 to the product of obj2 and obj3. Default is '*' C operator.
  • DIV(obj1, obj2, obj3) : Set obj1 to the division of obj2 and obj3. Default is '/' C operator.
  • GET_KEY (container, key) --> &value: Return a pointer to the value object within the container associated to the key 'key' or return NULL if no object is associated to this key. 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.
  • GET_SET_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.
  • 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(obj, subobj) : Push 'subobj' (of type SUBTYPE() ) into the container 'obj'. How and where it is pushed is container dependent.
  • POP(&subobj, obj) : Pop an object from the container 'obj' and save it in the object '*subobj' (of type SUBTYPE()) if subobj is not NULL (giving back the ownership of the sub object to the caller). Which object is popped is container dependent. The container shall have at least one object.
  • PUSH_MOVE(obj, &subobj) : Push and move the object '*subobj' (of type SUBTYPE()) into the container 'obj' (subobj destructor). How it is pushed is container dependent. '*subobj' is cleared afterward and shall not be used anymore.
  • POP_MOVE(&subobj, obj) : Pop an object from the container'obj' and init & move it in the unitialized object '*subobj' (*subobj constructor). Which object is popped is container dependent. '*subobj' shall be uninitialized. The container shall have at least one object.
  • 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.
  • 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.
  • 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 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.
  • 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.
  • 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 output in a string through GET_STR, and an object which is read from this string through GET_STR are considered as equal.
  • 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 .
  • 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).
  • UPDATE(objd, objs): Update the object 'objd' with the object 'objs'. What it does exactly is container dependent. It can either SET or ADD (default is SET).
  • 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'.
  • 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).
  • LIMITS() --> ( numbers ): Return internal properties of a container (for internal use only).

The operator names listed above shall not be defined as macro.

More operators are expected.

Example:

    (INIT(mpz_init),SET(mpz_set),INIT_SET(mpz_init_set),CLEAR(mpz_clear))

If there is two operations with the same name in an oplist, the left one has the priority. This enables partial overriding.

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 space in their name can be registered. A typedef of the type can be used instead through. This can simplify a lot OPLIST usage.

Example:

    #define M_OPL_mpz_t() M_CLASSIC_OPLIST(mpz)

Within an OPLIST, you can also specify the needed low-level transformation to perform for the method. This is called API type. Assuming that the method to call is called 'method' and the first argument of the operator is 'output', then the following transformation are applied:

  • API_0: method(output, ...) /* Default transformation API */
  • API_1: method(oplist, output, ...) /* Give 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 */

Example:

    (INIT(API_0(mpz_init)), SET(API_0(mpz_set)), INIT_SET(API_0(mpz_init_set)), CLEAR(API_0(mpz_clear)))

An operator OP can be defined, omitted or disabled:

  • ( OP(f) ): the function f is the method of the operator OP
  • ( ): the operator NEW OP omitted, and the default global operation for OP is used.
  • ( OP(0) ): the operator OP is disabled, and it can never be used.

Which OPLIST to use?

My type is:

  • a C Boolean: M_BOOL_OPLIST (M_DEFAULT_OPLIST also works partially),
  • a C integer or a C float: M_DEFAULT_OPLIST (it can also be omitted),
  • a C enumerate: M_ENUM_OPLIST,
  • a pointer to something (the contained do nothing on the pointed object): M_PTR_OPLIST,
  • a plain structure that can be init/copy/compare with memset/memcpy/memcmp: M_POD_OPLIST,
  • a plain structure that is passed by reference using [1] and can be init,copy,compare with memset,memcpy,memcmp: M_A1_OPLIST,
  • a type that offers name_init, name_init_set, name_set, name_clear methods: M_CLASSIC_OPLIST,
  • a const string (const char *) that is neither freed nor moved: M_CSTR_OPLIST,
  • a M*LIB string_t: STRING_OPLIST,
  • a M*LIB container: the OPLIST of the used container,
  • other things: you need to provide a custom OPLIST to your type.

Note: The precise exported methods of the Oplist depend of the version of the C language used. Typically, in C11 mode, the M_DEFAULT_OPLIST exports all needed methods to handle generic input/output of int/floats (using _Generic) whereas it is not possible in C99 mode.

This explains why JSON import/export is only available in C11 mode (See below chapter).

Memory Allocation

Memory Allocation functions can be globally set by overriding the following macros before using the definition _DEF macros:

  • M_MEMORY_ALLOC (type): return a pointer to a new object of type 'type'.
  • M_MEMORY_DEL (ptr): free the single object pointed by 'ptr'.
  • M_MEMORY_REALLOC (type, ptr, number): return a pointer to an array of 'number' objects of type 'type', reusing the old array pointed by 'ptr'. 'ptr' can be NULL, in that case the array will be created.
  • M_MEMORY_FREE (ptr): free the array of objects pointed by 'ptr'.

ALLOC & DEL operators are supposed to allocate fixed size single element object (no array). Theses objects are not expected to grow. REALLOC & 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).

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 & DEL in the oplist given to a container so that only the container will use these memory allocation functions.

Out-of-memory error

When a memory exhaustion is reached, the global macro "M_MEMORY_FULL" is called and the function returns immediately after. 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.

Indeed, 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.

It can however be overloaded to handle other policy for error handling like:

  • throwing an error (in that case, the user is responsible to free memory of the allocated objects - destructor can still be called),
  • set a global error and handle it when the function returns,
  • other policy.

This function takes the size in bytes of the memory that has been tried to be allocated.

If needed, this macro shall be defined prior to instantiate the structure.

NOTE: Throwing an error is not fully supported yet. Some help from the library is needed to avoid losing memory. See issue #15.

ERRORS & COMPILERS

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_MISTMACH: 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_DEFAULT_TYPE: The oplist M_DEFAULT_OPLIST (directly or indirectly) has been used with the given type, but the given type is not a default type. You need to give the right oplist for this type.

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 always in one of the oplist definition.

Examples of typical errors:

  • lack of inclusion of an header,
  • overriding locally operator names by macros (like NEW, DEL, INIT, OPLIST, ...),
  • lack of ( ) or double level of ( ) around the oplist,
  • an unknown variable (example using DEFAULT_OPLIST instead of M_DEFAULT_OPLIST or M_STRING_OPLIST instead of STRING_OPLIST),
  • the name given to the oplist is not the same as the one used to define the methods,
  • use of a type instead of an oplist in the OPLIST definition,
  • a missing sub oplist in the OPLIST definition.

A good way to avoid theses errors is to register the oplist globally as soon as you define the container.

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 > test-file.i
      perl -pi -e 's/;/;\n/g' test-file.i
      cc -std=c99 -c -Wall test-file.i

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.

Benchmarks

All bench codes are available in the bench directory. The results are available in a separate page.

External Reference

Many other implementation of generic container libraries in C exist. For example:

Each can be classified into one of the following concept:

  • Each object is handled through a pointer to void (with potential registered callbacks to handle the contained objects for the specialized methods). From a user point of view, this makes the code harder to use (as you don't have any help from the compiler) and type unsafe with a lot of cast (so no formal proof of the code is possible). This also generally generate slower code (even if using link time optimization, this penalty can be reduced). Properly used, it can yet be the most space efficient for the code, but can consume a lot more for the data due to the obligation of using pointers. This is however the easiest to design & code.
  • Macros are used to access structures in a generic way (using known fields of a structure - typically size, number, etc.). From a user point of view, this can create subtitle bug in the use of the library (as everything is done through macro expansion in the user defined code) or hard to understand warnings. This can generates fully efficient code. From a library developer point of view, this can be quite limiting in what you can offer.
  • A known structure is put in an intrusive way in the type of all the objects you wan to handle. From a user point of view, he needs to modify its structure and has to perform all the allocation & deallocation code itself (which is good or bad depending on the context). This can generate efficient code (both in speed and size). From a library developer point of view, this is easy to design & code. You need internally a cast to go from a pointer to the known structure to the pointed object (a reverse of offsetof) that is generally type unsafe (except if mixed with the macro generating concept). This is quite limitation in what you can do: you can't move your objects so any container that has to move some objects is out-of-question (which means that you cannot use the most efficient container).
  • Header files are included multiple times with different contexts (some different values given to defined macros) in order to generate different code for each type. From a user point of view, this creates a new step before using the container: an instantiating stage that has to be done once per type and per compilation unit (The user is responsible to create only one instance of the container, which can be troublesome if the library doesn't handle proper prefix for its naming convention). The debug of the library is generally easy and can generate fully specialized & efficient code. Incorrectly used, this can generate a lot of code bloat. Properly used, this can even create smaller code than the void pointer variant. The interface used to configure the library can be quite tiresome in case of a lot of specialized methods to configure: it doesn't enable to chain the configuration from a container to another one easily. It also cannot have heavy customization of the code.
  • Macros are used to generate context-dependent C code enabling to generate code for different type. This is pretty much like the headers solution but with added flexibility. From a user point of view, this creates a new step before using the container: an instantiating stage that has to be done once per type and per compilation unit (The user is responsible to create only one instance of the container, which can be troublesome if the library doesn't handle proper prefix for its naming convention). This can generate fully specialized & efficient code. Incorrectly used, this can generate a lot of code bloat. Properly used, this can even create smaller code than the void pointer variant. From a library developer point of view, the library is harder to design and to debug: everything being expanded in one line, you can't step in the library (there is however a solution to overcome this limitation by adding another stage to the compilation process). You can however see the generated code by looking at the preprocessed file. You can perform heavy context-dependent customization of the code (transforming the macro preprocessing step into its own language). Properly done, you can also chain the methods from a container to another one easily, enabling expansion of the library. Errors within the macro expansion are generally hard to decipher, but errors in code using containers are easy to read and natural.

M*LIB's category is mainly the last one. Some macros are also defined to access structure in a generic way, but they are optional. There are also intrusive containers.

M*LIB main added value compared to other libraries is its oplist feature enabling it to chain the containers and/or use complex types in containers: list of array of dictionary of C++ objects are perfectly supported by M*LIB.

For the macro-preprocessing part, other libraries also exist. For example:

For the string library, there is for example:

API Documentation

The M*LIB reference card is available here.

M-LIST

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 representing a sequence.

LIST_DEF(name, type, [, oplist])

Define the singly linked list named 'name##_t' that contains objects of type 'type' and the 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 and functions to handle the container. This definition shall be done once per name and per compilation unit. It also define the iterator name##_it_t and its associated methods as "static inline" functions.

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).

The type oplist is expected to have at least the following operators (INIT_SET, SET and CLEAR). If there is no given oplist, the default oplist for standard C type is used or a globally registered oplist is used if there is one available. The created methods use the operators to init, set and clear the contained object.

For this structure, the back is always the first element, and the front is the last element: the list grows from the back.

Example:

    LIST_DEF(list_uint, unsigned int)

    list_uint_t list_of_integer;

    void fi(unsigned int z) {
            list_uint_push_back (list_of_integer, z);
    }
    
    LIST_DEF(list_mpz, mpz_t,                                               \
            (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear)))

    list_mpz_t my_list;

    void fz(mpz_t z) {
            list_mpz_push_back (my_list, z);
    }

If the given oplist contain the method MEMPOOL, then LIST_DEF macro will create a dedicated mempool that is named with the given value of the method MEMPOOL. This mempool (see mempool chapter) is optimized for this kind of list:

  • it creates a mempool named by the concatenation of "name" and "_mempool",
  • it creates a variable named by the value of the method MEMPOOL with the linkage defined by the value of the method MEMPOOL_LINKAGE (can be extern, static or none). This variable is shared by all lists of the same type.
  • it links the memory allocation of the list to use this mempool with this variable.

mempool create heavily efficient list. However it is only worth the effort in some heavy performance context. The created mempool has to be explicitly initialized before using any methods of the created list by calling mempool_list_name_init(variable) and cleared by calling mempool_list_name_clear(variable).

Example:

    LIST_DEF(list_uint, unsigned int, (MEMPOOL(list_mpool), MEMPOOL_LINKAGE(static)))

    static void test_list (size_t n)
    {
      list_uint_mempool_init(list_mpool);
      M_LET(a1, LIST_OPLIST(uint)) {
          for(size_t i = 0; i < n; i++)
              list_uint_push_back(a1, rand_get() );
      }
      list_uint_mempool_clear(list_mpool);
    }

LIST_DEF_AS(name, name_t, name_it_t, type, [, oplist])

Same as LIST_DEF except the name of the types name_t, name_it_t are provided.

LIST_OPLIST(name [, oplist])

Return the oplist of the list defined by calling LIST_DEF & LIST_DUAL_PUSH_DEF with name & oplist. If there is no given oplist, the default oplist for standard C type is used.

Created methods

In the following methods, name stands for the name given to the macro that is used to identify the type. The following types are automatically defined by the previous definition macro:

name_t

Type of the list of 'type'.

name_it_t

Type of an iterator over this list.

The following methods are automatically created by the previous definition macro:

void name_init(name_t list)

Initialize the list 'list' (aka constructor) to an empty list.

void name_init_set(name_t list, const name_t ref)

Initialize the list 'list' (aka constructor) and set it to a copy of 'ref'.

void name_set(name_t list, const name_t ref)

Set the list 'list' to the a copy of 'ref'.

void name_init_move(name_t list, name_t ref)

Initialize the list 'list' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared and can no longer be used.

void name_move(name_t list, name_t ref)

Set the list 'list' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared and can no longer be used.

void name_clear(name_t list)

Clear the list 'list (aka destructor), calling the CLEAR method of all the objects of the list and freeing memory. The list can't be used anymore, except with a constructor.

void name_clean(name_t list)

Clean the list (the list becomes empty). It is like CLEAR but the list remains initialized and empty.

const type *name_back(const name_t list)

Return a constant pointer to the data stored in the back of the list.

void name_push_back(name_t list, const type value)

Push a new element within the list 'list' with the value 'value' contained within.

type *name_push_raw(name_t list)

Push a new element within the list 'list' without initializing it and returns a pointer to the non-initialized data. The first thing to do after calling this function is to initialize the data using the proper constructor. This enables using more specialized constructor than the generic one. Return a pointer to the non-initialized data.

type *name_push_new(name_t list)

Push a new element within the list 'list' and initialize it with the default constructor of the type. Return a pointer to the initialized object. This method is only defined if the type of the element defines an INIT method.

void name_push_move(name_t list, type *value)

Push a new element within the list 'list' with the value '*value' contained within by stealing as much resources from '*value' than possible. Afterward '*value' is cleared and cannot longer be used.

void name_pop_back(type *data, name_t list)

Pop a element from the list 'list', and set *data to this value if data is not the NULL pointer (otherwise only pop the data).

void name_pop_move(type *data, name_t list)

Pop a element from the list 'list', and initialize and set *data to this value by stealing as much resources from the list as possible. data cannot be a NULL pointer.

bool name_empty_p(const name_t list)

Return true if the list is empty, false otherwise.

void name_swap(name_t list1, name_t list2)

Swap the list 'list1' and 'list2'.

void name_it(name_it_t it, const name_t list)

Set the iterator 'it' to the back(=first) element of 'list'. 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 list)

Set the iterator 'it' to a non valid element of the list. 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 top(=last) element 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 it2.

void name_next(name_it_t it)

Move the iterator 'it' to the next element of the list, i.e. from the back (=first) element to the front (=last) element.

type *name_ref(name_it_t it)

Return a pointer to the element pointed by the iterator. This pointer remains valid until the element is destroyed in the list.

const type *name_cref(const name_it_t it)

Return a constant pointer to the element pointed by the iterator. This pointer remains valid until the element is destroyed in the list.

type *name_get(const name_t list, size_t i)

Return a pointer to the element i-th of the list (from 0). It is assumed than i is within the size of the list. This function is slow and iterates linearly over the element of the elements until it reaches the desired element.

const type *name_cget(const name_t list, size_t i)

Return a constant pointer to the element i-th of the list (from 0). It is assumed than i is within the size of the list. This function is slow and iterates linearly over the element of the elements until it reaches the desired element.

size_t name_size(const name_t list)

Return the number elements of the list (aka size). Return 0 if there no element. This function is slow and iterates linearly over all the element to compute the size.

void name_insert(name_t list, const name_it_t it, const type x)

Insert 'x' after the position pointed by 'it' (which is an iterator of the list 'list') or if 'it' doesn't point anymore to a valid element of the list, it is added as the back (=first) element of the 'list'

void name_remove(name_t list, name_it_t it)

Remove the element 'it' from the list 'list'. After wise, 'it' points to the next element of the list.

void name_splice_back(name_t list1, name_t list2, name_it_t it)

Move the element pointed by 'it' (which is an iterator of 'list2') from the list 'list2' to the back position of 'list1'. After wise, 'it' points to the next element of 'list2'.

void name_splice_at(name_t list1, name_it_t it1, name_t list2, name_it_t it2)

Move the element pointed by 'it2' (which is an iterator of 'list2') from the list 'list2' to the position just after 'it1' in the list 'list1'. After wise, 'it2' points to the next element of 'list2' and 'it1' points to the inserted element in 'list1'. If 'it1' is the end position, it inserts it at the back (just like _insert_at).

void name_splice(name_t list1, name_t list2)

Move all the element of 'list2' into 'list1", moving the last element of 'list2' after the first element of 'list1'. After-wise, 'list2' remains initialized but is emptied.

void name_reverse(name_t list)

Reverse the order of the list.

void name_get_str(string_t str, const name_t list, bool append)

Set 'str' to the formatted string representation of the list 'list' (if 'append' is false) or append 'str' with this representation (if 'append' is true). This method is only defined if the type of the element defines a GET_STR method itself.

bool name_parse_str(name_t list, const char str[], const char **endp)

Parse the formatted string 'str', that is assumed to be a string representation of a list and set 'list' to this representation. This method is only defined if the type of the element defines a PARSE_STR & INIT methods itself. 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.

void name_out_str(FILE *file, const name_t list)

Generate a formatted string representation of the list 'list' and outputs it into the FILE 'file'. This method is only defined if the type of the element defines a OUT_STR method itself.

void name_in_str(name_t list, FILE *file)

Read from the file 'file' a formatted string representation of a list and set 'list' to this representation. This method is only defined if the type of the element defines a IN_STR & INIT method itself.

bool name_equal_p(const name_t list1, const name_t list2)

Return true if both lists 'list1' and 'list2' are equal. This method is only defined if the type of the element defines a EQUAL method itself.

size_t name_hash(const name_t list)

Return a hash value of 'list'. This method is only defined if the type of the element defines a HASH method itself.

LIST_DUAL_PUSH_DEF(name, type[, oplist])

Define the singly linked list named 'name##_t' that contains the objects of type 'type' and the 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 and functions to handle the container. 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 too.

The only difference with the list defined by LIST_DEF is the support of the method PUSH_FRONT in addition to PUSH_BACK (therefore the DUAL PUSH name). There is still only POP method (POP_BACK). The head of the list is a bit bigger to be able to handle such methods to work. This enables this list to be able to represent both stack (PUSH_BACK + POP_BACK) and queue (PUSH_FRONT + POP_BACK).

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 on the list.

The object oplist is expected to have at least the following operators (INIT_SET, SET and CLEAR). If there is no given oplist, the default oplist for standard C type is used or a globally registered oplist is used. The created methods will use the operators to init, set and clear the contained object.

For this structure, the back is always the first element, and the front is the last element.

Example:

    LIST_DUAL\_PUSH\_DEF(list_mpz, mpz_t,                                   \
            (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear)))

    list_mpz_t my_list;

    void f(mpz_t z) {
            list_mpz_push_front (my_list, z);
            list_mpz_pop_back (z, my_list);
    }

If the given oplist contain the method MEMPOOL, then macro will create a dedicated mempool that is named with the given value of the method MEMPOOL, optimized for this kind of list:

  • it creates a mempool named by the concatenation of "name" and "_mempool",
  • it creates a variable named by the value of the method MEMPOOL with linkage defined by the value of the method MEMPOOL_LINKAGE (can be extern, static or none), this variable will be shared by all lists of the same type.
  • it overwrites memory allocation of the created list to use this mempool with this variable.

mempool creates heavily efficient list but it will be only worth the effort in some heavy performance context. The created mempool has to be initialized before using any methods of the created list by calling mempool_list_name_init(variable) and cleared by calling mempool_list_name_clear(variable).

The methods follow closely the methods defined by LIST_DEF.

LIST_DUAL_PUSH_DEF_AS(name, name_t, name_it_t, type, [, oplist])

Same as LIST_DUAL_PUSH_DEF except the name of the types name_t, name_it_t are provided.

Created methods

In the following methods, name stands for the name given to the macro that is used to identify the type. The following types are automatically defined by the previous macro:

name_t

Type of the list of 'type'.

name_it_t

Type of an iterator over this list.

The following methods are automatically and properly created by the previous macro.

void name_init(name_t list)

Initialize the list 'list' (aka constructor) to an empty list.

void name_init_set(name_t list, const name_t ref)

Initialize the list 'list' (aka constructor) and set it to the value of 'ref'.

void name_set(name_t list, const name_t ref)

Set the list 'list' to the value of 'ref'.

void name_init_move(name_t list, name_t ref)

Initialize the list 'list' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared and can no longer be used.

void name_move(name_t list, name_t ref)

Set the list 'list' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared and can no longer be used.

void name_clear(name_t list)

Clear the list 'list (aka destructor). The list can't be used anymore, except with a constructor.

void name_clean(name_t list)

Clean the list (the list becomes empty). The list remains initialized but is empty.

const type *name_back(const name_t list)

Return a constant pointer to the data stored in the back of the list.

void name_push_back(name_t list, type value)

Push a new element within the list 'list' with the value 'value' into the back of the list.

type *name_push_back_raw(name_t list)

Push a new element within the list 'list' without initializing it into the back of the list and returns a pointer to the non-initialized data. The first thing to do after calling this function is to initialize the data using the proper constructor. This enables to use a more specialized constructor than the generic one. Return a pointer to the non-initialized data.

type *name_push_back_new(name_t list)

Push a new element within the list 'list' into the back of the list and initialize it with the default constructor of the type. Return a pointer to the initialized object. This method is only defined if the type of the element defines an INIT method.

void name_push_back_move(name_t list, type *value)

Push a new element within the list 'list' with the value '*value' ,by stealing as much resources from '*value' as possible, into the back of the list. Afterwards, *value is cleared and cannot be used anymore. value cannot be NULL.

const type *name_front(const name_t list)

Return a constant pointer to the data stored in the front of the list.

void name_push_front(name_t list, type value)

Push a new element within the list 'list' with the value 'value' contained within into the front of the list.

type *name_push_front_raw(name_t list)

Push a new element within the list 'list' without initializing it into the front of the list and returns a pointer to the non-initialized data. The first thing to do after calling this function is to initialize the data using the proper constructor. This enables to use a more specialized constructor than the generic one. Return a pointer to the non-initialized data.

type *name_push_front_new(name_t list)

Push a new element within the list 'list' into the front of the list and initialize it with the default constructor of the type. Return a pointer to the initialized object. This method is only defined if the type of the element defines an INIT method.

void name_push_front_move(name_t list, type *value)

Push a new element within the list 'list' with the value '*value' ,by stealing as much resources from '*value' as possible, into the front of the list. Afterwards, *value is cleared and cannot be used anymore. value cannot be NULL.

void name_pop_back(type *data, name_t list)

Pop a element from the list 'list' and set *data to this value if data is not NULL.

void name_pop_move(type *data, name_t list)

Pop a element from the list 'list' and initialize and set *data to this value, stealing as much resources from the list as possible.

bool name_empty_p(const name_t list)

Return true if the list is empty, false otherwise.

void name_swap(name_t list1, name_t list2)

Swap the list 'list1' and 'list2'.

void name_it(name_it_t it, name_t list)

Set the iterator 'it' to the back(=first) element of 'list'. 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 list)

Set the iterator 'it' to an invalid reference of 'list'. 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 top(=last) element 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 it2.

void name_next(name_it_t it)

Move the iterator 'it' to the next element of the list, ie. from the back (=first) element to the front(=last) element.

type *name_ref(name_it_t it)

Return a pointer to the element pointed by the iterator. This pointer remains valid until the object is destroyed.

const type *name_cref(const name_it_t it)

Return a constant pointer to the element pointed by the iterator. This pointer remains valid until the object is destroyed.

size_t name_size(const name_t list)

Compute and return the number elements of the list (aka size). Return 0 if there no element.

void name_insert(name_t list, const name_it_t it, const type x)

Insert 'x' after the position pointed by 'it' (which is an iterator of the list 'list') or if 'it' doesn't point anymore to a valid element of the list, it is added as the back (=first) element of the 'list'

void name_remove(name_t list, name_it_t it)

Remove the element 'it' from the list 'list'. After wise, 'it' points to the next element of the list.

void name_splice_back(name_t list1, name_t list2, name_it_t it)

Move the element pointed by 'it' (which is an iterator of 'list2') from the list 'list2' to the back position of 'list1'. After wise, 'it' points to the next element of 'list2'.

void name_splice(name_t list1, name_t list2)

Move all the element of 'list2' into 'list1", moving the last element of 'list2' after the first element of 'list1'. After-wise, 'list2' is emptied.

void name_reverse(name_t list)

Reverse the order of the list.

void name_get_str(string_t str, const name_t list, bool append)

Generate a formatted string representation of the list 'list' and set 'str' to this representation (if 'append' is false) or append 'str' with this representation (if 'append' is true). This method is only defined if the type of the element defines a GET_STR method itself.

bool name_parse_str(name_t list, const char str[], const char **endp)

Parse the formatted string 'str' that is assumed to be a string representation of a list and set 'list' to this representation. This method is only defined if the type of the element defines PARSE_STR & INIT methods itself. 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.

void name_out_str(FILE *file, const name_t list)

Generate a formatted string representation of the list 'list' and outputs it into the FILE 'file'. This method is only defined if the type of the element defines a OUT_STR method itself.

void name_in_str(name_t list, FILE *file)

Read from the file 'file' a formatted string representation of a list and set 'list' to this representation. This method is only defined if the type of the element defines a IN_STR & INIT method itself.

bool name_equal_p(const name_t list1, const name_t list2)

Return true if both lists 'list1' and 'list2' are equal. This method is only defined if the type of the element defines a EQUAL method itself.

size_t name_hash(const name_t list)

Return a hash value of 'list'. This method is only defined if the type of the element defines a HASH method itself.

M-ARRAY

An array is a growable collection of element that are individually indexable.

ARRAY_DEF(name, type [, oplist])

Define the array 'name##_t' that contains the objects of type 'type' 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 also define the iterator name##_it_t and its associated methods as "static inline" functions.

The object oplist is expected to have at least the following operators (CLEAR), and usually (INIT, INIT_SET, SET and CLEAR) otherwise default operators are used. If there is no given oplist, the default oplist for standard C type is used or a globally registered oplist is used. The created methods will use the operators to init-and-set, set and clear the contained object.

Example:

    ARRAY_DEF(array_mpfr_t, mpfr,                                                                  \
       (INIT(mpfr_init), INIT_SET(mpfr_init_set), SET(mpfr_set), CLEAR(mpfr_clear)))

    array_mpfr_t my_array;

    void f(mpfr_t z) {
            array_mpfr_push_back (my_array, z);
    }

ARRAY_DEF_AS(name, name_t, name_it_t, type, [, oplist])

Same as ARRAY_DEF except the name of the types name_t, name_it_t are provided.

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 default oplist for standard C type is used.

Created methods

In the following methods, name stands for the name given to the macro. This is used to identify the type. The following types are automatically defined by the previous macro:

name_t

Type of the array of 'type'.

name_it_t

Type of an iterator over this array.

The following methods are automatically and properly created by the previous macros:

void name_init(name_t array)

Initialize the array 'array' (aka constructor) to an empty array.

void name_init_set(name_t array, const name_t ref)

Initialize the array 'array' (aka constructor) and set it to the value of 'ref'. This method is created if the INIT_SET & SET operators are provided.

void name_set(name_t array, const name_t ref)

Set the array 'array' to the value of 'ref'. This method is created if the INIT_SET & SET operators are provided.

void name_init_move(name_t array, name_t ref)

Initialize the array 'array' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared.

void name_move(name_t array, name_t ref)

Set the array 'array' by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared.

void name_clear(name_t array)

Clear the array 'array (aka destructor).

void name_clean(name_t array)

Clean the array (the array becomes empty but remains initialized).

type *name_push_raw(name_t array)

Push the needed storage of a new element into the back of the array 'array' without initializing it and return a pointer to the non-initialized data. The first thing to do after calling this function is to initialize the data using the proper constructor. This enables to use a more specialized constructor than the generic one. It is recommended to use other _push function if possible rather than this one as it is low level and error prone.

void name_push_back(name_t array, const type value)

Push a new element into the back of the array 'array' with the value 'value' contained within. This method is created if the INIT_SET operator is provided.

type *name_push_new(name_t array)

Push a new element into the back of the array 'array' and initialize it with the default constructor. Return a pointer to this created element. This method is only defined if the type of the element defines an INIT method.

void name_push_move(name_t array, type *val)

Push '*val' a new element into the back of the array 'array' by stealing as much resources as possible from '*val'. After-wise '*x' is cleared. This method is created if the INIT_SET or INIT_MOVE operator is provided.

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' contained within. 'key' shall be a valid position of the array: from 0 to the size of array (included). This method is created if the INIT_SET operator is provided.

void name_pop_back(type *data, name_t array)

Pop a element from the back of the array 'array' and set *data to this value if data is not NULL (if data is NULL, the popped data is cleared). This method is created if the SET or INIT_MOVE operator is provided.

void name_pop_move(type *data, name_t array)

Pop a element from the back of the array 'array' and initialize *data with this value by stealing as much from the array as possible. This method is created if the INIT_SET or INIT_MOVE 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, clearing them. This method is only defined if the type of the element defines an INIT method.

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. 'key' shall be within the size of the array. This method is created if the SET or INIT_MOVE operator is provided.

const type *name_front(const name_t array)

Return a constant pointer to the first element of the array.

const type *name_back(const name_t array)

Return a constant pointer to the last element of the array.

void name_set_at(name_t array, size_t i, type value)

Set the element 'i' of array 'array' to 'value'. 'i' shall be within 0 to the size of the array (excluded). This method is created if the INIT_SET operator is provided.

type *name_get(name_t array, size_t i)

Return a pointer to the element 'i' of the array. 'i' shall be within 0 to the size of the array (excluded). The returned pointer cannot be NULL. This pointer remains valid until the array is modified by another method.

const type *name_cget(const name_t it, size_t i)

Return a constant pointer to the element 'i' of the array. 'i' shall be within 0 to the size of the array (excluded). The returned pointer cannot be NULL. This pointer remains valid until the array is modified by another method.

type *name_get_at(name_t array, size_t i)

Return a pointer to the element 'i' of array 'array', by increasing the size of the array if needed (creating new elements with INIT). The returned pointer cannot be NULL. This method is only defined if the type of the element defines an INIT method. This pointer remains valid until the array is modified by another method.

bool name_empty_p(const name_t array)

Return true if the array is empty, false otherwise.

size_t name_size(const name_t array)

Return the size of the array.

size_t name_capacity(const name_t array)

Return the capacity of the array.

void name_resize(name_t array, size_t size)

Resize the array 'array' to the size 'size' (initializing or clearing elements). This method is only defined if the type of the element defines an INIT method.

void name_reserve(name_t array, size_t capacity)

Extend or reduce the capacity of the 'array' to a rounded value based on 'capacity'. If the given capacity is below the current size of the array, the capacity is set to the size of the array.

void name_remove(name_t array, name_it_t it)

Remove the element pointed by the iterator 'it' from the array 'array'. 'it' shall be a valid iterator. Afterward 'it' points to the next element, or points to the end. This method is created 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(name_t array, name_it_t it, const type x)

Insert the object 'x' at the position 'it' of the array. 'it' shall be a valid iterator of the array. This method is created if the INIT_SET operator is provided.

void name_insert_v(name_t array, size_t i, size_t j)

Insert from the element 'i' (included) to the element 'j' (excluded) new empty elements to the array. 'i' and 'j' shall be within the size of the array, and i < j. This method is only defined if the type of the element defines an INIT method.

void name_swap(name_t array1, name_t array2)

Swap the array 'array1' and 'array2'.

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_it(name_it_t it, name_t array)

Set the iterator 'it' to the first element of 'array'.

void name_it_last(name_it_t it, name_t array)

Set the iterator 'it' to the last element of 'array'.

void name_it_end(name_it_t it, name_t array)

Set the iterator 'it' to the end of 'array'.

void name_it_set(name_it_t it1, name_it_t it2)

Set the iterator 'it1' to 'it2'.

bool name_end_p(name_it_t it)

Return true if the iterator doesn't reference a valid element anymore.

bool name_last_p(name_it_t it)

Return true if the iterator references the last element of the array, or doesn't reference a valid element.

bool name_it_equal_p(const name_it_t it1, const name_it_t it2)

Return true if both iterators reference the same element.

void name_next(name_it_t it)

Move the iterator 'it' to the next element of the array.

void name_previous(name_it_t it)

Move the iterator 'it' to the previous element of the array.

type *name_ref(name_it_t it)

Return a pointer to the element pointed by the iterator. This pointer remains valid until the array is modified by another method.

const type *name_cref(const name_it_t it)

Return a constant pointer to the element pointed by the iterator. This pointer remains valid until the array is modified by another method.

void name_special_sort(name_t array)

Sort the array 'array'. This method is defined if the type of the element defines CMP method. This method uses the qsort function of the C library.

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_get_str(string_t str, const name_t array, bool append)

Generate a formatted string representation of the array 'array' and set 'str' to this representation (if 'append' is false) or append 'str' with this representation (if 'append' is true). This method is only defined if the type of the element defines a GET_STR method itself.

bool name_parse_str(name_t array, const char str[], const char **endp)

Parse the formatted string 'str' that is assumed to be a string representation of an array and set 'array' to this representation. This method is only defined if the type of the element defines both PARSE_STR & INIT methods itself. 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.

void name_out_str(FILE *file, const name_t array)

Generate a formatted string representation of the array 'array' and outputs it into the FILE 'file'. This method is only defined if the type of the element defines a OUT_STR method itself.

void name_in_str(name_t array, FILE *file)

Read from the file 'file' a formatted string representation of an array and set 'array' to this representation. This method is only defined if the type of the element defines both IN_STR & INIT methods itself.

bool name_equal_p(const name_t array1, const name_t array2)

Return true if both arrays 'array1' and 'array2' are equal. This method is only defined if the type of the element defines a EQUAL method itself.

size_t name_hash(const name_t array)

Return an hash value of 'array'. This method is only defined if the type of the element defines a HASH method itself.

void name_splice(name_t array1, name_t array2)

Merge the elements of 'array2' in 'array1' at its end. Afterwards, 'array2' is empty.

M-DEQUE

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])

Define 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 and functions to handle the container. 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 is expected to have at least the following operators (INIT, INIT_SET, SET and CLEAR), otherwise default operators are used. If there is no given oplist, the default oplist for standard C type is used or a globally registered oplist is used. The created methods will use the operators to init, set and clear the contained object.

Example:

    DEQUE_DEF(deque_mpz, mpz_t,                                               \
            (INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear)))

    deque_mpz_t my_deque;

    void f(mpz_t z) {
            deque_mpz_push_back (my_deque, z);
    }

DEQUE_DEF_AS(name, name_t, name_it_t, type, [, oplist])

Same as DEQUE_DEF except the name of the types name_t, name_it_t are provided.

DEQUE_OPLIST(name [, oplist])

Return the oplist of the deque defined by calling DEQUE_DEF with name & oplist.

Created methods

In the following methods, name stands for the name given to the macro that is used to identify the type. The following types are automatically defined by the previous macro:

name_t

Type of the deque of 'type'.

name_it_t

Type of an iterator over this deque.

The following methods are automatically and properly created by the previous macro.

void name_init(name_t deque)

Initialize the deque 'deque' (aka constructor) to an empty deque.

void name_init_set(name_t deque, const name_t ref)

Initialize the deque 'deque' (aka constructor) and set it to the value of 'ref'.

void name_set(name_t deque, const name_t ref)

Set the deque 'deque' to the value of 'ref'.

void name_init_move(name_t deque, name_t ref)

Initialize the deque 'deque' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared and can no longer be used.

void name_move(name_t deque, name_t ref)

Set the deque 'deque' (aka constructor) by stealing as many resources from 'ref' as possible. After-wise 'ref' is cleared and can no longer be used.

void name_clear(name_t deque)

Clear the deque 'deque (aka destructor). The deque can't be used anymore, except with a constructor.

void name_clean(name_t deque)

Clean the deque (the deque becomes empty). The deque remains initialized but is empty.

const type *name_back(const name_t deque)

Return a constant pointer to the data stored in the back of the deque.

void name_push_back(name_t deque, type value)

Push a new element within the deque 'deque' with the value 'value' at the back of the deque.

type *name_push_back÷_raw(name_t deque)

Push at the back a new element within the deque 'deque' without initializing it and returns a pointer to the non-initialized data. The first thing to do after calling this function is to initialize the data using the proper constructor. This enables to use a more specialized constructor than the generic one. Return a pointer to the non-initialized data.

type *name_push_back_new(name_t deque)

Push at the back a new element within the deque 'deque' and initialize it with the default constructor of the type. Return a pointer to the initialized object.

void name_pop_back(type *data, name_t deque)

Pop a element from the deque 'deque' and set *data to this value. If data pointer is NULL, then the popped value is discarded.

const type *name_front(const name_t deque)

Return a constant pointer to the data stored in the front of the deque.

void name_push_front(name_t deque, type value)

Push at the front a new element within the deque 'deque' with the value 'value'.

type *name_push_front_raw(name_t deque)

Push at the front a new element within the deque 'deque' without initializing it and returns a pointer to the non-initialized data. The first thing to do after calling this function is to initialize the data using the proper constructor. This enables to use a more specialized constructor than the generic one. Return a pointer to the non-initialized data.

type *name_push_front_new(name_t deque)

Push at the front a new element within the deque 'deque' and initialize it with the default constructor of the type. Return a pointer to the initialized object.

void name_pop_front(type *data, name_t deque)

Pop a element from the deque 'deque' and set *data to this value. If data pointer is NULL, then the pop-ed value is discarded.

bool name_empty_p(const name_t deque)

Return true if the deque is empty, false otherwise.

void name_swap(name_t deque1, name_t deque2)

Swap the deque 'deque1' and 'deque2'.

void name_it(name_it_t it, name_t deque)

Set the iterator 'it' to the first element of 'deque' (aka the front). 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.

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 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 it2.

void name_next(name_it_t it)

Move the iterator 'it' to the next element of the deque, ie. from the front element to the back element.

void name_previous(name_it_t it)

Move the iterator 'it' to the previous element of the deque, ie. from the back element to the front element.

type *name_ref(name_it_t it)

Return a pointer to the element pointed by the iterator. This pointer remains valid until the deque is modified by another method.

const type *name_cref(const name_it_t it)

Return a constant pointer to the element pointed by the iterator. This pointer remains valid until the deque is modified by another method.