1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: fnd_Queue.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: 16743 $
14 *---------------------------------------------------------------------------*/
15
16 /*! @file
17 @brief キューを扱うクラステンプレートです。
18
19 */
20
21 #ifndef NN_FND_FND_QUEUE_
22 #define NN_FND_FND_QUEUE_
23
24 #ifdef __cplusplus
25
26 #include <nn/util/util_NonCopyable.h>
27
28 namespace nn { namespace fnd {
29
30 /*!
31 @brief キューのためのクラステンプレートです。
32 */
33 template <typename T, typename Tag = void>
34 class IntrusiveQueue : private nn::util::NonCopyable<IntrusiveQueue<T, Tag> >
35 {
36 public:
37
38 class Item; //!< ノードクラス
39
40 /*!
41 @brief コンストラクタです。
42 */
IntrusiveQueue()43 IntrusiveQueue() : m_Head(0), m_Tail(0) {}
44
45 /*!
46 @brief キューが空かどうかを取得します。
47
48 @return キューが空なら true を返します。そうでなければ false を返します。
49 */
IsEmpty()50 bool IsEmpty() const { return m_Head == 0; }
51
52 /*!
53 @brief キューの末尾に要素を追加します。
54
55 @param[in] p キューに追加する要素
56 */
57 void Enqueue(T* p);
58
59 /*!
60 @brief キューの先頭の要素を削除します。
61
62 取り出した後は先頭のノードを削除します。
63
64 @return キューから取り出した要素を返します。
65 */
66 T* Dequeue();
67
68 /*!
69 @brief キューから全要素を削除します。
70 */
71 void Clear();
72
73 private:
74
75 Item* m_Head; //!< キューの先頭のノード
76 Item* m_Tail; //!< キューの末尾のノード
77
78 };
79
80 /*!
81 :private
82
83 @brief キューのためのノードです。
84 */
85 template <typename T, typename Tag>
86 class IntrusiveQueue<T, Tag>::Item : private nn::util::NonCopyable<IntrusiveQueue<T, Tag>::Item>
87 {
88 friend class IntrusiveQueue;
89 protected:
Item()90 Item() : m_NextLink(0) {}
~Item()91 ~Item() { NN_TASSERT_(!m_NextLink); }
92 private:
93 Item* m_NextLink;
94 };
95
96 template <typename T, typename Tag>
Enqueue(T * p)97 inline void IntrusiveQueue<T, Tag>::Enqueue(T* p)
98 {
99 NN_TASSERT_(p);
100 Item* pNode = static_cast<Item*>(p);
101 NN_TASSERT_(!pNode->m_NextLink);
102 if (IsEmpty())
103 {
104 this->m_Head = this->m_Tail = pNode;
105 pNode->m_NextLink = pNode;
106 }
107 else
108 {
109 m_Tail->m_NextLink = p;
110 this->m_Tail = p;
111 }
112 }
113
114 template <typename T, typename Tag>
Dequeue()115 inline T* IntrusiveQueue<T, Tag>::Dequeue()
116 {
117 if (IsEmpty())
118 {
119 return 0;
120 }
121 else
122 {
123 Item* ret = m_Head;
124 if (m_Head == m_Tail)
125 {
126 this->m_Head = 0;
127 }
128 else
129 {
130 this->m_Head = m_Head->m_NextLink;
131 }
132 ret->m_NextLink = 0;
133 return static_cast<T*>(ret);
134 }
135 }
136
137 template <typename T, typename Tag>
Clear()138 inline void IntrusiveQueue<T, Tag>::Clear()
139 {
140 if (m_Head)
141 {
142 Item* p = m_Head;
143 do
144 {
145 Item* q = p;
146 p = p->m_NextLink;
147 q->m_NextLink = 0;
148 } while (p != m_Tail);
149 this->m_Head = 0;
150 }
151 }
152
153 }}
154
155 #endif // __cplusplus
156
157 #endif
158