Method orderList

Engine/source/T3D/gameBase/processList.cpp:130–193

//----------------------------------------------------------------------------

void ProcessList::orderList()
{
   // ProcessObject tags are initialized to 0, so current tag should never be 0.
   if (++mCurrentTag == 0)
      mCurrentTag++;

   // Install a temporary head node
   ProcessObject list;
   list.plLinkBefore(mHead.mProcessLink.next);
   mHead.plUnlink();

   // start out by (bubble) sorting list by GUID
   for (ProcessObject * cur = list.mProcessLink.next; cur != &list; cur = cur->mProcessLink.next)
   {
      if (cur->mOrderGUID == 0)
         // special case -- can be no lower, so accept as lowest (this is also
         // a common value since it is what non ordered objects have)
         continue;

      for (ProcessObject * walk = cur->mProcessLink.next; walk != &list; walk = walk->mProcessLink.next)
      {
         if (walk->mOrderGUID < cur->mOrderGUID)
         {
            // swap walk and cur -- need to be careful because walk might be just after cur
            // so insert after item before cur and before item after walk
            ProcessObject * before = cur->mProcessLink.prev;
            ProcessObject * after = walk->mProcessLink.next;
            cur->plUnlink();
            walk->plUnlink();
            cur->plLinkBefore(after);
            walk->plLinkAfter(before);
            ProcessObject * swap = walk;
            walk = cur;
            cur = swap;
         }
      }
   }

   // Reverse topological sort into the original head node
   while (list.mProcessLink.next != &list) 
   {
      ProcessObject * ptr = list.mProcessLink.next;
      ProcessObject * afterObject = ptr->getAfterObject();
      ptr->mProcessTag = mCurrentTag;
      ptr->plUnlink();
      if (afterObject) 
      {
         // Build chain "stack" of dependent objects and patch
         // it to the end of the current list.
         while (afterObject && afterObject->mProcessTag != mCurrentTag)
         {
            afterObject->mProcessTag = mCurrentTag;
            afterObject->plUnlink();
            afterObject->plLinkBefore(ptr);
            ptr = afterObject;
            afterObject = ptr->getAfterObject();
         }
         ptr->plJoin(&mHead);