What's your solution when you need contiguous storage for data, but you don't know the size ahead of time. And I don't mean just while developing. It's dependent on the user input, so you have to ship it that way. My first attempt was to create some kind of sliced array, where each slice is a bigger chunk of memory. That way, data should still be cache friendly most of the time, except when it needs to jump to other slice. I want fast access and fast iteration time, so instead of linking the slices, I have another array of pointers to those slices. Each slice is same size, and all elements are same size. Here's my implementation using memory arena. What do you think? How would you improve it?
1 2 3 4 5 6 7 8 9 10 11 | struct SlicedArray { MemArena arena; uptr *slices[128]; /* this can be dynamic too */ sizet sliceCount; sizet itemCount; sizet effectiveItemSize; sizet itemsPerSlice; }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | INLINE void initSlicedArray(SlicedArray *array, sizet sliceSize, sizet itemSize, u32 alignment) { array->effectiveItemSize = ALIGN_POW_2(itemSize, alignment); /* ensure that at least one item fits */ ASSERT(sliceSize >= (array->effectiveItemSize + sizeof(MemBlockFooter))); sizet effectiveSliceSize = sliceSize - sizeof(MemBlockFooter); array->itemsPerSlice = (effectiveSliceSize / array->effectiveItemSize); sizet arenaBlockSize = sliceSize; initArena(&array->arena, win32Allocate, win32Deallocate, arenaBlockSize); array->sliceCount = 0; array->itemCount = 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 | INLINE void *pushItem(SlicedArray *array) { sizet prevSliceCount = array->sliceCount; void *result = pushSize(&array->arena, array->effectiveItemSize, noAlignNoClear()); ++array->itemCount; array->sliceCount = array->arena.blockCount; if (prevSliceCount != array->sliceCount) { array->slices[array->sliceCount - 1] = (uptr *)array->arena.base; } return result; } |
1 2 3 4 5 6 7 8 | INLINE void *getItem(SlicedArray *array, sizet index) { sizet sliceIndex = (index / array->itemsPerSlice); sizet itemIndex = (index % array->itemsPerSlice); void *slice = array->slices[sliceIndex]; void *result = (u8 *)slice + (itemIndex * array->effectiveItemSize); return result; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | struct Item; /* some data type */ SlicedArray array; initSlicedArray(&array, MEGABYTES(1), sizeof(Item), 4); Item *item = pushItem(&array); /* adding */ Item *firstItem = getItem(&array, 0); /* fetching */ /* iteration */ sizet itemIndex; for (itemIndex = 0; itemIndex < array.itemCount; ++itemIndex) { Item *item = getItem(&array, itemIndex); } |