map.h

/********************** # Map me ! *********************/
// **A unprecedented MT-safe implementation of a map library that can manage maps, sets and sorted lists and that can do it all with a minimalist interface.**
//
// (c) L. Farhi, 2024.
// Language: C (C11 or higher).

/* This library manages sorted maps, sorted sets and sorted lists, FIFO and LIFO queues (depending on how the "map" is created).
   It uses a balanced binary tree for blazing fast insertion and removal (O(log n)) and a doubly-linked list for fast traversing (O(n)).

> An outstanding, never seen before, fast, MT-safe implementation of map container that can do everything.

It all came from a simple idea:

- Why iterating on (traversing) elements of a collection if not for operating on them ?
- To operate on these elements, it is necessary to iterate on them first.

Iterating and operating are two bound actions. This departs from traditional approach found in usual collections.

Therefore, the library is based on an original paradigm: all operations on the elements of the map are applied through searching or traversing the map.

The interface has no more than 8 functions to do everything needed (create, read, update, insert, count, move, remove, destroy, etc.), all of them being MT-safe:

- `map_create`
- `map_destroy`
- `map_size` (MT-safe)
- `map_insert_data` (MT-safe)
- `map_find_key` (MT-safe)
- `map_traverse` (MT-safe)
- `map_traverse_backward` (MT-safe)
- `map_traverse_keys` (MT-safe)

They are detailed below.

- All calls are MT-safe: thread safety comes naturally and for free by design ; concurrent threads using the same "map" will synchronise (block and wait for each other).
- All calls are non-recursive.
*/

// ## Type definitions
#ifndef  __MAP_H__
#  define __MAP_H__

#  include <stddef.h>

// ### Map
// A map is an opaque Abstract Data Type (internally modelled as a sorted binary tree):
typedef struct map map;
/* The map stores (and keep track of) pointers to previously (automatically, statically or dynamically) allocated data:

  void *data;

> The data handled by the map is never copied and does not belong to the map. The map stores and tracks references (pointers) to objects and not objects themselves.
*/

// ### Key
// The key of the map is extracted from the data managed by it (generally but not necessarily a subset of it). A user-defined function of type `map_key_extractor` (passed to `map_create`) can be used to extract this subset.
// `map_key_extractor` is the type of the user-defined function that should return a pointer to the the part of `data` that contains the key of the map.
typedef const void *(*map_key_extractor) (void *data);
// > `data` is a pointer to `T`, where `T` is the type managed by the map. Use `(T *)data` to access its content.
// Should returns a pointer to the key component of `T`, where `T` is the type managed by the map.
// > The key returned by the functions of type `map_key_extractor` should not be allocated dynamically. If the key is calculated, its result might be stored in the structure of the data itself,
/* Example:

If the type of data is a structure as:

  enum class { NOUN, VERB, ADJECTIVE, ADVERB, PRONOUN, DETERMINER, PREPOSITION, CONJUNCTION, INTERJECTION };
  enum gender { MASCULINE, FEMININE, NEUTER };
  struct entry  // The type of the data managed by the map
  {
    struct word { char *spelling ; enum class class ; } word;
    enum gender gender ;
    char* definition;
  };

then, a key function could be:

  static const void* get_word (void* data)             // 'data' is supposed to be a pointer to 'struct entry'
  {
    return &((const struct entry *)data)->word;        // 'word' is declared as the subset of the 'data' that defines the key of the map.
  }

*/

// ### Key comparator
// The type of a user-defined function that compares two keys of elements of a map.
typedef int (*map_key_comparator) (const void *key_a, const void *key_b, const void *arg);
// > If `map_key_extractor` is not `0`, `key_a` and `key_b` are pointers to keys, as they would be returned by a function of type `map_key_extractor`. Use `(K *)key` to access its content.
// > Otherwise, `key_a` and `key_b` are pointers to `T`, where `T` is the type managed by the map. Use `(T *)data` to access its content.
// The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.
// The third argument `arg` receives the pointer that was passed to `map_create`.
/* Example:

  static int
  cmp_word (const void *p1, const void *p2, void *arg)
  {
    (void) arg;
    const struct word *w1 = p1;
    const struct word *w2 = p2;
    int ret = strcoll (w1->spelling, w2->spelling);
    if (!ret)
      ret = w1->class > w2->class ? 1 : w1->class < w2->class ? -1 : 0;
    return ret;
  }

*/

// ### Selector on elements of the map
// The type of a user-defined function that selects elements while traversing a map with `map_traverse` or `map_traverse_backward`. 
typedef int (*map_selector) (const void *data, void *sel_arg);
// The data of the element of the map is passed as the first argument of the map_selector.
// > `data` is a pointer to `T`, where `T` is the type managed by the map. Use `(T *)data` to access its content.
// The second argument `sel_arg` receives the pointer passed to `map_find_key`, `map_traverse` and `map_traverse_backward`.
// Should return `1` if the `data` conforms to the user-defined conditions (and should be selected by `map_traverse` or `map_traverse_backward`), `0` otherwise.

// ### Operator on elements of the map
// The type of a user-defined function that operates on (accesses, and optionally modifies or removes) an element of a map
// picked by `map_traverse`, `map_traverse_backward` or `map_find_key`.
typedef int (*map_operator) (void *data, void *op_arg, int *remove);
// The data of the element of the map is passed as the first argument of the `map_operator`.
// > `data` is a pointer to `T`, where `T` is the type managed by the map. Use `(T *)data` to access its content.
// The second argument `op_arg` receives the pointer passed to `map_traverse`, `map_traverse_backward` and `map_find_key`.
// The third argument `remove` receives a non-null pointer for which `*remove` is set to `0`.
// If (and only if) the operator sets `*remove` to a non-zero value,
//
//   - the element will be forgotten by the map thread-safely ; the element will **not** by deallocated automatically (since it was not copied on insertion with `map_insert_data`) ;
//   - the operator **should** ultimately free the data passed to it **if** it was allocated dynamically before insertion into the map with `map_insert_data` (otherwise data would be lost in memory leaks).
// The `map_operator` should return `1` if the operator should be applied on further elements of the map (continue), `0` otherwise (break). In other words,
// as soon as the operator returns `0`, it stops `map_traverse`, `map_traverse_backward` or `map_find_key`. 
// > The operator `map_operator` should neither modify the pointer returned by `map_key_extractor` nor its content (as evaluated by `map_key_comparator`). In other words, the key of the element in the map should remain untouched by `map_operator`, otherwise results are undefined.

// ## Interface

// ### Create a map
map *map_create (map_key_extractor get_key, map_key_comparator cmp_key, const void *cmp_arg, int unicity);
// Returns `0` if the map could not be allocated (and `errno` set to `ENOMEM`).
// Otherwise, returns a pointer to the created map.
// If not `0`, the comparison function `cmp_key` must return an integer less than, equal to, or greater than zero
// if the first argument is considered to be respectively less than, equal to, or greater than the second.
// `cmp_key` is applied on `get_key (data)` if `get_key` is not `0` ; otherwise, `cmp_key` is applied on `data` (where `data` is a pointer inserted by `map_insert_data`).
// > `cmp_key` must be set if `get_key` is set.
// The pointer `arg` (which can be `0`) is passed to the comparison function `cmp_key` (as third argument).

// If `unicity` is not `0`, elements are unique in the map (equal elements are not inserted and `map_insert_data` will return `0`).
// Otherwise, equal elements are ordered as they were inserted.

/* 7 possible uses, depending on `unicity`, `cmp_key` and `get_key`:

| Use            | `unicity` | `cmp_key` | `get_key` | Comment                                                                                                                          |
| -              | -         | -         | -         | -                                                                                                                                |
| Sorted map     | `1`       | Non-zero  | Non-zero  | Each key is unique in the map.                                                                                                   |
| Dictionary     | `0`       | Non-zero  | Non-zero  | Keys can have multiple entries in the map for the same key (entries are ordered as they are inserted.)                           |
| Sorted set     | `1`       | Non-zero  | `0`       | Elements are unique. `cmp_key` applies to inserted `data` (the `data` is the key).                                               |
| Sorted list    | `0`       | Non-zero  | `0`       | Equal elements are ordered as they are inserted. `cmp_key` applies to inserted `data` (the `data` is the key).                   |
| FIFO           | `0`       | `0`       | `0`       | Elements are appended after the last element. Use `map_traverse (m, MAP_REMOVE_ONE, &data, 0, 0)` to remove an element.          |
| LIFO           | `0`       | `0`       | `0`       | Elements are appended after the last element. Use `map_traverse_backward (m, MAP_REMOVE_ONE, &data, 0, 0)` to remove an element. |

For unsorted lists, sets or maps on type `T` of fixed size, a generic comparison function `MAP_GENERIC_CMP` is provided.
*/

// ### Destroy a map
int map_destroy (map *);
// Destroys an **empty** and previously created map.
// If the map is not empty, the map is not destroyed.
// Returns `0` (and `errno` set to `EPERM`) if the map is not empty (and the map is NOT destroyed), `1` otherwise.

// ### Retrieve the number of elements in a map
size_t map_size (map *);
// Returns the number of elements in a map.
// Note: if the map is used by several threads, `map_size` should better not be used since the size of the map can be modified any time by other threads.
// Complexity : 1. MT-safe.

// ### Add an element into a map
int map_insert_data (map *, void *data);
// Adds a previously allocated data into map and returns `1` if the element was added, `0` otherwise.
// > `data` should be a pointer to `T`, where `T` is the type managed by the map.
// > The map keeps track of `data` but `data` does not belong to (is not copied and stored in) the map after insertion. `*data` should persist until it is removed from the map (using `map_traverse` or `map_find_key`).
// > If `data` is a pointer to memory allocated dynamically, a destructor should be passed as an argument to operator `MAP_REMOVE_ALL` in case it would be used.
// `0` will be returned if `unicity` was set to `1` at creation of the map and a `data` with the same key is already in the map.
// Complexity : log n (1 if `cmp_key` or `get_key` is `0`). MT-safe. Non-recursive.
// > About one million elements can be inserted and sorted per second.

// ### Retrieve and remove elements from a map

// #### Find an element from its key
size_t map_find_key (struct map *map, const void *key, map_operator op, void *op_arg, map_selector sel, void *sel_arg);
// > `key` is a pointer to a key, as returned by a function of type `map_key_extractor` (if set) or a pointer to a `T` (if `map_key_extractor` is not set), where `T` is the type managed by the map.
// If `get_key` (as defined at map creation) is not null, applies `op` on the data of the elements in the map that matches the `key` (for which `cmp_key (get_key (data), key)` returns `0`), as long as `op` returns non-zero.
// If `get_key` is null, applies the operator `op` on the data of the elements in the map that matches the data (for which `cmp_key (data, key)` returns `0`), as long as `op` returns non-zero.
// If the selector `sel` is not null, elements for which `sel (data)` (where `data` is an element previously inserted into the map) returns `0` are ignored.
// If `op` is null, all the elements matching with the `key` and also selected by `sel` are found and counted.
// `op_arg` and `sel_arg` are passed as the second argument of operator `op` and selector `sel` respectively. For instance,
// `op_arg` could be used as a pointer to an aggregator of an aggregating function `op`.
// Returns the number of elements of the map that match `sel` (if set) and on which the operator `op` (if set) has been applied.
// Complexity : log n. MT-safe. Non-recursive.
// > `cmp_key` should have been previously set by `map_create` (otherwise, `0` is returned and `errno` is set to `EPERM`.)
// If `op` is null, `map_find_key` simply counts and returns the number of matching elements with the `key`.
// > `map_find_key`, `map_traverse`, `map_traverse_backward` and `map_insert_data` can call each other *in the same thread* (the first argument `map` can be passed again through the `op_arg` argument). Therefore,
// elements can be removed from (when `*remove` is set to `1` in `op`) or inserted into (when `map_insert_data` is called in `op`) the map *by the same thread* while finding elements.

// #### Traverse the elements of a map
size_t map_traverse (map * map, map_operator op, void *op_arg, map_selector sel, void *sel_arg);
size_t map_traverse_backward (map * map, map_operator op, void *op_arg, map_selector sel, void *sel_arg);
// Traverse (iterate on) the elements of the map.
// If the operator `op` is not null, it is applied on the data managed by the map, from the first element to the last (resp. the other way round), as long as the operator `op` returns non-zero.
// If the selector `sel` is not null, elements for which `sel (data)` (where `data` is an element previously inserted into the map) returns `0` are ignored. `map_traverse` (resp.`map_traverse_backward`) behaves as if the operator `op` would start with: `if (!sel (data, sel_arg)) return 1;`.
// `op_arg` and `sel_arg` are passed as the second argument of operator `op` and selector `sel` respectively. For instance,
// `op_arg` could be used as a pointer to an aggregator of an aggregating function `op`.
// Returns the number of elements of the map that match `sel` (if set) and on which the operator `op` (if set) has been applied.
// Complexity : n. MT-safe. Non-recursive.
// If `op` is null, all the elements are traversed without any further effect than counting the elements selected by `sel`. `map_traverse` and `map_traverse_backward` simply count and return the number of elements selected by `sel` (if set).
// If `op` and `sel `are null, `map_traverse` and `map_traverse_backward` simply count and return the number of elements in the map (as would `map_size`).
// > `map_find_key`, `map_traverse`, `map_traverse_backward` and `map_insert_data` can call each other *in the same thread* (the first argument `map` can be passed again through the `op_arg` argument). Therefore,
// elements can be removed from (when `*remove` is set to `1` in `op`) or inserted into (when `map_insert_data` is called in `op`) the map *by the same thread* while traversing elements.
// > Insertion while traversing should be done with care since an infinite loop **will** logically occur if, in `op`:
// >
// >  - while traversing forward: at least an equal or greater element is inserted (after the element being traversed) ;
// >  - while traversing backward: at least a lower element is inserted (before the element being traversed).

// ### Traverse the keys of a map
typedef void (*map_operator_on_key) (const void *key, void *op_arg);
size_t map_traverse_keys (map * map, map_operator_on_key op, void *op_arg);
// Iterates on the distinct keys of a map.
// > `key` is a pointer to a key, as returned by a function of type `map_key_extractor`.
// For each distinct key of a map, the operator `op` (if not null) is called once with the *key* (as returned by the declared `get_key` passed to `map_create`) passed as its first element, and `op_arg` as its second.
// Returns `0` if `get_key` is `0` (with `errno` set to `EPERM`), the number of keys otherwise.

// ### Predefined helper comparator for use with `map_create`.

// #### Generic comparison for unordered types.
extern const map_key_comparator MAP_GENERIC_CMP;
// For unsorted lists, sets or maps, a generic comparison function is provided. It is a wrapper around `memcmp`.
// This can be used with `map_create` when elements (with keys of fixed size) can be compared equal but can not be ordered with a lower than operator:
//
// - `MAP_GENERIC_CMP` is passed as the second argument to `map_create`.
// - The address of a persistent value equal to the size of the key must be passed as third argument to `map_create`.

// For instance, for a set of objects of type, say, `SpaceTimeRegion`:
//
//    static const size_t size = sizeof (SpaceTimeRegion);
//    map *m = map_create (0, MAP_GENERIC_CMP, &size, 1);

// ### Predefined useful and usual helper operators for use with `map_find_key`, `map_traverse` and `map_traverse_backward`.

// `map_operator` functions passed to `map_find_key`, `map_traverse` and `map_traverse_backward` can be user-defined according to one's need.
// But useful operators are provided below.

// #### Map operator to count elements.
extern const map_operator MAP_COUNT;
// When `0` or `MAP_COUNT` is used as `map_operator`, `map_find_key`, `map_traverse` and `map_traverse_backward` return the number of elements for which the selector operator returns 1.

// #### Map operator to check if at least one element verifies the selector operator.
extern const map_operator MAP_EXISTS_ONE;
// When the helper operator `MAP_EXISTS_ONE` is used, `map_find_key`, `map_traverse` and `map_traverse_backward` return `1`
// if the selector operator returns `1` for at least one element, `0` otherwise.

// #### Map operator to retrieve one element
// This map operator simply retrieves one element from the map.
extern const map_operator MAP_GET_ONE;
// > Its use is **not recommended** though. Actions on an element should better be directly integrated in the `map_operator` function.
// The helper operator `MAP_GET_ONE` retrieves an element found by `map_find_key`, `map_traverse` or `map_traverse_backward`
// and, if the parameter `op_arg` of `map_find_key`, `map_traverse` or `map_traverse_backward` is a non null pointer,
// it sets the pointer `op_arg` to the data of this element.
// > `op_arg` should be the address of an allocated pointer to type T (`&a` where `T* a = 0`), where `op_arg` is the argument passed to `map_find_key`, `map_traverse` or `map_traverse_backward`.
// Example: to get the last element, use `T *data = 0; if (map_traverse_backward (m, MAP_GET_ONE, &data, 0, 0)) { ... }`

// #### Map operator to retrieve and remove one element
// This map operator simply retrieves and removes one element from the map.
extern const map_operator MAP_REMOVE_ONE;
// > Its use is **not recommended** though. Actions on an element should better be directly integrated in the `map_operator` function.
// The helper operator `MAP_REMOVE_ONE` removes and retrieves an element found by `map_find_key`, `map_traverse` or `map_traverse_backward`
// and, if the parameter `op_arg` of `map_find_key`, `map_traverse` or `map_traverse_backward` is a non null pointer,
// it sets the pointer `op_arg` to the data of this element.
// > `op_arg` should be `0` or the address of an allocated pointer to type T set to 0 (`&a` where `T* a = 0`), where `op_arg` is the argument passed to `map_find_key`, `map_traverse` or `map_traverse_backward`.
// > The content of `a` **should** ultimately be free'd if it was allocated dynamically before insertion into the map with `map_insert_data` (otherwise data would be lost in memory leaks).
/* Example

If `m` is a map of elements of type T and `sel` a map_selector, the following piece of code will remove and retrieve the data of the first element selected by `sel`:

  T *data = 0;  // `data` is a *pointer* to the type managed by the map, set to 0.
  if (map_traverse (m, MAP_REMOVE_ONE, &data, sel, 0) && data)  // A *pointer to the pointer* `data` is passed to map_traverse.
  {
    // `data` can thread-safely be used to work with.
    ...
    // If needed, it can be reinserted in the map after use.
    map_insert_data (m, data);
  }
*/

// #### Map operator to remove all elements
// This map operator removes all the selected element from the map.
extern const map_operator MAP_REMOVE_ALL;
// The parameter `op_arg` of `map_find_key`, `map_traverse` or `map_traverse_backward` should be `0` or a pointer to a destructor function with signature `void (*)(void * ptr)` (such as `free`).
// This destructor is applied to each element selected by `map_find_key`, `map_traverse` or `map_traverse_backward`.
// > The parameter `op_arg`should not be `0` if elements were allocated dynamically before insertion into the map with `map_insert_data` (otherwise data would be lost in memory leaks).

// #### Map operator to move elements from one map to another
// This map operator moves each element selected by `map_find_key`, `map_traverse` or `map_traverse_backward` to another **different** map passed in the argument `op_arg` of `map_find_key`, `map_traverse` or `map_traverse_backward`.
// N.B.: A destination map identical to the source map would **deadly lock** the calling thread.
extern const map_operator MAP_MOVE_TO;

// ## For debugging purpose
// > For fans only.
// ### Display the internal structure of the BBT of a map
#  include <stdio.h>
struct map *map_display (map * map, FILE * stream, void (*displayer) (FILE * stream, const void *data));
// `displayer` is called for each element of the BBT.
extern void (*const SHAPE) (FILE * stream, const void *data);
// `SHAPE` is a convenient displayer that only shows the structure of the BBT.
// ### Check the BBT structure of a map
#  define map_check(map) map_display ((map), 0, 0)
// `map_check` controls invariants and the consistency of the map.

// ### Retrieve some internals of the balanced binary tree of a map.
size_t map_height (map *);

size_t map_nb_balancing (map * m);

#endif