lists.c

空战游戏flacon源码

/* ----------------------------------------------------------

   LISTS.CPP

   List functions.

   AUTHORS:
     KBR   08/18/94   implemented at spectrum holobyte
     KBR   10/30/94   list allocation blocks
     KBR   05/01/96   ported to win95 (non-specific port) 
     KBR   12/03/96   added thread-safe code
   ---------------------------------------------------------- */
  
#include <stdio.h>
#include <stdlib.h>

#include "lists.h"
#if MEM_ENABLED
#    include "memmgr.h"
#endif

#define ALLOC_UNITS           512
#define ALLOC_SAFETY          20
#define ALLOC_USED_FLAG       0x53554445  /* 'U'S'E'D' */
#define ALLOC_FREE_FLAG       0x52464545  /* 'F'R'E'E' */
#define ALLOC_SWAP_SIZE       64


#ifdef USE_SH_POOLS
	#undef MemFree
	#undef MemFreePtr
	#undef MemMalloc
	#include "Smartheap\Include\smrtheap.h"
	extern MEM_POOL gResmgrMemPool;
	#  define LIST_ALLOC()  MemAllocPtr( gResmgrMemPool, sizeof(LIST), 0 )
	#  define LIST_FREE(a)  MemFreePtr(a)
#else
	#if( USE_LIST_ALLOCATION )
	#  define LIST_ALLOC()  ListAlloc()
	#  define LIST_FREE(a)  ListFree(a)
	#else
	#  define LIST_ALLOC()  MemMalloc( sizeof(LIST), "LIST" )
	#  define LIST_FREE(a)  MemFree(a)
	#endif
#endif


#if( USE_THREAD_SAFE )

   int LIST_MUTEX = 0;         /* If you want to bypass microsoft's very heavy
                                  mutex implementation, do so here. */

#  define WAIT_FOR_LOCK(a)     WaitForSingleObject( a, INFINITE );
#  define RELEASE_LOCK(a)      ReleaseMutex( a );
#  define CREATE_LOCK(a)       { if( !a ) a = CreateMutex( NULL, FALSE, NULL ); \
                                 if( !a ) KEVS_FATAL_ERROR( "Could not get mutex lock." ); }
#else
#  define WAIT_FOR_LOCK(a)     
#  define RELEASE_LOCK(a)      
#  define CREATE_LOCK(a)       
#endif


#if( USE_LIST_ALLOCATION )


/*
 -------------------------------------------------------
            LIST ALLOCATION MEMORY POOLS
 -------------------------------------------------------

  Allocate all list related memory from memory pools

     (... per Roger Fuji's bitchin' & moanin! )


  Allocation Strategy:

  Memory is doled out for LISTs from large blocks of
  memory called 'POOL's.

  The pools are actually ALLOC_UNIT structs.
  The unit of memory that is provided to the caller  
  (and retrieved from a pool) is a LIST_UNIT.        
                                                     
  When a significant number of the LIST_UNITs have   
  been allocated from a pool, a new pool is created. 

  Additionally, LIST_UNITs are provided sequentially.
  eg; unit 1,2,3...  however towards the end of the  
  series, it is quite probable that earlier units    
  have been released.  At this point (when we are    
  doling out indices > ALLOC_SAFETY) we pack the     
  different pools.

  I'm sorry to admit, however, that pack - does not. 
  There is no clean way to pack the memory without   
  substantially vulgarizing the LIST type.

  So...  What I do is,

  a) see if any old pools now have 100% of their     
     units released. if so, free that pool.          

  b) see if any old pools now have more available    
     memory than our current pool, if so swap.       
     >>note: this one may not be a good idea.<<

  d) if this pool still has a lot of available       
     memory, reset our current index to 0.  This     
     will cause us to count up, looking for free     
     units - thus filling in spaces on a first come  
     basis.

  c) if we have to (eg; avail < ALLOC_SAFETY) we 
     allocate another pool.
 -------------------------------------------------------
      ROGERS' LAME O' HACK ADDED ON OCTOBER 3RD      
 -------------------------------------------------------
*/

typedef struct LIST_UNIT
{
   int     check;                   /* Has this unit been provided as a fulfillment ?   */
   void  * ptr_a;                   /* node                                             */
   void  * ptr_b;                   /* roger's lame o' hack                             */
   void  * ptr_c;                   /* next                                             */

} LIST_UNIT;

typedef struct ALLOC_UNIT
{
   LIST_UNIT unit[ ALLOC_UNITS ];   /* The actual table of memory to dole out as LIST * */

   int    index;                    /* Our current location in the table                */
   int    avail;                    /* Number of unit[]'s available from the table      */

   int    sleeping;                 /* Has this block been relegated to hibernation     */

   long   timer;                    /* Always nice to have a timer                      */

   void * min;                      /* Convenience for finding the correct block to     */
   void * max;                      /* perform a free from.                             */

   ALLOC_UNIT * next;               /* Link the allocation blocks                       */
   ALLOC_UNIT * prev;               /* Link the allocation blocks                       */

} ALLOC_UNIT;


PRIVATE
ALLOC_UNIT * 
   GLOBAL_ALLOC_TABLE = NULL;


PRIVATE
void
   ListGlobalPack( void ),
   ListGlobalAlloc( void );

PRIVATE
void
   ListFree( void * unit );

PRIVATE
void *
   ListAlloc( void );

#endif





/* ---------------------------------------------------------------------
   ---------------------------------------------------------------------

   L I S T   A L L O C A T I O N   F U N C T I O N S

   ---------------------------------------------------------------------
   --------------------------------------------------------------------- */


#if( USE_LIST_ALLOCATION )

PUBLIC
void
ListGlobalFree( void )
{
   ALLOC_UNIT * table, *tblptr;

   WAIT_FOR_LOCK( LIST_MUTEX );

   if( !GLOBAL_ALLOC_TABLE )
      return;

   table = GLOBAL_ALLOC_TABLE;

   while( table -> prev )
      table = table -> prev;

   for( ; table ;  ) 
   {
      tblptr = table -> next;
	  #ifdef USE_SH_POOLS
      MemFreePtr( table );
	  #else
      MemFree( table );
	  #endif
      table = tblptr;
   }

   GLOBAL_ALLOC_TABLE = NULL;

   RELEASE_LOCK( LIST_MUTEX );
}


PRIVATE
void 
ListGlobalAlloc( void )
{
   int   i;

   ALLOC_UNIT * new_unit = NULL;
   ALLOC_UNIT * old_unit = NULL;

   WAIT_FOR_LOCK( LIST_MUTEX, INFINITE );

   #ifdef USE_SH_POOLS
   new_unit = (ALLOC_UNIT *)MemAllocPtr( gResmmgrMemPool, sizeof( ALLOC_UNIT ), 0 );
   #else
   new_unit = (ALLOC_UNIT *)MemMalloc( sizeof( ALLOC_UNIT ), "LIST_MEM" );
   #endif

   if( !new_unit )
      KEVS_FATAL_ERROR( "No memory for list pool." );

   if( GLOBAL_ALLOC_TABLE )
   {
      old_unit = GLOBAL_ALLOC_TABLE;

      while( old_unit -> next )
         old_unit = old_unit -> next;
      
      old_unit -> next = new_unit;
      new_unit -> prev = old_unit;
      new_unit -> next = NULL;

      old_unit -> sleeping = TRUE;
   }
   else
   {
      new_unit -> next = NULL;
      new_unit -> prev = NULL;
   }

   new_unit -> sleeping = FALSE;

   new_unit -> avail = ALLOC_UNITS;
   new_unit -> index = 0;
   new_unit -> timer = TIME_COUNT;

   new_unit -> min = &new_unit -> unit[0].ptr_a;
   new_unit -> max = &new_unit -> unit[ALLOC_UNITS].ptr_a;

   for( i=0; i<ALLOC_UNITS; i++ )
      new_unit -> unit[i].check = ALLOC_FREE_FLAG;

   GLOBAL_ALLOC_TABLE = new_unit;

   RELEASE_LOCK( LIST_MUTEX );
}


PRIVATE
void *
ListAlloc( void )
{
   LIST_UNIT * lu;

   CREATE_LOCK( LIST_MUTEX );

   WAIT_FOR_LOCK( LIST_MUTEX );

   if( !GLOBAL_ALLOC_TABLE )
      ListGlobalAlloc();

   do
   {
      if ( ( GLOBAL_ALLOC_TABLE -> avail < ALLOC_SAFETY) ||
           ( GLOBAL_ALLOC_TABLE -> index > (ALLOC_UNITS - ALLOC_SAFETY)) )
 
          ListGlobalPack();
      
      lu = (LIST_UNIT *)(&GLOBAL_ALLOC_TABLE -> unit[ GLOBAL_ALLOC_TABLE -> index ]);

      GLOBAL_ALLOC_TABLE -> index++;

   } while( lu -> check != ALLOC_FREE_FLAG );

   lu -> check = ALLOC_USED_FLAG;

   GLOBAL_ALLOC_TABLE -> timer = TIME_COUNT;
   GLOBAL_ALLOC_TABLE -> avail--;

   RELEASE_LOCK( LIST_MUTEX );

   return ( &lu -> ptr_a );
}


PUBLIC
void
ListValidate( void )
{
   ALLOC_UNIT * tmp   = NULL;
   ALLOC_UNIT * table = NULL;

   int i;

   WAIT_FOR_LOCK( LIST_MUTEX );

   if( !GLOBAL_ALLOC_TABLE )
      return;

   for( tmp = GLOBAL_ALLOC_TABLE; tmp; tmp = (ALLOC_UNIT *)table -> prev )
      table = tmp;

   for( tmp = table; tmp; tmp = tmp -> next )
      for( i=0; i<ALLOC_UNITS; i++ )
         if( (tmp -> unit[i].check != ALLOC_FREE_FLAG ) &&
             (tmp -> unit[i].check != ALLOC_USED_FLAG ))
         {
            DBG(PF( "ERROR: Possible overwrite in lists." ));

            DBG(PF( "Unit Address: %x index: %d\n", &tmp -> unit[i] ));
            DBG(PF( "------------------------------------------\n"  ));
            DBG(PF( "node: %x\n", tmp -> unit[i].ptr_a ));
            DBG(PF( "user: %x\n", tmp -> unit[i].ptr_b ));
            DBG(PF( "next: %x\n", tmp -> unit[i].ptr_c ));
         }

   RELEASE_LOCK( LIST_MUTEX );
}


PRIVATE
void
ListFree( void * unit )
{
   int done = FALSE;

   LIST_UNIT * lu;

   ALLOC_UNIT * t   = NULL;
   ALLOC_UNIT * tbl = NULL;

   WAIT_FOR_LOCK( LIST_MUTEX );

   for( t = GLOBAL_ALLOC_TABLE; t; t = (ALLOC_UNIT *)tbl -> prev )
      tbl = t;

   if( !tbl )
   {
      DBG(PF( "Error freeing list structure.\n" ));
      RELEASE_LOCK( LIST_MUTEX );
      return;
   }

   lu = (LIST_UNIT *)( (int) unit - sizeof( int ) );

   if( lu -> check != ALLOC_USED_FLAG )
   {
      ERROR( "Free of a corrupt list node from allocation table." );
      RELEASE_LOCK( LIST_MUTEX );
      return;
   }

   do
   {
      if ( (unit >= tbl -> min) && (unit < tbl -> max) )
      {
         tbl -> avail++;

         lu -> check = ALLOC_FREE_FLAG;

         lu -> ptr_a = NULL;
         lu -> ptr_b = NULL;
         lu -> ptr_c = NULL;

         done = TRUE;

         break;
      }
      else
      {
         tbl = (ALLOC_UNIT *)tbl -> next;
      }

   } while( tbl && !done );

   if ( !done )
      ERROR( "Couldn't find list in allocation table\n" );

   RELEASE_LOCK( LIST_MUTEX );
}


PRIVATE
void
ListGlobalPack( void )
{
   int done  = FALSE;
   int total = 0;