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