OVR_List.h
Go to the documentation of this file.
00001 /************************************************************************************
00002 
00003 PublicHeader:   OVR
00004 Filename    :   OVR_List.h
00005 Content     :   Template implementation for doubly-connected linked List
00006 Created     :   September 19, 2012
00007 Notes       : 
00008 
00009 Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
00010 
00011 Use of this software is subject to the terms of the Oculus license
00012 agreement provided at the time of installation or download, or which
00013 otherwise accompanies this software in either electronic or hard copy form.
00014 
00015 ************************************************************************************/
00016 
00017 #ifndef OVR_List_h
00018 #define OVR_List_h
00019 
00020 #include "OVR_Types.h"
00021 
00022 namespace OVR {
00023 
00024 //-----------------------------------------------------------------------------------
00025 // ***** ListNode
00026 //
00027 // Base class for the elements of the intrusive linked list.
00028 // To store elements in the List do:
00029 //
00030 // struct MyData : ListNode<MyData>
00031 // {
00032 //     . . .
00033 // };
00034 
00035 template<class T>
00036 struct ListNode
00037 {
00038     union {
00039         T*    pPrev;
00040         void* pVoidPrev;
00041     };
00042     union {
00043         T*    pNext;
00044         void* pVoidNext;
00045     };
00046 
00047     void    RemoveNode()
00048     {
00049         pPrev->pNext = pNext;
00050         pNext->pPrev = pPrev;
00051     }
00052 
00053     // Removes us from the list and inserts pnew there instead.
00054     void    ReplaceNodeWith(T* pnew)
00055     {
00056         pPrev->pNext = pnew;
00057         pNext->pPrev = pnew;
00058         pnew->pPrev = pPrev;
00059         pnew->pNext = pNext;
00060     }
00061        
00062     // Inserts the argument linked list node after us in the list.
00063     void    InsertNodeAfter(T* p)
00064     {
00065         p->pPrev          = pNext->pPrev; // this
00066         p->pNext          = pNext;
00067         pNext->pPrev      = p;
00068         pNext             = p;
00069     }
00070     // Inserts the argument linked list node before us in the list.
00071     void    InsertNodeBefore(T* p)
00072     {
00073         p->pNext          = pNext->pPrev; // this
00074         p->pPrev          = pPrev;
00075         pPrev->pNext      = p;
00076         pPrev             = p;
00077     }
00078 
00079     void    Alloc_MoveTo(ListNode<T>* pdest)
00080     {
00081         pdest->pNext = pNext;
00082         pdest->pPrev = pPrev;
00083         pPrev->pNext = (T*)pdest;
00084         pNext->pPrev = (T*)pdest;
00085     }
00086 };
00087 
00088 
00089 //------------------------------------------------------------------------
00090 // ***** List
00091 //
00092 // Doubly linked intrusive list. 
00093 // The data type must be derived from ListNode.
00094 // 
00095 // Adding:   PushFront(), PushBack().
00096 // Removing: Remove() - the element must be in the list!
00097 // Moving:   BringToFront(), SendToBack() - the element must be in the list!
00098 //
00099 // Iterating:
00100 //    MyData* data = MyList.GetFirst();
00101 //    while (!MyList.IsNull(data))
00102 //    {
00103 //        . . .
00104 //        data = MyList.GetNext(data);
00105 //    }
00106 //
00107 // Removing:
00108 //    MyData* data = MyList.GetFirst();
00109 //    while (!MyList.IsNull(data))
00110 //    {
00111 //        MyData* next = MyList.GetNext(data);
00112 //        if (ToBeRemoved(data))
00113 //             MyList.Remove(data);
00114 //        data = next;
00115 //    }
00116 //
00117 
00118 // List<> represents a doubly-linked list if T, where each T must derive
00119 // from ListNode<B>. B specifies the base class that was directly
00120 // derived from ListNode, and is only necessary if there is an intermediate
00121 // inheritance chain.
00122 
00123 template<class T, class B = T> class List
00124 {
00125 public:
00126     typedef T ValueType;
00127 
00128     List()
00129     {
00130         Root.pNext = Root.pPrev = (ValueType*)&Root;
00131     }
00132 
00133     void Clear()
00134     {
00135         Root.pNext = Root.pPrev = (ValueType*)&Root;
00136     }
00137 
00138     const ValueType* GetFirst() const { return (const ValueType*)Root.pNext; }
00139     const ValueType* GetLast () const { return (const ValueType*)Root.pPrev; }
00140           ValueType* GetFirst()       { return (ValueType*)Root.pNext; }
00141           ValueType* GetLast ()       { return (ValueType*)Root.pPrev; }
00142 
00143     // Determine if list is empty (i.e.) points to itself.
00144     // Go through void* access to avoid issues with strict-aliasing optimizing out the
00145     // access after RemoveNode(), etc.
00146     bool IsEmpty()                   const { return Root.pVoidNext == (const T*)(const B*)&Root; }
00147     bool IsFirst(const ValueType* p) const { return p == Root.pNext; }
00148     bool IsLast (const ValueType* p) const { return p == Root.pPrev; }
00149     bool IsNull (const ValueType* p) const { return p == (const T*)(const B*)&Root; }
00150 
00151     inline static const ValueType* GetPrev(const ValueType* p) { return (const ValueType*)p->pPrev; }
00152     inline static const ValueType* GetNext(const ValueType* p) { return (const ValueType*)p->pNext; }
00153     inline static       ValueType* GetPrev(      ValueType* p) { return (ValueType*)p->pPrev; }
00154     inline static       ValueType* GetNext(      ValueType* p) { return (ValueType*)p->pNext; }
00155 
00156     void PushFront(ValueType* p)
00157     {
00158         p->pNext          =  Root.pNext;
00159         p->pPrev          = (ValueType*)&Root;
00160         Root.pNext->pPrev =  p;
00161         Root.pNext        =  p;
00162     }
00163 
00164     void PushBack(ValueType* p)
00165     {
00166         p->pPrev          =  Root.pPrev;
00167         p->pNext          = (ValueType*)&Root;
00168         Root.pPrev->pNext =  p;
00169         Root.pPrev        =  p;
00170     }
00171 
00172     static void Remove(ValueType* p)
00173     {
00174         p->pPrev->pNext = p->pNext;
00175         p->pNext->pPrev = p->pPrev;
00176     }
00177 
00178     void BringToFront(ValueType* p)
00179     {
00180         Remove(p);
00181         PushFront(p);
00182     }
00183 
00184     void SendToBack(ValueType* p)
00185     {
00186         Remove(p);
00187         PushBack(p);
00188     }
00189 
00190     // Appends the contents of the argument list to the front of this list;
00191     // items are removed from the argument list.
00192     void PushListToFront(List<T>& src)
00193     {
00194         if (!src.IsEmpty())
00195         {
00196             ValueType* pfirst = src.GetFirst();
00197             ValueType* plast  = src.GetLast();
00198             src.Clear();
00199             plast->pNext   = Root.pNext;
00200             pfirst->pPrev  = (ValueType*)&Root;
00201             Root.pNext->pPrev = plast;
00202             Root.pNext        = pfirst;
00203         }
00204     }
00205 
00206     void PushListToBack(List<T>& src)
00207     {
00208         if (!src.IsEmpty())
00209         {
00210             ValueType* pfirst = src.GetFirst();
00211             ValueType* plast  = src.GetLast();
00212             src.Clear();
00213             plast->pNext   = (ValueType*)&Root;
00214             pfirst->pPrev  = Root.pPrev;
00215             Root.pPrev->pNext = pfirst;
00216             Root.pPrev        = plast;
00217         }
00218     }
00219 
00220     // Removes all source list items after (and including) the 'pfirst' node from the 
00221     // source list and adds them to out list.
00222     void    PushFollowingListItemsToFront(List<T>& src, ValueType *pfirst)
00223     {
00224         if (pfirst != &src.Root)
00225         {
00226             ValueType *plast = src.Root.pPrev;
00227 
00228             // Remove list remainder from source.
00229             pfirst->pPrev->pNext = (ValueType*)&src.Root;
00230             src.Root.pPrev      = pfirst->pPrev;
00231             // Add the rest of the items to list.
00232             plast->pNext      = Root.pNext;
00233             pfirst->pPrev     = (ValueType*)&Root;
00234             Root.pNext->pPrev = plast;
00235             Root.pNext        = pfirst;
00236         }
00237     }
00238 
00239     // Removes all source list items up to but NOT including the 'pend' node from the 
00240     // source list and adds them to out list.
00241     void    PushPrecedingListItemsToFront(List<T>& src, ValueType *ptail)
00242     {
00243         if (src.GetFirst() != ptail)
00244         {
00245             ValueType *pfirst = src.Root.pNext;
00246             ValueType *plast  = ptail->pPrev;
00247 
00248             // Remove list remainder from source.
00249             ptail->pPrev      = (ValueType*)&src.Root;
00250             src.Root.pNext    = ptail;            
00251 
00252             // Add the rest of the items to list.
00253             plast->pNext      = Root.pNext;
00254             pfirst->pPrev     = (ValueType*)&Root;
00255             Root.pNext->pPrev = plast;
00256             Root.pNext        = pfirst;
00257         }
00258     }
00259 
00260 
00261     // Removes a range of source list items starting at 'pfirst' and up to, but not including 'pend',
00262     // and adds them to out list. Note that source items MUST already be in the list.
00263     void    PushListItemsToFront(ValueType *pfirst, ValueType *pend)
00264     {
00265         if (pfirst != pend)
00266         {
00267             ValueType *plast = pend->pPrev;
00268 
00269             // Remove list remainder from source.
00270             pfirst->pPrev->pNext = pend;
00271             pend->pPrev          = pfirst->pPrev;
00272             // Add the rest of the items to list.
00273             plast->pNext      = Root.pNext;
00274             pfirst->pPrev     = (ValueType*)&Root;
00275             Root.pNext->pPrev = plast;
00276             Root.pNext        = pfirst;
00277         }
00278     }
00279 
00280 
00281     void    Alloc_MoveTo(List<T>* pdest)
00282     {
00283         if (IsEmpty())
00284             pdest->Clear();
00285         else
00286         {
00287             pdest->Root.pNext = Root.pNext;
00288             pdest->Root.pPrev = Root.pPrev;
00289 
00290             Root.pNext->pPrev = (ValueType*)&pdest->Root;
00291             Root.pPrev->pNext = (ValueType*)&pdest->Root;
00292         }        
00293     }
00294 
00295 
00296 private:
00297     // Copying is prohibited
00298     List(const List<T>&);
00299     const List<T>& operator = (const List<T>&);
00300 
00301     ListNode<B> Root;
00302 };
00303 
00304 
00305 //------------------------------------------------------------------------
00306 // ***** FreeListElements
00307 //
00308 // Remove all elements in the list and free them in the allocator
00309 
00310 template<class List, class Allocator>
00311 void FreeListElements(List& list, Allocator& allocator)
00312 {
00313     typename List::ValueType* self = list.GetFirst();
00314     while(!list.IsNull(self))
00315     {
00316         typename List::ValueType* next = list.GetNext(self);
00317         allocator.Free(self);
00318         self = next;
00319     }
00320     list.Clear();
00321 }
00322 
00323 } // OVR
00324 
00325 #endif


oculus_sdk
Author(s):
autogenerated on Mon Oct 6 2014 03:01:19