[−][src]Module basic_allocator::blocklist
A linked list of memory blocks
This module provides two main abstractions:
Blocklist, a linked list of memory blocks, and
FreeBlock, a memory block in that list.
FreeBlock
The basic unit in this module is the FreeBlock. A
FreeBlock is a safe wrapper around a pointer to a memory block "owned" by
that FreeBlock, in the sense that the FreeBlock should have exclusive
read-write privileges for that memory block. These memory blocks could be
managed by a memory allocator, e.g. sections of a static array or boxed
arrays (see e.g. ToyHeap), or as is
the case in this package, free memory on the heap.
Internals
Each FreeBlock consists of a non-null pointer to a section of memory. That
memory starts with a FreeHeader, which consists
of an Option<FreeBlock> (e.g., a nullable pointer to the next memory
block) and a size denoting the size of the current block.
FreeBlock does not implement Copy or Clone, because it should be the
exclusive pointer to a block of memory. Safe methods returning a FreeBlock
are marked with #[must_use], as dropping a FreeBlock leaks memory.
FreeBlock implements Drop with a debug_assert!(false), as it should
never be simply dropped; internally, we use mem::forget when necessary.
Blocklist
A Blocklist is a linked list of memory blocks,
called FreeBlocks. The ownership model is that
the BlockList owns the first FreeBlock, and
each FreeBlock owns the next.
As a consequence, IterMut cannot be safely implemented on BlockList, as
the list does not own the blocks directly, but indirectly, and changes to
one block can affect the structure of the list. Instead, a general-purpose
apply function is implemented.
Structs
| BlockIter | |
| BlockList | A |
| FreeBlock | A |
| FreeHeader | The header for our free blocks. |
| Stats | |
| Validity | Validity contains a representation of all invalid states found in a BlockList. |
Enums
| ApplyState | State after a single "apply". |
| Relation | An enum for easy comparison of blocks and their order |