[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)