1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: fnd_LinkedList.h
4
5 Copyright (C)2009-2012 Nintendo Co., Ltd. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Rev: 47266 $
14 *---------------------------------------------------------------------------*/
15
16 /*---------------------------------------------------------------------------*
17 Project: NW4R - SystemLib - include - nw4r - ut
18 File: LinkedList.h
19
20 Copyright (C)2005-2008 Nintendo All rights reserved.
21
22 These coded instructions, statements, and computer programs contain
23 proprietary information of Nintendo of America Inc. and/or Nintendo
24 Company Ltd., and are protected by Federal copyright law. They may
25 not be disclosed to third parties or copied or duplicated in any form,
26 in whole or in part, without the prior written consent of Nintendo.
27
28 $Revision: 1.13 #$
29 *---------------------------------------------------------------------------*/
30
31 /*
32
33
34 */
35
36 #ifndef NN_FND_FND_LINKEDLIST_H_
37 #define NN_FND_FND_LINKEDLIST_H_
38
39 #ifdef __cplusplus
40
41 #include <nn/assert.h>
42 #include <nn/util/util_NonCopyable.h>
43 #include <nn/fnd/fnd_Result.h>
44
45 namespace nn { namespace fnd {
46
47 // Usage examples
48 //
49 // class Hoge : public IntrusiveLinkedList<Hoge>::Item { ... };
50 // tyepdef IntrusiveLinkedList<Hoge> HogeList;
51 //
52 // Hoge a, b, c;
53 // {
54 // HogeList list;
55 // list.PushFront(&a);
56 // list.PushBack(&b);
57 // list.PushFront(&a); // PANIC: Item cannot be inserted in list twice
58 // if (Hoge* p = list.PopBack())
59 // {
60 // // Processing using *p
61 // }
62 // list.Erase(&a); // Specify the element and delete
63 // list.Clear();
64 // } // Automatic Clear() using destructor
65
66 // TODO: Untested
67 // NEED_DOCUMENT
68 // NEED_TEST
69
70 /*
71
72 */
73 template <typename T, typename Tag = void>
74 class IntrusiveLinkedList : private nn::util::NonCopyable<IntrusiveLinkedList<T, Tag> >
75 {
76 public:
77
78 class Item; //
79
80 /*
81
82 */
IntrusiveLinkedList()83 IntrusiveLinkedList() : m_Head(0) {}
84
85 /*
86
87 */
~IntrusiveLinkedList()88 ~IntrusiveLinkedList() { Clear(); }
89
90 /*
91
92
93
94 */
IsEmpty()95 bool IsEmpty() const { return !m_Head; }
96
97 /*
98
99
100
101 */
102 void PushBack(T* p);
103
104 /*
105
106
107
108 */
109 void PushFront(T* p);
110
111 /*
112
113
114
115 */
116 T* GetFront() const;
117
118 /*
119
120
121
122 */
123 T* GetBack() const;
124
125 /*
126
127
128
129
130
131 */
132 T* PopFront();
133
134 /*
135
136
137
138
139
140 */
141 T* PopBack();
142
143 /*
144
145
146
147
148
149 */
150 T* GetNext(T* p) const;
151
152 /*
153
154
155
156
157
158 */
159 T* GetPrevious(T* p) const;
160
161 /*
162
163
164
165
166
167
168 */
169 void Insert(T* position, T* inserted);
170
171 /*
172
173
174
175 */
176 void Erase(T* p);
177
178 /*
179
180 */
181 void Clear();
182
183 private:
184
185 Item* m_Head; //
186
187 /*
188 :private
189
190
191
192
193 */
194 static void ClearLinks(Item* p);
195
196 /*
197 :private
198
199
200 */
201 static void InsertBefore(Item* p, Item* q);
202
203 };
204
205 // NEED_DOCUMENT
206 // NEED_TEST
207 /*
208 :private
209
210
211 */
212 template <typename T, typename Tag>
213 class IntrusiveLinkedList<T, Tag>::Item : private nn::util::NonCopyable<IntrusiveLinkedList<T, Tag>::Item>
214 {
215 friend class IntrusiveLinkedList;
216 protected:
Item()217 Item() : m_PreviousLink(0), m_NextLink(0) {}
~Item()218 ~Item() { NN_TASSERT_(!m_PreviousLink && !m_NextLink); }
GetPrevious()219 T* GetPrevious() const { return static_cast<T*>(m_PreviousLink); }
GetNext()220 T* GetNext() const { return static_cast<T*>(m_NextLink); }
IsChained()221 bool IsChained() const { return m_PreviousLink != NULL; }
222 private:
223 Item* m_PreviousLink;
224 Item* m_NextLink;
225 };
226
227 template <typename T, typename Tag>
ClearLinks(Item * p)228 inline void IntrusiveLinkedList<T, Tag>::ClearLinks(Item* p)
229 {
230 p->m_PreviousLink = p->m_NextLink = 0;
231 }
232
233 template <typename T, typename Tag>
InsertBefore(Item * p,Item * q)234 inline void IntrusiveLinkedList<T, Tag>::InsertBefore(Item* p, Item* q)
235 {
236 q->m_NextLink = p;
237 p->m_PreviousLink->m_NextLink = q;
238 q->m_PreviousLink = p->m_PreviousLink;
239 p->m_PreviousLink = q;
240 }
241
242 template <typename T, typename Tag>
PushBack(T * p)243 inline void IntrusiveLinkedList<T, Tag>::PushBack(T* p)
244 {
245 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
246 NN_TASSERT_(p);
247 Item* pNode = static_cast<Item*>(p);
248 NN_ASSERT_WITH_RESULT(!pNode->m_PreviousLink, MakeResultAlreadyListed());
249 NN_TASSERT_(!pNode->m_PreviousLink);
250 NN_TASSERT_(!pNode->m_NextLink);
251 if (IsEmpty())
252 {
253 p->m_PreviousLink = p->m_NextLink = p;
254 this->m_Head = p;
255 }
256 else
257 {
258 InsertBefore(m_Head, pNode);
259 }
260 }
261
262 template <typename T, typename Tag>
PushFront(T * p)263 inline void IntrusiveLinkedList<T, Tag>::PushFront(T* p)
264 {
265 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
266 NN_TASSERT_(p);
267 Item* pNode = static_cast<Item*>(p);
268 NN_ASSERT_WITH_RESULT(!pNode->m_PreviousLink, MakeResultAlreadyListed());
269 NN_TASSERT_(!pNode->m_PreviousLink);
270 NN_TASSERT_(!pNode->m_NextLink);
271 if (IsEmpty())
272 {
273 p->m_PreviousLink = p->m_NextLink = p;
274 }
275 else
276 {
277 InsertBefore(m_Head, pNode);
278 }
279 this->m_Head = p;
280 }
281
282 template <typename T, typename Tag>
GetFront()283 inline T* IntrusiveLinkedList<T, Tag>::GetFront() const
284 {
285 return static_cast<T*>(m_Head);
286 }
287
288 template <typename T, typename Tag>
GetBack()289 inline T* IntrusiveLinkedList<T, Tag>::GetBack() const
290 {
291 if (IsEmpty())
292 {
293 return 0;
294 }
295 else
296 {
297 return static_cast<T*>(m_Head->m_PreviousLink);
298 }
299 }
300
301 template <typename T, typename Tag>
PopFront()302 inline T* IntrusiveLinkedList<T, Tag>::PopFront()
303 {
304 if (T* ret = GetFront())
305 {
306 this->Erase(ret);
307 return ret;
308 }
309 else
310 {
311 return 0;
312 }
313 }
314
315 template <typename T, typename Tag>
PopBack()316 inline T* IntrusiveLinkedList<T, Tag>::PopBack()
317 {
318 if (T* ret = GetBack())
319 {
320 this->Erase(ret);
321 return ret;
322 }
323 else
324 {
325 return 0;
326 }
327 }
328
329 template <typename T, typename Tag>
GetPrevious(T * p)330 inline T* IntrusiveLinkedList<T, Tag>::GetPrevious(T* p) const
331 {
332 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
333 NN_TASSERT_(p);
334 Item* pNode = static_cast<Item*>(p);
335 NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
336 NN_TASSERT_(pNode->m_PreviousLink);
337 NN_TASSERT_(pNode->m_NextLink);
338 if (p == this->GetFront())
339 {
340 return 0;
341 }
342 return static_cast<T*>(pNode->m_PreviousLink);
343 }
344
345 template <typename T, typename Tag>
GetNext(T * p)346 inline T* IntrusiveLinkedList<T, Tag>::GetNext(T* p) const
347 {
348 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
349 NN_TASSERT_(p);
350 Item* pNode = static_cast<Item*>(p);
351 NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
352 NN_TASSERT_(pNode->m_PreviousLink);
353 NN_TASSERT_(pNode->m_NextLink);
354 if (p == this->GetBack())
355 {
356 return 0;
357 }
358 return static_cast<T*>(pNode->m_NextLink);
359 }
360
361 template <typename T, typename Tag>
Insert(T * position,T * inserted)362 inline void IntrusiveLinkedList<T, Tag>::Insert(T* position, T* inserted)
363 {
364 NN_ASSERT_WITH_RESULT(inserted, MakeResultInvalidAddress());
365 NN_TASSERT_(inserted);
366 Item* pNodeInserted = static_cast<Item*>(inserted);
367 Item* pNodePosition = static_cast<Item*>(position);
368 NN_ASSERT_WITH_RESULT(!pNodeInserted->m_PreviousLink, MakeResultAlreadyListed());
369 NN_TASSERT_(!pNodeInserted->m_PreviousLink);
370 NN_TASSERT_(!pNodeInserted->m_NextLink);
371 if (pNodePosition == m_Head)
372 {
373 PushFront(inserted);
374 }
375 else if (pNodePosition)
376 {
377 NN_ASSERT_WITH_RESULT(pNodePosition->m_PreviousLink, MakeResultInvalidNode());
378 NN_TASSERT_(pNodePosition->m_PreviousLink);
379 NN_TASSERT_(pNodePosition->m_NextLink);
380 InsertBefore(pNodePosition, pNodeInserted);
381 }
382 else
383 {
384 PushBack(inserted);
385 }
386 }
387
388 template <typename T, typename Tag>
Erase(T * p)389 inline void IntrusiveLinkedList<T, Tag>::Erase(T* p)
390 {
391 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
392 NN_TASSERT_(p);
393 Item* pNode = static_cast<Item*>(p);
394 NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
395 NN_TASSERT_(pNode->m_PreviousLink);
396 NN_TASSERT_(pNode->m_NextLink);
397 if (pNode == pNode->m_PreviousLink)
398 {
399 this->m_Head = 0;
400 }
401 else
402 {
403 if (m_Head == pNode)
404 {
405 this->m_Head = m_Head->m_NextLink;
406 }
407 pNode->m_NextLink->m_PreviousLink = pNode->m_PreviousLink;
408 pNode->m_PreviousLink->m_NextLink = pNode->m_NextLink;
409 }
410 ClearLinks(pNode);
411 }
412
413 template <typename T, typename Tag>
Clear()414 inline void IntrusiveLinkedList<T, Tag>::Clear()
415 {
416 if (m_Head)
417 {
418 Item* p = m_Head;
419 while (p)
420 {
421 Item* q = p;
422 p = p->m_NextLink;
423 ClearLinks(q);
424 }
425 this->m_Head = 0;
426 }
427 }
428
429 } // namespace util
430 } // namespace nn
431
432 #endif // __cplusplus
433
434 #endif /* NN_UTIL_LINKEDLIST_H_ */
435