Crate rulloc

General purpose memory allocator. Memory regions are requested from the underlying kernel using mmap syscalls on Unix platforms and VirtualAlloc on Windows platforms. This is how the allocator looks like internally:

                                 Next Free Block                    Next Free Block
                      +------------------------------------+   +-----------------------+
                      |                                    |   |                       |
     +--------+-------|----------------+      +--------+---|---|-----------------------|-----+
     |        | +-----|-+    +-------+ |      |        | +-|---|-+    +-------+    +---|---+ |
0 -> | Region | | Free  | -> | Block | | ---> | Region | | Free  | -> | Block | -> | Free  | |
     |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
     +--------+------------------------+      +--------+-------------------------------------+

                                              Next Free Block
                                 +----------------------------------------+
                                 |                                        |
     +--------+------------------|-----+      +--------+------------------|------------------+
     |        | +-------+    +---|---+ |      |        | +-------+    +---|---+    +-------+ |
1 -> | Region | | Block | -> | Free  | | ---> | Region | | Block | -> | Free  | -> | Block | |
     |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
     +--------+------------------------+      +--------+-------------------------------------+

..............................................................................................

                                        Next Free Block
                                 +---------------------------+
                                 |                           |
     +--------+------------------|-----+      +--------+-----|-------------------------------+
     |        | +-------+    +---|---+ |      |        | +---|---+    +-------+    +-------+ |
N -> | Region | | Block | -> | Free  | | ---> | Region | | Free  | -> | Block | -> | Block | |
     |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
     +--------+------------------------+      +--------+-------------------------------------+

The allocator contains multiple buckets, each bucket contains a list of regions and each region stores a list of memory blocks. Implemented optimizations:

• Block coalescing: merge adjacent free blocks into one bigger block.
• Block splitting: blocks that are too big are split in two blocks.
• Free list: linked list of only free blocks, finds free blocks faster.
• In place reallocations: if possible, avoid creating new memory blocks.
• Fixed size buckets: reduce fragmentation by grouping allocation sizes.

See Rulloc for usage examples.

Structs

Rulloc

This struct exposes the public interface by implementing std::alloc::Allocator.