1 /*---------------------------------------------------------------------------*
2   Project:  Horizon
3   File:     util_LockFreeQueueImpl.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: 12449 $
14  *---------------------------------------------------------------------------*/
15 
16 #ifndef NN_UTIL_ARMV6_UTIL_LOCKFREEQUEUEIMPL_H_
17 #define NN_UTIL_ARMV6_UTIL_LOCKFREEQUEUEIMPL_H_
18 
19 #include <nn/types.h>
20 #include <nn/assert.h>
21 #include <nn/util/util_Noncopyable.h>
22 #include <nn/util/util_StaticAssert.h>
23 
24 namespace nn { namespace util { namespace ARMv6 {
25 
26 namespace detail {
27 
28     class LockFreeQueueNodeBase;
29 
30     struct LockFreeQueuePointerData
31     {
32         LockFreeQueueNodeBase* pointer;
33         u32 tag;
34     };
35     struct LockFreeQueuePointer
36     {
37         union
38         {
39             bit64 buf;
40             LockFreeQueuePointerData data;
41         };
LockFreeQueuePointerLockFreeQueuePointer42         LockFreeQueuePointer() {}
LockFreeQueuePointerLockFreeQueuePointer43         LockFreeQueuePointer(const LockFreeQueuePointer& other) : buf(other.buf) {}
44         bool operator==(const LockFreeQueuePointer& other) { return buf == other.buf; }
45     };
46 
47     class LockFreeQueueNodeBase : private NonCopyable<LockFreeQueueNodeBase>
48     {
49         friend class LockFreeQueueImplBase;
50         template <typename> friend class LockFreeQueueImpl;
51     private:
52         typedef LockFreeQueuePointer Pointer;
53 
54         Pointer m_next;
55 
MarkAsNotInserted()56         void MarkAsNotInserted()
57         {
58 #ifdef NN_BUILD_NOOPT
59             m_next.buf = 0xffffffffffffffffULL;
60 #endif
61         }
62 
AssertNotInserted()63         void AssertNotInserted() const
64         {
65 #ifdef NN_BUILD_NOOPT
66             NN_TASSERT_(m_next.buf == 0xffffffffffffffffULL);
67 #endif
68         }
69 
70     protected:
Initialize()71         void Initialize()
72         {
73             MarkAsNotInserted();
74         }
75     };
76 
77     template <typename T>
78     class LockFreeQueueNode : private nn::util::NonCopyable<LockFreeQueueNode<T> >, private LockFreeQueueNodeBase
79     {
80         friend class LockFreeQueueImplBase;
81         template <typename> friend class LockFreeQueueImpl;
82     private:
83         typedef LockFreeQueueNodeBase Base;
84 
85         T m_x;
Initialize()86         void Initialize() { Base::Initialize(); }
87 
88     public:
LockFreeQueueNode()89         LockFreeQueueNode() { Initialize(); }
LockFreeQueueNode(const T & x)90         explicit LockFreeQueueNode(const T& x) : m_x(x) { Initialize(); }
91 
Value()92         T& Value() { return m_x; }
Value()93         const T& Value() const { return m_x; }
94     };
95 
96     class LockFreeQueueImplBase : private NonCopyable<LockFreeQueueImplBase>
97     {
98     protected:
99         typedef LockFreeQueuePointer Pointer;
100         typedef LockFreeQueueNodeBase NodeType;
101 
102         Pointer m_head, m_tail;
103 
LockFreeQueueImplBase(NodeType * emptyNode)104         LockFreeQueueImplBase(NodeType* emptyNode)
105         {
106             emptyNode->m_next.data.pointer = 0;
107             m_head.data.pointer = m_tail.data.pointer = emptyNode;
108         }
109 
IsEmpty()110         bool IsEmpty() const
111         {
112             return m_head.data.pointer == m_tail.data.pointer;
113         }
114 
115         void EnqueueImpl(NodeType* pNode);
116     };
117 
118     template <typename T>
119     class LockFreeQueueImpl : private NonCopyable<LockFreeQueueImpl<T> >, private LockFreeQueueImplBase
120     {
121     public:
122         typedef T ValueType;
123         typedef LockFreeQueueNode<T> NodeType;
124 
LockFreeQueueImpl(NodeType * nullNode)125         LockFreeQueueImpl(NodeType* nullNode) : LockFreeQueueImplBase(nullNode) {}
EnqueueImpl(NodeType * pNode)126         void EnqueueImpl(NodeType* pNode) { return LockFreeQueueImplBase::EnqueueImpl(pNode); }
127         NodeType* DequeueImpl(T* pDequeuedObject); // 返されたノードは、ユーザ側が適切に破棄などをする必要がある。このノードはpDequeuedObjectとは無関係
128         using LockFreeQueueImplBase::IsEmpty;
129     };
130 
131     bool CompareAndSwapQueuePointer(LockFreeQueuePointer* pTarget, const LockFreeQueuePointer& comp, LockFreeQueueNodeBase* swapNode, u32 swapTag);
132 
133     template <typename T>
DequeueImpl(T * pDequeuedObject)134     LockFreeQueueImpl<T>::NodeType* LockFreeQueueImpl<T>::DequeueImpl(T* pDequeuedObject)
135     {
136         while (true)
137         {
138             LockFreeQueuePointer head = this->m_head;
139             LockFreeQueuePointer tail = this->m_tail;
140             LockFreeQueuePointer next = head.data.pointer->m_next;
141             if (head == this->m_head)
142             {
143                 if (head.data.pointer == tail.data.pointer)
144                 {
145                     if (!next.data.pointer)
146                     {
147                         return 0;
148                     }
149                     else
150                     {
151                         CompareAndSwapQueuePointer(&(this->m_tail), tail, next.data.pointer, tail.data.tag + 1);
152                     }
153                 }
154                 else
155                 {
156                     T DequeuedObject = static_cast<LockFreeQueueNode<T>*>(next.data.pointer)->Value();
157                     if (CompareAndSwapQueuePointer(&(this->m_head), head, next.data.pointer, head.data.tag + 1))
158                     {
159                         *pDequeuedObject = DequeuedObject;
160                         LockFreeQueueNode<T>* ret = static_cast<LockFreeQueueNode<T>*>(head.data.pointer);
161                         ret->MarkAsNotInserted();
162                         return ret;
163                     }
164                 }
165             }
166         }
167     }
168 
169 }
170 
171 }}}
172 
173 #endif
174