Generic pseudo-templated containers for C. Written entirely in C89 with design inspired by the C++ STL. /// DOCS ARE SLIGHTLY OUTDATED, PROJECT IS STABLE AND STILL BEING DEVELOPED
The main disadvantage of vector implementation with C-like access (that is, vec[i] instead of smth like vec_value( vec, i ) or vec->data[i]) is that we have to modify all the references on any vector operation that reallocates the underlying buffer. That could be not suitable for some cases.
There's a concept. To keep all the things unified, we can just add a data field into the vector header that will be NULL if vector is in the "mutable handles" mode (as now), and point to the data buffer otherwise.
Problems:
A set of functions obtaining the immutable handle type to operate on a vector will be reqired in a naive case, which is sucks (especially due to the nature of function instantiation). But it can be overcomed using the "reduced header" trick. That is, the data field in the header should be the last one. Thus, on every IGVEC_HEADER() we must go sizeof(void*) bytes back and examine the value. It it's NULL, then we're in the mutable mode so the header is up there. Otherwise, the examined value points to the header stored separately (which is the immutable handle), while the data field of the header itself points to the first element of the data (but not the actual buffer - its location is data - sizeof(void*)!). Thereby, we can operate on vectors using immutable handles just by passing immutable_handle->data (or &(immutable_handle->data) when required) to the same functions as used by regular mutable vectors, which is pretty cool.
By using another sizeof(void*) bytes of overhead we can go deeper and implement immutable headers that we'll can pass to functions just as mutable ones, i.e. without the ->data part. "Immutability costs", lol. But this is dirty from the point of view of types (it's better to have "immutable handle" as type alias of the type of header) and readability (easiness to mess up the mutable and the immutable handles). And how to access the actual vector data (particularly, its elements) in that case? However, in case of vec->data we can't access elements too because it's void*.
I should think of both implementations more thoroughly. Maybe it's better to have two different vector implementations at all (mutable / immutable)? But this is code duplication, and it sucks. But does anyone really need the mode switching feature?
Oh, a real trilemma of "speed / space / code beauty". :(
I still don't like e.g. GENA_USE_SAMPLE, GENA_USE_ENTITY and so on, as they're not intuitive.
The new approach to defining a terminology should be next:
avoid homonyms;
prepare an initial list of words that can be used, then select from them by considering intuitivity;
... (I'll think about it later, now I'm slightly discouraged).
Add ability to run tests, get rid of hardcoded CodeBlocks project.
Modular library compilation (i.e. user should be able to choose only necessary data structures).
Use CMake (halp ;C).
Add safe compilation mode that will use -O2 instead of -O3, -fno-strict-aliasing etc. since the C standard is utterly retarded but GCC considers it as a honor to follow it.
Separate binary tree structure from AVL tree implementation, leaving support for tree-specific data ("balance factor" for AVL, "color" for red-black, etc).
Add other tree implementations: red-black, AA (made simple™), WAVL, etc.
Allow to select necessary tree algorithm in instantiation macros by specifying either macro definition argument (e.g. GENA_2TREE_BACKEND_AVL, what is preferable and desirable) or constant interface structure with methods (like in interators now, but I would like to leave that approach there and won't apply it more anywhere).
Such functionality will be also needed for hash-based data structures in the future.
All of this is somewhat related to #18 because of multimap / multiset capabilities we need.
Also:
Think about non-binary trees and their usability in such context (e.g. for multimaps / multisets).
Think about the possibility of tree implementations with flattened array, which seems to be quite effective for balanced trees.
Think about storing nodes in a realloc-based or chunk-based buffer.
1. Should support dereference operation. This can be done since value is always nearly from its managing structure (tree node, for example).
2. Should be intercompatible between different data structures.
This will help implement complex types such as vector of dynamic strings or multidimensional vectors with dynamic dimensions.
Custom grow functions (or maybe macros instead, more effecient?).
In-place constructors and destructors for elements.
Custom memory management (something like allocators in C++).
To save memory in such cases when callbacks aren't needed, pointers to them should be derived into another struct and pointer to that struct should be stored in header. If it's NULL, then we don't use them.
Forget about assignment callbacks: we don't need them here at all. In addition, for assignment callbacks we also need typecast callbacks, that's out of scope of this library.
In far and happy future:
Custom hash functions (for maps based on hashes).
Custom comparison functions (for maps based on trees).
They're cannot be naively assigned through = operator, so we need to add something like GENA_COMPARE_NAIVE / GENA_COMPARE_MEMCMP / GENA_COMPARE_STRCMP,
but for assignment, say GENA_ASSIGN_NAIVE / GENA_ASSIGN_MEMCPY / GENA_ASSIGN_STRCPY.
We also may want to add G***_INSTANTIATE_EX and so on, which will support additional argument for assignment type. That's useful because array types are such a rare and specific case, and all other types can (and should) use naive assignment.