#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "allocator.h"

#define MAGICNUMBER (0x84D80111)

#define HEADERSIZE sizeof(freeHeader)

#define DEAFBEED(0xDEAFBEED)

#define HEADER_SIZE sizeof(link);

typedef struct _node *link;

typedef struct _node {
  int size;
  int magicnumber;
  link next;
  link previous;
} node;

typedef unsigned char byte;

static byte *free_list_ptr;
static byte *memory = NULL;

void allocator_init(u_int32_t size){
  if(memory == NULL){
    memory = malloc(sizeof(byte)*size);
    node freeHeader = {size, MAGICNUMBER, (link) memory, (link) memory};
    *((node*) memory) = freeHeader;
    free_list_ptr = memory;
  }
}

void *allocator_malloc(u_int32_t n){
  link tempPointer, returnPointer;
  uint32_t s;
  int found = 0;
  int runOnce = 0;

  if (free_list_pointer->magicnumber != NULL){
	fprintf(stderr, "Error with memory.\n");
	abort();
  }

  tempPointer = free_list_pointer;

  while((tempPointer != free_list_pointer && found == 0) || (runOnce == 0)){
    if(tempPointer->size >= (HEADER_SIZE +n)){
	  found = 1;
	}else{
	  tempPointer = tempPointer->next;
	}
	runOnce = 1;
  }

  if(found == 0){
    tempPointer = NULL;
  }

  if(tempPointer == NULL){
    return NULL;
  }

  s = returnPointer->size;

  if(s/2 >= (HEADER_SIZE + n)){
    while(s/2 >= (HEADER_SIZE + n)){
      s /= 2;
      tempPointer = link ((char *) returnPointer + s);
	  tempPointer->next = returnPointer->next;
	  tempPointer->prev = (byte *) returnPointer;
	  tempPointer->size = s;
	  tempPointer->magicnumber = MAGICNUMBER;
	  returnPointer->size = s;
	  returnPointer->next->prev = (byte *) tempPointer;
	  returnPointer->next = (byte *) tempPointer;
      }
	}else{
	  tempPointer = link ((char*) returnPointer + s);
	}

	if((returnPointer == link returnPointer->next) && (returnPointer->next == returnPointer->prev)){
	  return NULL;
	}

	tempPointer->prev = returnPointer->prev;
	returnPointer->prev->next = (byte *) tempPointer;
	returnPointer->magicnumber = DEAFBEED;
	free_list_ptr = (byte *) tempPointer;
	return ((void *) ((char *) returnPointer + HEADER_SIZE));

}

void allocator_free(void *object){
}

void allocator_end(void){
free(memory);
}