c - 实现功能/持久字典数据结构

Question

我正在尝试在 C 中实现一个函数式字典。实现函数式列表或 b 树相当容易，但我几乎找不到关于字典/关联数组的任何引用。

我查看了 erlang 的 dict 实现——在他们参考这篇论文的源代码中：
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon。

如果有人能简要解释一下 erlang 的方法或解决此问题的其他方法，那就太好了。

Answer 1

在 C 中实现持久数据结构的工作方式与在函数式语言中的实现方式基本相同。Chris Okasaki 的Purely Functional Data Structures是一个很好的参考。

一般来说，将固定宽度的整数映射到对象就足够了，因为虽然这本身并不能为您提供一个完整的字典，但您可以在上面构建一个字典：使用实际键的哈希作为底层映射，并让叶子指向相同哈希值的（键，值）对列表。

棘手的部分是内存管理，因为您通常不知道数据结构的某些部分何时变得无法访问。幸运的是，由于大多数持久性数据结构都基于树，因此引用计数通常效果很好。为了能够管理数据结构引用的对象，您可以为当叶节点的引用计数变为 0 时调用的回调提供挂钩。

例如，我的位图Patricia Trees的 C 实现提供了以下 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);

该实现也可能会给您一些想法。