simple malloc and free implementation

malloc.cpp

/*
Imagine this is a block of memory. Goal is to give users access to parts of this global shared resource. 
They can access X memory locations by doing `malloc(X)` and can free it by returning the pointer they were handed

Goal of the question is to fill in class Allocator without using any additional class variables.

|--------------|0
|              |...
|--------------|
|              |
|--------------|
|              |
|--------------|
| ... x more   |1000

:> allocator.malloc(2)
:> 0


|--------------|0
|              |2
|--------------|...
|              |3
|--------------|...
|              |
|--------------|
| ... x more   |1000

Your algorithm runs and returns 0 (lets say). The user program then fills the two slots in with data 


:> allocator.malloc(20) 
:> 3

You return 3 because that's free.

|--------------|0
| USER 1 DATA  |2
|--------------|...
|              |3
|--------------|23
|              |...
|--------------|
| ... x more   |1000


Now let's go through a few more operations
:> allocator.malloc(10) 
:> 24


|--------------|0
| USER 1 DATA  |2
|--------------|...
| USER 2 DATA  |3
|--------------|23
|              |...
|--------------|
| ... x more   |1000

...

:> free 0

|--------------|0
|              |2
|--------------|...
| USER 2 DATA  |3
|--------------|23
| USER 3 DATA  |24
|--------------|34
|              |....
| ... x more   |1000


:> free 3

|--------------|0
|              |2
|--------------|...
|              |3
|--------------|23
| USER 3 DATA  |24
|--------------|34
|              |
|--------------|...
| ... x more   |1000


:> malloc(21)
:> 0
NOTE: Here 0 should return re-using and combining chunks of memory that were previously split

|--------------|0
| USER 1 DATA  |20
|--------------|...
|              |
|--------------|23
| USER 3 DATA  |24
|--------------|34
|              |
|--------------|...
| ... x more   |1000

*/

#include <iostream>
#include <vector>
#include <functional>
#include <cmath>

const int MEM_SIZE = 1000;

struct ControlBlock
{
  int16_t prev;
  int16_t next;
  bool free;
  uint8_t _pad[3]; // Padding to fill size of struct up to 2x int32
};

const int BLOCK_SIZE = sizeof(ControlBlock) / sizeof(int);


class Allocator {
private:
  ControlBlock* _cb_at(int addr)
  {
    return reinterpret_cast<ControlBlock*>(&memory_block[addr]);
  }

public:
  Allocator()
  {
    std::cout << "\nSizeof: " << sizeof(ControlBlock) << " | " << sizeof(int) << std::endl;

    memory_block = new int[MEM_SIZE];
    auto cb = _cb_at(0);
    cb->prev = -1;
    cb->next = MEM_SIZE;
    cb->free = true;
  }
  
  /*
   * This method will find if there is a memory chunk large enough for this allocation.
   * If there is, allocate it.  If not, return -1.
   *
   * size: int representing the number of integers I want control over.
   * return: The address where the caller can manipulate a memory block of the given size.
   */
  int malloc(int size)
  {
    std::cout << "Malloc: " << size << std::endl;

    int i = 0;
    while (i < MEM_SIZE)
    {
      auto cbi = _cb_at(i);
      
      if (cbi->free and cbi->next - i - BLOCK_SIZE >= size)
      {
        // create new control block at end of current allocation
        int j = i + size + BLOCK_SIZE;
        auto cbj = _cb_at(j);
        cbj->prev = i;
        cbj->next = cbi->next;
        cbj->free = true;
  
        // update current control block
        cbi->next = j;
        cbi->free = false;

        print();
        return i + BLOCK_SIZE;
      }
      
      i = cbi->next;
    }
    return -1;
  }
  
  /*
   * This method will allow a previously allocated memory block to be reallocated later.
   *
   * key: An address that was handed to you by the malloc()
   */
  void free(int key)
  {
    int i = key - BLOCK_SIZE;
    std::cout << "Free: " << i << std::endl;
    
    // Mark block as free
    auto cb = _cb_at(i);
    cb->free = true;

    if (cb->next < MEM_SIZE)
    {
      auto cb_next = _cb_at(cb->next);
      if (cb_next->free)
      {
        // If block after this block is also free, merge them.
        cb->next = cb_next->next;
        if (cb->next < MEM_SIZE)
        {
          _cb_at(cb->next)->prev = i;
        }
      }
    }

    if (cb->prev >= 0)
    {
      auto cb_prev = _cb_at(cb->prev);
      if (cb_prev->free)
      {
        // If block before this block is also free, merge them.
        cb_prev->next = cb->next;
        if (cb->next < MEM_SIZE)
        {
          _cb_at(cb->next)->prev = cb->prev;
        }
      }
    }
    print();
  }
  
  void print()
  {
    int i = 0;
    while (i < MEM_SIZE)
    {
      auto cb = _cb_at(i);
      std::cout << i << "\t[" << cb->free << "] " << cb->prev << "\t" << cb->next << std::endl;
      i = cb->next;
    }
  }

  int* memory_block;
  // |---------------------------------------|
  // |   NO OTHER CLASS VARIABLES ALLOWED    |
  // |---------------------------------------|
};


class Tests
{
public:
  Tests()
  {
    tests.push_back(std::bind(&Tests::test_0, this));
    tests.push_back(std::bind(&Tests::test_1, this));
    tests.push_back(std::bind(&Tests::test_2, this));
    tests.push_back(std::bind(&Tests::test_3, this));
  }
  
  std::vector<std::function<bool()>> tests;
  
  bool run_tests()
  {
    bool success = true;
    for (size_t i = 0; i < tests.size(); ++i)
    {
      bool pass = tests.at(i)();
      success = success && pass;
      std::cout << "\nTest " << i << " " << (pass ? "passed" : "failed") << std::endl;
    } 
    return success;
  }
    
  bool test_0()
  {
    auto allocator = Allocator();
    int a = allocator.malloc(400);
    int b = allocator.malloc(500);
    int c = allocator.malloc(600);
    // We cannot allocate c it is over the limit of space we have
    return (c == -1 && a > 0 && b > 0 && a != b);
  }
  
  bool test_1()
  {
    auto allocator = Allocator();
    int a = allocator.malloc(10);
    int b = allocator.malloc(20);
    int c = allocator.malloc(30);
    
    allocator.free(b);
    
    // Ideally d is allocated at a higher point than c
    int d = allocator.malloc(40);
    return (a > 0 && d > c);
  }
  
  bool test_2()
  {
    auto allocator = Allocator();
    int a = allocator.malloc(10);
    int b = allocator.malloc(20);
    int c = allocator.malloc(30);
    
    allocator.free(a);
    allocator.free(b);
    
    // Ideally the fragments from A & B combine and D is allocated where A was allocated
    int d = allocator.malloc(15);
    return (a == d && a !=-1 && c > 0);
  }   
  
  bool test_3()
  {
    auto allocator = Allocator();
    int a = allocator.malloc(10);
    int b = allocator.malloc(20);
    int c = allocator.malloc(30);
    
    allocator.free(b);
    allocator.free(c);
    
    // Ideally the fragments from B & C combine and D is allocated where b was allocated
    int d = allocator.malloc(100);
    return (b == d && a > 0 && b > 0 && c > 0);
  } 
};


int main()
{
  Tests t = Tests(); 
  if (t.run_tests())
  {
    std::cout << "All tests pass!  Huzzah!" << std::endl;
  }
  else
  {
    std::cout << "Some tests failed." << std::endl;
  }
}