Hello,
First of all, being fairly new to watching handmade hero, I have been trying to do my best to play catch up with understanding the design, though this is fairly difficult due to the sheer amount of episodes, so if I'm mistaken at any point, feel free to correct me.
Second of all, excuse me for having such a beginner-like question.
So, the way I understand the arena-style allocation works in HH, you allocate blocks of varying sizes, and to avoid invalidating the pointers, when a request doesn't fit in the block, you allocate a new block and add it to the list of blocks in a given arena, and provide memory from the newly-allocated block.
Right now I'm building a system which records user input, every entry being of size N.
Pushing entries into an arena of say, M*N is fairly simple, but without knowing the absolute maximum M in advance, how would you go about iterating (accessing) the list of entries, because of the possible block boundaries?
Note: In my case there would only ever be two actions performed on the data, pushing to the back of the list, and iterating from start to finish. How should I structure my data? Any help is greatly appreciated.
Thank you in advance!
First of all, being fairly new to watching handmade hero, I have been trying to do my best to play catch up with understanding the design, though this is fairly difficult due to the sheer amount of episodes, so if I'm mistaken at any point, feel free to correct me.
Second of all, excuse me for having such a beginner-like question.
So, the way I understand the arena-style allocation works in HH, you allocate blocks of varying sizes, and to avoid invalidating the pointers, when a request doesn't fit in the block, you allocate a new block and add it to the list of blocks in a given arena, and provide memory from the newly-allocated block.
Right now I'm building a system which records user input, every entry being of size N.
Pushing entries into an arena of say, M*N is fairly simple, but without knowing the absolute maximum M in advance, how would you go about iterating (accessing) the list of entries, because of the possible block boundaries?
Note: In my case there would only ever be two actions performed on the data, pushing to the back of the list, and iterating from start to finish. How should I structure my data? Any help is greatly appreciated.
Thank you in advance!
Edited by execi
on
Reason: Initial post
If you don't know the upper bound of your array, you have mainly 2 options:
1) Resize & Copy: when you fill the array, you either check if there's more room in the arena to resize it (i.e. update the capacity) or you make a new allocation for a bigger array and copy all contents of the old one into the new one. To make the latter work without wasting memory, you need a memory system more complex that a linear memory arena (e.g. malloc)
2) Use a linked list. Every link in the list can contain an array of elements so, when running out of space in one link, you allocate a new one from the arena (connect them via next/prev pointers) and start filling the next array.
There are pros & cons to both options. Also, you can create abstractions that hide the inner workings of your solution to make it look like an ever growing array (e.g. what std::vector does for option #1).
1) Resize & Copy: when you fill the array, you either check if there's more room in the arena to resize it (i.e. update the capacity) or you make a new allocation for a bigger array and copy all contents of the old one into the new one. To make the latter work without wasting memory, you need a memory system more complex that a linear memory arena (e.g. malloc)
2) Use a linked list. Every link in the list can contain an array of elements so, when running out of space in one link, you allocate a new one from the arena (connect them via next/prev pointers) and start filling the next array.
There are pros & cons to both options. Also, you can create abstractions that hide the inner workings of your solution to make it look like an ever growing array (e.g. what std::vector does for option #1).
You can also extend the array but that requires that there is something to extend into.
In other words if it was the last thing allocated in an arena and the block is large enough to hold it then you can increase that allocation.
In other words if it was the last thing allocated in an arena and the block is large enough to hold it then you can increase that allocation.