/*
  Quick and Braindamaged Malloc Implementation for Quake III: Arena
  Copyright 2001  PhaethonH <phaethon@linux.ucla.edu>

  Permission to copy, redistribute, modify, use, and produce derivative
  works is granted provided this copyright notice remains intact.
  Code is provided "as-is" without any express or implied warranty, no claims
  are made for fitness of merchantability or fitness for a particular use.
  Use at your own risk.

*/

/* "Quick" refers to the time I spent on this code. */

/* A page size is determined by the size of a mheader. */


enum {
  MAGIC_MALLOC = 0x4F5D50D2,
  MAGIC_FREE   = 0xDEADBEEF,
};


#define printf CG_Printf


typedef int size_t;  /* Apparently already declared in bg_lib.h */

#include "qmalloc.h"



typedef struct mheader_s {
  unsigned int magic;
  int length; /* in pages. */
  struct mheader_s *prev, *next;
} mheader_t;

unsigned char arena[MALLOC_ARENA];

#define MAX_PAGES (sizeof(arena) / sizeof(mheader_t))
#define arenaend ((mheader_t*)(arena) + MAX_PAGES)







/*
  Returns a pointer to a malloc header that can hold sufficient number of `size' bytes.
  Malloc header is automagically filled.
  Considers mheader at `reconsider' to be "empty" for search purposes.
  Set to NULL to not reconsider any.
*/
static
mheader_t *
find_spot (size_t size, void *reconsider)
{
  mheader_t *retval;
  mheader_t *m, *next, *temp;
  int pages;
  int i;

  retval = NULL;
  temp = NULL;
  m = (mheader_t *)arena;

  pages = ((size - 1) / sizeof(mheader_t)) + 1;
  if (m->magic != MAGIC_MALLOC)
    {
      /* Establish root. */
      m->magic = MAGIC_MALLOC;
      m->length = 0;
      m->prev = NULL;
      m->next = NULL;
    }
  while (m->next)
    {
      next = m->next;
      if (next == (mheader_t*)reconsider)
        {
          if (next->next)
              next = m->next->next;
          else
              next = arenaend;
        }
      else
        {
          next = m->next;
        }
      i = next - (m + 1) - m->length;
      /* Amount of free pages between this chunk and next chunk. */
      if (i >= pages)
        {
          /* We can slip in between. */
          temp = m + m->length + 1;
          temp->magic = MAGIC_MALLOC;
          temp->length = pages;
          temp->next = next;
          temp->prev = m;
          if (temp->next)
              temp->next->prev = temp;
          m->next = temp;
          break;
        }
      m = next;
    }
  if (!m->next)
    {
      /* Reached end of used blocks. */
      temp = m + m->length + 1;
      if ((arenaend - temp) > pages)
        {
          temp->magic = MAGIC_MALLOC;
          temp->length = pages;
          temp->next = NULL;
          temp->prev = m;
          m->next = temp;
        }
      else
          temp = NULL;
    }

  retval = temp;
  return retval;
}


void*
malloc(size_t size)
{
  char *retval;
  mheader_t *m;

  m = find_spot(size, NULL);
  retval = (char *)m + sizeof(mheader_t);
  return (void*)retval;
}



void *
calloc(size_t nmemb, size_t size)
{
  void *x;
  x = malloc(nmemb * size);
  memset(x, 0, nmemb * size);
  return x;
}




void
free(void *ptr)
{
  mheader_t *m, *t;

  t = (mheader_t *)((char*)ptr - sizeof(mheader_t));

  if (t->magic != MAGIC_MALLOC)
      return;  /* Silently fail? */

  m = (mheader_t *)arena;
  if (t == m)
      return;  /* Not clearing root. */
  if (t->prev)
      t->prev->next = t->next;
  if (t->next)
      t->next->prev = t->prev;
  t->magic = MAGIC_FREE;
  t->length = 0;
}



void *
realloc(void *ptr, size_t size)
{
  char *a, *b;
  mheader_t *m, *orig;
  int movesize;

  orig = (mheader_t *)((char*)ptr - sizeof(mheader_t));
  if (orig->magic != MAGIC_MALLOC)
    {
      return ptr;
    }
  m = find_spot(size, orig);
  a = (char*)orig + sizeof(mheader_t);
  b = (char*)m + sizeof(mheader_t);
  movesize = orig->length * sizeof(mheader_t);
  if (size < movesize)
      movesize = size;
  memmove((void*)b, (void*)a, movesize);
  return (void*)b;
}





















#if 0


/* Debugging routines. */

void
dump_mheader (void *x)
{
  mheader_t *m;
  m = (mheader_t*)x;
  printf("dumping mheader %d\n", m);
  printf(" magic = %d\n", m->magic);
  printf(" length = %d\n", m->length);
  printf(" prev = %d\n", m->prev);
  printf(" next = %d\n", m->next);
}

void
dump_block (void *x)
{
  dump_mheader((void*)((char*)x - sizeof(mheader_t)));
}


int
test_malloc ()
{
  char *a, *b, *c, *d, *e, *f;

  printf("arena @ %d\n", arena);
  printf("arenaned @ %d\n", arenaend);
  printf("pages = %d\n", MAX_PAGES);

  a = (char*)malloc(700);
  dump_mheader(arena);
  printf("a @ %d\n", a);
  dump_block(a);

  b = (char*)malloc(7);
  printf("b @ %d\n", b);
  dump_block(b);

printf("\n");

  free(a);
  dump_mheader(arena);
  dump_block(b);

  c = (char*)malloc(100);
  printf("c @ %d\n", c);
  dump_block(c);

printf("\n");

  dump_mheader(arena);
  c = (char*)realloc(c, 3);
  printf("c @ %d\n", c);
  dump_block(c);

  c = (char*)realloc(c, 3000);
  printf("c @ %d\n", c);
  dump_block(c);


  return 1;
}


/* testing with GCC */
//int
//main()
//{
//  test_malloc();
//  return 0;
//}

#endif