>>107008315
>How about a linked list that as it dynamically creates new nodes, stores a table of indices for its elements so you can directly index to the nodes you want?
I've done that for a custom allocator, it was much faster than a simple linked list but despite taking a lot of space and being a complete mess, even in the best case, it was two times slower than malloc. Had to actually have 3 different hash tables to make the coalescence of adjacent nodes O(1). Searching for a free node capable of storing given size was still O(n).
struct FL_Chunk {
void *base;
void *end;
struct FL_Chunk *prev;
struct FL_Chunk *next;
};
struct FL_Slot {
struct FL_Chunk *chunk;
struct FL_Slot *prev;
struct FL_Slot *next;
};
struct FL_Page {
void *memory;
size_t capacity;
size_t curr_size;
ullong num_chunks_max;
struct Pool *pool_chunks;
struct FL_Chunk *list_chunks_used;
struct FL_Chunk *list_chunks_free;
struct Pool *pool_slots;
struct FL_Slot **table_bases;
struct FL_Slot **table_ends;
struct FL_Slot **table_used;
ullong num_chunks_used;
ullong num_chunks_free;
struct FL_Page *next;
};
struct FL {
bool is_extendable;
size_t alignment;
struct FL_Page *page;
};
