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 : beg1_(0), end1_(0), beg2_(0), end2_(0) {}
20  NLIB_MOVE_MEMBER_HELPER_5(Nqueue, beg1_, end1_, beg2_, end2_, list_)
21  size_t size() const NLIB_NOEXCEPT { return (end1_ - beg1_) + (end2_ - beg2_); }
22  size_t capacity() const NLIB_NOEXCEPT { return list_.capacity(); }
23  bool empty() const NLIB_NOEXCEPT { return end1_ - beg1_ == 0 && end2_ - beg2_ == 0; }
24  T* push_back() NLIB_NOEXCEPT;
25 #ifdef NLIB_CXX11_RVALUE_REFERENCES
26  T* push_back(T&& rhs) NLIB_NOEXCEPT;
27 #endif
29  T tmp;
30  return this->pop_front_swap(&tmp);
31  }
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(beg1_, rhs.beg1_);
43  swap(end1_, rhs.end1_);
44  swap(beg2_, rhs.beg2_);
45  swap(end2_, rhs.end2_);
46  swap(list_, rhs.list_);
47  }
48 
49  private:
50  uint32_t beg1_;
51  uint32_t end1_;
52  uint32_t beg2_;
53  uint32_t end2_;
54  Nlist<T, AL> list_;
56 };
57 
58 template <class T, class AL>
60  if (end1_ != beg2_ && beg2_ != end2_) {
61  using std::swap;
62  swap(list_[end1_++], list_[beg2_++]);
63  if (beg2_ != end2_) {
64  swap(list_[end1_++], list_[beg2_++]);
65  }
66  if (beg2_ == end2_) {
67  beg2_ = beg1_;
68  end2_ = end1_;
69  beg1_ = end1_ = 0;
70  }
71  }
72  if (list_.size() == end2_) {
73  T* tmp = list_.push_back();
74  if (tmp) ++end2_;
75  return tmp;
76  } else {
77  return &list_[end2_++];
78  }
79 }
80 
81 #ifdef NLIB_CXX11_RVALUE_REFERENCES
82 template <class T, class AL>
84  if (end1_ != beg2_ && beg2_ != end2_) {
85  using std::swap;
86  swap(list_[end1_++], list_[beg2_++]);
87  if (beg2_ != end2_) {
88  swap(list_[end1_++], list_[beg2_++]);
89  }
90  if (beg2_ == end2_) {
91  beg2_ = beg1_;
92  end2_ = end1_;
93  beg1_ = end1_ = 0;
94  }
95  }
96  if (list_.size() == end2_) {
97 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
98  NLIB_STATIC_ASSERT(std::is_nothrow_move_constructible<T>::value);
99 #endif
100  T* tmp = list_.push_back(std::move(rhs));
101  if (tmp) ++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  list_[end2_] = std::move(rhs);
108  return &list_[end2_++];
109  }
110 }
111 #endif
112 
113 template <class T, class AL>
115  if (!v) return false;
116  using std::swap;
117  if (beg1_ != end1_) {
118  swap(*v, list_[beg1_++]);
119  if (beg1_ == end1_) {
120  beg1_ = end1_ = 0;
121  } else if ((end1_ - beg1_) * 8 < end1_) {
122  uint32_t cnt = static_cast<uint32_t>(end1_ - beg1_);
123  for (uint32_t i = 0; i < cnt; ++i) {
124  swap(list_[i], list_[beg1_ + i]);
125  }
126  beg1_ = 0;
127  end1_ = cnt;
128  }
129  } else if (beg2_ != end2_) {
130  NLIB_ASSERT(beg1_ + end1_ == 0);
131  swap(*v, list_[beg2_++]);
132  if (beg2_ == end2_) beg2_ = 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
bool push_back_swap(T *v) noexcept
キューに要素を追加してから、その要素とvをstd::swapによって交換します。
Definition: Nqueue.h:32
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:145
STL namespace
std::queueに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nqueue.h:16
Nqueue() noexcept
デフォルトコンストラクタです。空のキューを作成します。
Definition: Nqueue.h:18
void swap(Nqueue &rhs) noexcept
コンテナをスワップします。
Definition: Nqueue.h:40
pointer push_back()
末尾に要素を追加してデフォルトコンストラクタで初期化します。
Definition: Nlist.h:377
std::vectorに似ていますが、コピーできないオブジェクトを格納可能なクラスが定義されています。 ...
bool pop_front() noexcept
先頭の要素をキューから取り出します。
Definition: Nqueue.h:28
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:86
std::vectorに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nlist.h:19
bool empty() const noexcept
コンテナが空かどうかを調べます。
Definition: Nqueue.h:23
size_type size() const noexcept
格納されている要素の個数を返します。
Definition: Nlist.h:365
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:136
size_t capacity() const noexcept
アロケート済みの要素の個数を返します。
Definition: Nqueue.h:22