Data structures

Librcd comes with two data structures built in: dictionaries (fstring -> data maps) and linked lists.

Dictionaries have type dict(X)*, where X is the type of the data (the preprocessor converts this to an internal name struct __rcd_dict__X*). Internally, dictionaries are based on red-black trees, which makes lookups, insertions and deletions take O(log N) time each. Librcd does have hashmaps (hmap.h), but they are not used here, to avoid potential performance gotchas in the common case. When iterating over a dictionary, the order will be the same as the order of insertion. (This is maintained by a linked list inside the tree.) All dict operations are macros, and generally take as parameters the dict to operate on together with its type. Here is an example:

dict(int)* d;
dict_replace(d, int, "key1", 5);
dict_replace(d, int, "key2", 3);
dict_foreach(d, int, k, v) {
    DBG(k, " = ", v);
    dict_delete_current(d, int);
}

Lists have type list(X)* (internally, struct __rcd_list__X*), and behave, well, pretty much exactly like you'd expect linked lists to behave. Pushing and popping from either side is O(1), and there is no direct indexing. An example:

list(fstr_t)* list = new_list(fstr_t);
list_push_end(list, fstr_t, "there");
list_push_front(list, fstr_t, "hi ");
list_foreach(list, fstr_t, value)
    DBG(value);

A vector data structure is currently missing (issue #8), but only because no strong need has come up.

Because of the particular macro desugarings, there is a small detail to be aware of: if the first use of a dict type happens within a parameter list, the compiler will parse the struct type as local to the function, and generate warnings like "declaration of 'struct blah' will not be visible outside of this function" and "incompatible pointer types passing 'struct blah *' to parameter of type 'struct blah *'" (see this Stack Overflow question). In this case, just add a forward declaration of the struct near the top of the file:

dict(blah);
...
void f(dict(blah)* arg, dict(blah*)* another_arg, ...)