/***********************************************************************
 *  Memory.c:
 *  Copyright (c) 2001, Eidatsu Interactive, Inc.
 *                      All Rights Reserved
 *  Version: 0.0.0-1
 *
 *  Revision History:
 *   *
 *
 *  Notes:
 *   * This is a total rewrite of the previous memory manager featured
 *     on flipcode's COTD.  The previous memory manager had a few
 *     dormant bugs that would cause corruption of the memory heap,
 *     and, only in some *rare* cases, a crash.  Obviously, these bugs
 *     were hard to track down.  Other than bug fixes, this total
 *     rewrite features MUCH MUCH MUCH cleaner and more easy-to-read
 *     code.  Yay!
 *
 *   * This code contains calls to functions and macros in our run-time
 *     library.  These functions are not included, but their purpose
 *     should be pretty clear, and not need any further documentation.
 *
 *   * Oh, and unlike the previous version, this version of the dyn
 *     memory allocator is now thread-safe.
 *
 *   * ALL of the following functions are heavily dependant on machine
 *     size and architecture.  Word-size is expected to be 32 bits.
 **********************************************************************/

/***********************************************************************
 *  Function Declarations
 **********************************************************************/

private void* _Alloc         ( uword );
private void  _Free          ( void* );

export  void* MemAlloc       ( uword );
export  void* MemReAlloc     ( void*, uword );
export  void  MemFree        ( void* );

public  word  _MemInitialize ( void );
public  void  _MemShutdown   ( void );

/* Not included. */
export  void  MemCopy        ( void*, const void*, uword );
export  void  MemMove        ( void*, const void*, uword );
export  void  MemFill        ( void*, uword, uint8 );

/***********************************************************************
 *  Global Variables
 **********************************************************************/

private Mutex_t  gMemMutex;

private DWORD    gPageSize;

private uword   *gFirstSuperBlock;
private uword   *gEndOfLastSuperBlock;
private uword   *gLastUsedBlock;

/***********************************************************************
 *  Function Macros
 **********************************************************************/

#define MemArrayAlloc( size, count ) \
          MemAlloc( (size) * (count) )

#define MemArrayReAlloc( ptr, size, count ) \
          MemReAlloc( ptr, (size) * (count) )

#define MemZero( ptr, count ) \
          MemFill( ptr, count, 0x00 )

/***********************************************************************
 *  Functions
 **********************************************************************/

/*  Block Header:
 *    ----------------
 *   | Block Size |E|F|
 *    ----------------
 *
 *    Block Size:  The offset to the next block header.
 *    E:           Flag is set if this is the last block.
 *    F:           Flag is set if this block is full (allocated).
 *
 *  Superblock:
 *    --------------
 *   | Prev Pointer |
 *    --------------
 *   | Block Header | ---> E=0     F=1
 *    --------------
 *   |     DATA     |
 *    --------------
 *   |     ....     |
 *    --------------
 *   |     DATA     |
 *    --------------
 *   | Block Header | ---> E=1     F=0
 *    --------------
 *   |    EMPTY     |
 *    --------------
 *   |     ....     |
 *    --------------
 *   |    EMPTY     |
 *    --------------
 *   | Next Pointer |
 *    --------------
 *
 *    Prev Pointer:  Pointer to the previous superblock.
 *    Next Pointer:  Pointer to the next superblock.
 *
 *       The superblocks are kept in a circular linked list.  If
 *    there is only one superblock, then both it's "next" and "prev"
 *    pointers point to the first byte in the superblock (which,
 *    coincidentally, is the "prev" pointer).
 */
private
void*
_Alloc
  ( uword Size )
{
  uword *tmpblk;
  uword  NewSupBlockSize, tmpi;
  
  /* We round the requested size up to the nearest multiple of eight
   * bytes, and then add a four byte buffer.  We also set tmpblk to
   * gLastUsedBlock, as is required for the next block of code. */
  Size   = ((Size + 7) & 0xFFFFFFF8) + 4;
  tmpblk = gLastUsedBlock;
  
  /* We now do a search through the entire heap to see if there is
   * a block of the right size available. */
    do
  {
    /* If we find an unused block of the appropriate size, then
     * we break out of this loop to the BlockFound label below. */
    if ( (*tmpblk & 0x1) == 0 )
      if ( (((*tmpblk >> 2) - 1) << 2) > Size )
        goto BlockFound;
    
    /* Otherwise we advance to the next block header.  If the
     * block we are currently looking at is the last in the
     * superblock (the end bit is set), then we must advance
     * one more time to the first block in the next
     * superblock. */
    tmpi   = *tmpblk;
    tmpblk =  tmpblk + (tmpi >> 2);
    if ( (tmpi & 0x2) != 0 )
      tmpblk = (uword*)( *tmpblk + sizeof(uword) );
  }
    while ( tmpblk != gLastUsedBlock );
  
  /* A block of the appropriate size was not found.  We must
   * therefore request another chunk of memory from the
   * operating system.  The new chunk of memory must be large
   * enough to hold the requested memory, two pointers, and
   * a block header, and must be a multiple of gPageSize.
   *
   * In the following calculation we assume that gPageSize is
   * a power of 2. */
  NewSupBlockSize = (Size + 3 * sizeof(uword) + gPageSize - 1) &
                     ~(gPageSize - 1);
  
  tmpblk = VirtualAlloc( NULL, NewSupBlockSize,
                         MEM_RESERVE | MEM_COMMIT,
                         PAGE_READWRITE );
  
  if ( tmpblk == NULL )
    return NULL;
  
  /* Set the Prev pointer. */
  *tmpblk = *gFirstSuperBlock;
  
  /* Insert this new superblock into the heap as the last
   * superblock. */
  *gFirstSuperBlock     = (uword)  tmpblk;
  *gEndOfLastSuperBlock = (uword)  tmpblk;
   gEndOfLastSuperBlock = tmpblk + (NewSupBlockSize >> 2) - 1;
  
  /* Now set the Next pointer, which gEndOfLastSuperBlock
   * now points to. */
  *gEndOfLastSuperBlock = (uword) gFirstSuperBlock;
  
  /* Before we move on to allocate the new block, we set up
   * a default block the size of the newly allocated space,
   * and set tmpblk equal to it's header. */
  ++tmpblk;
   *tmpblk = (NewSupBlockSize - 2 * sizeof(uword)) | 0x2;
  
BlockFound:
  
  /* If the block we found is too big, we split it.  The cut-off
   * limit of 24 is arbitrary.  I have absolutly no idea what an
   * optimal cut-off limit in real life situations would be.  24
   * just sounded good.
   * 
   * If we split, then we set gLastUsedBlock to the value of the
   * second (free) block, otherwise we set it to the value of the
   * block being used. */
  if
    ( ((*tmpblk & 0xFFFFFFFC) - sizeof(uword) - Size) > 24 )
  {
     gLastUsedBlock = tmpblk + 1 + (Size >> 2);
    *gLastUsedBlock = *tmpblk - Size - sizeof(uword);
    *tmpblk         = (Size + sizeof(uword)) | 0x1;
  }
    else
  {
    *tmpblk         = *tmpblk | 0x1;
     gLastUsedBlock = tmpblk;
  }
  
  return tmpblk + 1;
}

private
void
_Free
  ( void *Ptr )
{
  uword *BlockToBeFreed, *BlockItr, *SupBlockFreedFrom;
  uword  tmpi;
  
  /* The value passed to this function should be a pointer
   * to the first byte of memory that was allocated - the
   * same value that was returned from _Alloc().  To get
   * the header of the block we're freeing, we simply move
   * back one uword. */
  BlockToBeFreed = ((uword*) Ptr) - 1;
  
  /* We clear the "full" bit in the block header. */
  *BlockToBeFreed = *BlockToBeFreed ^ 0x1;
  
  /* Finding the next block after the one being freed is
   * easy. */
  if
    ( (*BlockToBeFreed & 0x2) != 0 )
  {
    /* We use BlockItr as a temporary. */
    BlockItr = BlockToBeFreed + (*BlockToBeFreed >> 2);
    
    /* If the next block is empty, we merge it and the
     * block now being freed. */
    if ( (*BlockItr & 0x1) == 0 )
      *BlockToBeFreed += *BlockItr;
  }
  
  /* Now we find the previous block to the one being freed.
   * This is a little more time consuming, as we need to
   * advance all the way to the next superblock, use the
   * Prev pointer to get back to the beginning of the
   * superblock we're in, and then advance to the block
   * right before the block we're freeing. */
  BlockItr = BlockToBeFreed;
  
    do
  {
    tmpi      = *BlockItr;
    BlockItr += tmpi >> 2;
  }
    while ( (tmpi & 0x2) != 0 );
  
  SupBlockFreedFrom = **((uword***) BlockItr);
  BlockItr          = SupBlockFreedFrom + 1;
  
  if
    ( BlockItr != BlockToBeFreed )
  {
    while ( BlockItr + (*BlockItr >> 2) != BlockToBeFreed )
      BlockItr += (*BlockItr >> 2);
    
    /* If the previous block is empty, we merge it and the
     * block being freed. */
    if
      ( (*BlockItr & 0x1) == 0 )
    {
      *BlockItr       += *BlockToBeFreed;
       BlockToBeFreed  =  BlockItr;
    }
  }
  
  /* We set gLastBlockUsed to the value of BlockToBeFreed.
   * That way the next call to _Alloc() will begin its search
   * for free memory with an empty block, hopefully saving
   * time in the long run. */
  gLastUsedBlock = BlockToBeFreed;
  
  /* Now we test to see if the superblock is empty, and if
   * it is, then we request the operating system to free
   * it. */
  if
    ( (*(SupBlockFreedFrom + 1) & 0x2) != 0 )
  {
    /* We do not deallocate the superblock if it is the
     * superblock pointed to by gFirstSuperBlock - that way
     * we can be assured that there will always be at least
     * one superblock in memory. */
    if
      ( SupBlockFreedFrom != gFirstSuperBlock )
    {
      /* Before we free the superblock we must first remove it
       * from the global list of superblocks. */
      
      /* First we advance BlockItr to the Prev pointer in the
       * next superblock, taking advantage of the fact that we
       * know this superblock to contain only one unused block. */
      BlockItr  = SupBlockFreedFrom + 1;
      BlockItr += *BlockItr >> 2;
      BlockItr  = *((uword**) BlockItr);
      
      /* And then set this Prev pointer to the value of the Prev
       * pointer in the superblock being freed. */
      *BlockItr = *SupBlockFreedFrom;
      
      /* In order to save on the number of variables we have,
       * we use BlockToBeFreed as a temporary. */
      BlockToBeFreed = BlockItr;
      
      /* Now we set BlockItr to the beginning of the previous
       * superblock, and advance until we reach the Next pointer
       * at the end of the superblock. */
      BlockItr = *((uword**) SupBlockFreedFrom) + 1;
      
        do
      {
        tmpi      = *BlockItr;
        BlockItr += tmpi >> 2;
      }
        while ( (tmpi & 0x2) == 0 );
      
      /* Now we set the Next pointer in the previous superblock to
       * the address of the superblock after the one being freed.
       * BlockToBeFreed, in this case, is just a temporary
       * containing a pointer to the next superblock. */
      *BlockItr = (uword) BlockToBeFreed;
      
      VirtualFree( SupBlockFreedFrom, 0, MEM_DECOMMIT | MEM_RELEASE );
      
      /* Finally, we must choose another value for gLastBlockUsed,
       * since we just deallocated the memory it pointed to.  We
       * simply play it safe and point it at the only block we
       * know to be in existance - the first one. */
      gLastUsedBlock = gFirstSuperBlock + 1;
    }
  }
  
  return;
}

export
void*
MemAlloc
  ( uword Size )
{
  void *Mem;
  
  MutexLock( &gMemMutex );
  
  Mem = _Alloc( Size );
  
  MutexUnLock( &gMemMutex );
  
  return Mem;
}

export
void*
MemReAlloc
  ( void *OldMemory, uword NewSize )
{
  void  *NewMemory;
  uword  OldSize;
  
  MutexLock( &gMemMutex );
  
    do
  {
    if
      ( NULL == OldMemory )
    {
      /* If OldMemory is NULL, then the user is simply requesting
       * that NewSize bytes be allocated. */
      NewMemory = _Alloc( NewSize );
      break;
    }
      else if ( NewSize == 0 )
    {
      /* If NewSize is zero, then the user is requesting that
       * OldMemory be freed. */
      _Free( OldMemory );
      break;
    }
      else
    {
      /* Otherwise the user is requesting that the memory block
       * pointed to by OldMemory be either increased or decreased
       * to NewSize bytes. */
      OldSize = ((*(((uword*) OldMemory) - 1) >> 2) + 1) << 2;
      
      if
        ( NewSize > OldSize )
      {
        NewMemory = _Alloc( NewSize );
        
        if ( NewMemory == NULL )
          break;
        
        MemCopy( NewMemory, OldMemory, OldSize );
        MemFree( OldMemory );
        
        break;
      }
    }
  }
    while ( 0 );

  MutexUnLock( &gMemMutex );
  
  return NewMemory;
}

export
void
MemFree
  ( void *Ptr )
{
  MutexLock( &gMemMutex );
  
  _Free( Ptr );
  
  MutexUnLock( &gMemMutex );
  
  return;
}

public
word
_MemInitialize
  ( void )
{
  SYSTEM_INFO SystInfo;
  
  MutexCreate( &gMemMutex );
  
  GetSystemInfo( &SystInfo );
  
  gPageSize = SystInfo.dwPageSize;
  
  if ( gPageSize <= 0 )
    return -1; /* FIXME: need error code */
  
  gFirstSuperBlock = VirtualAlloc( NULL, gPageSize,
                                   MEM_COMMIT | MEM_RESERVE,
                                   PAGE_READWRITE );
  
  if ( gFirstSuperBlock == NULL )
    return -1; /* FIXME: need error code */
  
  gLastUsedBlock        = gFirstSuperBlock + 1;
  gEndOfLastSuperBlock  = (uword*)(((byte*) gFirstSuperBlock) +
                           gPageSize - sizeof(uword));
  *gFirstSuperBlock     = (uword) gFirstSuperBlock;
  *gEndOfLastSuperBlock = (uword) gFirstSuperBlock;
  *gLastUsedBlock       = (gPageSize - sizeof(uword) * 2) | 0x2;
  
  return 0;
}

public
void
_MemShutdown
  ( void )
{
  /* No heap cleanup routines provided, as they are usually not
   * needed (the operating system deallocates all memory when
   * the application exits).  This would, however, be a good
   * place to call routines that browse the heap and print
   * memory information to a log file, as any allocated
   * memory present when this function is called may safely
   * be considered a memory leak. */
  
  MutexDestroy( &gMemMutex );
  
  return;
}

/***********************************************************************
 *  The End
 **********************************************************************/
