[HN Gopher] Show HN: A hash array-mapped trie implementation in C ___________________________________________________________________ Show HN: A hash array-mapped trie implementation in C Long-simmering side project that is finally ready to see the light. HAMTs are a cool persistent data structure and implementing one has been a lot of fun. Beyond the code, there is likely some value in the extensive and largely complete implementation docs; basic benchmarks are linked in the README, too. Kind of aiming to be "the libavl for HAMTs". That is obviously a high and aspirational bar but a distinct possibility if it stirs up a little interest and/or contribution. Anyways, it's time for this to go out, collect feedback and maybe even some use outside of toy projects. Let me know how it goes. Author : mkirchner Score : 32 points Date : 2023-07-10 21:06 UTC (1 hours ago) (HTM) web link (github.com) (TXT) w3m dump (github.com) | thechao wrote: | Just a note about your 'exported memory allocation' API: | struct hamt_allocator { void *(*malloc)(const size_t | size); void *(*realloc)(void *chunk, const size_t | size); void (*free)(void *chunk); }; | | This whole thing could just be: struct | hamt_allocator { void *cookie; void* | (*realloc) (struct hamt_allocator* h, void* chk, const size_t | size); }; | | With the following constraints: | | 1. `realloc(H, nullptr, N)` -- allocated N bytes | | 2. `realloc(H, p, 0)` -- frees the pointer p | | 3. `realloc(H, p, N)` -- resizes the pointer p | | And, the user has access to a 'context' (`cookie`) so they can | use a (for instance) pool allocation scheme. Personally, I like a | slightly different API: struct hamt_allocator { | void *cookie; void* (*realloc) (struct | hamt_allocator* h, void* chk, const size_t oldsize, const size_t | newsize); }; | | With the following constraints: | | 1. `realloc(H, nullptr, 0, N)` -- allocated N bytes | | 2. `realloc(H, p, N, 0)` -- frees the pointer p | | 3. `realloc(H, p, N, M)` -- resizes the pointer p | | But I know a lot of people get confused and/or don't like having | to pass (& thus keep) so much information to the allocator. | david2ndaccount wrote: | I generally like this pattern, but why pass the allocator | instead of the cookie? | tombert wrote: | I discovered HAMTs first when Erlang added support for first- | class maps, and it was sort of a "holy shit!" moment for me. They | felt like the "holy grail" of data structures for me; I can treat | any updates as "copies" without the cost of a copy. | | About a year later, I learned Clojure, and fell even more in love | with the data structure; when the language fully embraces a | useful data structure, it changes the way you think about the | entire program, and now it's sort of hard for me to go back to | languages that don't have a good HAMT implementation. | | I mean, I still do it, but I do think that having a "go to | standard" in C really has the potential to set a great precedent. ___________________________________________________________________ (page generated 2023-07-10 23:00 UTC)