기능적/영속적 인 사전 데이터 구조 구현

Question

나는 기능적 사전을 C로 구현하려고합니다. 기능 목록이나 b- 트리를 구현하는 것은 상당히 쉽지만 사전/연관 배열에 대한 참조는 거의 찾을 수 없습니다.

소스 코드에서이 문서는 참조 번호
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon과 같이 erlang의 dict 구현을 살펴 보았습니다.

누군가가 erlang의 접근법이나이 문제에 대한 다른 해결책을 간략하게 설명 할 수 있다면 좋을 것입니다.

Answer 1

C에서 영구 데이터 구조의 구현은 기본적으로 함수 언어에서와 같은 방식으로 작동합니다. Chris Okasaki의 Purely Functional Data Structures은 훌륭한 참고 자료입니다.

일반적으로 은 본격적인 사전을 제공하지 않지만 고정 길이 정수는 개체에 매핑하면 충분합니다. 실제 키의 해시를 사용하십시오. 기본 맵의 키로 사용하고 리프가 동일한 해시 값의 (키, 값) 쌍 목록을 가리 키도록합니다.

까다로운 부분은 일반적으로 데이터 구조의 일부가 도달 할 수없는 시점을 알지 못하기 때문에 메모리 관리입니다. 다행히 대부분의 영구 데이터 구조는 나무를 기반으로하기 때문에 일반적으로 참조 계산이 잘 작동합니다. 데이터 구조에서 참조하는 객체를 관리하려면 리프 노드의 참조 수가 0이 될 때 호출되는 콜백에 대한 후크를 제공 할 수 있습니다.

예를 들어, 비트 맵핑 된 Patricia Trees의 myC 구현은 다음을 제공합니다. 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도 몇 가지 아이디어를 줄 수 있습니다.