# Bigger Example 1: Custom Memory Allocator

Question: Develop a basic memory allocator that mimics the functionality of malloc() and free() in C. The allocator should manage a pool of memory and provide functions for allocating and freeing memory blocks. Implement features such as coalescing adjacent free blocks to optimize memory usage.

Below is a simple implementation of a basic memory allocator in C that mimics the functionality of `malloc()` and `free()`. The allocator manages a pool of memory and provides functions for allocating and freeing memory blocks. It also includes a basic coalescing mechanism to optimize memory usage.

```c
#include <stdio.h>
#include <stdlib.h>

#define MEMORY_POOL_SIZE 1024

typedef struct Block {
    size_t size;
    struct Block* next;
} Block;

static char memoryPool[MEMORY_POOL_SIZE];

static Block* freeList = NULL;

void initializeAllocator() {
    // Initialize the allocator with a single block representing the entire memory pool
    freeList = (Block*)memoryPool;
    freeList->size = MEMORY_POOL_SIZE - sizeof(Block);
    freeList->next = NULL;
}

void* myMalloc(size_t size) {
    if (size == 0 || size > MEMORY_POOL_SIZE) {
        return NULL; // Invalid size
    }

    Block* current = freeList;
    Block* previous = NULL;

    // Find the first block that is large enough to accommodate the requested size
    while (current != NULL && (current->size < size)) {
        previous = current;
        current = current->next;
    }

    if (current == NULL) {
        return NULL; // Out of memory
    }

    // If the block is larger than needed, split it into two blocks
    if (current->size > size + sizeof(Block)) {
        Block* newBlock = (Block*)((char*)current + sizeof(Block) + size);
        newBlock->size = current->size - sizeof(Block) - size;
        newBlock->next = current->next;
        current->size = size;
        current->next = newBlock;
    }

    // Remove the allocated block from the free list
    if (previous == NULL) {
        freeList = current->next;
    } else {
        previous->next = current->next;
    }

    return (void*)((char*)current + sizeof(Block));
}

void myFree(void* ptr) {
    if (ptr == NULL) {
        return; // Invalid pointer
    }

    // Add the freed block back to the free list
    Block* block = (Block*)((char*)ptr - sizeof(Block));
    block->next = freeList;
    freeList = block;

    // Coalesce adjacent free blocks
    Block* current = freeList;
    while (current != NULL && current->next != NULL) {
        if ((char*)current + sizeof(Block) + current->size == (char*)current->next) {
            // Merge current and the next block
            current->size += sizeof(Block) + current->next->size;
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
}

int main() {
    initializeAllocator();

    // Example usage
    int* a = (int*)myMalloc(sizeof(int));
    *a = 42;
    printf("Allocated memory for integer: %d\n", *a);

    double* b = (double*)myMalloc(sizeof(double));
    *b = 3.14;
    printf("Allocated memory for double: %f\n", *b);

    myFree(a);
    printf("Freed memory for integer\n");

    char* c = (char*)myMalloc(50);
    printf("Allocated memory for char array\n");

    myFree(b);
    myFree(c);

    return 0;
}
```

Let's break down the provided C code step by step:

### Header Files:

```c
#include <stdio.h>
#include <stdlib.h>
```

These are standard header files in C. `<stdio.h>` is for input/output operations, and `<stdlib.h>` is for memory allocation and other standard library functions.

### Macros:

```c
#define MEMORY_POOL_SIZE 1024
```

Defines the size of the memory pool, which is a fixed-size array named `memoryPool`. This is the total amount of memory that the allocator manages.

### Data Structure:

```c
typedef struct Block {
    size_t size;
    struct Block* next;
} Block;
```

Defines a structure `Block` representing a memory block. It contains the size of the block and a pointer to the next block.

### Global Variables:

```c
static char memoryPool[MEMORY_POOL_SIZE];
static Block* freeList = NULL;
```

* `memoryPool` is an array of characters representing the memory pool.
    
* `freeList` is a pointer to the linked list of free memory blocks.
    

### Function: `initializeAllocator()`

```c
void initializeAllocator() {
    freeList = (Block*)memoryPool;
    freeList->size = MEMORY_POOL_SIZE - sizeof(Block);
    freeList->next = NULL;
}
```

* Initializes the allocator by setting the free list to the beginning of the memory pool.
    
* The size of the initial block is set to the entire size of the memory pool minus the size of the `Block` structure.
    

### Function: `myMalloc(size_t size)`

```c
void* myMalloc(size_t size) {
    if (size == 0 || size > MEMORY_POOL_SIZE) {
        return NULL; // Invalid size
    }
    // ...
}
```

* Checks if the requested size is valid.
    
* Searches for the first free block that can accommodate the requested size.
    
* If the block is larger than needed, it is split into two blocks.
    
* Removes the allocated block from the free list and returns a pointer to the allocated memory.
    

### Function: `myFree(void* ptr)`

```c
void myFree(void* ptr) {
    if (ptr == NULL) {
        return; // Invalid pointer
    }
    // ...
}
```

* Checks if the pointer is valid.
    
* Adds the freed block back to the free list.
    
* Coalesces adjacent free blocks to optimize memory usage.
    

### Function: `main()`

```c
int main() {
    initializeAllocator();
    // ...
}
```

* Calls `initializeAllocator()` to set up the memory allocator.
    

```c
int* a = (int*)myMalloc(sizeof(int));
*a = 42;
printf("Allocated memory for integer: %d\n", *a);
```

* Allocates memory for an integer, sets its value, and prints the allocated memory.
    

```c
double* b = (double*)myMalloc(sizeof(double));
*b = 3.14;
printf("Allocated memory for double: %f\n", *b);
```

* Allocates memory for a double, sets its value, and prints the allocated memory.
    

```c
myFree(a);
printf("Freed memory for integer\n");
```

* Frees the memory allocated for the integer and prints a message.
    

```c
char* c = (char*)myMalloc(50);
printf("Allocated memory for char array\n");
```

* Allocates memory for a character array and prints a message.
    

```c
myFree(b);
myFree(c);
```

* Frees the memory allocated for the double and character array.
    

### Summary:

* The code implements a simple memory allocator with a fixed-size memory pool and basic memory allocation and deallocation functions.
    
* It maintains a linked list of free memory blocks, coalescing adjacent free blocks to optimize memory usage.
    
* The `main()` function demonstrates the usage of the allocator by allocating and freeing memory for different data types.