1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: fnd_LinkedList.h
4
5 Copyright (C)2009 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: 21468 $
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 /* @file
32 @brief 双方向リンクリストを扱うクラステンプレートです。
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 // 使用例
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: 二重にリストに入れることはできない。
58 // if (Hoge* p = list.PopBack())
59 // {
60 // // *p を使った処理
61 // }
62 // list.Erase(&a); // 要素を指定して削除
63 // list.Clear();
64 // } // デストラクタで自動 Clear()
65
66 // TODO: 未テスト
67 // NEED_DOCUMENT
68 // NEED_TEST
69
70 /*
71 @brief 双方向リンクリストのためのクラステンプレートです。
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 @brief コンストラクタです。
82 */
IntrusiveLinkedList()83 IntrusiveLinkedList() : m_Head(0) {}
84
85 /*
86 @brief デストラクタです。
87 */
~IntrusiveLinkedList()88 ~IntrusiveLinkedList() { Clear(); }
89
90 /*
91 @brief リストが空かどうかを取得します。
92
93 @return リストが空であれば true を返します。そうでなければ false を返します。
94 */
IsEmpty()95 bool IsEmpty() const { return !m_Head; }
96
97 /*
98 @brief リストの末尾に要素を追加します。
99
100 @param[in] p 追加する要素
101 */
102 void PushBack(T* p);
103
104 /*
105 @brief リストの先頭に要素を追加します。
106
107 @param[in] p 追加する要素
108 */
109 void PushFront(T* p);
110
111 /*
112 @brief リストの先頭の要素へのポインタを取得します。
113
114 @return 先頭の要素へのポインタを返します。
115 */
116 T* GetFront() const;
117
118 /*
119 @brief リストの末尾の要素へのポインタを取得します。
120
121 @return 末尾の要素へのポインタを返します。
122 */
123 T* GetBack() const;
124
125 /*
126 @brief リストの先頭の要素をリストから取り出します。
127
128 リストの先頭のノードを削除し、要素へのポインタを返します。
129
130 @return 先頭の要素へのポインタを返します。
131 */
132 T* PopFront();
133
134 /*
135 @brief リストの末尾の要素をリストから取り出します。
136
137 リストの末尾のノードを削除し、要素へのポインタを返します。
138
139 @return 末尾の要素へのポインタを返します。
140 */
141 T* PopBack();
142
143 /*
144 @brief 次の要素へのポインタを取得します。
145
146 @param[in] 基準となる要素の位置
147
148 @return 次の要素へのポインタを返します。
149 */
150 T* GetNext(T* p) const;
151
152 /*
153 @brief 前の要素へのポインタを取得します。
154
155 @param[in] 基準となる要素の位置
156
157 @return 前の要素へのポインタを返します。
158 */
159 T* GetPrevious(T* p) const;
160
161 /*
162 @brief 要素をリストに挿入します。
163
164 position で指定したノードの直前に inserted が挿入されます。
165
166 @param[in] position 基準となる要素の位置
167 @param[in] inserted 挿入する要素
168 */
169 void Insert(T* position, T* inserted);
170
171 /*
172 @brief 要素をリストから削除します。
173
174 @parma[in] p 削除する要素
175 */
176 void Erase(T* p);
177
178 /*
179 @brief リストから全要素を削除します。
180 */
181 void Clear();
182
183 private:
184
185 Item* m_Head; //!< 先頭のノード
186
187 /*
188 :private
189
190 @brief 指定したノードのリンクをクリアします。
191
192 @param[in] p リンクをクリアする対象のノード
193 */
194 static void ClearLinks(Item* p);
195
196 /*
197 :private
198
199 @brief ノード p の直前にノード p を挿入します。
200 */
201 static void InsertBefore(Item* p, Item* q);
202
203 };
204
205 // NEED_DOCUMENT
206 // NEED_TEST
207 /*
208 :private
209
210 @brief 双方向リンクリストのためのノードです。
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