nuclear@3: /************************************************************************************
nuclear@3: 
nuclear@3: PublicHeader:   OVR
nuclear@3: Filename    :   OVR_List.h
nuclear@3: Content     :   Template implementation for doubly-connected linked List
nuclear@3: Created     :   September 19, 2012
nuclear@3: Notes       : 
nuclear@3: 
nuclear@3: Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@3: 
nuclear@3: Use of this software is subject to the terms of the Oculus license
nuclear@3: agreement provided at the time of installation or download, or which
nuclear@3: otherwise accompanies this software in either electronic or hard copy form.
nuclear@3: 
nuclear@3: ************************************************************************************/
nuclear@3: 
nuclear@3: #ifndef OVR_List_h
nuclear@3: #define OVR_List_h
nuclear@3: 
nuclear@3: #include "OVR_Types.h"
nuclear@3: 
nuclear@3: namespace OVR {
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ListNode
nuclear@3: //
nuclear@3: // Base class for the elements of the intrusive linked list.
nuclear@3: // To store elements in the List do:
nuclear@3: //
nuclear@3: // struct MyData : ListNode<MyData>
nuclear@3: // {
nuclear@3: //     . . .
nuclear@3: // };
nuclear@3: 
nuclear@3: template<class T>
nuclear@3: struct ListNode
nuclear@3: {
nuclear@3:     union {
nuclear@3:         T*    pPrev;
nuclear@3:         void* pVoidPrev;
nuclear@3:     };
nuclear@3:     union {
nuclear@3:         T*    pNext;
nuclear@3:         void* pVoidNext;
nuclear@3:     };
nuclear@3: 
nuclear@3:     void    RemoveNode()
nuclear@3:     {
nuclear@3:         pPrev->pNext = pNext;
nuclear@3:         pNext->pPrev = pPrev;
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Removes us from the list and inserts pnew there instead.
nuclear@3:     void    ReplaceNodeWith(T* pnew)
nuclear@3:     {
nuclear@3:         pPrev->pNext = pnew;
nuclear@3:         pNext->pPrev = pnew;
nuclear@3:         pnew->pPrev = pPrev;
nuclear@3:         pnew->pNext = pNext;
nuclear@3:     }
nuclear@3:        
nuclear@3:     // Inserts the argument linked list node after us in the list.
nuclear@3:     void    InsertNodeAfter(T* p)
nuclear@3:     {
nuclear@3:         p->pPrev          = pNext->pPrev; // this
nuclear@3:         p->pNext          = pNext;
nuclear@3:         pNext->pPrev      = p;
nuclear@3:         pNext             = p;
nuclear@3:     }
nuclear@3:     // Inserts the argument linked list node before us in the list.
nuclear@3:     void    InsertNodeBefore(T* p)
nuclear@3:     {
nuclear@3:         p->pNext          = pNext->pPrev; // this
nuclear@3:         p->pPrev          = pPrev;
nuclear@3:         pPrev->pNext      = p;
nuclear@3:         pPrev             = p;
nuclear@3:     }
nuclear@3: 
nuclear@3:     void    Alloc_MoveTo(ListNode<T>* pdest)
nuclear@3:     {
nuclear@3:         pdest->pNext = pNext;
nuclear@3:         pdest->pPrev = pPrev;
nuclear@3:         pPrev->pNext = (T*)pdest;
nuclear@3:         pNext->pPrev = (T*)pdest;
nuclear@3:     }
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: //------------------------------------------------------------------------
nuclear@3: // ***** List
nuclear@3: //
nuclear@3: // Doubly linked intrusive list. 
nuclear@3: // The data type must be derived from ListNode.
nuclear@3: // 
nuclear@3: // Adding:   PushFront(), PushBack().
nuclear@3: // Removing: Remove() - the element must be in the list!
nuclear@3: // Moving:   BringToFront(), SendToBack() - the element must be in the list!
nuclear@3: //
nuclear@3: // Iterating:
nuclear@3: //    MyData* data = MyList.GetFirst();
nuclear@3: //    while (!MyList.IsNull(data))
nuclear@3: //    {
nuclear@3: //        . . .
nuclear@3: //        data = MyList.GetNext(data);
nuclear@3: //    }
nuclear@3: //
nuclear@3: // Removing:
nuclear@3: //    MyData* data = MyList.GetFirst();
nuclear@3: //    while (!MyList.IsNull(data))
nuclear@3: //    {
nuclear@3: //        MyData* next = MyList.GetNext(data);
nuclear@3: //        if (ToBeRemoved(data))
nuclear@3: //             MyList.Remove(data);
nuclear@3: //        data = next;
nuclear@3: //    }
nuclear@3: //
nuclear@3: 
nuclear@3: // List<> represents a doubly-linked list of T, where each T must derive
nuclear@3: // from ListNode<B>. B specifies the base class that was directly
nuclear@3: // derived from ListNode, and is only necessary if there is an intermediate
nuclear@3: // inheritance chain.
nuclear@3: 
nuclear@3: template<class T, class B = T> class List
nuclear@3: {
nuclear@3: public:
nuclear@3:     typedef T ValueType;
nuclear@3: 
nuclear@3:     List()
nuclear@3:     {
nuclear@3:         Root.pNext = Root.pPrev = (ValueType*)&Root;
nuclear@3:     }
nuclear@3: 
nuclear@3:     void Clear()
nuclear@3:     {
nuclear@3:         Root.pNext = Root.pPrev = (ValueType*)&Root;
nuclear@3:     }
nuclear@3: 
nuclear@3:     const ValueType* GetFirst() const { return (const ValueType*)Root.pNext; }
nuclear@3:     const ValueType* GetLast () const { return (const ValueType*)Root.pPrev; }
nuclear@3:           ValueType* GetFirst()       { return (ValueType*)Root.pNext; }
nuclear@3:           ValueType* GetLast ()       { return (ValueType*)Root.pPrev; }
nuclear@3: 
nuclear@3:     // Determine if list is empty (i.e.) points to itself.
nuclear@3:     // Go through void* access to avoid issues with strict-aliasing optimizing out the
nuclear@3:     // access after RemoveNode(), etc.
nuclear@3:     bool IsEmpty()                   const { return Root.pVoidNext == (const T*)(const B*)&Root; }
nuclear@3:     bool IsFirst(const ValueType* p) const { return p == Root.pNext; }
nuclear@3:     bool IsLast (const ValueType* p) const { return p == Root.pPrev; }
nuclear@3:     bool IsNull (const ValueType* p) const { return p == (const T*)(const B*)&Root; }
nuclear@3: 
nuclear@3:     inline static const ValueType* GetPrev(const ValueType* p) { return (const ValueType*)p->pPrev; }
nuclear@3:     inline static const ValueType* GetNext(const ValueType* p) { return (const ValueType*)p->pNext; }
nuclear@3:     inline static       ValueType* GetPrev(      ValueType* p) { return (ValueType*)p->pPrev; }
nuclear@3:     inline static       ValueType* GetNext(      ValueType* p) { return (ValueType*)p->pNext; }
nuclear@3: 
nuclear@3:     void PushFront(ValueType* p)
nuclear@3:     {
nuclear@3:         p->pNext          =  Root.pNext;
nuclear@3:         p->pPrev          = (ValueType*)&Root;
nuclear@3:         Root.pNext->pPrev =  p;
nuclear@3:         Root.pNext        =  p;
nuclear@3:     }
nuclear@3: 
nuclear@3:     void PushBack(ValueType* p)
nuclear@3:     {
nuclear@3:         p->pPrev          =  Root.pPrev;
nuclear@3:         p->pNext          = (ValueType*)&Root;
nuclear@3:         Root.pPrev->pNext =  p;
nuclear@3:         Root.pPrev        =  p;
nuclear@3:     }
nuclear@3: 
nuclear@3:     static void Remove(ValueType* p)
nuclear@3:     {
nuclear@3:         p->pPrev->pNext = p->pNext;
nuclear@3:         p->pNext->pPrev = p->pPrev;
nuclear@3:     }
nuclear@3: 
nuclear@3:     void BringToFront(ValueType* p)
nuclear@3:     {
nuclear@3:         Remove(p);
nuclear@3:         PushFront(p);
nuclear@3:     }
nuclear@3: 
nuclear@3:     void SendToBack(ValueType* p)
nuclear@3:     {
nuclear@3:         Remove(p);
nuclear@3:         PushBack(p);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Appends the contents of the argument list to the front of this list;
nuclear@3:     // items are removed from the argument list.
nuclear@3:     void PushListToFront(List<T>& src)
nuclear@3:     {
nuclear@3:         if (!src.IsEmpty())
nuclear@3:         {
nuclear@3:             ValueType* pfirst = src.GetFirst();
nuclear@3:             ValueType* plast  = src.GetLast();
nuclear@3:             src.Clear();
nuclear@3:             plast->pNext   = Root.pNext;
nuclear@3:             pfirst->pPrev  = (ValueType*)&Root;
nuclear@3:             Root.pNext->pPrev = plast;
nuclear@3:             Root.pNext        = pfirst;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     void PushListToBack(List<T>& src)
nuclear@3:     {
nuclear@3:         if (!src.IsEmpty())
nuclear@3:         {
nuclear@3:             ValueType* pfirst = src.GetFirst();
nuclear@3:             ValueType* plast  = src.GetLast();
nuclear@3:             src.Clear();
nuclear@3:             plast->pNext   = (ValueType*)&Root;
nuclear@3:             pfirst->pPrev  = Root.pPrev;
nuclear@3:             Root.pPrev->pNext = pfirst;
nuclear@3:             Root.pPrev        = plast;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Removes all source list items after (and including) the 'pfirst' node from the 
nuclear@3:     // source list and adds them to out list.
nuclear@3:     void    PushFollowingListItemsToFront(List<T>& src, ValueType *pfirst)
nuclear@3:     {
nuclear@3:         if (pfirst != &src.Root)
nuclear@3:         {
nuclear@3:             ValueType *plast = src.Root.pPrev;
nuclear@3: 
nuclear@3:             // Remove list remainder from source.
nuclear@3:             pfirst->pPrev->pNext = (ValueType*)&src.Root;
nuclear@3:             src.Root.pPrev      = pfirst->pPrev;
nuclear@3:             // Add the rest of the items to list.
nuclear@3:             plast->pNext      = Root.pNext;
nuclear@3:             pfirst->pPrev     = (ValueType*)&Root;
nuclear@3:             Root.pNext->pPrev = plast;
nuclear@3:             Root.pNext        = pfirst;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Removes all source list items up to but NOT including the 'pend' node from the 
nuclear@3:     // source list and adds them to out list.
nuclear@3:     void    PushPrecedingListItemsToFront(List<T>& src, ValueType *ptail)
nuclear@3:     {
nuclear@3:         if (src.GetFirst() != ptail)
nuclear@3:         {
nuclear@3:             ValueType *pfirst = src.Root.pNext;
nuclear@3:             ValueType *plast  = ptail->pPrev;
nuclear@3: 
nuclear@3:             // Remove list remainder from source.
nuclear@3:             ptail->pPrev      = (ValueType*)&src.Root;
nuclear@3:             src.Root.pNext    = ptail;            
nuclear@3: 
nuclear@3:             // Add the rest of the items to list.
nuclear@3:             plast->pNext      = Root.pNext;
nuclear@3:             pfirst->pPrev     = (ValueType*)&Root;
nuclear@3:             Root.pNext->pPrev = plast;
nuclear@3:             Root.pNext        = pfirst;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3: 
nuclear@3:     // Removes a range of source list items starting at 'pfirst' and up to, but not including 'pend',
nuclear@3:     // and adds them to out list. Note that source items MUST already be in the list.
nuclear@3:     void    PushListItemsToFront(ValueType *pfirst, ValueType *pend)
nuclear@3:     {
nuclear@3:         if (pfirst != pend)
nuclear@3:         {
nuclear@3:             ValueType *plast = pend->pPrev;
nuclear@3: 
nuclear@3:             // Remove list remainder from source.
nuclear@3:             pfirst->pPrev->pNext = pend;
nuclear@3:             pend->pPrev          = pfirst->pPrev;
nuclear@3:             // Add the rest of the items to list.
nuclear@3:             plast->pNext      = Root.pNext;
nuclear@3:             pfirst->pPrev     = (ValueType*)&Root;
nuclear@3:             Root.pNext->pPrev = plast;
nuclear@3:             Root.pNext        = pfirst;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3: 
nuclear@3:     void    Alloc_MoveTo(List<T>* pdest)
nuclear@3:     {
nuclear@3:         if (IsEmpty())
nuclear@3:             pdest->Clear();
nuclear@3:         else
nuclear@3:         {
nuclear@3:             pdest->Root.pNext = Root.pNext;
nuclear@3:             pdest->Root.pPrev = Root.pPrev;
nuclear@3: 
nuclear@3:             Root.pNext->pPrev = (ValueType*)&pdest->Root;
nuclear@3:             Root.pPrev->pNext = (ValueType*)&pdest->Root;
nuclear@3:         }        
nuclear@3:     }
nuclear@3: 
nuclear@3: 
nuclear@3: private:
nuclear@3:     // Copying is prohibited
nuclear@3:     List(const List<T>&);
nuclear@3:     const List<T>& operator = (const List<T>&);
nuclear@3: 
nuclear@3:     ListNode<B> Root;
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: //------------------------------------------------------------------------
nuclear@3: // ***** FreeListElements
nuclear@3: //
nuclear@3: // Remove all elements in the list and free them in the allocator
nuclear@3: 
nuclear@3: template<class List, class Allocator>
nuclear@3: void FreeListElements(List& list, Allocator& allocator)
nuclear@3: {
nuclear@3:     typename List::ValueType* self = list.GetFirst();
nuclear@3:     while(!list.IsNull(self))
nuclear@3:     {
nuclear@3:         typename List::ValueType* next = list.GetNext(self);
nuclear@3:         allocator.Free(self);
nuclear@3:         self = next;
nuclear@3:     }
nuclear@3:     list.Clear();
nuclear@3: }
nuclear@3: 
nuclear@3: } // OVR
nuclear@3: 
nuclear@3: #endif