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

Question

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.

Answer 1

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.