hh::halloc::Block Class Reference

Manages a contiguous memory block with RB-tree based allocation. More...

#include <Block.hpp>

Public Member Functions
	Block ()
	Default constructor - creates invalid block.
	Block (std::size_t bytes)
	Constructs a memory block of specified size.
	Block (Block &&other)
	Move constructor.
Block &	operator= (Block &&other)
	Move assignment operator.
MemoryNode *	best_fit (std::size_t bytes)
	Finds best-fit free node for allocation.
	~Block ()
	Destructor - releases memory back to OS.
std::size_t	get_size () const
	Gets total block size.
void *	get_head () const
	Gets pointer to the head node.
void *	allocate (std::size_t bytes, MemoryNode *node)
	Allocates memory from a specific node.
void	deallocate (void *ptr, std::size_t bytes)
	Deallocates previously allocated memory.
void	log_block_state (std::ofstream &logfile) const
	Logs the current state of the block to a file.

Detailed Description

Manages a contiguous memory block with RB-tree based allocation.

The Block class provides memory allocation and deallocation within a fixed memory region. It uses:

• Red-Black tree for O(log n) best-fit searches among free blocks
• Doubly-linked list for O(1) merging of adjacent free blocks

Memory is obtained from the OS via mmap and released via munmap. Internal fragmentation is minimized through block splitting and coalescing.

Constructor & Destructor Documentation

Block() [1/3]

hh::halloc::Block::Block

(

)

Default constructor - creates invalid block.

Postcondition

size = 0, head = nullptr

Block() [2/3]

hh::halloc::Block::Block ( std::size_t  bytes )

explicit

Constructs a memory block of specified size.

Allocates memory from OS via mmap and initializes the block with a single large free node.

Parameters

bytes

Total block size in bytes

Exceptions

std::bad_alloc

if mmap fails

Postcondition

Block is initialized with one free node of size (bytes - MEMORY_NODE_SIZE)

Block() [3/3]

hh::halloc::Block::Block

(

Block &&

other

)

Move constructor.

Parameters

other

Block to move from

Postcondition

other is left in valid but empty state

~Block()

hh::halloc::Block::~Block

(

)

Destructor - releases memory back to OS.

Destructor - releases the entire memory block back to the OS.

Postcondition

Memory is returned via munmap

Uses munmap to return the entire mmap'd region to the operating system. This deallocates all memory nodes at once, regardless of individual allocation status.

Postcondition

All memory in this Block is returned to OS

head pointer is invalid after this call

Member Function Documentation

allocate()

void * hh::halloc::Block::allocate	(	std::size_t	bytes,
		MemoryNode *	node
	)

Allocates memory from a specific node.

Allocates memory from a specific free node.

Removes node from RB-tree, potentially splits it if too large, and returns pointer to usable memory (after metadata).

Parameters

bytes	Size in bytes requested
node	The node to allocate from (typically from best_fit)

Returns

Pointer to usable memory (skips MEMORY_NODE_SIZE header)

Precondition

node must be a valid free node from this block

Postcondition

node is marked as used

If node was larger, remainder is added as new free node

This function performs the final allocation step after best_fit has found a suitable node:

1. Removes the node from the RB-tree of free blocks
2. Splits the node if it's larger than needed (via shrink_then_align)
3. Marks the node as used
4. Returns pointer to usable memory (after metadata)

Parameters

bytes	Number of bytes requested by user (excluding metadata)
node	Free node to allocate from (must be large enough)

Returns

void* Pointer to usable memory area (metadata already skipped)

Precondition

node != nullptr

is_free(node->value) == true

get_actual_value(node->value) >= bytes

Postcondition

is_free(node->value) == false (node marked as used)

If node was split, a new free node exists in RB-tree

best_fit()

MemoryNode * hh::halloc::Block::best_fit

(

std::size_t

bytes

)

Finds best-fit free node for allocation.

Searches the RB-tree for the smallest free node that can fit the requested size.

Parameters

bytes

Size in bytes to allocate

Returns

Pointer to best-fit node, or nullptr if no suitable node exists

Note

Uses RB-tree's lower_bound for O(log n) search

deallocate()

void hh::halloc::Block::deallocate	(	void *	ptr,
		std::size_t	bytes
	)

Deallocates previously allocated memory.

Deallocates previously allocated memory and merges with adjacent free blocks.

Marks the region as free and attempts to merge with adjacent free blocks to reduce fragmentation.

Parameters

ptr	Pointer returned from allocate()
bytes	Size parameter (currently unused)

Precondition

ptr must have been returned from allocate() on this block

Postcondition

Memory is marked as free

Adjacent free blocks are merged if possible

Merged block is inserted into RB-tree

This function reverses the allocation:

1. Converts user pointer back to MemoryNode pointer
2. Marks the node as free
3. Attempts to merge with adjacent free blocks (coalescing)
4. Inserts the (possibly merged) node into RB-tree

Coalescing reduces fragmentation by combining adjacent free blocks into larger blocks.

Parameters

ptr	Pointer previously returned by allocate() (not the MemoryNode pointer)
bytes	Size parameter (unused, for interface compatibility)

Precondition

ptr != nullptr

ptr was previously returned by allocate()

The block containing this node has not been destroyed

Postcondition

Node is marked as free

Node is inserted into RB-tree (possibly merged with neighbors)

Adjacent free blocks are coalesced if possible

get_head()

void * hh::halloc::Block::get_head ( ) const

inline

Gets pointer to the head node.

Returns

Pointer to first memory node

get_size()

std::size_t hh::halloc::Block::get_size ( ) const

inline

Gets total block size.

Returns

Size in bytes including all metadata

log_block_state()

void hh::halloc::Block::log_block_state ( std::ofstream &  logfile ) const

inline

Logs the current state of the block to a file.

The log includes: Address: memory address of the block Total Size: of the block For each MemoryNode: Address | Size | Status (Free/Used) Summary statistics: Actual Free Space (The data used by the app) Total Used Space Headers Used Space Number of Free Nodes Number of Used Nodes

Parameters

logfile_dir

Path to the log file.

Postcondition

Appends the block state information to the specified log file.

operator=()

Block & hh::halloc::Block::operator=

(

Block &&

other

)

Move assignment operator.

Parameters

other

Block to move from

Returns

Reference to this block

Postcondition

other is left in valid but empty state

---

The documentation for this class was generated from the following files:

• halloc/includes/Block.hpp
• halloc/src/Block.cpp