實現功能/持久性字典數據結構

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可能會給你一些想法了。