1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: fnd_LinkedList.h
4 Copyright (C)2009 Nintendo Co., Ltd. All rights reserved.
5 These coded instructions, statements, and computer programs contain
6 proprietary information of Nintendo of America Inc. and/or Nintendo
7 Company Ltd., and are protected by Federal copyright law. They may
8 not be disclosed to third parties or copied or duplicated in any form,
9 in whole or in part, without the prior written consent of Nintendo.
10 $Rev: 21468 $
11 *---------------------------------------------------------------------------
12
13
14 */
15
16 /*---------------------------------------------------------------------------*
17 Project: NW4R - SystemLib - include - nw4r - ut
18 File: LinkedList.h
19 Copyright (C) 2005-2008 Nintendo. All rights reserved.
20 These coded instructions, statements, and computer programs contain
21 proprietary information of Nintendo of America Inc. and/or Nintendo
22 Company Ltd., and are protected by Federal copyright law. They may
23 not be disclosed to third parties or copied or duplicated in any form,
24 in whole or in part, without the prior written consent of Nintendo.
25 $Revision: 1.13 #$
26 *---------------------------------------------------------------------------
27
28
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); }
221 private:
222 Item* m_PreviousLink;
223 Item* m_NextLink;
224 };
225
226 template <typename T, typename Tag>
ClearLinks(Item * p)227 inline void IntrusiveLinkedList<T, Tag>::ClearLinks(Item* p)
228 {
229 p->m_PreviousLink = p->m_NextLink = 0;
230 }
231
232 template <typename T, typename Tag>
InsertBefore(Item * p,Item * q)233 inline void IntrusiveLinkedList<T, Tag>::InsertBefore(Item* p, Item* q)
234 {
235 q->m_NextLink = p;
236 p->m_PreviousLink->m_NextLink = q;
237 q->m_PreviousLink = p->m_PreviousLink;
238 p->m_PreviousLink = q;
239 }
240
241 template <typename T, typename Tag>
PushBack(T * p)242 inline void IntrusiveLinkedList<T, Tag>::PushBack(T* p)
243 {
244 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
245 NN_TASSERT_(p);
246 Item* pNode = static_cast<Item*>(p);
247 NN_ASSERT_WITH_RESULT(!pNode->m_PreviousLink, MakeResultAlreadyListed());
248 NN_TASSERT_(!pNode->m_PreviousLink);
249 NN_TASSERT_(!pNode->m_NextLink);
250 if (IsEmpty())
251 {
252 p->m_PreviousLink = p->m_NextLink = p;
253 this->m_Head = p;
254 }
255 else
256 {
257 InsertBefore(m_Head, pNode);
258 }
259 }
260
261 template <typename T, typename Tag>
PushFront(T * p)262 inline void IntrusiveLinkedList<T, Tag>::PushFront(T* p)
263 {
264 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
265 NN_TASSERT_(p);
266 Item* pNode = static_cast<Item*>(p);
267 NN_ASSERT_WITH_RESULT(!pNode->m_PreviousLink, MakeResultAlreadyListed());
268 NN_TASSERT_(!pNode->m_PreviousLink);
269 NN_TASSERT_(!pNode->m_NextLink);
270 if (IsEmpty())
271 {
272 p->m_PreviousLink = p->m_NextLink = p;
273 }
274 else
275 {
276 InsertBefore(m_Head, pNode);
277 }
278 this->m_Head = p;
279 }
280
281 template <typename T, typename Tag>
GetFront()282 inline T* IntrusiveLinkedList<T, Tag>::GetFront() const
283 {
284 return static_cast<T*>(m_Head);
285 }
286
287 template <typename T, typename Tag>
GetBack()288 inline T* IntrusiveLinkedList<T, Tag>::GetBack() const
289 {
290 if (IsEmpty())
291 {
292 return 0;
293 }
294 else
295 {
296 return static_cast<T*>(m_Head->m_PreviousLink);
297 }
298 }
299
300 template <typename T, typename Tag>
PopFront()301 inline T* IntrusiveLinkedList<T, Tag>::PopFront()
302 {
303 if (T* ret = GetFront())
304 {
305 this->Erase(ret);
306 return ret;
307 }
308 else
309 {
310 return 0;
311 }
312 }
313
314 template <typename T, typename Tag>
PopBack()315 inline T* IntrusiveLinkedList<T, Tag>::PopBack()
316 {
317 if (T* ret = GetBack())
318 {
319 this->Erase(ret);
320 return ret;
321 }
322 else
323 {
324 return 0;
325 }
326 }
327
328 template <typename T, typename Tag>
GetPrevious(T * p)329 inline T* IntrusiveLinkedList<T, Tag>::GetPrevious(T* p) const
330 {
331 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
332 NN_TASSERT_(p);
333 Item* pNode = static_cast<Item*>(p);
334 NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
335 NN_TASSERT_(pNode->m_PreviousLink);
336 NN_TASSERT_(pNode->m_NextLink);
337 if (p == this->GetFront())
338 {
339 return 0;
340 }
341 return static_cast<T*>(pNode->m_PreviousLink);
342 }
343
344 template <typename T, typename Tag>
GetNext(T * p)345 inline T* IntrusiveLinkedList<T, Tag>::GetNext(T* p) const
346 {
347 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
348 NN_TASSERT_(p);
349 Item* pNode = static_cast<Item*>(p);
350 NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
351 NN_TASSERT_(pNode->m_PreviousLink);
352 NN_TASSERT_(pNode->m_NextLink);
353 if (p == this->GetBack())
354 {
355 return 0;
356 }
357 return static_cast<T*>(pNode->m_NextLink);
358 }
359
360 template <typename T, typename Tag>
Insert(T * position,T * inserted)361 inline void IntrusiveLinkedList<T, Tag>::Insert(T* position, T* inserted)
362 {
363 NN_ASSERT_WITH_RESULT(inserted, MakeResultInvalidAddress());
364 NN_TASSERT_(inserted);
365 Item* pNodeInserted = static_cast<Item*>(inserted);
366 Item* pNodePosition = static_cast<Item*>(position);
367 NN_ASSERT_WITH_RESULT(!pNodeInserted->m_PreviousLink, MakeResultAlreadyListed());
368 NN_TASSERT_(!pNodeInserted->m_PreviousLink);
369 NN_TASSERT_(!pNodeInserted->m_NextLink);
370 if (pNodePosition == m_Head)
371 {
372 PushFront(inserted);
373 }
374 else if (pNodePosition)
375 {
376 NN_ASSERT_WITH_RESULT(pNodePosition->m_PreviousLink, MakeResultInvalidNode());
377 NN_TASSERT_(pNodePosition->m_PreviousLink);
378 NN_TASSERT_(pNodePosition->m_NextLink);
379 InsertBefore(pNodePosition, pNodeInserted);
380 }
381 else
382 {
383 PushBack(inserted);
384 }
385 }
386
387 template <typename T, typename Tag>
Erase(T * p)388 inline void IntrusiveLinkedList<T, Tag>::Erase(T* p)
389 {
390 NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
391 NN_TASSERT_(p);
392 Item* pNode = static_cast<Item*>(p);
393 NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
394 NN_TASSERT_(pNode->m_PreviousLink);
395 NN_TASSERT_(pNode->m_NextLink);
396 if (pNode == pNode->m_PreviousLink)
397 {
398 this->m_Head = 0;
399 }
400 else
401 {
402 if (m_Head == pNode)
403 {
404 this->m_Head = m_Head->m_NextLink;
405 }
406 pNode->m_NextLink->m_PreviousLink = pNode->m_PreviousLink;
407 pNode->m_PreviousLink->m_NextLink = pNode->m_NextLink;
408 }
409 ClearLinks(pNode);
410 }
411
412 template <typename T, typename Tag>
Clear()413 inline void IntrusiveLinkedList<T, Tag>::Clear()
414 {
415 if (m_Head)
416 {
417 Item* p = m_Head;
418 while (p)
419 {
420 Item* q = p;
421 p = p->m_NextLink;
422 ClearLinks(q);
423 }
424 this->m_Head = 0;
425 }
426 }
427
428 } // namespace util
429 } // namespace nn
430
431 #endif // __cplusplus
432
433 #endif /* NN_UTIL_LINKEDLIST_H_ */
434