/*
What's new:
C44 - [Martin Zoubek] first public release
*/

#ifdef MALLOC
  #include <stdlib.h>
#else
  #ifdef WIN32
    #include <windows.h>
  #else
    #include <stdlib.h>
  #endif
#endif
#include "Error.h"
#include "Types.h"

  uint vMemory_CurAlloc=0;
  uint vMemory_MaxAlloc=0;

#ifndef MALLOC
  #define PS sizeof(pointer)

  pointer vMemory_FreeList[29]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0};
  pointer vMemory_GlobalList=0;

  #define Memory_Block_Prev(b) (*(pointer *)(b))
  #define Memory_Block_Next(b) (*((pointer *)(b)+1))
  #define Memory_Block_PrevFree(b) (*((pointer *)(b)+2))  //-1=used
  #define Memory_Block_GlobalLast(b) Memory_Block_PrevFree(b)
  #define Memory_Block_NextFree(b) (*((pointer *)(b)+3))
  #define Memory_Block_Size(b) (Memory_Block_Next(b)-(pointer)(b)-4*PS)

  #define cMemory_AllocMinimumSize 65536

static void Memory_Free2(pointer p,BOOL canfree){
  pointer cur;
  pointer index;
  cur=Memory_Block_Next(p);
  if(cur&&Memory_Block_PrevFree(cur)!=(pointer)(-1)){
    if(Memory_Block_Size(cur)){
      if(Memory_Block_PrevFree(cur))  //remove from free list
        Memory_Block_NextFree(Memory_Block_PrevFree(cur))=
          Memory_Block_NextFree(cur);
      else{
        for(index=0;(16<<index)<Memory_Block_Size(cur);index++);  //count index
        vMemory_FreeList[index]=Memory_Block_NextFree(cur);
        }
      if(Memory_Block_NextFree(cur))
        Memory_Block_PrevFree(Memory_Block_NextFree(cur))=
          Memory_Block_PrevFree(cur);
      }
    Memory_Block_Next(p)=Memory_Block_Next(cur);
    if(Memory_Block_Next(p))
      Memory_Block_Prev(Memory_Block_Next(p))=p;
    }
  cur=Memory_Block_Prev(p);
  if(cur&&Memory_Block_PrevFree(cur)!=(pointer)(-1)){
    if(Memory_Block_Size(cur)){
      if(Memory_Block_PrevFree(cur))  //remove from free list
        Memory_Block_NextFree(Memory_Block_PrevFree(cur))=
          Memory_Block_NextFree(cur);
      else{
        for(index=0;(16<<index)<Memory_Block_Size(cur);index++);  //count index
        vMemory_FreeList[index]=Memory_Block_NextFree(cur);
        }
      if(Memory_Block_NextFree(cur))
        Memory_Block_PrevFree(Memory_Block_NextFree(cur))=
          Memory_Block_PrevFree(cur);
      }
    Memory_Block_Next(cur)=Memory_Block_Next(p);
    if(Memory_Block_Next(cur))
      Memory_Block_Prev(Memory_Block_Next(cur))=cur;
    p=cur;
    }
  if(!Memory_Block_Size(p))
    return;
  if(canfree&&Memory_Block_Size(p)>=cMemory_AllocMinimumSize){
    cur=vMemory_GlobalList;
    while(cur&&cur<p-4*PS)
      cur=Memory_Block_Next(cur);
    if(cur==p-4*PS&&Memory_Block_Next(p)==Memory_Block_GlobalLast(cur)){
      if(Memory_Block_Prev(p))  //unchain from main list
        Memory_Block_Next(Memory_Block_Prev(p))=
          Memory_Block_Next(Memory_Block_GlobalLast(cur));
      if(Memory_Block_Next(Memory_Block_GlobalLast(cur)))
        Memory_Block_Prev(Memory_Block_Next(Memory_Block_GlobalLast(cur)))=
          Memory_Block_Prev(p);
      if(Memory_Block_Prev(cur))  //unchain from global list
        Memory_Block_Next(Memory_Block_Prev(cur))=Memory_Block_Next(cur);
      else
        vMemory_GlobalList=Memory_Block_Next(cur);
      if(Memory_Block_Next(cur))
        Memory_Block_Prev(Memory_Block_Next(cur))=Memory_Block_Prev(cur);
      vMemory_CurAlloc-=Memory_Block_GlobalLast(cur)-cur+4*PS;
    #ifdef WIN32
      LocalFree((void *)cur);
    #else
      free((void *)cur);
    #endif
      return;
      }
    }
  for(index=0;(16<<index)<Memory_Block_Size(p);index++);  //count index
  Memory_Block_PrevFree(p)=0;
  Memory_Block_NextFree(p)=vMemory_FreeList[index];
  if(Memory_Block_NextFree(p))
    Memory_Block_PrevFree(Memory_Block_NextFree(p))=p;
  vMemory_FreeList[index]=p;
  }

void *Memory_Get(uint size){
  pointer index;
  pointer cur,p,s2,newblock,newsize;
  if(!size)
    return 0;
  size+=15;  //align on 16-byte boundary
  size&=~15;
  for(index=0;(16<<index)<size;index++);  //count index
  for(cur=0;!cur&&index<29;){  //search in lists
    p=vMemory_FreeList[index];
    while(p&&(!cur||Memory_Block_Size(cur)>size)){
      s2=Memory_Block_Size(p);
      if(s2>=size&&(!cur||Memory_Block_Size(cur)>s2))
        cur=p;
      p=Memory_Block_NextFree(p);
      }
    if(!cur)
      index++;
    }
  if(cur){  //free block found
    if(Memory_Block_PrevFree(cur))  //remove from free list
      Memory_Block_NextFree(Memory_Block_PrevFree(cur))=
        Memory_Block_NextFree(cur);
    else
      vMemory_FreeList[index]=Memory_Block_NextFree(cur);
    if(Memory_Block_NextFree(cur))
      Memory_Block_PrevFree(Memory_Block_NextFree(cur))=
        Memory_Block_PrevFree(cur);
    Memory_Block_PrevFree(cur)=-1;  //mark as used
    if(Memory_Block_Size(cur)>size){  //part of block left free
      p=cur+size+4*PS;
      Memory_Block_Prev(p)=cur;
      Memory_Block_Next(p)=Memory_Block_Next(cur);
      if(Memory_Block_Next(p))
        Memory_Block_Prev(Memory_Block_Next(p))=p;
      Memory_Block_Next(cur)=p;
      Memory_Free2(p,FALSE);
      }
    return (void *)(cur+4*PS);
    }
  newsize=max(cMemory_AllocMinimumSize,size)+12*PS;  //allocate new memory
#ifdef WIN32
  if((newblock=(pointer)LocalAlloc(LMEM_FIXED,newsize))==0){
#else
  if((newblock=(pointer)malloc(newsize))==0){
#endif
    Error("Memory_Get","Not enough memory");
    return 0;  //error
    }
#ifdef WIN32
  s2=LocalSize((void *)newblock);  //did it allocated more memory?
  newsize=max(newsize,s2);
#endif
  newsize&=~15;  //align on 16-byte boundary
  vMemory_CurAlloc+=newsize;
  if(vMemory_CurAlloc>vMemory_MaxAlloc)
    vMemory_MaxAlloc=vMemory_CurAlloc;
  p=vMemory_GlobalList;  //add to global list
  while(p&&p<newblock&&Memory_Block_Next(p)&&Memory_Block_Next(p)<newblock)
    p=Memory_Block_Next(p);
  if(p>newblock)  //first has greater addr
    p=0;
  if(p)
    Memory_Block_Prev(newblock)=p;
  else
    Memory_Block_Prev(newblock)=0;
  if(p)
    Memory_Block_Next(newblock)=Memory_Block_Next(p);
  else{
    Memory_Block_Next(newblock)=vMemory_GlobalList;
    vMemory_GlobalList=newblock;
    }
  if(Memory_Block_Prev(newblock))
    Memory_Block_Next(Memory_Block_Prev(newblock))=newblock;
  if(Memory_Block_Next(newblock))
    Memory_Block_Prev(Memory_Block_Next(newblock))=newblock;
  Memory_Block_GlobalLast(newblock)=newblock+newsize-4*PS;
  if(Memory_Block_Prev(newblock)){
    Memory_Block_Prev(newblock+4*PS)=
      Memory_Block_GlobalLast(Memory_Block_Prev(newblock));
    Memory_Block_Next(Memory_Block_GlobalLast(Memory_Block_Prev(newblock)))=
      newblock+4*PS;
    }
  else
    Memory_Block_Prev(newblock+4*PS)=0;
  Memory_Block_Next(newblock+4*PS)=Memory_Block_GlobalLast(newblock);
  Memory_Block_Prev(Memory_Block_GlobalLast(newblock))=newblock+4*PS;
  if(Memory_Block_Next(newblock)){
    Memory_Block_Next(Memory_Block_GlobalLast(newblock))=
      Memory_Block_Next(newblock)+4*PS;
    Memory_Block_Prev(Memory_Block_Next(newblock)+4*PS)=
      Memory_Block_GlobalLast(newblock);
    }
  else
    Memory_Block_Next(Memory_Block_GlobalLast(newblock))=0;
  Memory_Block_PrevFree(Memory_Block_GlobalLast(newblock))=-1;  //mark as used
  Memory_Free2(newblock+4*PS,FALSE);
  for(index=0;(16<<index)<size;index++);  //count index
  for(cur=0;!cur;){  //search in lists
    p=vMemory_FreeList[index];
    while(p&&(!cur||Memory_Block_Size(cur)>size)){
      s2=Memory_Block_Size(p);
      if(s2>=size&&(!cur||Memory_Block_Size(cur)>s2))
        cur=p;
      p=Memory_Block_NextFree(p);
      }
    if(!cur)
      index++;
    }
  if(Memory_Block_PrevFree(cur))  //remove from free list
    Memory_Block_NextFree(Memory_Block_PrevFree(cur))=
      Memory_Block_NextFree(cur);
  else
    vMemory_FreeList[index]=Memory_Block_NextFree(cur);
  if(Memory_Block_NextFree(cur))
    Memory_Block_PrevFree(Memory_Block_NextFree(cur))=
      Memory_Block_PrevFree(cur);
  Memory_Block_PrevFree(cur)=-1;  //mark as used
  if(Memory_Block_Size(cur)>size){  //part of block left free
    p=cur+size+4*PS;
    Memory_Block_Prev(p)=cur;
    Memory_Block_Next(p)=Memory_Block_Next(cur);
    if(Memory_Block_Next(p))
      Memory_Block_Prev(Memory_Block_Next(p))=p;
    Memory_Block_Next(cur)=p;
    Memory_Free2(p,FALSE);
    }
  return (void *)(cur+4*PS);
  }

void Memory_Free(void *b){
  if(!b)
    return;
  Memory_Free2((pointer)b-4*PS,TRUE);
  }
#else
void *Memory_Get(uint size){
  void *m;
  m=malloc(size);
  if(!m){
    Error("Memory_Get","Not enough memory");
    return 0;  //error
    }
  vMemory_CurAlloc+=size;
  vMemory_MaxAlloc=vMemory_CurAlloc;
  return m;
  }

void Memory_Free(void *b){
  if(!b)
    return;
  free(b);
  }
#endif

