ovr_sdk

annotate LibOVR/Src/Kernel/OVR_List.h @ 0:1b39a1b46319

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