0

I am in the process of implementing a persistent collection in C, specifically, an immutable hash trie. In order to increase acceptance and reusability, I have identified the following key areas that should be abstracted:

  • typing of key and value
  • allocation & freeing of additional nodes

Typing of key and value also comes with the complexity abstracting hash and equality functions.

I am mostly interested in being able to handle the following cases in particular, regarding memory management:

  • creating new nodes with malloc and using reference counting to free them
  • using the ravenbrooks memory pool system (mps) as a garbage collector, which means I'll have to use the mps api to request new memory

and typing:

  • (void *) as default for key and value types
  • making any or both of key and value types a struct

In addition I am wondering whether it would be useful to give users the option to provide hash and equals functions either:

  • at runtime, and passing them down the trie every time, or
  • at compile time, "baking" them into the various functions with the help of preprocessor macros

Are there "standard" ways to achieve those goals? Patterns, so to speak? Or are these goals misguided?

I haven't gotten to the point of a working implementation yet, but from first experiments I think I can achieve these goals via heavy use of macros and an unorthodox #include order.

  • As in, allowing users to specify "a struct of function pointers" (for extension purpose) where each function performs a required operation, such as: construct-in-place, copy, compare, hash, destroy, increment reference count, decrement reference count? (To learn how to use "a struct of function pointers" for extension purpose, take a look at jpeglib and libtiff, and many other C libraries that use the same technique. – rwong Mar 24 at 6:35
  • @rwong Ah, that's a method I hadn't considered yet. I would have gone the gnome_hash_table route of taking function pointers in the "constructor". I'll go ahead and describe my current design in more detail in the question. – ammut Mar 24 at 8:27
  • 1
    "I am wondering whether it would be useful to give users the option to provide hash and equals ..." - to answer such questions, you need to know the real world use cases for this collection (at least some representative examples). You won't find out about these use cases by asking strangers on the internet - you find out by asking some of your typical users. – Doc Brown Mar 24 at 21:02
  • I would say the aspects of allocation and typing are very separate questions too. – Greg A. Woods Mar 24 at 23:40
  • When writing generic C code, you should first figure out whether C++ wouldn't be a better choice. Using lots of void* pointers and lots of macros is hell to debug, and templates are much simpler. – amon Apr 1 at 12:53
2

How should I provide generic typing and allocation for a collection library ... ?

Establish boundaries

Without scope limits, this task will evolve into a re-creation of C++. Assuming that is not the goal, maintain design limitations.

Divide and Conquer

Set up the collection library to handle only void * objects and void * keying. There is so much design and code for this task alone, it is better to stay on that focus with only nominal consideration for the general-ness. This void * toolset may be somewhat private.

2nd layer: To handle non-void * (real world cases), add a 2nd set of tools, perhaps using _Generic(), that call the void* collection routines. This is the public tool set.

User functions

Yes, allow the user to supply run-time function pointers and data at either initialization or first function assignment time. Perhaps along the line of:

typedef struct { 
  void *(*key)(const void *data, int context);
  int context;
  size_t (*hash)(const void *key);
  int (*cmp)(const void *key1, const void *key2);
  void (*copy)(void *data_dest, const void *data_src);
  void *(*alloc)(void *data); // like copy, but to a new allocation
  void (*free)(void *data);
  size_t data_size;
} collection_func;

collection *collection_open(const collection_func *func, ...);

I would not pass the needed characterization info on other calls, just once at the beginning.

Various instances of collection_func could be pre-defined to support a collection of double, string, struct pixel, etc.

Speed vs. Robustness

If the goal is speed, you may need another language with the ability to hide functions as inline code. For general-ness accept minor linear slowness of calling a function rather than templated code and strive for type checking with the 2nd layer mentioned above.

I'd avoid "baking".


Are there "standard" ways to achieve those goals? Patterns, so to speak? Or are these goals misguided?

There are no C "standard" way. There exist many good approaches. The goal is not misguided, just grand. Use good engineering to balance the general-ness, speed, type safety, etc. You will not achieve excellence in all, but may get good enough for your purpose.

Considerations that affect linear memory or linear speed performance are last on my list.

| improve this answer | |
  • Thank you so much, this is pretty much what I was hoping for in an answer. I've meanwhile finished a first version of this collection and put it up for comment over at codereview.stackexchange. I would appreciate your input there as well. One question though: I don't quite understand the second paragraph of Divide and Conquer. Could you elaborate a bit? – ammut Apr 30 at 11:42
  • @ammut Divide and Conquer --> divide the task into two phases: 1) Collection functions that handle void * pointers in an abstract fashion and 2) code that interfaces various types. IOWs do not embedded the type management within the collection code. Collection code works with void * and function pointers to do its role. E.g. to compare, call int (*cmp)(void *key_a, void *key_b), to copy, do not memcpy(data_a, data_b, size); but (*copy)(void *data_a, const void *data b) – chux - Reinstate Monica Apr 30 at 14:43
  • the (*copy)(void *dst, const void *src) is certainly something I need to do yet, but I was wondering about how you would handle non-void * cases, or what you mean when you refer to the "2nd layer, public tool set". Currently, I have at the top of my header file #ifndef KEY_T #define KEY_T void *, and then struct data { KEY_T key; VALUE_T value; }. This would allow a client to, for example, #define KEY_T int and then #include "hashmap.h". The problem here is obviously, that the implementation is compiled with void *, but used as if that was an int, which is UB. – ammut May 1 at 14:34
  • @ammut "how you would handle non-void * cases" --> Say collection routines only handled void *, no macro subbing, just void *. One could save an int, bool, complex double, time_t, my_foo_t etc by allocating memory for that, copy data into that memory and then save the void * pointer. True this is not efficient for small types, yet for real applications of collection functions, it is efficient for large types. Thus my emphasis on generality of void * and not spend lots of effort trying to code with a collection data element that is not a void _*. It depends on your goals. – chux - Reinstate Monica May 1 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.