oculus1

annotate libovr/Src/Kernel/OVR_List.h @ 1:e2f9e4603129

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