Classes
struct	MemNode
	Metadata structure for each memory block. More...

Typedefs
using	MemSizeT = unsigned long long
	Type definition for memory size.

Functions
bool	is_free (MemSizeT &size)
	Check if block is free using bit 63.

void	make_free (MemSizeT &size)
	Mark block as free by setting bit 63.

void	make_used (MemSizeT &size)
	Mark block as used by clearing bit 63.

MemSizeT	get_size (MemSizeT &size)
	Extract actual size by masking off bit 63.

MemSizeT	add (MemSizeT a, MemSizeT b)
	Add two sizes (clearing free bits first).

MemSizeT	sub (MemSizeT a, MemSizeT b)
	Subtract two sizes (clearing free bits first).

void *	sbrk_then_alloc (MemSizeT size)
	Request memory from OS using sbrk and allocate.

void	coalesce_nodes (MemNode *nd)
	Merge a free node with adjacent free nodes.

void *	free (void *ptr)
	Free a memory block and merge with adjacent free blocks.

void	shrink_then_align (MemNode *nd, MemSizeT size)
	Shrink a block and create a new free block from remainder.

void *	try_alloc (MemSizeT size)
	Allocate memory using first-fit strategy.

void	mem_copy (void dest, const void src, size_t n)
	Copy n bytes from source to destination.

void *	try_realloc (void *ptr, MemSizeT size)
	Reallocate a memory block to a new size.

void	mem_set (void *ptr, int value, size_t num)
	Set num bytes to specified value.

void *	try_calloc (size_t num, size_t size)
	Allocate and zero-initialize an array.

void	alloc_print ()
	Print allocation status table for debugging.

Variables
MemNode *	__head = nullptr
	Pointer to the head of the memory block linked list.

MemNode *	__tail = nullptr

constexpr MemSizeT	MIN_FRAGMENT_SIZE = 32
	Minimum fragment size to consider splitting a block.

constexpr MemSizeT	BLOCK_SIZE = 4096
	Size of each memory block requested from OS via sbrk.

constexpr MemSizeT	MEM_NODE_SIZE = sizeof(MemNode)
	Size of the MemNode structure.

Typedef Documentation

◆ MemSizeT

using hh::basic_alloc::MemSizeT = typedef unsigned long long

Type definition for memory size.

Function Documentation

◆ add()

MemSizeT hh::basic_alloc::add	(	MemSizeT	a,
		MemSizeT	b
	)

inline

Add two sizes (clearing free bits first).

Add two memory sizes with overflow checking.

Parameters

a	First operand
b	Second operand

Returns: a + b with free bits cleared

Parameters

a	First operand
b	Second operand

Returns: a + b

Exceptions

std::overflow_error if addition overflows

◆ alloc_print()

void hh::basic_alloc::alloc_print ( )

Print allocation status table for debugging.

Print allocation status for debugging.

Displays all blocks with:

Address
Size (excluding metadata)
Total size (including metadata)
Status (FREE/USED)
Previous and next pointers
Summary statistics

Displays all blocks (free and used) with their sizes and addresses.

Postcondition: Allocator state is unchanged

Note: For debugging purposes only

◆ coalesce_nodes()

void hh::basic_alloc::coalesce_nodes ( MemNode * nd )

Merge a free node with adjacent free nodes.

Merge adjacent free blocks to reduce fragmentation.

Attempts to coalesce:

Forward: if next node is free, merge into current
Backward: if previous node is free, merge current into previous

This reduces fragmentation by combining adjacent free blocks.

Parameters

nd	Node to merge (must be free)

Precondition: nd is marked as free

Postcondition: Adjacent free blocks are merged

Attempts to merge the given free node with:

Next node (if free)
Previous node (if free)

Parameters

nd	Node to merge (must be free)

Precondition: nd != nullptr; is_free(nd->size) == true

Postcondition: Adjacent free blocks are coalesced

◆ free()

void * hh::basic_alloc::free ( void * ptr )

Free a memory block and merge with adjacent free blocks.

Free a previously allocated memory block.

Parameters

ptr	Pointer to memory (returned by try_alloc)

Returns: Always nullptr

Postcondition: Block is marked as free and merged if possible

Marks the block as free and attempts to merge with adjacent free blocks.

Parameters

ptr	Pointer to memory (returned by try_alloc)

Returns: Always returns nullptr

Precondition: ptr != nullptr; ptr was allocated by try_alloc

Postcondition: Block is marked as free; Block is merged with adjacent free blocks if possible

◆ get_size()

MemSizeT hh::basic_alloc::get_size ( MemSizeT & size )

inline

Extract actual size by masking off bit 63.

Get the actual size of a block (excluding free bit).

Parameters

size	Size field from MemNode

Returns: Size in bytes without free/used bit

Parameters

size	Size field from MemNode

Returns: Size in bytes (bit 0 masked out)

◆ is_free()

bool hh::basic_alloc::is_free ( MemSizeT & size )

inline

Check if block is free using bit 63.

Check if a block is free.

Parameters

size	Size field from MemNode

Returns: true if bit 63 is set (free), false otherwise (used)

Parameters

size	Size field from MemNode

Returns: true if block is free (bit 0 == 1), false if used

◆ make_free()

void hh::basic_alloc::make_free ( MemSizeT & size )

inline

Mark block as free by setting bit 63.

Mark a block as free.

Parameters

size	Size field from MemNode

Postcondition: Bit 63 of size is set to 1

Parameters

size	Size field from MemNode

Postcondition: Bit 0 of size is set to 1

◆ make_used()

void hh::basic_alloc::make_used ( MemSizeT & size )

inline

Mark block as used by clearing bit 63.

Mark a block as used.

Parameters

size	Size field from MemNode

Postcondition: Bit 63 of size is cleared to 0

Parameters

size	Size field from MemNode

Postcondition: Bit 0 of size is cleared to 0

◆ mem_copy()

void hh::basic_alloc::mem_copy	(	void *	dest,
		const void *	src,
		size_t	n
	)

Copy n bytes from source to destination.

Copy memory from source to destination.

Parameters

dest	Destination pointer
src	Source pointer
n	Number of bytes to copy

Note: Simple byte-by-byte copy (not optimized)

Parameters

dest	Destination pointer
src	Source pointer
n	Number of bytes to copy

Precondition: dest and src do not overlap

Postcondition: n bytes copied from src to dest

◆ mem_set()

void hh::basic_alloc::mem_set	(	void *	ptr,
		int	value,
		size_t	num
	)

Set num bytes to specified value.

Set a block of memory to a specific value.

Parameters

ptr	Pointer to memory
value	Value to set (cast to unsigned char)
num	Number of bytes to set
ptr	Pointer to memory block
value	Value to set (cast to unsigned char)
num	Number of bytes to set

Postcondition: num bytes at ptr are set to value

◆ sbrk_then_alloc()

void * hh::basic_alloc::sbrk_then_alloc ( MemSizeT size )

Request memory from OS using sbrk and allocate.

Request memory from OS and allocate.

Extends program break by size + metadata, creates new MemNode, and adds it to the tail of the linked list.

Parameters

size	Requested allocation size (excluding metadata)

Returns: Pointer to usable memory (after MemNode header)

Exceptions

std::bad_alloc if sbrk fails

Uses sbrk() to extend the program break by at least size bytes (rounded up to BLOCK_SIZE multiples). Creates a new MemNode and returns pointer to usable memory.

Parameters

size	Number of bytes requested

Returns: Pointer to allocated memory, or nullptr on failure

Postcondition: Program break is extended; New block is added to linked list; Block is marked as used

◆ shrink_then_align()

void hh::basic_alloc::shrink_then_align	(	MemNode *	nd,
		MemSizeT	size
	)

Shrink a block and create a new free block from remainder.

If the fragment is large enough (> MIN_FRAGMENT_SIZE + metadata), splits the block:

Current node becomes 'size' bytes (used)
Remainder becomes a new free node

Parameters

nd	Node to shrink
size	Desired size for node

Postcondition: If split: nd->size == size and new free node created; If no split: nd remains unchanged

If the node is significantly larger than requested size, splits it:

Current node becomes 'size' bytes (used)
Remainder becomes a new free node

Parameters

nd	Node to shrink
size	Desired size for node

Precondition: nd != nullptr

Postcondition: nd->size == size (if split occurred); If split, a new free node exists after nd

◆ sub()

MemSizeT hh::basic_alloc::sub	(	MemSizeT	a,
		MemSizeT	b
	)

inline

Subtract two sizes (clearing free bits first).

Subtract two memory sizes with underflow checking.

Parameters

a	Minuend
b	Subtrahend

Returns: a - b with free bits cleared

Parameters

a	Minuend
b	Subtrahend

Returns: a - b

Exceptions

std::underflow_error if subtraction underflows

◆ try_alloc()

void * hh::basic_alloc::try_alloc ( MemSizeT size )

Allocate memory using first-fit strategy.

Allocate a memory block using first-fit strategy.

Searches linked list for first free block large enough. If found, allocates from that block (splitting if necessary). If not found, requests more memory from OS via sbrk.

Parameters

size	Number of bytes to allocate

Returns: Pointer to allocated memory, or nullptr if size is 0

Note: Time complexity: O(n) where n = number of blocks

Searches the linked list for the first free block large enough to satisfy the request. If found, splits if necessary and marks as used. If not found, requests more memory from OS via sbrk_then_alloc.

Parameters

size	Number of bytes to allocate

Returns: Pointer to allocated memory, or nullptr on failure

Postcondition: If successful, returned pointer is valid; Block is marked as used

Note: Time complexity: O(n) where n = number of blocks

◆ try_calloc()

void * hh::basic_alloc::try_calloc	(	size_t	num,
		size_t	size
	)

Allocate and zero-initialize an array.

Parameters

num	Number of elements
size	Size of each element

Returns: Pointer to zero-initialized memory, or nullptr on failure

Note: Checks for overflow before allocation

Allocates num * size bytes and initializes all bytes to zero.

Parameters

num	Number of elements
size	Size of each element

Returns: Pointer to zero-initialized memory, or nullptr on failure

Postcondition: All bytes in allocated memory are zero

◆ try_realloc()

void * hh::basic_alloc::try_realloc	(	void *	ptr,
		MemSizeT	size
	)

Reallocate a memory block to a new size.

If new size fits in current block, shrinks in place. Otherwise, allocates new block, copies data, and frees old block.

Parameters

ptr	Pointer to existing allocation (or nullptr)
size	New size in bytes

Returns: Pointer to resized memory

Note: If ptr is nullptr, behaves like try_alloc

Attempts to resize the block in place if possible. Otherwise:

Allocate new block of requested size
Copy old data to new block
Free old block

Parameters

ptr	Pointer to existing allocation
size	New size in bytes

Returns: Pointer to resized memory, or nullptr on failure

Precondition: ptr was allocated by try_alloc (or nullptr)

Postcondition: If successful, old data is preserved (up to min(old_size, new_size)); Old pointer may be invalidated

Variable Documentation

◆ __head

MemNode * hh::basic_alloc::__head = nullptr

Pointer to the head of the memory block linked list.

◆ __tail

MemNode * hh::basic_alloc::__tail = nullptr

◆ BLOCK_SIZE

constexpr MemSizeT hh::basic_alloc::BLOCK_SIZE = 4096

constexpr

Size of each memory block requested from OS via sbrk.

◆ MEM_NODE_SIZE

constexpr MemSizeT hh::basic_alloc::MEM_NODE_SIZE = sizeof(MemNode)

constexpr

Size of the MemNode structure.

◆ MIN_FRAGMENT_SIZE

constexpr MemSizeT hh::basic_alloc::MIN_FRAGMENT_SIZE = 32

constexpr

Minimum fragment size to consider splitting a block.

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ MemSizeT

Function Documentation

◆ add()

◆ alloc_print()

◆ coalesce_nodes()

◆ free()

◆ get_size()

◆ is_free()

◆ make_free()

◆ make_used()

◆ mem_copy()

◆ mem_set()

◆ sbrk_then_alloc()

◆ shrink_then_align()

◆ sub()

◆ try_alloc()

◆ try_calloc()

◆ try_realloc()

Variable Documentation

◆ __head

◆ __tail

◆ BLOCK_SIZE

◆ MEM_NODE_SIZE

◆ MIN_FRAGMENT_SIZE