我正在尝试用C实现一个函数字典.实现函数列表或b-tree相当容易,但我几乎找不到关于字典/关联数组的任何引用.
我看了一下erlang的dict实现 – 在他们引用本文的源代码中：
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon.
解决方法
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,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也可能会给你一些想法.
