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

Question

我试图在C中实现一个功能字典。它很容易实现功能列表或B树，但我几乎找不到任何字典/关联数组的引用。

我看了一下erlang的字典实现 - 在他们提到的这篇论文的源代码中：
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon。

如果有人能简单解释一下erlang的方法或解决这个问题的另一种解决方案，那将会很棒。

Answer 1

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

一般来说，将固定宽度的整数映射到对象就足够了，因为 虽然没有为您提供完整的字典本身，但您可以在顶部创建一个字典：使用实际密钥的散列作为基础地图的关键字，并让叶指向相同散列值的（键，值）对的列表。

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

例如，我的C位实现Patricia Trees提供了以下内容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可能会给你一些想法了。