Mastodon Feed
dysfun@treehouse.systems ("gaytabase") wrote:
when you write this down, much of the design falls out quite naturally. adding or incrementing only happens at the end of the list. the rest must be searched. we are chunking, we can search just the first element of each chunk to just locate the chunk we need to look at, then there are only 32 elements to search.
then there's the question of how to handle individual chunks. of course we start by filling them out in order. we can keep a pair of integers marking out the used range of a block's entries. this allows for the lowest or highest key to be removed easily and that space quickly reused (although this mostly benefits the last block).
and what do we do when we introduce a gap by reducing the refcount to 0? do we remove it or leave it in place? similarly, do we attempt to merge multiple partially-filled blocks (blocks become partially full when we delete entries)? if you can find space by moving elements, you can avoid extra allocation. but what heuristic gives the best payoff?
i'm still deciding.