Thực hiện một cấu trúc dữ liệu từ điển chức năng/liên tục

Question

Tôi đang cố gắng thực hiện một từ điển chức năng trong C. Thật dễ dàng để thực hiện các danh sách chức năng hoặc cây b nhưng tôi khó có thể tìm thấy bất kỳ tham chiếu nào về từ điển/mảng kết hợp.

tôi đã có một cái nhìn tại thực hiện dict erlang của - trong mã nguồn họ tham khảo bài viết này:
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon.

Sẽ thật tuyệt vời nếu ai đó có thể giải thích ngắn gọn cách tiếp cận của Erlang hoặc giải pháp khác cho vấn đề này.

Answer 1

Việc triển khai cấu trúc dữ liệu liên tục trong C hoạt động về cơ bản giống như cách thực hiện trong ngôn ngữ chức năng. Sốcủa Chris Okasaki là một tài liệu tham khảo tuyệt vời. Nói chung, nó đủ để ánh xạ các số nguyên cố định chiều rộng cho các đối tượng, bởi vì trong khi đó không cung cấp cho bạn một từ điển chính thức, bạn có thể xây dựng từ điển ở trên cùng: Sử dụng băm của khóa thực tế như là chìa khóa của bản đồ cơ bản, và có lá trỏ đến danh sách các cặp (khóa, giá trị) của cùng một giá trị băm.

Phần khó khăn là quản lý bộ nhớ, vì bạn thường không biết khi nào các phần của cấu trúc dữ liệu trở nên không thể truy cập được. May mắn thay, vì hầu hết các cấu trúc dữ liệu liên tục dựa trên cây, việc đếm tham chiếu thường hoạt động tốt. Để có thể quản lý các đối tượng được tham chiếu bởi cấu trúc dữ liệu, bạn có thể cung cấp một móc cho các cuộc gọi lại được gọi khi số tham chiếu của nút lá trở thành 0.

Ví dụ, việc triển khai bitmap của tôi là Patricia Trees cung cấp 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 cũng có thể cung cấp cho bạn một số ý tưởng.