On: Show HN: A hash array-mapped trie implementation i...

[thechao]

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

[cataphract → thechao]

You don't need the cookie then. You can just allocate a larger struct (sort of subclassing it). You save a pointer indirection.

[thechao → cataphract]

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

[pixelpoet → thechao]

I have discovered a truly marvelous allocator pattern which this HN comment is too small to contain.

[jjgreen → pixelpoet]

[350 years later] I have confirmed the optimality of the allocator pattern as a special case in my proof of the Inter-universal Teichmüller theorem (Springer, 879pp).

[cataphract → thechao]

Fair enough:

    struct hamt_allocator {
        void *(*realloc)(struct hamt_allocator *h, void *chk, size_t oldsize,
                        size_t newsize);
    };
    struct my_allocator {
        struct hamt_allocator parent;
        size_t used;
        char buffer[8192];
    };
    static void *alloc_func(struct hamt_allocator *h, void *chk,
                            const size_t oldsize, const size_t newsize)
    {
        if (!newsize) {
            return NULL;
        }
        if (h && newsize <= oldsize) {
            return h;
        }
        // this cast is allowed by the standard for this purpose
        __auto_type *alloc = (struct my_allocator*) h;
        if (newsize > sizeof(alloc->buffer) - alloc->used) {
            return NULL;
        }
        void *ret = alloc->buffer + alloc->used;
        alloc->used += newsize;
        if (h && oldsize) {
            memcpy(ret, h, oldsize);
        }
        return ret;
    }
    void func_taking_allocator(struct hamt_allocator *h);
    void user_code() {
        struct my_allocator alloc = { .parent.realloc = alloc_func };
        func_taking_allocator(&alloc.parent);
    }

[cataphract → cataphract]

While this was not the point of the comment, one thing missing is that oldsize and newsize should be rounded for alignment purposes:

    struct my_allocator {
        struct hamt_allocator parent;
        size_t used;
        union {
            char buffer[8192];
            max_align_t _align;
        };
    };
    
    static inline size_t align_size(size_t value)
    {
        size_t alignment = _Alignof(max_align_t);
    
        // if (value % _Alignof(max_align_t) == 0) {
        //     return value;
        // } else {
        //     return ((value / alignment) + 1) * alignment;
        // }
    
        return value + (alignment - 1) & ~(alignment - 1);
    }

Even better, the allocator function should get the alignment so don't waste bytes unnecessarily.

[mkirchner → cataphract]

Beautiful, thanks!

[inopinatus → thechao]

The solution is obviously to realloc the comment.