Implementación de una estructura de datos de diccionario funcional/persistente

Question

Estoy intentando implementar un diccionario funcional en C. Es bastante fácil implementar listas funcionales o b-trees, pero apenas puedo encontrar referencias en los diccionarios/matrices asociativas.

Eché un vistazo a la implementación dict de erlang - en el código fuente se refieren a este documento:
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon.

Sería genial si alguien pudiera explicar brevemente el enfoque de erlang u otra solución a este problema.

Answer 1

La implementación de una estructura de datos persistente en C funciona básicamente de la misma manera que en un lenguaje funcional. Chris Okasaki's Purely Functional Data Structures es una gran referencia.

En general, basta con mapear enteros de ancho fijo a los objetos, porque mientras que eso no le da un diccionario completo por sí mismo, puede construir un diccionario en la parte superior: Use un hash de la clave real como la clave del mapa subyacente, y hacer que las hojas apunten a listas de pares (clave, valor) del mismo valor hash.

La parte complicada es la administración de la memoria, ya que generalmente no se sabe cuándo partes de la estructura de datos se vuelven inalcanzables. Afortunadamente, dado que la mayoría de las estructuras de datos persistentes se basan en árboles, el conteo de referencias generalmente funciona bien. Para poder gestionar los objetos a los que hace referencia la estructura de datos, puede proporcionar un enganche para las devoluciones de llamada que se invocan cuando el recuento de referencia de un nodo hoja se convierte en 0.

Por ejemplo, mi implementación de C de bitmapped Patricia Trees proporciona lo siguiente 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); 

El implementation podría darle algunas ideas, también.