oculus1

annotate libovr/Src/Kernel/OVR_List.h @ 12:d797639e0234

find changesets by author, revision, files, or words in the commit message
moving on to the distortion... not correct yet
author John Tsiombikas <nuclear@member.fsf.org>
date Fri, 20 Sep 2013 10:14:29 +0300
parents e2f9e4603129
children
rev   line source
nuclear@3 1 /************************************************************************************
nuclear@3 2
nuclear@3 3 PublicHeader: OVR
nuclear@3 4 Filename : OVR_List.h
nuclear@3 5 Content : Template implementation for doubly-connected linked List
nuclear@3 6 Created : September 19, 2012
nuclear@3 7 Notes :
nuclear@3 8
nuclear@3 9 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@3 10
nuclear@3 11 Use of this software is subject to the terms of the Oculus license
nuclear@3 12 agreement provided at the time of installation or download, or which
nuclear@3 13 otherwise accompanies this software in either electronic or hard copy form.
nuclear@3 14
nuclear@3 15 ************************************************************************************/
nuclear@3 16
nuclear@3 17 #ifndef OVR_List_h
nuclear@3 18 #define OVR_List_h
nuclear@3 19
nuclear@3 20 #include "OVR_Types.h"
nuclear@3 21
nuclear@3 22 namespace OVR {
nuclear@3 23
nuclear@3 24 //-----------------------------------------------------------------------------------
nuclear@3 25 // ***** ListNode
nuclear@3 26 //
nuclear@3 27 // Base class for the elements of the intrusive linked list.
nuclear@3 28 // To store elements in the List do:
nuclear@3 29 //
nuclear@3 30 // struct MyData : ListNode<MyData>
nuclear@3 31 // {
nuclear@3 32 // . . .
nuclear@3 33 // };
nuclear@3 34
nuclear@3 35 template<class T>
nuclear@3 36 struct ListNode
nuclear@3 37 {
nuclear@3 38 union {
nuclear@3 39 T* pPrev;
nuclear@3 40 void* pVoidPrev;
nuclear@3 41 };
nuclear@3 42 union {
nuclear@3 43 T* pNext;
nuclear@3 44 void* pVoidNext;
nuclear@3 45 };
nuclear@3 46
nuclear@3 47 void RemoveNode()
nuclear@3 48 {
nuclear@3 49 pPrev->pNext = pNext;
nuclear@3 50 pNext->pPrev = pPrev;
nuclear@3 51 }
nuclear@3 52
nuclear@3 53 // Removes us from the list and inserts pnew there instead.
nuclear@3 54 void ReplaceNodeWith(T* pnew)
nuclear@3 55 {
nuclear@3 56 pPrev->pNext = pnew;
nuclear@3 57 pNext->pPrev = pnew;
nuclear@3 58 pnew->pPrev = pPrev;
nuclear@3 59 pnew->pNext = pNext;
nuclear@3 60 }
nuclear@3 61
nuclear@3 62 // Inserts the argument linked list node after us in the list.
nuclear@3 63 void InsertNodeAfter(T* p)
nuclear@3 64 {
nuclear@3 65 p->pPrev = pNext->pPrev; // this
nuclear@3 66 p->pNext = pNext;
nuclear@3 67 pNext->pPrev = p;
nuclear@3 68 pNext = p;
nuclear@3 69 }
nuclear@3 70 // Inserts the argument linked list node before us in the list.
nuclear@3 71 void InsertNodeBefore(T* p)
nuclear@3 72 {
nuclear@3 73 p->pNext = pNext->pPrev; // this
nuclear@3 74 p->pPrev = pPrev;
nuclear@3 75 pPrev->pNext = p;
nuclear@3 76 pPrev = p;
nuclear@3 77 }
nuclear@3 78
nuclear@3 79 void Alloc_MoveTo(ListNode<T>* pdest)
nuclear@3 80 {
nuclear@3 81 pdest->pNext = pNext;
nuclear@3 82 pdest->pPrev = pPrev;
nuclear@3 83 pPrev->pNext = (T*)pdest;
nuclear@3 84 pNext->pPrev = (T*)pdest;
nuclear@3 85 }
nuclear@3 86 };
nuclear@3 87
nuclear@3 88
nuclear@3 89 //------------------------------------------------------------------------
nuclear@3 90 // ***** List
nuclear@3 91 //
nuclear@3 92 // Doubly linked intrusive list.
nuclear@3 93 // The data type must be derived from ListNode.
nuclear@3 94 //
nuclear@3 95 // Adding: PushFront(), PushBack().
nuclear@3 96 // Removing: Remove() - the element must be in the list!
nuclear@3 97 // Moving: BringToFront(), SendToBack() - the element must be in the list!
nuclear@3 98 //
nuclear@3 99 // Iterating:
nuclear@3 100 // MyData* data = MyList.GetFirst();
nuclear@3 101 // while (!MyList.IsNull(data))
nuclear@3 102 // {
nuclear@3 103 // . . .
nuclear@3 104 // data = MyList.GetNext(data);
nuclear@3 105 // }
nuclear@3 106 //
nuclear@3 107 // Removing:
nuclear@3 108 // MyData* data = MyList.GetFirst();
nuclear@3 109 // while (!MyList.IsNull(data))
nuclear@3 110 // {
nuclear@3 111 // MyData* next = MyList.GetNext(data);
nuclear@3 112 // if (ToBeRemoved(data))
nuclear@3 113 // MyList.Remove(data);
nuclear@3 114 // data = next;
nuclear@3 115 // }
nuclear@3 116 //
nuclear@3 117
nuclear@3 118 // List<> represents a doubly-linked list of T, where each T must derive
nuclear@3 119 // from ListNode<B>. B specifies the base class that was directly
nuclear@3 120 // derived from ListNode, and is only necessary if there is an intermediate
nuclear@3 121 // inheritance chain.
nuclear@3 122
nuclear@3 123 template<class T, class B = T> class List
nuclear@3 124 {
nuclear@3 125 public:
nuclear@3 126 typedef T ValueType;
nuclear@3 127
nuclear@3 128 List()
nuclear@3 129 {
nuclear@3 130 Root.pNext = Root.pPrev = (ValueType*)&Root;
nuclear@3 131 }
nuclear@3 132
nuclear@3 133 void Clear()
nuclear@3 134 {
nuclear@3 135 Root.pNext = Root.pPrev = (ValueType*)&Root;
nuclear@3 136 }
nuclear@3 137
nuclear@3 138 const ValueType* GetFirst() const { return (const ValueType*)Root.pNext; }
nuclear@3 139 const ValueType* GetLast () const { return (const ValueType*)Root.pPrev; }
nuclear@3 140 ValueType* GetFirst() { return (ValueType*)Root.pNext; }
nuclear@3 141 ValueType* GetLast () { return (ValueType*)Root.pPrev; }
nuclear@3 142
nuclear@3 143 // Determine if list is empty (i.e.) points to itself.
nuclear@3 144 // Go through void* access to avoid issues with strict-aliasing optimizing out the
nuclear@3 145 // access after RemoveNode(), etc.
nuclear@3 146 bool IsEmpty() const { return Root.pVoidNext == (const T*)(const B*)&Root; }
nuclear@3 147 bool IsFirst(const ValueType* p) const { return p == Root.pNext; }
nuclear@3 148 bool IsLast (const ValueType* p) const { return p == Root.pPrev; }
nuclear@3 149 bool IsNull (const ValueType* p) const { return p == (const T*)(const B*)&Root; }
nuclear@3 150
nuclear@3 151 inline static const ValueType* GetPrev(const ValueType* p) { return (const ValueType*)p->pPrev; }
nuclear@3 152 inline static const ValueType* GetNext(const ValueType* p) { return (const ValueType*)p->pNext; }
nuclear@3 153 inline static ValueType* GetPrev( ValueType* p) { return (ValueType*)p->pPrev; }
nuclear@3 154 inline static ValueType* GetNext( ValueType* p) { return (ValueType*)p->pNext; }
nuclear@3 155
nuclear@3 156 void PushFront(ValueType* p)
nuclear@3 157 {
nuclear@3 158 p->pNext = Root.pNext;
nuclear@3 159 p->pPrev = (ValueType*)&Root;
nuclear@3 160 Root.pNext->pPrev = p;
nuclear@3 161 Root.pNext = p;
nuclear@3 162 }
nuclear@3 163
nuclear@3 164 void PushBack(ValueType* p)
nuclear@3 165 {
nuclear@3 166 p->pPrev = Root.pPrev;
nuclear@3 167 p->pNext = (ValueType*)&Root;
nuclear@3 168 Root.pPrev->pNext = p;
nuclear@3 169 Root.pPrev = p;
nuclear@3 170 }
nuclear@3 171
nuclear@3 172 static void Remove(ValueType* p)
nuclear@3 173 {
nuclear@3 174 p->pPrev->pNext = p->pNext;
nuclear@3 175 p->pNext->pPrev = p->pPrev;
nuclear@3 176 }
nuclear@3 177
nuclear@3 178 void BringToFront(ValueType* p)
nuclear@3 179 {
nuclear@3 180 Remove(p);
nuclear@3 181 PushFront(p);
nuclear@3 182 }
nuclear@3 183
nuclear@3 184 void SendToBack(ValueType* p)
nuclear@3 185 {
nuclear@3 186 Remove(p);
nuclear@3 187 PushBack(p);
nuclear@3 188 }
nuclear@3 189
nuclear@3 190 // Appends the contents of the argument list to the front of this list;
nuclear@3 191 // items are removed from the argument list.
nuclear@3 192 void PushListToFront(List<T>& src)
nuclear@3 193 {
nuclear@3 194 if (!src.IsEmpty())
nuclear@3 195 {
nuclear@3 196 ValueType* pfirst = src.GetFirst();
nuclear@3 197 ValueType* plast = src.GetLast();
nuclear@3 198 src.Clear();
nuclear@3 199 plast->pNext = Root.pNext;
nuclear@3 200 pfirst->pPrev = (ValueType*)&Root;
nuclear@3 201 Root.pNext->pPrev = plast;
nuclear@3 202 Root.pNext = pfirst;
nuclear@3 203 }
nuclear@3 204 }
nuclear@3 205
nuclear@3 206 void PushListToBack(List<T>& src)
nuclear@3 207 {
nuclear@3 208 if (!src.IsEmpty())
nuclear@3 209 {
nuclear@3 210 ValueType* pfirst = src.GetFirst();
nuclear@3 211 ValueType* plast = src.GetLast();
nuclear@3 212 src.Clear();
nuclear@3 213 plast->pNext = (ValueType*)&Root;
nuclear@3 214 pfirst->pPrev = Root.pPrev;
nuclear@3 215 Root.pPrev->pNext = pfirst;
nuclear@3 216 Root.pPrev = plast;
nuclear@3 217 }
nuclear@3 218 }
nuclear@3 219
nuclear@3 220 // Removes all source list items after (and including) the 'pfirst' node from the
nuclear@3 221 // source list and adds them to out list.
nuclear@3 222 void PushFollowingListItemsToFront(List<T>& src, ValueType *pfirst)
nuclear@3 223 {
nuclear@3 224 if (pfirst != &src.Root)
nuclear@3 225 {
nuclear@3 226 ValueType *plast = src.Root.pPrev;
nuclear@3 227
nuclear@3 228 // Remove list remainder from source.
nuclear@3 229 pfirst->pPrev->pNext = (ValueType*)&src.Root;
nuclear@3 230 src.Root.pPrev = pfirst->pPrev;
nuclear@3 231 // Add the rest of the items to list.
nuclear@3 232 plast->pNext = Root.pNext;
nuclear@3 233 pfirst->pPrev = (ValueType*)&Root;
nuclear@3 234 Root.pNext->pPrev = plast;
nuclear@3 235 Root.pNext = pfirst;
nuclear@3 236 }
nuclear@3 237 }
nuclear@3 238
nuclear@3 239 // Removes all source list items up to but NOT including the 'pend' node from the
nuclear@3 240 // source list and adds them to out list.
nuclear@3 241 void PushPrecedingListItemsToFront(List<T>& src, ValueType *ptail)
nuclear@3 242 {
nuclear@3 243 if (src.GetFirst() != ptail)
nuclear@3 244 {
nuclear@3 245 ValueType *pfirst = src.Root.pNext;
nuclear@3 246 ValueType *plast = ptail->pPrev;
nuclear@3 247
nuclear@3 248 // Remove list remainder from source.
nuclear@3 249 ptail->pPrev = (ValueType*)&src.Root;
nuclear@3 250 src.Root.pNext = ptail;
nuclear@3 251
nuclear@3 252 // Add the rest of the items to list.
nuclear@3 253 plast->pNext = Root.pNext;
nuclear@3 254 pfirst->pPrev = (ValueType*)&Root;
nuclear@3 255 Root.pNext->pPrev = plast;
nuclear@3 256 Root.pNext = pfirst;
nuclear@3 257 }
nuclear@3 258 }
nuclear@3 259
nuclear@3 260
nuclear@3 261 // Removes a range of source list items starting at 'pfirst' and up to, but not including 'pend',
nuclear@3 262 // and adds them to out list. Note that source items MUST already be in the list.
nuclear@3 263 void PushListItemsToFront(ValueType *pfirst, ValueType *pend)
nuclear@3 264 {
nuclear@3 265 if (pfirst != pend)
nuclear@3 266 {
nuclear@3 267 ValueType *plast = pend->pPrev;
nuclear@3 268
nuclear@3 269 // Remove list remainder from source.
nuclear@3 270 pfirst->pPrev->pNext = pend;
nuclear@3 271 pend->pPrev = pfirst->pPrev;
nuclear@3 272 // Add the rest of the items to list.
nuclear@3 273 plast->pNext = Root.pNext;
nuclear@3 274 pfirst->pPrev = (ValueType*)&Root;
nuclear@3 275 Root.pNext->pPrev = plast;
nuclear@3 276 Root.pNext = pfirst;
nuclear@3 277 }
nuclear@3 278 }
nuclear@3 279
nuclear@3 280
nuclear@3 281 void Alloc_MoveTo(List<T>* pdest)
nuclear@3 282 {
nuclear@3 283 if (IsEmpty())
nuclear@3 284 pdest->Clear();
nuclear@3 285 else
nuclear@3 286 {
nuclear@3 287 pdest->Root.pNext = Root.pNext;
nuclear@3 288 pdest->Root.pPrev = Root.pPrev;
nuclear@3 289
nuclear@3 290 Root.pNext->pPrev = (ValueType*)&pdest->Root;
nuclear@3 291 Root.pPrev->pNext = (ValueType*)&pdest->Root;
nuclear@3 292 }
nuclear@3 293 }
nuclear@3 294
nuclear@3 295
nuclear@3 296 private:
nuclear@3 297 // Copying is prohibited
nuclear@3 298 List(const List<T>&);
nuclear@3 299 const List<T>& operator = (const List<T>&);
nuclear@3 300
nuclear@3 301 ListNode<B> Root;
nuclear@3 302 };
nuclear@3 303
nuclear@3 304
nuclear@3 305 //------------------------------------------------------------------------
nuclear@3 306 // ***** FreeListElements
nuclear@3 307 //
nuclear@3 308 // Remove all elements in the list and free them in the allocator
nuclear@3 309
nuclear@3 310 template<class List, class Allocator>
nuclear@3 311 void FreeListElements(List& list, Allocator& allocator)
nuclear@3 312 {
nuclear@3 313 typename List::ValueType* self = list.GetFirst();
nuclear@3 314 while(!list.IsNull(self))
nuclear@3 315 {
nuclear@3 316 typename List::ValueType* next = list.GetNext(self);
nuclear@3 317 allocator.Free(self);
nuclear@3 318 self = next;
nuclear@3 319 }
nuclear@3 320 list.Clear();
nuclear@3 321 }
nuclear@3 322
nuclear@3 323 } // OVR
nuclear@3 324
nuclear@3 325 #endif