3 ms·
Maybe it requires this in Zig (I don’t know), but in general there’s no reason why you couldn’t allocate the nodes of an extrusive linked list from a pool resid
by foldr 2y ago
Maybe it requires this in Zig (I don’t know), but in general there’s no reason why you couldn’t allocate the nodes of an extrusive linked list from a pool residing on the heap or on the stack. For example, you could do this with the STL (for all that STL allocators are a pain to use in practice). Or you could have a slightly different API where you add nodes to the list by passing an entire Node<T> to the relevant function rather than just T, at which point you can trivially allocate the nodes as you please.
- reissbaker 2y agoEven if you allocate from a pool on the heap, the pool will reside in a different part of the heap than the elements that you're inserting into the linked list, meaning you have worse cache locality. You could have an API that is aware of T, and allocates both Node<T> and T together, ensuring cache locality for both. Congratulations! You have rediscovered intrusive linked lists.