nlib
Nqueue.h
[詳解]
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_NQUEUE_H_
4 #define INCLUDE_NN_NLIB_NQUEUE_H_
5 
6 #include <memory>
7 #include "nn/nlib/Swap.h"
8 #include "nn/nlib/Nlist.h"
9 #include "nn/nlib/TypeTraits.h"
10 
11 NLIB_NAMESPACE_BEGIN
12 
13 extern void* nqueue_enabler;
14 
15 template <class T, class AL = std::allocator<char> >
16 class Nqueue {
17  public:
18  Nqueue() NLIB_NOEXCEPT : m_Beg1(0), m_End1(0), m_Beg2(0), m_End2(0) {}
20  NLIB_MOVE_MEMBER_HELPER_5(Nqueue, m_Beg1, m_End1, m_Beg2, m_End2, m_List)
21  size_t size() const NLIB_NOEXCEPT { return (m_End1 - m_Beg1) + (m_End2 - m_Beg2); }
22  size_t capacity() const NLIB_NOEXCEPT { return m_List.capacity(); }
23  bool empty() const NLIB_NOEXCEPT { return m_End1 - m_Beg1 == 0 && m_End2 - m_Beg2 == 0; }
24  T* push_back() NLIB_NOEXCEPT;
25 #ifdef NLIB_CXX11_RVALUE_REFERENCES
26  T* push_back(T&& rhs) NLIB_NOEXCEPT;
27 #endif
28  bool pop_front() NLIB_NOEXCEPT {
29  T tmp;
30  return this->pop_front_swap(&tmp);
31  }
32  bool push_back_swap(T* v) NLIB_NOEXCEPT {
33  T* tmp = this->push_back();
34  if (!tmp || !v) return false;
35  using std::swap;
36  swap(*tmp, *v);
37  return true;
38  }
39  bool pop_front_swap(T* v) NLIB_NOEXCEPT;
40  void swap(Nqueue& rhs) NLIB_NOEXCEPT { // NOLINT
41  using std::swap;
42  swap(m_Beg1, rhs.m_Beg1);
43  swap(m_End1, rhs.m_End1);
44  swap(m_Beg2, rhs.m_Beg2);
45  swap(m_End2, rhs.m_End2);
46  swap(m_List, rhs.m_List);
47  }
48 
49  private:
50  uint32_t m_Beg1;
51  uint32_t m_End1;
52  uint32_t m_Beg2;
53  uint32_t m_End2;
54  Nlist<T, AL> m_List;
56 };
57 
58 template <class T, class AL>
60  if (m_End1 != m_Beg2 && m_Beg2 != m_End2) {
61  using std::swap;
62  swap(m_List[m_End1++], m_List[m_Beg2++]);
63  if (m_Beg2 != m_End2) {
64  swap(m_List[m_End1++], m_List[m_Beg2++]);
65  }
66  if (m_Beg2 == m_End2) {
67  m_Beg2 = m_Beg1;
68  m_End2 = m_End1;
69  m_Beg1 = m_End1 = 0;
70  }
71  }
72  if (m_List.size() == m_End2) {
73  T* tmp = m_List.push_back();
74  if (tmp) ++m_End2;
75  return tmp;
76  } else {
77  return &m_List[m_End2++];
78  }
79 }
80 
81 #ifdef NLIB_CXX11_RVALUE_REFERENCES
82 template <class T, class AL>
84  if (m_End1 != m_Beg2 && m_Beg2 != m_End2) {
85  using std::swap;
86  swap(m_List[m_End1++], m_List[m_Beg2++]);
87  if (m_Beg2 != m_End2) {
88  swap(m_List[m_End1++], m_List[m_Beg2++]);
89  }
90  if (m_Beg2 == m_End2) {
91  m_Beg2 = m_Beg1;
92  m_End2 = m_End1;
93  m_Beg1 = m_End1 = 0;
94  }
95  }
96  if (m_List.size() == m_End2) {
97 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
98  NLIB_STATIC_ASSERT(std::is_nothrow_move_constructible<T>::value);
99 #endif
100  T* tmp = m_List.push_back(std::move(rhs));
101  if (tmp) ++m_End2;
102  return tmp;
103  } else {
104 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
105  NLIB_STATIC_ASSERT(std::is_nothrow_move_assignable<T>::value);
106 #endif
107  m_List[m_End2] = std::move(rhs);
108  return &m_List[m_End2++];
109  }
110 }
111 #endif
112 
113 template <class T, class AL>
114 bool Nqueue<T, AL>::pop_front_swap(T* v) NLIB_NOEXCEPT {
115  if (!v) return false;
116  using std::swap;
117  if (m_Beg1 != m_End1) {
118  swap(*v, m_List[m_Beg1++]);
119  if (m_Beg1 == m_End1) {
120  m_Beg1 = m_End1 = 0;
121  } else if ((m_End1 - m_Beg1) * 8 < m_End1) {
122  uint32_t cnt = static_cast<uint32_t>(m_End1 - m_Beg1);
123  for (uint32_t i = 0; i < cnt; ++i) {
124  swap(m_List[i], m_List[m_Beg1 + i]);
125  }
126  m_Beg1 = 0;
127  m_End1 = cnt;
128  }
129  } else if (m_Beg2 != m_End2) {
130  NLIB_ASSERT(m_Beg1 + m_End1 == 0);
131  swap(*v, m_List[m_Beg2++]);
132  if (m_Beg2 == m_End2) m_Beg2 = m_End2 = 0;
133  } else {
134  return false;
135  }
136  return true;
137 }
138 
139 NLIB_NAMESPACE_END
140 
141 #ifndef NLIB_STD_SWAP_WORKAROUND
142 NLIB_NAMESPACE_BEGIN
143 #else
144 NLIB_DEFINE_STD_SWAP_T_BEGIN1(std) // NOLINT
145 #endif
146 
147 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::Nqueue) // NOLINT
148 
149 #ifndef NLIB_STD_SWAP_WORKAROUND
150 NLIB_NAMESPACE_END
151 #else
152 NLIB_DEFINE_STD_SWAP_T_END1(std) // NOLINT
153 #endif
154 
155 #endif // INCLUDE_NN_NLIB_NQUEUE_H_
~Nqueue() noexcept
デストラクタです。
Definition: Nqueue.h:19
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Platform.h:2151
bool push_back_swap(T *v) noexcept
キューに要素を追加してから、その要素とvをstd::swapによって交換します。
Definition: Nqueue.h:32
size_t capacity() const noexcept
アロケート済みの要素の個数を返します。
Definition: Nqueue.h:22
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:126
STL namespace.
std::queueに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nqueue.h:16
Nqueue() noexcept
デフォルトコンストラクタです。空のキューを作成します。
Definition: Nqueue.h:18
void swap(Nqueue &rhs) noexcept
コンテナをスワップします。
Definition: Nqueue.h:40
bool empty() const noexcept
コンテナが空かどうかを調べます。
Definition: Nqueue.h:23
std::vectorに似ていますが、コピーできないオブジェクトを格納可能なクラスが定義されています。 ...
bool pop_front() noexcept
先頭の要素をキューから取り出します。
Definition: Nqueue.h:28
std::vectorに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nlist.h:19
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:117