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

Question

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

我看过 erlang 的 dict 实现 - 在他们引用本文的源代码中:
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon .

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

Answer 1

在 C 中实现持久数据结构的工作方式与在函数式语言中的工作方式基本相同。克里斯冈崎的 Purely Functional Data Structures是一个很好的引用。

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

棘手的部分是内存管理，因为您通常不知道数据结构的某些部分何时变得不可访问。幸运的是，由于大多数持久数据结构都是基于树的，因此引用计数通常效果很好。为了能够管理数据结构引用的对象，您可以提供一个钩子(Hook)，用于在叶节点的引用计数变为 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);

implementation也可能会给您一些想法。