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