Free list
Free list
New header at cell at 3
To avoid fragmentation, we have 8 free lists of different sized free cell blocks:
|<------------------ 256 bits ----------------->|
|<idx1>|<idx2|<idx3-4>|<idx5-8>|...|<idx65-more>|
-
idxI-J
is the head of the free list of contiguous block size between I to J (inclusive). - 0 is for NULL
Free cell
The last cell
|<------------------ 256 bits ----------------->|
|<-n cells (32bits)>|<-prev->|<-next->| |-253|
- The first 32 bits are the number of cells in this free cell block, including itself.
- The next 32 bits are the pointer to the last cell of the previous free cell block. If 0, it is the first of the list.
- The 3rd 32 bits are the pointer to the last cell of the next free cell block. If 0, it is the end of the list.
The first cell (if n > 1)
|<------------------ 256 bits ----------------->|
|<-n cells (32bits)>|<- 1 ->|<- 1 ->| |-253|
- If the free cell block has more than 1 cells, the first cell must be also marked for free block concatenation.
Concatenation free cell block
When a new free block is added, and it finds other free blocks adjacent to it, they must be merged. The double links of the merged blocks must be taken care of properly.
Integrity
The integrity of the free lists must be assured by journaling. See #80 (closed)
APIs
allocate : t -> int -> (t * Index.t) option
add : t -> (Index.t * int) -> t