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