21–30 of 59 posts
[0]: https://cr.yp.to/critbit.html
Edit: I think I understand now from the design section on your page, they are both tries, but the HAMT uses the hash of the key to locate the node whereas Crit-bit uses the key itself.
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 persisten…
This is explained in the readme[1]. You can pass custom allocation functions (mallic, realloc, free), so you can plug in Boehm fex.
Are these the same as Crit-bit trees [0]? [0]: https://cr.yp.to/critbit.html Edit: I think I understand now from the design section on your page, they are both tries, but the HAMT uses the hash of the key to locate the node whereas Crit-bit uses the key itself.
See also https://dotat.at/prog/qp/README.html
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 persisten…
> How does your implementation handle that? This is explained in the readme[1]. You can pass custom allocation functions (mallic, realloc, free), so you can plug in Boehm fex. [1]: https://github.com/mkirchner/hamt#memory-management
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…
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…
Earlier quoted context omitted.
> How does your implementation handle that? This is explained in the readme[1]. You can pass custom allocation functions (mallic, realloc, free), so you can plug in Boehm fex. [1]: https://github.com/mkirchner/hamt#memory-management
So refcounting?
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…
That's not why I think it' a bad idea.
I prefer the original because:
1. I can pass use the existing `free`, `malloc` and `realloc` implementations. By using a function with a different set of params I cannot do that. The user has to always write the `realloc` function you propose.
2. The interface for free, malloc and realloc is already documented, I don't have to explain to the programmers what constraints are needed for their memory allocator function. Under your proposal the programmer has to now have, and read, the documentation
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…
Sadly, this pattern doesn't work with standard realloc() anymore. C23 makes this undefined behavior due to existing non-conforming implementations. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf
https://pubs.opengroup.org/onlinepubs/009696899/functions/re...
https://pubs.opengroup.org/onlinepubs/9699919799/functions/r...