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.

Show HN: A hash array-mapped trie implementation in C
github.com

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.

If you want to "shim" the API, then it's easier to have the whole previous object, rather than just the cookie.

The biggest advantages here are not having a single function, but instead:

1. Having a context.

2. Having free and realloc getting the old size. Not having the size passed is more or less consensually regarded as a mistake in the C stdlib.

If you're interested in persistent data structures for C++, then I highly recommend Immer. High quality and easy to work with.

https://github.com/arximboldi/immer