Implementing a functional / persistent dictionary data structure

Question

I am trying to implement a functional dictionary in C. It is fairly easy to implement functional lists or b-trees, but I can hardly find references to dictionaries / associative arrays.

I looked at the erlang dict implementation - in the source code they link to this article:
Design and implementation of dynamic hashing for sets and tables in the icon .

It would be great if someone could briefly explain the erlang approach or another solution to this problem.

Answer 1

Implementing a persistent data structure in C works basically the same as in a functional language. Chris Okasaki Purely functional data structures are a great recommendation.

In the general case, it is enough to compare fixed-width integers for objects, since while this does not give you a complete dictionary on its own, you can build the dictionary from above: use the hash of the actual key as the key of the base map, and the leaves indicate the lists (key , value) pairs of the same hash value.

The tricky part is memory management, because you usually don’t know when parts of the data structure become inaccessible. Fortunately, since most robust data structures are tree-based, link counting usually works well. To be able to manage the objects referenced by the data structure, you can provide a hook for callbacks that are called when the node link list becomes 0.

For example, my Patricia Trees bitmap C implementation provides the following API:

// Querying void *bpt_get(bpt_t bpt, bpt_key_t key); bool bpt_has_key(bpt_t bpt, bpt_key_t key); // Adding and Removing Entries bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item); bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key); // Managing Memory void bpt_retain(bpt_t bpt); void bpt_release(bpt_t bpt); void bpt_dealloc(bpt_t bpt); void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t key, void* value)); // Iteration void bpt_for_mappings(bpt_t bpt, void (*thunk)(bpt_key_t, void*, void*), void *user_data); // Making a Map Persistent (you can elide this if you don't // want to support transients) void bpt_seal(bpt_t bpt); 

may give you some ideas.