Design Memory Allocator - Leetcode Solution

Problem Statement:

Design a memory allocator that allocates and deallocates memory blocks of different sizes.

Solution:

When we make the request for memory allocation through malloc or new operator, it calls a function allocating some bytes of memory from the heap. This memory allocator can be seen as a program that manages this allocation of memory and returns a pointer to the requested block of memory. We will design a memory allocator that needs to allocate memory blocks that can be of any sizes.

Approach:

Our approach is based on two fundamental operations: allocating and deallocating memory.

Functions of Memory Allocator

1. Initialization: The first thing we need to do before using an allocator is initialize it. During the initialization, we set up the allocator so that it can be ready to manage memory blocks.

2. Allocation: When an allocation request comes in, we need to allocate space in memory for the requested block. If there are not enough unallocated blocks to satisfy the request, a new block will have to be allocated from the heap.

3. Deallocation: After the program has finished using a memory block, it must be deallocated. This means that the previously allocated block is made available again.

Design and Implementation of Allocator

For our Memory Allocator, we will use a combination of a bitmap, a free list or a heap.

Bitmap:

A bitmap is a simple structure that is used to denote the status of individual memory blocks. In essence, it is a boolean array that has one bit for each memory block in the heap. If the bit is 0, the block is free, if it is 1, the block is in use.

Free List:

The free list is a linked list of free memory blocks, each with the size and the starting address of the block. It is used to keep track of the free blocks in memory.

Heap:

The heap is an area of memory that is allocated at the start of the program and is used to hold all the memory blocks allocated by the program.

The basic idea behind this allocator is to use a free list and allocate memory blocks of predetermined sizes. When an allocation request is made, the free list is checked for an available block of the required size. If a block is found, it is allocated and added to the list of allocated blocks. If no block of the required size is found, a new block is allocated from the heap and added to the list of allocated blocks.

For deallocation, the block is removed from the list of allocated blocks and added to the free list.

Code implementation:

typedef struct block
{
    unsigned int size;
    struct block *next;
} Block;

Block *freeList;   //head of free list
void *heapStart;   //reference to start address

void initialize_allocator(size_t size) //initialize allocator
{
    heapStart = malloc(size);    //allocate memory from heap
    freeList = (Block*) heapStart;
    freeList->size = size - sizeof(Block);
    freeList->next = NULL;
}

void *allocate(size_t size)  //function to allocate memory
{
    Block *prev = freeList;
    Block *curr = freeList;

    while(curr != NULL)
    {
        if(curr->size >= size)  //if block size is greater or equal to required size
        {
            if(curr->size == size)  //if block size and required size match
            {
                prev->next = curr->next;
                return (void*)(curr + 1);
            }
            else   //if block size is greater than required size
            {
                Block *temp = (Block*)((void*)curr + sizeof(Block) + size);
                temp->size = curr->size - sizeof(Block) - size;
                temp->next = curr->next;
                prev->next = temp;
                curr->size = size;
                return (void*)(curr + 1);
            }
        }
        prev = curr;
        curr = curr->next;
    }
    return NULL;
}

void deallocate(void *p)   //function to deallocate memory
{
    Block *b = (Block*)((void*)p - sizeof(Block));
    Block *prev = freeList;
    Block *curr = freeList;

    while(curr != NULL)
    {
        if(curr > b)
        {
            break;
        }
        prev = curr;
        curr = curr->next;
    }

    if(prev == curr)
    {
        prev = b;
        prev->next = curr;
    }
    else if(curr == NULL)
    {
        prev->next = b;
        b->next = NULL;
    }
    else
    {
        prev->next = b;
        b->next = curr;
    }
}

Complexity Analysis:

The time complexity of the allocation function is O(N) where N is the number of blocks in the free list. However, the average time complexity can be considered as O(1), because it is most likely that the block we are searching for is at the beginning of the list.

The time complexity of the deallocation function is O(N) where N is the total number of blocks either in the allocated blocks or in the free list. Again, the average time complexity can be considered as O(1), because it is most likely that the block we are searching for is at the beginning of the free list.

Conclusion:

We successfully designed a memory allocator that can allocate and deallocate memory blocks of different sizes by using Bitmap, Free List, and Heap. We used an initializing function to set up the allocator so that it can be ready to manage memory blocks. The allocate function is used to allocate space in memory for the requested block, and the deallocate function is used to deallocate the allocated block. The time complexity of both the functions is O(N), but the average time complexity can be considered as O(1) for both.

1