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> >
30 class Nqueue {
31  public:
32  Nqueue() NLIB_NOEXCEPT : beg1_(0), end1_(0), beg2_(0), end2_(0) {}
34  NLIB_MOVE_MEMBER_HELPER_5(Nqueue, beg1_, end1_, beg2_, end2_, list_)
35  size_t size() const NLIB_NOEXCEPT { return (end1_ - beg1_) + (end2_ - beg2_); }
36  size_t capacity() const NLIB_NOEXCEPT { return list_.capacity(); }
37  bool empty() const NLIB_NOEXCEPT { return end1_ - beg1_ == 0 && end2_ - beg2_ == 0; }
38  T* push_back() NLIB_NOEXCEPT;
39 #ifdef NLIB_CXX11_RVALUE_REFERENCES
40  T* push_back(T&& rhs) NLIB_NOEXCEPT;
41 #endif
43  T tmp;
44  return this->pop_front_swap(&tmp);
45  }
47  T* tmp = this->push_back();
48  if (!tmp || !v) return false;
49  using std::swap;
50  swap(*tmp, *v);
51  return true;
52  }
53  bool pop_front_swap(T* v) NLIB_NOEXCEPT;
54  void swap(Nqueue& rhs) NLIB_NOEXCEPT { // NOLINT
55  using std::swap;
56  swap(beg1_, rhs.beg1_);
57  swap(end1_, rhs.end1_);
58  swap(beg2_, rhs.beg2_);
59  swap(end2_, rhs.end2_);
60  swap(list_, rhs.list_);
61  }
62 
63  private:
64  uint32_t beg1_;
65  uint32_t end1_;
66  uint32_t beg2_;
67  uint32_t end2_;
68  Nlist<T, AL> list_;
70 };
71 
72 template <class T, class AL>
74  if (end1_ != beg2_ && beg2_ != end2_) {
75  using std::swap;
76  swap(list_[end1_++], list_[beg2_++]);
77  if (beg2_ != end2_) {
78  swap(list_[end1_++], list_[beg2_++]);
79  }
80  if (beg2_ == end2_) {
81  beg2_ = beg1_;
82  end2_ = end1_;
83  beg1_ = end1_ = 0;
84  }
85  }
86  if (list_.size() == end2_) {
87  T* tmp = list_.push_back();
88  if (tmp) ++end2_;
89  return tmp;
90  } else {
91  return &list_[end2_++];
92  }
93 }
94 
95 #ifdef NLIB_CXX11_RVALUE_REFERENCES
96 template <class T, class AL>
98  if (end1_ != beg2_ && beg2_ != end2_) {
99  using std::swap;
100  swap(list_[end1_++], list_[beg2_++]);
101  if (beg2_ != end2_) {
102  swap(list_[end1_++], list_[beg2_++]);
103  }
104  if (beg2_ == end2_) {
105  beg2_ = beg1_;
106  end2_ = end1_;
107  beg1_ = end1_ = 0;
108  }
109  }
110  if (list_.size() == end2_) {
111 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
112  NLIB_STATIC_ASSERT(std::is_nothrow_move_constructible<T>::value);
113 #endif
114  T* tmp = list_.push_back(std::move(rhs));
115  if (tmp) ++end2_;
116  return tmp;
117  } else {
118 #ifdef NLIB_HAS_NATIVE_TYPETRAITS
119  NLIB_STATIC_ASSERT(std::is_nothrow_move_assignable<T>::value);
120 #endif
121  list_[end2_] = std::move(rhs);
122  return &list_[end2_++];
123  }
124 }
125 #endif
126 
127 template <class T, class AL>
129  if (!v) return false;
130  using std::swap;
131  if (beg1_ != end1_) {
132  swap(*v, list_[beg1_++]);
133  if (beg1_ == end1_) {
134  beg1_ = end1_ = 0;
135  } else if ((end1_ - beg1_) * 8 < end1_) {
136  uint32_t cnt = static_cast<uint32_t>(end1_ - beg1_);
137  for (uint32_t i = 0; i < cnt; ++i) {
138  swap(list_[i], list_[beg1_ + i]);
139  }
140  beg1_ = 0;
141  end1_ = cnt;
142  }
143  } else if (beg2_ != end2_) {
144  NLIB_ASSERT(beg1_ + end1_ == 0);
145  swap(*v, list_[beg2_++]);
146  if (beg2_ == end2_) beg2_ = end2_ = 0;
147  } else {
148  return false;
149  }
150  return true;
151 }
152 
153 NLIB_NAMESPACE_END
154 
155 #ifndef NLIB_STD_SWAP_WORKAROUND
156 NLIB_NAMESPACE_BEGIN
157 #else
158 NLIB_DEFINE_STD_SWAP_T_BEGIN1(std) // NOLINT
159 #endif
160 
161 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::Nqueue) // NOLINT
162 
163 #ifndef NLIB_STD_SWAP_WORKAROUND
164 NLIB_NAMESPACE_END
165 #else
166 NLIB_DEFINE_STD_SWAP_T_END1(std) // NOLINT
167 #endif
168 
169 #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:46
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:163
STL namespace
std::queueに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nqueue.h:30
Nqueue() noexcept
デフォルトコンストラクタです。空のキューを作成します。
Definition: Nqueue.h:32
void swap(Nqueue &rhs) noexcept
コンテナをスワップします。
Definition: Nqueue.h:54
pointer push_back()
末尾に要素を追加してデフォルトコンストラクタで初期化します。
Definition: Nlist.h:390
std::vectorに似ていますが、コピーできないオブジェクトを格納可能なクラスが定義されています。 ...
bool pop_front() noexcept
先頭の要素をキューから取り出します。
Definition: Nqueue.h:42
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:99
std::vectorに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nlist.h:32
bool empty() const noexcept
コンテナが空かどうかを調べます。
Definition: Nqueue.h:37
size_type size() const noexcept
格納されている要素の個数を返します。
Definition: Nlist.h:378
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:154
size_t capacity() const noexcept
アロケート済みの要素の個数を返します。
Definition: Nqueue.h:36