/**
 * Simple and educational `malloc` implementation.
 *
 * Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
 *
 * Maintains explicit linked list of allocated memory blocks. Each block
 * has a header, containing meta-information, such as whether a block is
 * free, its size, and a reference to the next block.
 *
 * Homework assignments:
 *
 *   - Implement "splitting" procedure (if an allocation request is smaller
 *     than the first free block, split the free block)
 *
 *   - Implement coalescing of blocks on free operation (merge two or more
 *     adjacent free blocks).
 *
 *   - Implement "explicit free list" (the "next" pointer points not to just
 *     the next block, but to an explicit "free" block). Faster allocation.
 *
 *   - Implement "segregated free list" (partition the allocations by block
 *     size, power of 2). Faster allocation.
 */

#include <iostream>

#include <sys/types.h>
#include <unistd.h>
#include <string.h>

using namespace std;

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wdeprecated-declarations"

/**
 * Memory blocks alignment by 4.
 *
 * malloc(4) -> 4
 * malloc(2) -> 4
 * malloc(5) -> 8
 * etc.
 */
#define ALLIGN_4(x) (((((x) - 1) >> 2) << 2) + 4)

/**
 * Memory block.
 *
 * Consists of a header, and a pointer to the payload
 * returned to a user.
 */
struct Block {
  /**
   * Meta-data header.
   */
  int free;
  size_t size;
  Block* next;

  /**
   * Payload pointer.
   */
  char data[1];
};

#define BLOCK_SIZE sizeof(struct Block)

/**
 * Initial base block.
 */
Block* base = NULL;

/**
 * Finds a block of a requested size.
 */
Block* find_block(Block** last, size_t size) {
  Block* block = base;

  while (block && !(block->free && block->size >= size)) {
    *last = block;
    block = block->next;
  }

  return block;
}

/**
 * Returns a pointer to an object header.
 */
Block* get_block(char* p) {
  return (Block*)(p - BLOCK_SIZE + 8);
}

/**
 * Extends the heap, by moving the heap-break pointer.
 */
Block* extend_heap(Block* last, size_t size) {

  // Current heap break.
  Block* block = (Block*)sbrk(0);

  // See if we can map more memory.
  if (sbrk(BLOCK_SIZE + size) == (void*) - 1) {
    return NULL;
  }

  block->size = size;
  block->next = NULL;

  if (last) {
    last->next = block;
  }

  block->free = 0;
  return block;
}

/**
 * Allocates the memory from heap of a needed size.
 *
 * Returns a void-pointer to the payload (the pointer should be cast).
 */
void* malloc(size_t size) {
  Block* block;
  Block* last;

  // Align the size.
  size = ALLIGN_4(size);

  if (base) {
    last = base;
    block = find_block(&last, size);

    // If we found a block of needed size.
    if (block) {
      block->free = 0;
    } else {
      // Otherwise, map more memory.
      block = extend_heap(last, size);

      // OOM.
      if (!block) {
        return NULL;
      }
    }
  } else {
    // First time allocation, move the heap-break.
    block = extend_heap(NULL, size);

    // OOM.
    if (!block) {
      return NULL;
    }

    base = block;
  }

  // Payload.
  return block->data;
}

void print_block_info(char* p) {
  Block* block = get_block(p);

  cout << endl << "Block info for \"" << p << "\":" << endl;
  cout << "  addr: " << (void*)block << endl;
  cout << "  free: " << boolalpha << (block->free ? true : false) << endl;
  cout << "  size: " << block->size << endl;
  cout << "  next: " << block->next << endl;
  cout << "  data: " << block->data << endl << endl;
}

/**
 * Simple and naive implementation of `free`. See homework assignments
 * to do more bookkeeping on free (coalesce the free blocks, etc).
 */
void free(char* p) {
  Block* block = get_block(p);
  cout << endl << "-- Freeing: " << (void*)block << endl << endl;
  block->free = 1;
}

int main(int argc, char const *argv[]) {
  char* c1 = (char*)malloc(4);
  char* c2 = (char*)malloc(8);

  strcpy(c2, "data");
  cout << "Data c2: " << c2 << endl;

  strcpy(c1, "1234");
  cout << "Data c1: " << c1 << endl;

  print_block_info(c1);
  print_block_info(c2);

  // Free c2, c3 will be able to reuse.
  free(c2);

  char* c3 = (char*)malloc(8);

  strcpy(c3, "abcd");
  cout << "Data c3: " << c3 << endl;

  print_block_info(c2); // same as 3, became "abcd"
  print_block_info(c3);

  return 0;
}

// Results:

/*

Data c2: data
Data c1: 1234

Block info for "1234":
  addr: 0x10e571000
  free: false
  size: 4
  next: 0x10e571024
  data: 1234


Block info for "data":
  addr: 0x10e571024
  free: false
  size: 8
  next: 0x0
  data: data


-- Freeing: 0x10e571024

Data c3: abcd

Block info for "abcd":
  addr: 0x10e571024
  free: false
  size: 8
  next: 0x0
  data: abcd


Block info for "abcd":
  addr: 0x10e571024
  free: false
  size: 8
  next: 0x0
  data: abcd

*/