This heap uses a 'segregated free list' system: the first list contains 16-octet blocks (including the header), the second list contains 32-octet blocks, the third has 64-octet blocks, etc. When there are N free lists, the last is for blocks of 16*2^(N-1) octets. Each block starts with an 8-octet header. If a block is in use, the header contains the block's size. If a block is still free, the header contains a pointer to the next block on the same free list.
An array with the starts of each free-list. This is an in-memory version of the array that's in the beginning of the heap.
The size of the smallest blocks. This must be a power of 2.
The minimum number of bytes that will be used to expand a free-list.
(defclass free-list-heap (heap)
((nr-free-lists :initarg :nr-free-lists :initform 32 :reader nr-free-lists)
(starts :documentation "An array with the starts of each free-list. This
is an in-memory version of the array that's in the beginning of the heap.")
(min-block-size :initarg :min-block-size
:initform 16 :reader min-block-size
:documentation "The size of the smallest blocks. This must
be a power of 2.")
(expansion-size :initarg :expansion-size
:initform (* 32 1024) :reader expansion-size
:documentation "The minimum number of bytes that will be
used to expand a free-list."))
(:documentation "This heap uses a 'segregated free list' system: the
first list contains 16-octet blocks (including the header), the second
list contains 32-octet blocks, the third has 64-octet blocks, etc. When
there are N free lists, the last is for blocks of 16*2^(N-1) octets.
Each block starts with an 8-octet header. If a block is in use, the
header contains the block's size. If a block is still free, the header
contains a pointer to the next block on the same free list."))