oculus1
diff libovr/Src/Kernel/OVR_List.h @ 1:e2f9e4603129
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 |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/libovr/Src/Kernel/OVR_List.h Sat Sep 14 16:14:59 2013 +0300 1.3 @@ -0,0 +1,1 @@ 1.4 +/************************************************************************************ 1.5 1.6 PublicHeader: OVR 1.7 Filename : OVR_List.h 1.8 Content : Template implementation for doubly-connected linked List 1.9 Created : September 19, 2012 1.10 Notes : 1.11 1.12 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved. 1.13 1.14 Use of this software is subject to the terms of the Oculus license 1.15 agreement provided at the time of installation or download, or which 1.16 otherwise accompanies this software in either electronic or hard copy form. 1.17 1.18 ************************************************************************************/ 1.19 1.20 #ifndef OVR_List_h 1.21 #define OVR_List_h 1.22 1.23 #include "OVR_Types.h" 1.24 1.25 namespace OVR { 1.26 1.27 //----------------------------------------------------------------------------------- 1.28 // ***** ListNode 1.29 // 1.30 // Base class for the elements of the intrusive linked list. 1.31 // To store elements in the List do: 1.32 // 1.33 // struct MyData : ListNode<MyData> 1.34 // { 1.35 // . . . 1.36 // }; 1.37 1.38 template<class T> 1.39 struct ListNode 1.40 { 1.41 union { 1.42 T* pPrev; 1.43 void* pVoidPrev; 1.44 }; 1.45 union { 1.46 T* pNext; 1.47 void* pVoidNext; 1.48 }; 1.49 1.50 void RemoveNode() 1.51 { 1.52 pPrev->pNext = pNext; 1.53 pNext->pPrev = pPrev; 1.54 } 1.55 1.56 // Removes us from the list and inserts pnew there instead. 1.57 void ReplaceNodeWith(T* pnew) 1.58 { 1.59 pPrev->pNext = pnew; 1.60 pNext->pPrev = pnew; 1.61 pnew->pPrev = pPrev; 1.62 pnew->pNext = pNext; 1.63 } 1.64 1.65 // Inserts the argument linked list node after us in the list. 1.66 void InsertNodeAfter(T* p) 1.67 { 1.68 p->pPrev = pNext->pPrev; // this 1.69 p->pNext = pNext; 1.70 pNext->pPrev = p; 1.71 pNext = p; 1.72 } 1.73 // Inserts the argument linked list node before us in the list. 1.74 void InsertNodeBefore(T* p) 1.75 { 1.76 p->pNext = pNext->pPrev; // this 1.77 p->pPrev = pPrev; 1.78 pPrev->pNext = p; 1.79 pPrev = p; 1.80 } 1.81 1.82 void Alloc_MoveTo(ListNode<T>* pdest) 1.83 { 1.84 pdest->pNext = pNext; 1.85 pdest->pPrev = pPrev; 1.86 pPrev->pNext = (T*)pdest; 1.87 pNext->pPrev = (T*)pdest; 1.88 } 1.89 }; 1.90 1.91 1.92 //------------------------------------------------------------------------ 1.93 // ***** List 1.94 // 1.95 // Doubly linked intrusive list. 1.96 // The data type must be derived from ListNode. 1.97 // 1.98 // Adding: PushFront(), PushBack(). 1.99 // Removing: Remove() - the element must be in the list! 1.100 // Moving: BringToFront(), SendToBack() - the element must be in the list! 1.101 // 1.102 // Iterating: 1.103 // MyData* data = MyList.GetFirst(); 1.104 // while (!MyList.IsNull(data)) 1.105 // { 1.106 // . . . 1.107 // data = MyList.GetNext(data); 1.108 // } 1.109 // 1.110 // Removing: 1.111 // MyData* data = MyList.GetFirst(); 1.112 // while (!MyList.IsNull(data)) 1.113 // { 1.114 // MyData* next = MyList.GetNext(data); 1.115 // if (ToBeRemoved(data)) 1.116 // MyList.Remove(data); 1.117 // data = next; 1.118 // } 1.119 // 1.120 1.121 // List<> represents a doubly-linked list of T, where each T must derive 1.122 // from ListNode<B>. B specifies the base class that was directly 1.123 // derived from ListNode, and is only necessary if there is an intermediate 1.124 // inheritance chain. 1.125 1.126 template<class T, class B = T> class List 1.127 { 1.128 public: 1.129 typedef T ValueType; 1.130 1.131 List() 1.132 { 1.133 Root.pNext = Root.pPrev = (ValueType*)&Root; 1.134 } 1.135 1.136 void Clear() 1.137 { 1.138 Root.pNext = Root.pPrev = (ValueType*)&Root; 1.139 } 1.140 1.141 const ValueType* GetFirst() const { return (const ValueType*)Root.pNext; } 1.142 const ValueType* GetLast () const { return (const ValueType*)Root.pPrev; } 1.143 ValueType* GetFirst() { return (ValueType*)Root.pNext; } 1.144 ValueType* GetLast () { return (ValueType*)Root.pPrev; } 1.145 1.146 // Determine if list is empty (i.e.) points to itself. 1.147 // Go through void* access to avoid issues with strict-aliasing optimizing out the 1.148 // access after RemoveNode(), etc. 1.149 bool IsEmpty() const { return Root.pVoidNext == (const T*)(const B*)&Root; } 1.150 bool IsFirst(const ValueType* p) const { return p == Root.pNext; } 1.151 bool IsLast (const ValueType* p) const { return p == Root.pPrev; } 1.152 bool IsNull (const ValueType* p) const { return p == (const T*)(const B*)&Root; } 1.153 1.154 inline static const ValueType* GetPrev(const ValueType* p) { return (const ValueType*)p->pPrev; } 1.155 inline static const ValueType* GetNext(const ValueType* p) { return (const ValueType*)p->pNext; } 1.156 inline static ValueType* GetPrev( ValueType* p) { return (ValueType*)p->pPrev; } 1.157 inline static ValueType* GetNext( ValueType* p) { return (ValueType*)p->pNext; } 1.158 1.159 void PushFront(ValueType* p) 1.160 { 1.161 p->pNext = Root.pNext; 1.162 p->pPrev = (ValueType*)&Root; 1.163 Root.pNext->pPrev = p; 1.164 Root.pNext = p; 1.165 } 1.166 1.167 void PushBack(ValueType* p) 1.168 { 1.169 p->pPrev = Root.pPrev; 1.170 p->pNext = (ValueType*)&Root; 1.171 Root.pPrev->pNext = p; 1.172 Root.pPrev = p; 1.173 } 1.174 1.175 static void Remove(ValueType* p) 1.176 { 1.177 p->pPrev->pNext = p->pNext; 1.178 p->pNext->pPrev = p->pPrev; 1.179 } 1.180 1.181 void BringToFront(ValueType* p) 1.182 { 1.183 Remove(p); 1.184 PushFront(p); 1.185 } 1.186 1.187 void SendToBack(ValueType* p) 1.188 { 1.189 Remove(p); 1.190 PushBack(p); 1.191 } 1.192 1.193 // Appends the contents of the argument list to the front of this list; 1.194 // items are removed from the argument list. 1.195 void PushListToFront(List<T>& src) 1.196 { 1.197 if (!src.IsEmpty()) 1.198 { 1.199 ValueType* pfirst = src.GetFirst(); 1.200 ValueType* plast = src.GetLast(); 1.201 src.Clear(); 1.202 plast->pNext = Root.pNext; 1.203 pfirst->pPrev = (ValueType*)&Root; 1.204 Root.pNext->pPrev = plast; 1.205 Root.pNext = pfirst; 1.206 } 1.207 } 1.208 1.209 void PushListToBack(List<T>& src) 1.210 { 1.211 if (!src.IsEmpty()) 1.212 { 1.213 ValueType* pfirst = src.GetFirst(); 1.214 ValueType* plast = src.GetLast(); 1.215 src.Clear(); 1.216 plast->pNext = (ValueType*)&Root; 1.217 pfirst->pPrev = Root.pPrev; 1.218 Root.pPrev->pNext = pfirst; 1.219 Root.pPrev = plast; 1.220 } 1.221 } 1.222 1.223 // Removes all source list items after (and including) the 'pfirst' node from the 1.224 // source list and adds them to out list. 1.225 void PushFollowingListItemsToFront(List<T>& src, ValueType *pfirst) 1.226 { 1.227 if (pfirst != &src.Root) 1.228 { 1.229 ValueType *plast = src.Root.pPrev; 1.230 1.231 // Remove list remainder from source. 1.232 pfirst->pPrev->pNext = (ValueType*)&src.Root; 1.233 src.Root.pPrev = pfirst->pPrev; 1.234 // Add the rest of the items to list. 1.235 plast->pNext = Root.pNext; 1.236 pfirst->pPrev = (ValueType*)&Root; 1.237 Root.pNext->pPrev = plast; 1.238 Root.pNext = pfirst; 1.239 } 1.240 } 1.241 1.242 // Removes all source list items up to but NOT including the 'pend' node from the 1.243 // source list and adds them to out list. 1.244 void PushPrecedingListItemsToFront(List<T>& src, ValueType *ptail) 1.245 { 1.246 if (src.GetFirst() != ptail) 1.247 { 1.248 ValueType *pfirst = src.Root.pNext; 1.249 ValueType *plast = ptail->pPrev; 1.250 1.251 // Remove list remainder from source. 1.252 ptail->pPrev = (ValueType*)&src.Root; 1.253 src.Root.pNext = ptail; 1.254 1.255 // Add the rest of the items to list. 1.256 plast->pNext = Root.pNext; 1.257 pfirst->pPrev = (ValueType*)&Root; 1.258 Root.pNext->pPrev = plast; 1.259 Root.pNext = pfirst; 1.260 } 1.261 } 1.262 1.263 1.264 // Removes a range of source list items starting at 'pfirst' and up to, but not including 'pend', 1.265 // and adds them to out list. Note that source items MUST already be in the list. 1.266 void PushListItemsToFront(ValueType *pfirst, ValueType *pend) 1.267 { 1.268 if (pfirst != pend) 1.269 { 1.270 ValueType *plast = pend->pPrev; 1.271 1.272 // Remove list remainder from source. 1.273 pfirst->pPrev->pNext = pend; 1.274 pend->pPrev = pfirst->pPrev; 1.275 // Add the rest of the items to list. 1.276 plast->pNext = Root.pNext; 1.277 pfirst->pPrev = (ValueType*)&Root; 1.278 Root.pNext->pPrev = plast; 1.279 Root.pNext = pfirst; 1.280 } 1.281 } 1.282 1.283 1.284 void Alloc_MoveTo(List<T>* pdest) 1.285 { 1.286 if (IsEmpty()) 1.287 pdest->Clear(); 1.288 else 1.289 { 1.290 pdest->Root.pNext = Root.pNext; 1.291 pdest->Root.pPrev = Root.pPrev; 1.292 1.293 Root.pNext->pPrev = (ValueType*)&pdest->Root; 1.294 Root.pPrev->pNext = (ValueType*)&pdest->Root; 1.295 } 1.296 } 1.297 1.298 1.299 private: 1.300 // Copying is prohibited 1.301 List(const List<T>&); 1.302 const List<T>& operator = (const List<T>&); 1.303 1.304 ListNode<B> Root; 1.305 }; 1.306 1.307 1.308 //------------------------------------------------------------------------ 1.309 // ***** FreeListElements 1.310 // 1.311 // Remove all elements in the list and free them in the allocator 1.312 1.313 template<class List, class Allocator> 1.314 void FreeListElements(List& list, Allocator& allocator) 1.315 { 1.316 typename List::ValueType* self = list.GetFirst(); 1.317 while(!list.IsNull(self)) 1.318 { 1.319 typename List::ValueType* next = list.GetNext(self); 1.320 allocator.Free(self); 1.321 self = next; 1.322 } 1.323 list.Clear(); 1.324 } 1.325 1.326 } // OVR 1.327 1.328 #endif 1.329 \ No newline at end of file