nlib
Nqueue.h
[詳解]
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_NQUEUE_H_
17 #define INCLUDE_NN_NLIB_NQUEUE_H_
18 
19 #include <memory>
20 #include <utility>
21 #include "nn/nlib/Swap.h"
22 #include "nn/nlib/Nlist.h"
23 #include "nn/nlib/TypeTraits.h"
24 
25 NLIB_NAMESPACE_BEGIN
26 
27 extern void* nqueue_enabler;
28 
29 template<class T, class AL = std::allocator<char> >
31  public:
32  NLIB_CEXPR Nqueue() NLIB_NOEXCEPT : beg1_(0), end1_(0), beg2_(0), end2_(0) {}
34 #ifdef __cpp_rvalue_references
35  Nqueue(Nqueue&& rhs) NLIB_NOEXCEPT : beg1_(rhs.beg1_),
36  end1_(rhs.end1_),
37  beg2_(rhs.beg2_),
38  end2_(rhs.end2_),
39  list_(std::move(rhs.list_)) {
40  beg1_ = end1_ = beg2_ = end2_ = 0;
41  }
43  beg1_ = rhs.beg1_;
44  end1_ = rhs.end1_;
45  beg2_ = rhs.beg2_;
46  end2_ = rhs.end2_;
47  list_ = std::move(rhs.list_);
48  beg1_ = end1_ = beg2_ = end2_ = 0;
49  return *this;
50  }
51 #endif
52  Nqueue(Nqueue& rhs, move_tag) NLIB_NOEXCEPT : beg1_(rhs.beg1_),
53  end1_(rhs.end1_),
54  beg2_(rhs.beg2_),
55  end2_(rhs.end2_),
56  list_(rhs.list_, move_tag()) {
57  beg1_ = end1_ = beg2_ = end2_ = 0;
58  }
60  beg1_ = rhs.beg1_;
61  end1_ = rhs.end1_;
62  beg2_ = rhs.beg2_;
63  end2_ = rhs.end2_;
64  list_.assign(rhs.list_, move_tag());
65  beg1_ = end1_ = beg2_ = end2_ = 0;
66  return *this;
67  }
68  size_t size() const NLIB_NOEXCEPT { return (end1_ - beg1_) + (end2_ - beg2_); }
69  size_t capacity() const NLIB_NOEXCEPT { return list_.capacity(); }
70  bool empty() const NLIB_NOEXCEPT { return end1_ - beg1_ == 0 && end2_ - beg2_ == 0; }
71  T* push_back() NLIB_NOEXCEPT;
72 #ifdef __cpp_rvalue_references
73  T* push_back(T&& rhs) NLIB_NOEXCEPT;
74 #endif
76  T tmp;
77  return this->pop_front_swap(&tmp);
78  }
80  T* tmp = this->push_back();
81  if (!tmp || !v) return false;
82  using std::swap;
83  swap(*tmp, *v);
84  return true;
85  }
86  bool pop_front_swap(T* v) NLIB_NOEXCEPT;
87 
88  private:
89  uint32_t beg1_;
90  uint32_t end1_;
91  uint32_t beg2_;
92  uint32_t end2_;
93  Nlist<T, AL> list_;
95 };
96 
97 template<class T, class AL>
99  if (end1_ != beg2_ && beg2_ != end2_) {
100  using std::swap;
101  swap(list_[end1_++], list_[beg2_++]);
102  if (beg2_ != end2_) {
103  swap(list_[end1_++], list_[beg2_++]);
104  }
105  if (beg2_ == end2_) {
106  beg2_ = beg1_;
107  end2_ = end1_;
108  beg1_ = end1_ = 0;
109  }
110  }
111  if (list_.size() == end2_) {
112  T* tmp = list_.push_back();
113  if (tmp) ++end2_;
114  return tmp;
115  } else {
116  return &list_[end2_++];
117  }
118 }
119 
120 #ifdef __cpp_rvalue_references
121 template<class T, class AL>
123  if (end1_ != beg2_ && beg2_ != end2_) {
124  using std::swap;
125  swap(list_[end1_++], list_[beg2_++]);
126  if (beg2_ != end2_) {
127  swap(list_[end1_++], list_[beg2_++]);
128  }
129  if (beg2_ == end2_) {
130  beg2_ = beg1_;
131  end2_ = end1_;
132  beg1_ = end1_ = 0;
133  }
134  }
135  if (list_.size() == end2_) {
136 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
137  NLIB_STATIC_ASSERT(std::is_nothrow_move_constructible<T>::value);
138 #endif
139  T* tmp = list_.push_back(std::move(rhs));
140  if (tmp) ++end2_;
141  return tmp;
142  } else {
143 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
144  NLIB_STATIC_ASSERT(std::is_nothrow_move_assignable<T>::value);
145 #endif
146  list_[end2_] = std::move(rhs);
147  return &list_[end2_++];
148  }
149 }
150 #endif
151 
152 template<class T, class AL>
154  if (!v) return false;
155  using std::swap;
156  if (beg1_ != end1_) {
157  swap(*v, list_[beg1_++]);
158  if (beg1_ == end1_) {
159  beg1_ = end1_ = 0;
160  } else if ((end1_ - beg1_) * 8 < end1_) {
161  uint32_t cnt = static_cast<uint32_t>(end1_ - beg1_);
162  for (uint32_t i = 0; i < cnt; ++i) {
163  swap(list_[i], list_[beg1_ + i]);
164  }
165  beg1_ = 0;
166  end1_ = cnt;
167  }
168  } else if (beg2_ != end2_) {
169  NLIB_ASSERT(beg1_ + end1_ == 0);
170  swap(*v, list_[beg2_++]);
171  if (beg2_ == end2_) beg2_ = end2_ = 0;
172  } else {
173  return false;
174  }
175  return true;
176 }
177 
178 NLIB_NAMESPACE_END
179 
180 NLIB_DEFINE_STD_SWAP_T_BEGIN2(nn, nlib)
181 NLIB_DEFINE_STD_SWAP_T2(T, AL, NLIB_NS::Nqueue)
182 NLIB_DEFINE_STD_SWAP_T_END2(nn, nlib)
183 
184 #endif // INCLUDE_NN_NLIB_NQUEUE_H_
~Nqueue() noexcept
デストラクタです。
Definition: Nqueue.h:33
bool push_back_swap(T *v) noexcept
キューに要素を追加してから、その要素とvをstd::swapによって交換します。
Definition: Nqueue.h:79
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:183
Definition: Base64.h:25
std::queueに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nqueue.h:30
Nqueue & assign(Nqueue &rhs, move_tag) noexcept
ムーブ代入演算子に相当します。
Definition: Nqueue.h:59
constexpr Nqueue() noexcept
デフォルトコンストラクタです。 空のキューを作成します。
Definition: Nqueue.h:32
Nqueue(Nqueue &&rhs) noexcept
ムーブコンストラクタです。
Definition: Nqueue.h:35
Nqueue(Nqueue &rhs, move_tag) noexcept
ムーブコンストラクタに相当します。
Definition: Nqueue.h:52
size_t size() const noexcept
格納されている要素数を返します。
Definition: Nqueue.h:68
std::vectorに似ていますが、コピーできないオブジェクトを格納可能なクラスが定義されています。 ...
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:270
bool pop_front() noexcept
先頭の要素をキューから取り出します。
Definition: Nqueue.h:75
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:111
std::vectorに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nlist.h:32
bool empty() const noexcept
格納されている要素数が0ならばtrue、それ以外ならfalseを返します。
Definition: Nqueue.h:70
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:250
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:174
size_t capacity() const noexcept
アロケート済みの要素の個数を返します。
Definition: Nqueue.h:69
Nqueue & operator=(Nqueue &&rhs) noexcept
ムーブ代入演算子です。
Definition: Nqueue.h:42