libhamt is a C99 implementation of a hash array-mapped trie (HAMT), which is a data structure used to efficiently implement persistent associative arrays and sets. The implementation follows Bagwell’s 2000 paper with a focus on code clarity. The author noticed a lack of in-depth documentation for HAMTs beyond the original paper, so this document aims to partially address that situation. The library can be built and tested using the provided instructions. The implementation provides functions for lifecycle management, memory management, querying, iterators, and insert/remove operations. It supports both ephemeral and persistent HAMTs, with the latter allowing for structural sharing and efficient memory usage.
https://github.com/mkirchner/hamt