Game Development Community

Core/llist.h optimizations and additions

by Danni · in Torque Game Engine Advanced · 06/30/2008 (11:42 pm) · 0 replies

Not realy a bug, i wanted to use the built in llist template rather than break the memory manager compatibility and use STL. I added a few methods which give allow more efficient use of the list rather than the ugly reitteration it does on unlink after already performing one itteration.

Please review and consider this for inclusion in the future for other developers. (An Andersson or Red/Black tree template would be marverlous too, ^_~ ... I may write one if i need it.)

T *pop_first(void)
   {
	   if (!first_entry)
		   return NULL;

	   T* e = first_entry->Data;
	   LListNode<T> *entryNode = first_entry;
      
       first_entry = first_entry->Next;
 
      if( entryNode->Next == NULL )
      {
         last_entry = entryNode->Prev;
      }
      else
      {
         entryNode->Next->Prev = entryNode->Prev;
      }

      delete entryNode;

      --cnt;
	   return e;
   }

   T *pop_last(void)
   {
	   if (!last_entry)
		   return NULL;

	   T* e = last_entry->Data;
	   LListNode<T> *entryNode = last_entry;
      
      if( entryNode->Prev == NULL )
      {
         first_entry = entryNode->Next;
      }
      else
      {
         entryNode->Prev->Next = entryNode->Next;
      }
      last_entry = entryNode->Prev;

      delete entryNode;

      --cnt;
	   return e;
   }
   void push_back(T &entry)
   {

	  T *newEntry = new T;
      *newEntry = entry;

      LListNode<T> *prevNode = NULL;
      LListNode<T> *newNode = new LListNode<T>;

      newNode->Data = newEntry;

      prevNode = last_entry;
      last_entry = newNode;
 
      newNode->Next = NULL;
      newNode->Prev = prevNode;

	  if (!first_entry)
		  first_entry = last_entry;

      ++cnt;
   }

   //---------------------------------------------------------------------------------------
   // Unlink node from list (without destroying it)
   //---------------------------------------------------------------------------------------
   void unlink(LListNode<T> *entryNode)
   {
      if( !entryNode ) return;

      if( entryNode->Prev == NULL )
      {
         first_entry = entryNode->Next;
      }
      else
      {
         entryNode->Prev->Next = entryNode->Next;
      }

      if( entryNode->Next == NULL )
      {
         last_entry = entryNode->Prev;
      }
      else
      {
         entryNode->Next->Prev = entryNode->Prev;
      }

      delete entryNode;

      --cnt;
   }   

   void free(LListNode<T> *entry)
   {
      unlink(entry);
      delete entry;
   }