nlib
Nqueue.h
Go to the documentation of this file.
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
Destructor.
Definition: Nqueue.h:19
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Platform.h:2151
bool push_back_swap(T *v) noexcept
Adds an element to the queue, and then swaps that element with v using std:: swap.
Definition: Nqueue.h:32
size_t capacity() const noexcept
Returns the number of allocated elements.
Definition: Nqueue.h:22
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:126
STL namespace.
A container-like class similar to std::queue that can store objects that do not have copy constructor...
Definition: Nqueue.h:16
Nqueue() noexcept
Instantiates the object with default parameters (default constructor). Creates an empty queue...
Definition: Nqueue.h:18
void swap(Nqueue &rhs) noexcept
Swaps the container.
Definition: Nqueue.h:40
bool empty() const noexcept
Checks whether the container is empty.
Definition: Nqueue.h:23
Defines the class that resembles std::vector but can store objects that cannot be copied...
bool pop_front() noexcept
Removes the first element from the front of the queue.
Definition: Nqueue.h:28
A container-like class similar to std::vector that can store objects that do not have copy constructo...
Definition: Nlist.h:19
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:117