Memory Allocation - Explicit free list

This project was designed for the purpose of the assignment of the subject Data Structures and Algorithms.
This program is a simulation of memory allocation similar to the functionality found int the stdlib.h library. Explicit free list method with first and best fit algorithm for searching free blocks.

Memory block design

• Total size of free block: 16B
• Total size of full block: 8B

Free block design

Header (12B)	Payload	Footer (4B)
size | next	content	size

Full block design

Header (4B)	Payload	Footer (4B)
size	content	size

Compile and Run

Windows and Linux compatible.

gcc main.c -o main

./main

Interface

void memory_init(void *ptr, c_size_t size);
void *memory_alloc(c_size_t size);
int memory_check(const void *ptr);
int memory_free(void *valid_ptr);

Project structure

• main.c: Main file with examples and tests.
• headers: Header files containing memory allocation algorithm.
• tests: Folder with tests and header file containing helper functions for tests.

Options

Situated in main.c.

#define CLEAR
#define ERROR

• CLEAR: Clear garbage values like old headers and footers.
• ERROR: Error messages.

Comment out to turn off.

Usage

1. At first you need to call memory_init with parameters: pointer to the start of the region and size of the region.

2. Then you can use other functions like memory_alloc (malloc), memory_free (free) and memory_check.

Description of functions

memory_init

• Time complexity: O(1)
• Space complexity: O(1)

memory_alloc

• Time complexity: O(n), n = linked list nodes
• Space complexity: O(1)

memory_free

• Time complexity: O(n), n = linked list nodes
• Space complexity: O(1)

memory_check

• Time complexity: O(n), n = memory blocks
• Space complexity: O(1)

By @PeterSkriba, FIIT STU BA 👍