1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4//-----------------------------------------------------------------------------
5// @File: slist.h
6//
7
8//
9// @commn: Bunch of utility classes
10//
11// HISTORY:
12// 02/03/98: created helper classes
13// SLink, link node for singly linked list, every class that is intrusively
14// linked should have a data member of this type
15// SList, template linked list class, contains only inline
16// methods for fast list operations, with proper type checking
17//
18// see below for futher info. on how to use these template classes
19//
20//-----------------------------------------------------------------------------
21
22//#ifndef _H_UTIL
23//#error I am a part of util.hpp Please don't include me alone !
24//#endif
25
26
27#ifndef _H_SLIST_
28#define _H_SLIST_
29
30//------------------------------------------------------------------
31// struct SLink, to use a singly linked list
32// have a data member m_Link of type SLink in your class
33// and instantiate the template SList class
34//--------------------------------------------------------------------
35
36struct SLink;
37typedef DPTR(struct SLink) PTR_SLink;
38
39struct SLink
40{
41 PTR_SLink m_pNext;
42 SLink()
43 {
44 LIMITED_METHOD_CONTRACT;
45
46 m_pNext = NULL;
47 }
48
49 void InsertAfter(SLink* pLinkToInsert)
50 {
51 LIMITED_METHOD_CONTRACT;
52 PRECONDITION_MSG(NULL == pLinkToInsert->m_pNext, "This method does not support inserting lists");
53
54 PTR_SLink pTemp = m_pNext;
55
56 m_pNext = PTR_SLink(pLinkToInsert);
57 pLinkToInsert->m_pNext = pTemp;
58 }
59
60 // find pLink within the list starting at pHead
61 // if found remove the link from the list and return the link
62 // otherwise return NULL
63 static SLink* FindAndRemove(SLink *pHead, SLink* pLink, SLink ** ppPrior)
64 {
65 LIMITED_METHOD_CONTRACT;
66
67 _ASSERTE(pHead != NULL);
68 _ASSERTE(pLink != NULL);
69
70 SLink* pFreeLink = NULL;
71 *ppPrior = NULL;
72
73 while (pHead->m_pNext != NULL)
74 {
75 if (pHead->m_pNext == pLink)
76 {
77 pFreeLink = pLink;
78 pHead->m_pNext = pLink->m_pNext;
79 *ppPrior = pHead;
80 break;
81 }
82 pHead = pHead->m_pNext;
83 }
84
85 return pFreeLink;
86 }
87};
88
89//------------------------------------------------------------------
90// class SList. Intrusive singly linked list.
91//
92// To use SList with the default instantiation, your class should
93// define a data member of type SLink and named 'm_Link'. To use a
94// different field name, you need to provide an explicit LinkPtr
95// template argument. For example:
96// 'SList<MyClass, false, MyClass*, &MyClass::m_FieldName>'
97//
98// SList has two different behaviours depending on boolean
99// fHead variable,
100//
101// if fHead is true, then the list allows only InsertHead operations
102// if fHead is false, then the list allows only InsertTail operations
103// the code is optimized to perform these operations
104// all methods are inline, and conditional compiled based on template
105// argument 'fHead'
106// so there is no actual code size increase
107//--------------------------------------------------------------
108template <class T, bool fHead = false, typename __PTR = T*, SLink T::*LinkPtr = &T::m_Link>
109class SList
110{
111public:
112 // typedef used by the Queue class below
113 typedef T ENTRY_TYPE;
114
115protected:
116
117 // used as sentinel
118 SLink m_link; // slink.m_pNext == Null
119 PTR_SLink m_pHead;
120 PTR_SLink m_pTail;
121
122 // get the list node within the object
123 static SLink* GetLink (T* pLink)
124 {
125 LIMITED_METHOD_DAC_CONTRACT;
126 return &(pLink->*LinkPtr);
127 }
128
129 // move to the beginning of the object given the pointer within the object
130 static T* GetObject (SLink* pLink)
131 {
132 LIMITED_METHOD_DAC_CONTRACT;
133 if (pLink == NULL)
134 {
135 return NULL;
136 }
137 else
138 {
139#if 1
140 // Newer compilers define offsetof to be __builtin_offsetof, which doesn't use the
141 // old-school memory model trick to determine offset.
142 const UINT_PTR offset = (((UINT_PTR)&(((T *)0x1000)->*LinkPtr))-0x1000);
143 return (T*)__PTR(dac_cast<TADDR>(pLink) - offset);
144#else
145 return (T*)__PTR(dac_cast<TADDR>(pLink) - offsetof(T, *LinkPtr));
146#endif
147 }
148 }
149
150public:
151
152 SList()
153 {
154 WRAPPER_NO_CONTRACT;
155#ifndef DACCESS_COMPILE
156 Init();
157#endif // !defined(DACCESS_COMPILE)
158 }
159
160 void Init()
161 {
162 LIMITED_METHOD_CONTRACT;
163 m_pHead = &m_link;
164 // NOTE :: fHead variable is template argument
165 // the following code is a compiled in, only if the fHead flag
166 // is set to false,
167 if (!fHead)
168 {
169 m_pTail = &m_link;
170 }
171 }
172
173 bool IsEmpty()
174 {
175 LIMITED_METHOD_CONTRACT;
176 return m_pHead->m_pNext == NULL;
177 }
178
179#ifndef DACCESS_COMPILE
180
181 void InsertTail(T *pObj)
182 {
183 LIMITED_METHOD_CONTRACT;
184 // NOTE : conditional compilation on fHead template variable
185 if (!fHead)
186 {
187 _ASSERTE(pObj != NULL);
188 SLink *pLink = GetLink(pObj);
189
190 m_pTail->m_pNext = pLink;
191 m_pTail = pLink;
192 }
193 else
194 {// you instantiated this class asking only for InsertHead operations
195 _ASSERTE(0);
196 }
197 }
198
199 void InsertHead(T *pObj)
200 {
201 LIMITED_METHOD_CONTRACT;
202 // NOTE : conditional compilation on fHead template variable
203 if (fHead)
204 {
205 _ASSERTE(pObj != NULL);
206 SLink *pLink = GetLink(pObj);
207
208 pLink->m_pNext = m_pHead->m_pNext;
209 m_pHead->m_pNext = pLink;
210 }
211 else
212 {// you instantiated this class asking only for InsertTail operations
213 _ASSERTE(0);
214 }
215 }
216
217 T* RemoveHead()
218 {
219 LIMITED_METHOD_CONTRACT;
220 SLink* pLink = m_pHead->m_pNext;
221 if (pLink != NULL)
222 {
223 m_pHead->m_pNext = pLink->m_pNext;
224 }
225 // conditionally compiled, if the instantiated class
226 // uses Insert Tail operations
227 if (!fHead)
228 {
229 if(m_pTail == pLink)
230 {
231 m_pTail = m_pHead;
232 }
233 }
234
235 return GetObject(pLink);
236 }
237
238#endif // !DACCESS_COMPILE
239
240 T* GetHead()
241 {
242 WRAPPER_NO_CONTRACT;
243 return GetObject(m_pHead->m_pNext);
244 }
245
246 T* GetTail()
247 {
248 WRAPPER_NO_CONTRACT;
249
250 // conditional compile
251 if (fHead)
252 { // you instantiated this class asking only for InsertHead operations
253 // you need to walk the list yourself to find the tail
254 _ASSERTE(0);
255 }
256 return (m_pHead != m_pTail) ? GetObject(m_pTail) : NULL;
257 }
258
259 static T *GetNext(T *pObj)
260 {
261 WRAPPER_NO_CONTRACT;
262
263 _ASSERTE(pObj != NULL);
264 return GetObject(GetLink(pObj)->m_pNext);
265 }
266
267 T* FindAndRemove(T *pObj)
268 {
269 WRAPPER_NO_CONTRACT;
270
271 _ASSERTE(pObj != NULL);
272
273 SLink *prior;
274 SLink *ret = SLink::FindAndRemove(m_pHead, GetLink(pObj), &prior);
275
276 if (ret == m_pTail)
277 m_pTail = prior;
278
279 return GetObject(ret);
280 }
281
282 class Iterator
283 {
284 friend class SList;
285
286 public:
287 Iterator & operator++()
288 { _ASSERTE(m_cur != NULL); m_cur = SList::GetNext(m_cur); return *this; }
289
290 Iterator operator++(int)
291 { Iterator it(m_cur); ++(*this); return it; }
292
293 bool operator==(Iterator const & other) const
294 {
295 return m_cur == other.m_cur ||
296 (m_cur != NULL && other.m_cur != NULL && *m_cur == *other.m_cur);
297 }
298
299 bool operator!=(Iterator const & other) const
300 { return !(*this == other); }
301
302 T & operator*()
303 { _ASSERTE(m_cur != NULL); return *m_cur; }
304
305 T * operator->() const
306 { return m_cur; }
307
308 private:
309 Iterator(SList * pList)
310 : m_cur(pList->GetHead())
311 { }
312
313 Iterator(T* pObj)
314 : m_cur(pObj)
315 { }
316
317 Iterator()
318 : m_cur(NULL)
319 { }
320
321 T* m_cur;
322 };
323
324 Iterator begin()
325 { return Iterator(GetHead()); }
326
327 Iterator end()
328 { return Iterator(); }
329};
330
331template <typename ElemT>
332struct SListElem
333{
334 SLink m_Link;
335 ElemT m_Value;
336
337 operator ElemT const &() const
338 { return m_Value; }
339
340 operator ElemT &()
341 { return m_Value; }
342
343 ElemT const & operator*() const
344 { return m_Value; }
345
346 ElemT & operator*()
347 { return m_Value; }
348
349 ElemT const & GetValue() const
350 { return m_Value; }
351
352 ElemT & GetValue()
353 { return m_Value; }
354
355 SListElem()
356 : m_Link()
357 , m_Value()
358 { }
359
360 template <typename T1>
361 SListElem(T1&& val)
362 : m_Link()
363 , m_Value(std::forward<T1>(val))
364 { }
365
366 template <typename T1, typename T2>
367 SListElem(T1&& val1, T2&& val2)
368 : m_Link()
369 , m_Value(std::forward<T1>(val1), std::forward<T2>(val2))
370 { }
371
372 template <typename T1, typename T2, typename T3>
373 SListElem(T1&& val1, T2&& val2, T3&& val3)
374 : m_Link()
375 , m_Value(std::forward<T1>(val1), std::forward<T2>(val2), std::forward<T3>(val3))
376 { }
377
378 template <typename T1, typename T2, typename T3, typename T4>
379 SListElem(T1&& val1, T2&& val2, T3&& val3, T4&& val4)
380 : m_Link()
381 , m_Value(std::forward<T1>(val1), std::forward<T2>(val2), std::forward<T3>(val3), std::forward<T4>(val4))
382 { }
383};
384
385#endif // _H_SLIST_
386
387// End of file: list.h
388