nuclear@0: /************************************************************************************
nuclear@0: 
nuclear@0: PublicHeader:   OVR
nuclear@0: Filename    :   OVR_List.h
nuclear@0: Content     :   Template implementation for doubly-connected linked List
nuclear@0: Created     :   September 19, 2012
nuclear@0: Notes       : 
nuclear@0: 
nuclear@0: Copyright   :   Copyright 2014 Oculus VR, LLC All Rights reserved.
nuclear@0: 
nuclear@0: Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
nuclear@0: you may not use the Oculus VR Rift SDK except in compliance with the License, 
nuclear@0: which is provided at the time of installation or download, or which 
nuclear@0: otherwise accompanies this software in either electronic or hard copy form.
nuclear@0: 
nuclear@0: You may obtain a copy of the License at
nuclear@0: 
nuclear@0: http://www.oculusvr.com/licenses/LICENSE-3.2 
nuclear@0: 
nuclear@0: Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
nuclear@0: distributed under the License is distributed on an "AS IS" BASIS,
nuclear@0: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
nuclear@0: See the License for the specific language governing permissions and
nuclear@0: limitations under the License.
nuclear@0: 
nuclear@0: ************************************************************************************/
nuclear@0: 
nuclear@0: #ifndef OVR_List_h
nuclear@0: #define OVR_List_h
nuclear@0: 
nuclear@0: #include "OVR_Types.h"
nuclear@0: 
nuclear@0: namespace OVR {
nuclear@0: 
nuclear@0: //-----------------------------------------------------------------------------------
nuclear@0: // ***** ListNode
nuclear@0: //
nuclear@0: // Base class for the elements of the intrusive linked list.
nuclear@0: // To store elements in the List do:
nuclear@0: //
nuclear@0: // struct MyData : ListNode<MyData>
nuclear@0: // {
nuclear@0: //     . . .
nuclear@0: // };
nuclear@0: 
nuclear@0: template<class T>
nuclear@0: struct ListNode
nuclear@0: {
nuclear@0:     union {
nuclear@0:         T*    pPrev;
nuclear@0:         void* pVoidPrev;
nuclear@0:     };
nuclear@0:     union {
nuclear@0:         T*    pNext;
nuclear@0:         void* pVoidNext;
nuclear@0:     };
nuclear@0: 
nuclear@0:     ListNode()
nuclear@0:     {
nuclear@0:         pPrev = NULL;
nuclear@0:         pNext = NULL;
nuclear@0:     }
nuclear@0: 
nuclear@0:     void    RemoveNode()
nuclear@0:     {
nuclear@0:         pPrev->pNext = pNext;
nuclear@0:         pNext->pPrev = pPrev;
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Removes us from the list and inserts pnew there instead.
nuclear@0:     void    ReplaceNodeWith(T* pnew)
nuclear@0:     {
nuclear@0:         pPrev->pNext = pnew;
nuclear@0:         pNext->pPrev = pnew;
nuclear@0:         pnew->pPrev = pPrev;
nuclear@0:         pnew->pNext = pNext;
nuclear@0:     }
nuclear@0:        
nuclear@0:     // Inserts the argument linked list node after us in the list.
nuclear@0:     void    InsertNodeAfter(T* p)
nuclear@0:     {
nuclear@0:         p->pPrev          = pNext->pPrev; // this
nuclear@0:         p->pNext          = pNext;
nuclear@0:         pNext->pPrev      = p;
nuclear@0:         pNext             = p;
nuclear@0:     }
nuclear@0:     // Inserts the argument linked list node before us in the list.
nuclear@0:     void    InsertNodeBefore(T* p)
nuclear@0:     {
nuclear@0:         p->pNext          = pNext->pPrev; // this
nuclear@0:         p->pPrev          = pPrev;
nuclear@0:         pPrev->pNext      = p;
nuclear@0:         pPrev             = p;
nuclear@0:     }
nuclear@0: 
nuclear@0:     void    Alloc_MoveTo(ListNode<T>* pdest)
nuclear@0:     {
nuclear@0:         pdest->pNext = pNext;
nuclear@0:         pdest->pPrev = pPrev;
nuclear@0:         pPrev->pNext = (T*)pdest;
nuclear@0:         pNext->pPrev = (T*)pdest;
nuclear@0:     }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: //------------------------------------------------------------------------
nuclear@0: // ***** List
nuclear@0: //
nuclear@0: // Doubly linked intrusive list. 
nuclear@0: // The data type must be derived from ListNode.
nuclear@0: // 
nuclear@0: // Adding:   PushFront(), PushBack().
nuclear@0: // Removing: Remove() - the element must be in the list!
nuclear@0: // Moving:   BringToFront(), SendToBack() - the element must be in the list!
nuclear@0: //
nuclear@0: // Iterating:
nuclear@0: //    MyData* data = MyList.GetFirst();
nuclear@0: //    while (!MyList.IsNull(data))
nuclear@0: //    {
nuclear@0: //        . . .
nuclear@0: //        data = MyList.GetNext(data);
nuclear@0: //    }
nuclear@0: //
nuclear@0: // Removing:
nuclear@0: //    MyData* data = MyList.GetFirst();
nuclear@0: //    while (!MyList.IsNull(data))
nuclear@0: //    {
nuclear@0: //        MyData* next = MyList.GetNext(data);
nuclear@0: //        if (ToBeRemoved(data))
nuclear@0: //             MyList.Remove(data);
nuclear@0: //        data = next;
nuclear@0: //    }
nuclear@0: //
nuclear@0: 
nuclear@0: // List<> represents a doubly-linked list of T, where each T must derive
nuclear@0: // from ListNode<B>. B specifies the base class that was directly
nuclear@0: // derived from ListNode, and is only necessary if there is an intermediate
nuclear@0: // inheritance chain.
nuclear@0: 
nuclear@0: template<class T, class B = T> class List
nuclear@0: {
nuclear@0: public:
nuclear@0:     typedef T ValueType;
nuclear@0: 
nuclear@0:     List()
nuclear@0:     {
nuclear@0:         Root.pNext = Root.pPrev = (ValueType*)&Root;
nuclear@0:     }
nuclear@0: 
nuclear@0:     void Clear()
nuclear@0:     {
nuclear@0:         Root.pNext = Root.pPrev = (ValueType*)&Root;
nuclear@0:     }
nuclear@0: 
nuclear@0:     const ValueType* GetFirst() const { return (const ValueType*)Root.pNext; }
nuclear@0:     const ValueType* GetLast () const { return (const ValueType*)Root.pPrev; }
nuclear@0:           ValueType* GetFirst()       { return (ValueType*)Root.pNext; }
nuclear@0:           ValueType* GetLast ()       { return (ValueType*)Root.pPrev; }
nuclear@0: 
nuclear@0:     // Determine if list is empty (i.e.) points to itself.
nuclear@0:     // Go through void* access to avoid issues with strict-aliasing optimizing out the
nuclear@0:     // access after RemoveNode(), etc.
nuclear@0:     bool IsEmpty()                   const { return Root.pVoidNext == (const T*)(const B*)&Root; }
nuclear@0:     bool IsFirst(const ValueType* p) const { return p == Root.pNext; }
nuclear@0:     bool IsLast (const ValueType* p) const { return p == Root.pPrev; }
nuclear@0:     bool IsNull (const ValueType* p) const { return p == (const T*)(const B*)&Root; }
nuclear@0: 
nuclear@0:     inline static const ValueType* GetPrev(const ValueType* p) { return (const ValueType*)p->pPrev; }
nuclear@0:     inline static const ValueType* GetNext(const ValueType* p) { return (const ValueType*)p->pNext; }
nuclear@0:     inline static       ValueType* GetPrev(      ValueType* p) { return (ValueType*)p->pPrev; }
nuclear@0:     inline static       ValueType* GetNext(      ValueType* p) { return (ValueType*)p->pNext; }
nuclear@0: 
nuclear@0:     void PushFront(ValueType* p)
nuclear@0:     {
nuclear@0:         p->pNext          =  Root.pNext;
nuclear@0:         p->pPrev          = (ValueType*)&Root;
nuclear@0:         Root.pNext->pPrev =  p;
nuclear@0:         Root.pNext        =  p;
nuclear@0:     }
nuclear@0: 
nuclear@0:     void PushBack(ValueType* p)
nuclear@0:     {
nuclear@0:         p->pPrev          =  Root.pPrev;
nuclear@0:         p->pNext          = (ValueType*)&Root;
nuclear@0:         Root.pPrev->pNext =  p;
nuclear@0:         Root.pPrev        =  p;
nuclear@0:     }
nuclear@0: 
nuclear@0:     static void Remove(ValueType* p)
nuclear@0:     {
nuclear@0:         p->pPrev->pNext = p->pNext;
nuclear@0:         p->pNext->pPrev = p->pPrev;
nuclear@0:     }
nuclear@0: 
nuclear@0:     void BringToFront(ValueType* p)
nuclear@0:     {
nuclear@0:         Remove(p);
nuclear@0:         PushFront(p);
nuclear@0:     }
nuclear@0: 
nuclear@0:     void SendToBack(ValueType* p)
nuclear@0:     {
nuclear@0:         Remove(p);
nuclear@0:         PushBack(p);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Appends the contents of the argument list to the front of this list;
nuclear@0:     // items are removed from the argument list.
nuclear@0:     void PushListToFront(List<T>& src)
nuclear@0:     {
nuclear@0:         if (!src.IsEmpty())
nuclear@0:         {
nuclear@0:             ValueType* pfirst = src.GetFirst();
nuclear@0:             ValueType* plast  = src.GetLast();
nuclear@0:             src.Clear();
nuclear@0:             plast->pNext   = Root.pNext;
nuclear@0:             pfirst->pPrev  = (ValueType*)&Root;
nuclear@0:             Root.pNext->pPrev = plast;
nuclear@0:             Root.pNext        = pfirst;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0:     void PushListToBack(List<T>& src)
nuclear@0:     {
nuclear@0:         if (!src.IsEmpty())
nuclear@0:         {
nuclear@0:             ValueType* pfirst = src.GetFirst();
nuclear@0:             ValueType* plast  = src.GetLast();
nuclear@0:             src.Clear();
nuclear@0:             plast->pNext   = (ValueType*)&Root;
nuclear@0:             pfirst->pPrev  = Root.pPrev;
nuclear@0:             Root.pPrev->pNext = pfirst;
nuclear@0:             Root.pPrev        = plast;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Removes all source list items after (and including) the 'pfirst' node from the 
nuclear@0:     // source list and adds them to out list.
nuclear@0:     void    PushFollowingListItemsToFront(List<T>& src, ValueType *pfirst)
nuclear@0:     {
nuclear@0:         if (pfirst != &src.Root)
nuclear@0:         {
nuclear@0:             ValueType *plast = src.Root.pPrev;
nuclear@0: 
nuclear@0:             // Remove list remainder from source.
nuclear@0:             pfirst->pPrev->pNext = (ValueType*)&src.Root;
nuclear@0:             src.Root.pPrev      = pfirst->pPrev;
nuclear@0:             // Add the rest of the items to list.
nuclear@0:             plast->pNext      = Root.pNext;
nuclear@0:             pfirst->pPrev     = (ValueType*)&Root;
nuclear@0:             Root.pNext->pPrev = plast;
nuclear@0:             Root.pNext        = pfirst;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Removes all source list items up to but NOT including the 'pend' node from the 
nuclear@0:     // source list and adds them to out list.
nuclear@0:     void    PushPrecedingListItemsToFront(List<T>& src, ValueType *ptail)
nuclear@0:     {
nuclear@0:         if (src.GetFirst() != ptail)
nuclear@0:         {
nuclear@0:             ValueType *pfirst = src.Root.pNext;
nuclear@0:             ValueType *plast  = ptail->pPrev;
nuclear@0: 
nuclear@0:             // Remove list remainder from source.
nuclear@0:             ptail->pPrev      = (ValueType*)&src.Root;
nuclear@0:             src.Root.pNext    = ptail;            
nuclear@0: 
nuclear@0:             // Add the rest of the items to list.
nuclear@0:             plast->pNext      = Root.pNext;
nuclear@0:             pfirst->pPrev     = (ValueType*)&Root;
nuclear@0:             Root.pNext->pPrev = plast;
nuclear@0:             Root.pNext        = pfirst;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     // Removes a range of source list items starting at 'pfirst' and up to, but not including 'pend',
nuclear@0:     // and adds them to out list. Note that source items MUST already be in the list.
nuclear@0:     void    PushListItemsToFront(ValueType *pfirst, ValueType *pend)
nuclear@0:     {
nuclear@0:         if (pfirst != pend)
nuclear@0:         {
nuclear@0:             ValueType *plast = pend->pPrev;
nuclear@0: 
nuclear@0:             // Remove list remainder from source.
nuclear@0:             pfirst->pPrev->pNext = pend;
nuclear@0:             pend->pPrev          = pfirst->pPrev;
nuclear@0:             // Add the rest of the items to list.
nuclear@0:             plast->pNext      = Root.pNext;
nuclear@0:             pfirst->pPrev     = (ValueType*)&Root;
nuclear@0:             Root.pNext->pPrev = plast;
nuclear@0:             Root.pNext        = pfirst;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     void    Alloc_MoveTo(List<T>* pdest)
nuclear@0:     {
nuclear@0:         if (IsEmpty())
nuclear@0:             pdest->Clear();
nuclear@0:         else
nuclear@0:         {
nuclear@0:             pdest->Root.pNext = Root.pNext;
nuclear@0:             pdest->Root.pPrev = Root.pPrev;
nuclear@0: 
nuclear@0:             Root.pNext->pPrev = (ValueType*)&pdest->Root;
nuclear@0:             Root.pPrev->pNext = (ValueType*)&pdest->Root;
nuclear@0:         }        
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0: private:
nuclear@0:     // Copying is prohibited
nuclear@0:     List(const List<T>&);
nuclear@0:     const List<T>& operator = (const List<T>&);
nuclear@0: 
nuclear@0:     ListNode<B> Root;
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: //------------------------------------------------------------------------
nuclear@0: // ***** FreeListElements
nuclear@0: //
nuclear@0: // Remove all elements in the list and free them in the allocator
nuclear@0: 
nuclear@0: template<class List, class Allocator>
nuclear@0: void FreeListElements(List& list, Allocator& allocator)
nuclear@0: {
nuclear@0:     typename List::ValueType* self = list.GetFirst();
nuclear@0:     while(!list.IsNull(self))
nuclear@0:     {
nuclear@0:         typename List::ValueType* next = list.GetNext(self);
nuclear@0:         allocator.Free(self);
nuclear@0:         self = next;
nuclear@0:     }
nuclear@0:     list.Clear();
nuclear@0: }
nuclear@0: 
nuclear@0: } // OVR
nuclear@0: 
nuclear@0: #endif