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

There's a limit to what can be crammed into a HN comment!

How does this compare to https://github.com/arximboldi/immer (other than the C/C++ difference)?

Also, it's my understanding that, in practice, persistent data structures require a garbage collector in order to handle deallocation when used in a general-purpose way. How does your implementation handle that?

Also, have you seen https://github.com/cnuernber/ham-fisted ? I think there are a few other Java-based persistent collections as well in the overall Clojure ecosystem that also improve on Hickey's original implementation, but I can't recall them now…

Doc fix: Iterators section repeats a code block with these declaration from the previous section:

  size_t hamt_size(const struct hamt *trie);
  const void *hamt_get(const struct hamt *trie, void *key);

I would drop the API directly and concentrate on the algorithm.

If users integrating HAMT need a different allocator situation, they can solve that problem by themselves, without a run-time indirection shim.

You can help those users by providing some macros somewhere like #define hamt_malloc(ctx, x) malloc(x) and so forth, so it can be retargeted in one place. Leave an ignored context argument in place for those who would like to have a run-time switch per-instance.

The pattern was never specified as fully working. Not in C99 and C90.

It's due to the following reason: it was never specified that realloc(ptr, 0) behaves like free(ptr).

The case of size == 0 is not separately discussed in the C99 description of realloc.

realloc(ptr, 0) can behave like (free(ptr), malloc(0)), where malloc(0) doesn't necessarily behave like ((void *) 0). Malloc may return a unique object that may be later freed.

That is to say, realloc can effectively reduce an object to zero size without freeing it, or possibly even free an object only to replace it with a different, unique zero-sized object.

Note that in the case when ptr == NULL, which is discussed in C99, realloc behaves like malloc. So in the case realloc(NULL, 0), we know that it's the same as malloc(0). That's a case when size == 0, and realloc is required to behave like malloc.

This is a standard-conforming realloc, and always has been:

  void *realloc(void *oldptr, size_t newsize)
  {
    size_t oldsize = __allocated_size(oldptr); // this handles NULL, and returns 0

    void *newptr = malloc(newsize);

    if (newptr != NULL && oldptr != NULL)
       memcpy(newptr, oldptr, min(newsize, oldsize);
    
    return newptr;
  }

This realloc will not behave like free if malloc(0) returns unique pointers.

If you want a realloc-like function that behaves like an "all in one allocator", you have to write your own:

   void *git_reset_of_allocators(void *oldptr, size_t newsize)
   {
      if (size == 0) {
        free(oldptr);
        return NULL;
      } else { 
        // handles all other cases OK
        return realloc(oldptr, newsize);
      }
   }