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