lists.c

空战游戏flacon源码

   ALLOC_UNIT * t,
              * tbl = NULL;

   WAIT_FOR_LOCK( LIST_MUTEX );

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

   if (!tbl)
   {
      ERROR( "List allocation table empty -- cannot pack." ); 
      GLOBAL_ALLOC_TABLE -> index = 0;
      RELEASE_LOCK( LIST_MUTEX );
      return;
   }

   do
   {
      if( (tbl -> avail == ALLOC_UNITS) &&
          (tbl -> sleeping) )
      {
         if( tbl -> prev )
            tbl -> prev -> next = tbl -> next;
         if( tbl -> next )
            tbl -> next -> prev = tbl -> prev;

         total += (ALLOC_UNITS - tbl -> avail);

         if( tbl -> prev )
            t = tbl -> prev;
         else
            t = tbl -> next;   

         if( GLOBAL_ALLOC_TABLE == tbl ) 
            GLOBAL_ALLOC_TABLE = t;

		  #ifdef USE_SH_POOLS
		  MemFreePtr( tbl );
		  #else
		  MemFree( tbl );
		  #endif
         tbl = t;
      }
      else
      {
         if( tbl -> avail > (GLOBAL_ALLOC_TABLE -> avail + ALLOC_SWAP_SIZE) ) {
            GLOBAL_ALLOC_TABLE = tbl;
         }
         total += (ALLOC_UNITS - tbl -> avail);
         tbl = tbl -> next;
      }

   } while( tbl );

   if( !GLOBAL_ALLOC_TABLE || (GLOBAL_ALLOC_TABLE -> avail < ALLOC_SWAP_SIZE) )
      ListGlobalAlloc();

   GLOBAL_ALLOC_TABLE -> index = 0;

   RELEASE_LOCK( LIST_MUTEX );
}

#endif /* USE_LIST_ALLOCATION */








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

   C O R E   L I S T   F U N C T I O N S

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


/*
 * append new node to front of list 
 * return pointer to new list head
 * caller should cast returned value to appropriate type
 */


LST_EXPORT LIST *
ListAppend( LIST * list, void * node )
{
   LIST * newnode;

   newnode = (LIST *)LIST_ALLOC();

   newnode -> node = node;
   newnode -> next = list;

   return( newnode );
}                         


/*
 * append new node to end of list
 * caller should cast returned value to appropriate type
 */

LST_EXPORT LIST *
ListAppendEnd( LIST * list, void * node )
{
   LIST * newnode;
   LIST * curr;

   newnode = (LIST *)LIST_ALLOC();

   newnode -> node = node;
   newnode -> next = NULL;

   /* list was null */
   if ( !list ) 
   {
     list = newnode;
   }
   else 
   {
      /* find end of list */
      for( curr=list ; curr -> next != NULL ; curr = curr -> next ) ;

      /* chain in at end */
      curr -> next = newnode;
   }

   return( list );
}

/*
 * append new node after first element, assumes list was non-null
 * caller should cast returned value to appropriate type
 * used to global lists, without disturbing the pointer to 
 * the head of such lists.
 */

LST_EXPORT LIST *
ListAppendSecond( LIST * list, void * node )
{
   LIST * newnode;

   newnode = (LIST *)LIST_ALLOC();

   newnode -> node = node;

   /* chain in after first element */
   newnode -> next = list -> next;

   list -> next = newnode;

   /* return original head unchanged */
   return( list );
}


/*
 * join 2 lists, add l2 at end of l1
 */

LST_EXPORT LIST *
ListCatenate( LIST * l1, LIST * l2 )
{
   LIST *curr;

   if ( !l1 )
      return l2;

   if ( !l2 )
      return l1;

   /* find last element of l1 */
   for( curr = l1; curr -> next != NULL; curr = curr -> next );

   /* catenate */
   curr -> next = l2;

   return l1;
}


/*
 * destroy a list
 * optionally free the data pointed to by node, using supplied destructor fn
 * If destructor is NULL, node data not affected, only list nodes get freed
 */

LST_EXPORT void 
ListDestroy( LIST * list, PFV destructor )
{
   LIST * prev,
        * curr;

   if ( !list )
      return;

   prev = list;
   curr = list -> next;

   while ( curr )
   {
      if ( destructor )
         (*destructor)(prev -> node);

      prev -> next = NULL;

      LIST_FREE( prev );

      prev = curr;
      curr = curr -> next;
   }

   if( destructor )
      (*destructor)( prev -> node );

   prev -> next = NULL;

   LIST_FREE( prev );

   //ListGlobalPack();
}

     
/*
 * return pointer to nth element in list 
 * return NULL if no such element
 */


LST_EXPORT LIST *
ListNth( LIST * list, int n )
{
   int    i;
   LIST * curr;

   curr = list;

   for( i=0 ; i<n && curr; i++ )
      curr = curr -> next;

   return( curr );
}


/*
 * return Number of entries in list
 */

LST_EXPORT int
ListCount( LIST * list)
{
   LIST * curr;
   int i;

   for( i = 0, curr = list; curr; i++, curr = curr  ->  next ) 
       ;
   
   return( i );
}


/*
 * return index of given list element
 * return -1 if not found
 */

LST_EXPORT int
ListWhere( LIST * list, void * node )
{
   LIST * curr;
   int i;

   for( i = 0, curr = list; curr; i++, curr = curr  ->  next ) 
   {
      if ( curr -> node == node )
         return( i );
   }
   
   /* not found */
   return( -1 );
}


/*
 * remove a node from a list, iff it is found
 * return shortened list
 */

LST_EXPORT LIST *
ListRemove( LIST * list, void * node )
{
   LIST * prev,
        * curr;

   if ( !list )
      return( NULL );

   prev = NULL;
   curr = list;

   while( curr && (curr -> node != node) )
   {
      prev = curr;
      curr = curr -> next;
   }

   /* not found, return list unmodified */
   if ( !curr )
      return( list );

   /* found at head */
   if ( !prev )
      list = list -> next;
   else
      prev -> next = curr -> next;
   
   curr -> next = NULL;

   LIST_FREE( curr );

   return( list );
}


/*
 * return pointer to list node if found, else NULL
 */

LST_EXPORT LIST *
ListFind( LIST * list, void * node )
{
   LIST * curr;

   for( curr = list; curr; curr = curr -> next ) 
   {
      if ( curr -> node == node )
         return curr;
   }
   
   return( NULL );
}

LST_EXPORT LIST *
ListSearch( LIST * list, void * node, PFI func_ptr )
{
   LIST * l;

   for( l =  list; list; list = list -> next )
      if( !((*func_ptr)( list -> node, node )) )
         return( l );

   return( NULL );
}


LST_EXPORT LIST *
ListDup( LIST * list )
{
   LIST * newlist;

   newlist = (LIST *)LIST_ALLOC();

   newlist -> next = NULL;
   newlist -> node = list -> node;
   newlist -> user = list -> user;

   return (newlist);
}


LST_EXPORT LIST *
ListSort( LIST ** list, PFI func_ptr )
{
   LIST **parent_a;
   LIST **parent_b;

   for( parent_a = list; *parent_a; parent_a = &(*parent_a) -> next )
   {
      for( parent_b = &(*parent_a) -> next; *parent_b; parent_b = &(*parent_b) -> next )
      {
         if( func_ptr(*parent_a, *parent_b) > 0 )
         {
            LIST *swap_a, *swap_a_child;
            LIST *swap_b, *swap_b_child;

            swap_a       = *parent_a;
            swap_a_child = (*parent_a) -> next;
            swap_b       = *parent_b;
            swap_b_child = (*parent_b) -> next;

            (*parent_a) -> next = swap_b_child;
            (*parent_a)         = swap_b;

            if( swap_b == swap_a_child )
            {
                (*parent_a) -> next = swap_a;
                parent_b            = &(*parent_a) -> next;
            }
            else {
                (*parent_b) -> next = swap_a_child;
                (*parent_b)         = swap_a;
            }
         }

      }
   }

   return( *list );
}