Skip to content

vslapik/ugeneric

Repository files navigation

Build Status

The library is a pile of code around concept of generic data item represented by 'ugeneric_t' type. It is not well structured, not well tested, not production ready, contains a lot of bugs, lacks UT coverage, lacks documentation and has no clear development roadmap. However I'd love to fix all above sooner or later and keep this repository as a set of reusable pieces of code for my other projects. The library routines are not supposed to be fast but rather easy to use. There is no clear library boundaries, it is just scattered files which can be separately copied in another project to provide pieces of functionality. Below some random notes instead of documentation which is apparently missing so far. I was able to successfully build and use it on x86, STM32 (ARM) and ESP-8266 (Xtensa) and MSP430 platforms (GCC) and there are no obvious reasons for not being able to use it anywhere else where decent C compiler exists. It requires C11 support however.

The ugeneric_t is a tagged union capable to represent most of the widely used C data types (for sure at some added cost). There are primitive types which can be wrapped by ugeneric_t (like signed/unsigned integers, strings, booleans, pointers) and two composite types:

  • dynamically resizing array (or vector or list or ...)
  • dictionary (or associative array or map or whatever name you like).

Also pointers to some arbitrary data can be stored in containers. You can copy, compare and destroy this arbitrary data if you register appropriate functions (void_cpy_t, void_cmp_t, void_dtr_t).

In addition to a vector and a dictionary (red-black tree based and hash-table based) there is also support for some other widely used data structures like heap (priority queue), stack, queue, linked list, disjoint set union, bitmap. There is also support for graphs and minimal set of graph alogrirthms (BFS, DFS, minimum cut, topological sort, Kruskal's minimal spanning tree, Dijkstra's shortest path). More likely to come. For convenience all containers can be serialized to JSON format or constructed from JSON though not all JSON features are supported (like unicode strings, some odd float points formats). All tree-based structures and graphs can be dumped into dot format to being able to explore them visually. Vectors can be dumped into gnuplot format.

All containers work with elements of ugeneric_t type, i.e. list and vector elements, dict keys and values, queue elements, stack elements - all of them are of ugeneric_t type. Variables of ugeneric_t are passed to / returned from functions by value (there are only a few exceptions). There are no return codes which need to be tested after each call in containers API. There are just few things which may go wrong there:

  • Caller of the API passed junk to an API function or called it in a wrong way (null pointer, attempting to pop an element from an empty stack, accessing an element beyond the end of vector, using iterator when iteration is completed and so on). The strategy is to do nothing to prevent the caller from doing it. It might be a bit unexpected if you came from programming languages which control each and every your action. But this is a good C tradition, not to prevent such cases and trust a programmer. Try to pass NULL pointer, say, to strlen(). It won't cry out, it will just merely crash and investigation of why it crashes is your responsibility. For convenience all API input is covered with asserts which can be optionally enabled and detect most of the aforementioned case. If a user of API is able to pass junk it is questionable whether he would be able to analyze the return code...
  • There is a bug in the library code and under some conditions internal library data is corrupted. It means the library code is broken and shouldn't be used until it gets fixed. Return codes wouldn't help here either. There some internal asserts for such conditions which are enabled by default in order to abort execution as soon as possible (by literally calling abort() when such situation is detected). Normally it shouldn't occur but I warned you, the stuff is not that well tested yet.
  • Internal memory allocation failed. This is probably the most difficult situation to recover from and here return code usually make sense which basically delegates the responsibility of handling such a situation to the caller. However in most situations callers don't care about it. If malloc or friends returned 0 most likely this is either ignored or logged and then application is aborted. The approach in this library is a bit different. No return code is used anyway but you can try to foresee such a situation by registering a callback which will be called to handle the memory allocation failure. The callback is expected to free some unused memory then initial allocation will be re-attempted. If subsequent allocation still fails after the second attempt - there is no way to proceed, so exit() is called and log message is produced to stderr. Calling exit() allows to execute additional actions you may have registered by atexit() or friends (like closing file descriptors, saving your precious data, informing your user and so on). To complicate the story further, some environments never report memory exhaustion by returning null pointer from memory allocation routines (google for Linux overcommit) so there is little chance you will be able to correctly handle memory exhaustion anyway.

Random notes:

  • library code is NOT thread safe, locks are caller's responsibility
  • xxx_destroy(NULL) safely does nothing similar to free(NULL)
  • containers are owners of elements memory by default, i.e. all elements memory is freed when container is destroyed, you don't need to keep pointers for everyting you put to container
  • xxx_remove_xxx - remove an element from container and destroy it without returning to a caller
  • xxx_pop_xxx - remove an element from a container and return to a caller (the caller is responsible for destroying the element)
  • xxx_get/peek_xxx - return an element to a caller without removing it from a container (shallow copy)
  • xxx_push/insert_xxx - insert an element to a container