nlib
Nlist.h
[詳解]
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_NLIST_H_
4 #define INCLUDE_NN_NLIB_NLIST_H_
5 
6 #include <string.h>
7 #include <utility>
8 #include <algorithm>
9 #include <iterator>
10 #include <memory>
11 
12 #include "nn/nlib/Config.h"
13 #include "nn/nlib/Swap.h"
14 #include "nn/nlib/TypeTraits.h"
15 
16 NLIB_NAMESPACE_BEGIN
17 
18 template <class T, class AL>
19 class Nlist;
20 
21 namespace nlist {
22 
23 class NLIB_VIS_PUBLIC NlistBase {
24  protected:
25  struct Blk {
26  Blk* next;
27  void* item;
28  };
29 
30  protected:
31  NLIB_CEXPR NlistBase() NLIB_NOEXCEPT : m_CurBlk(NULL),
32  m_CurLevel(0),
33  m_CurIdx(0),
34  m_FirstBlk(NULL) {}
35  static size_t BlkBaseIdx(size_t level) NLIB_NOEXCEPT {
36  return 8 * ((1 << level) - 1);
37  }
38  static size_t BlkSize(size_t level) NLIB_NOEXCEPT {
39  return 8 * (1 << level);
40  }
41  Blk* LastBlock(size_t* level) const NLIB_NOEXCEPT;
42  bool ConfirmBack() const NLIB_NOEXCEPT;
43  void ClearSimple() NLIB_NOEXCEPT {
44  m_CurLevel = 0;
45  m_CurIdx = 0;
46  m_CurBlk = m_FirstBlk;
47  }
48  const Blk* AtSub(size_t n, size_t* base) const NLIB_NOEXCEPT;
49 
50  protected:
51  mutable Blk* m_CurBlk;
52  mutable size_t m_CurLevel;
53  mutable size_t m_CurIdx;
54  mutable Blk* m_FirstBlk;
55 
56  private:
58 };
59 
60 template <class T>
61 class NlistConstIterator;
62 template <class T>
63 class NlistIterator;
64 
65 template <class T>
66 class NlistBaseT : public NlistBase {
67  public:
68  typedef T& reference;
69  typedef const T& const_reference;
70  typedef NlistIterator<T> iterator;
71  typedef NlistConstIterator<T> const_iterator;
72  typedef size_t size_type;
73  typedef T value_type;
74  typedef T* pointer;
75  typedef const T* const_pointer;
76  typedef ptrdiff_t difference_type;
77 
78  protected:
79  NLIB_CEXPR NlistBaseT() {}
80  static T* GetItem(Blk* blk) NLIB_NOEXCEPT {
81  return reinterpret_cast<T*>(blk->item);
82  }
83  static const T* GetItem(const Blk* blk) NLIB_NOEXCEPT {
84  return reinterpret_cast<const T*>(blk->item);
85  }
86  T* At(size_type n) const NLIB_NOEXCEPT {
87  size_type base;
88  const Blk* p = this->AtSub(n, &base);
89  return p ? const_cast<T*>(&(GetItem(p)[n - base])) : NULL;
90  }
91  iterator Begin() NLIB_NOEXCEPT { return iterator(this, TrueType()); }
92  iterator End() NLIB_NOEXCEPT { return iterator(this, FalseType()); }
93  const_iterator Begin() const NLIB_NOEXCEPT {
94  return const_iterator(this, TrueType());
95  }
96  const_iterator End() const NLIB_NOEXCEPT {
97  return const_iterator(this, FalseType());
98  }
99 
100  private:
101  NLIB_DISALLOW_COPY_AND_ASSIGN(NlistBaseT);
102  friend class NlistConstIterator<T>;
103  friend class NlistIterator<T>;
104 };
105 
106 template <class T>
107 class NlistConstIterator
108  : public std::iterator<std::forward_iterator_tag, T> {
109  private:
110  typedef NlistBaseT<T> ContainerType;
111  typedef typename ContainerType::Blk Blk;
112 
113  public:
114  typedef typename std::iterator<std::forward_iterator_tag, T> BaseType;
115  typedef typename BaseType::iterator_category iterator_category;
116  typedef typename BaseType::value_type value_type;
117  typedef typename BaseType::difference_type difference_type;
118  typedef typename BaseType::pointer pointer;
119  typedef typename BaseType::reference reference;
120 
121  public:
122  NLIB_CEXPR NlistConstIterator() NLIB_NOEXCEPT : m_Idx(0),
123  m_ElemPtr(NULL),
124  m_BlkEnd(NULL),
125  m_Blk(NULL) {}
126 
127  protected:
128  NlistConstIterator(const ContainerType* p, TrueType) NLIB_NOEXCEPT {
129  ContainerType* rhs = const_cast<ContainerType*>(p);
130  m_Idx = 0;
131  m_Blk = rhs->m_FirstBlk;
132  m_ElemPtr = GetItem(m_Blk);
133  m_BlkEnd = m_ElemPtr + 8;
134  }
135  NlistConstIterator(const ContainerType* p, FalseType) NLIB_NOEXCEPT {
136  ContainerType* rhs = const_cast<ContainerType*>(p);
137  m_Idx = rhs->BlkBaseIdx(rhs->m_CurLevel) + rhs->m_CurIdx;
138  m_Blk = rhs->m_CurBlk;
139  m_ElemPtr = &(GetItem(m_Blk)[rhs->m_CurIdx]);
140  m_BlkEnd = GetItem(m_Blk) + rhs->BlkSize(rhs->m_CurLevel);
141  if (m_ElemPtr == m_BlkEnd) this->Normalize();
142  }
143 
144  public:
145  const T& operator*() const NLIB_NOEXCEPT { return *m_ElemPtr; }
146  const T* operator->() const NLIB_NOEXCEPT { return m_ElemPtr; }
147  NlistConstIterator& operator++() NLIB_NOEXCEPT {
148  NLIB_ASSERT(m_ElemPtr != m_BlkEnd);
149  ++m_Idx;
150  if (++m_ElemPtr == m_BlkEnd) this->Normalize();
151  return *this;
152  }
153  NlistConstIterator operator++(int) NLIB_NOEXCEPT { // NOLINT
154  NlistConstIterator rval(*this);
155  this->operator++();
156  return rval;
157  }
158  bool operator==(const NlistConstIterator& rhs) const NLIB_NOEXCEPT {
159  return m_Idx == rhs.m_Idx && m_ElemPtr == rhs.m_ElemPtr;
160  }
161  bool operator!=(const NlistConstIterator& rhs) const NLIB_NOEXCEPT {
162  return !operator==(rhs);
163  }
164  void Advance(difference_type n) NLIB_NOEXCEPT;
165  difference_type Distance(NlistConstIterator to) const NLIB_NOEXCEPT {
166  return to.m_Idx - m_Idx;
167  }
168 
169  private:
170  static T* GetItem(Blk* blk) NLIB_NOEXCEPT {
171  return reinterpret_cast<T*>(blk->item);
172  }
173  static const T* GetItem(const Blk* blk) NLIB_NOEXCEPT {
174  return reinterpret_cast<const T*>(blk->item);
175  }
176  bool Normalize() NLIB_NOEXCEPT;
177 
178  private:
179  size_t m_Idx;
180  T* m_ElemPtr;
181  T* m_BlkEnd;
182  Blk* m_Blk;
183  friend class NlistBaseT<T>;
184 };
185 
186 template <class T>
187 bool NlistConstIterator<T>::Normalize() NLIB_NOEXCEPT {
188  if (m_Blk && m_Blk->next) {
189  Blk* next = m_Blk->next;
190  size_t next_size = 2 * static_cast<size_t>(m_BlkEnd - GetItem(m_Blk));
191  T* next_elemptr = GetItem(next);
192  T* next_end = next_elemptr + next_size;
193  m_Blk = next;
194  m_ElemPtr = next_elemptr;
195  m_BlkEnd = next_end;
196  return true;
197  }
198  return false;
199 }
200 
201 template <class T>
202 void NlistConstIterator<T>::Advance(difference_type n) NLIB_NOEXCEPT {
203  while (m_ElemPtr + n >= m_BlkEnd) {
204  n -= m_BlkEnd - m_ElemPtr;
205  m_Idx += m_BlkEnd - m_ElemPtr;
206  m_ElemPtr = m_BlkEnd;
207  if (!this->Normalize()) return;
208  }
209  m_ElemPtr += n;
210  m_Idx += n;
211 }
212 
213 template <class T>
214 class NlistIterator : public NlistConstIterator<T> {
215  private:
216  typedef NlistBaseT<T> ContainerType;
217  typedef typename ContainerType::Blk Blk;
218  typedef NlistConstIterator<T> MyBase;
219 
220  public:
221  typedef typename NlistConstIterator<T>::BaseType BaseType;
222  typedef typename BaseType::iterator_category iterator_category;
223  typedef typename BaseType::value_type value_type;
224  typedef typename BaseType::difference_type difference_type;
225  typedef typename BaseType::pointer pointer;
226  typedef typename BaseType::reference reference;
227 
228  public:
229  NLIB_CEXPR NlistIterator() NLIB_NOEXCEPT : MyBase() {}
230 
231  private:
232  NlistIterator(const ContainerType* p, TrueType) NLIB_NOEXCEPT : MyBase(p, TrueType()) {}
233  NlistIterator(const ContainerType* p, FalseType) NLIB_NOEXCEPT : MyBase(p, FalseType()) {}
234 
235  public:
236  T& operator*() const NLIB_NOEXCEPT {
237  const MyBase* tmp = static_cast<const MyBase*>(this);
238  return const_cast<T&>(**tmp);
239  }
240  T* operator->() const NLIB_NOEXCEPT {
241  const MyBase* tmp = static_cast<const MyBase*>(this);
242  return const_cast<T*>(tmp->operator->());
243  }
244  NlistIterator& operator++() NLIB_NOEXCEPT {
245  MyBase* tmp = static_cast<MyBase*>(this);
246  ++(*tmp);
247  return *this;
248  }
249  NlistIterator operator++(int) NLIB_NOEXCEPT { // NOLINT
250  NlistIterator rval(*this);
251  ++(*this);
252  return rval;
253  }
254  bool operator==(const NlistIterator& rhs) const NLIB_NOEXCEPT {
255  const MyBase* tmp = static_cast<const MyBase*>(this);
256  const MyBase* tmp2 = static_cast<const MyBase*>(&rhs);
257  return *tmp == *tmp2;
258  }
259  bool operator!=(const NlistIterator& rhs) const NLIB_NOEXCEPT {
260  return !operator==(rhs);
261  }
262  difference_type Distance(NlistIterator to) const NLIB_NOEXCEPT {
263  const MyBase* tmp = static_cast<const MyBase*>(this);
264  const MyBase* tmp2 = static_cast<const MyBase*>(&to);
265  return tmp->Distance(*tmp2);
266  }
267 
268  private:
269  friend class NlistBaseT<T>;
270 };
271 
272 template<bool is_empty, class AL>
273 class NlistAlloc {
274  public:
275  NlistAlloc() NLIB_NOEXCEPT : m_Alloc(AL()) {}
276  explicit NlistAlloc(const AL& al) NLIB_NOEXCEPT : m_Alloc(al) {}
277 
278  protected:
279  AL& _GetNlistAlloc() const NLIB_NOEXCEPT {
280  return const_cast<AL&>(m_Alloc);
281  }
282  void _SwapNlistAlloc(NlistAlloc& rhs) NLIB_NOEXCEPT { // NOLINT
283  using std::swap;
284  swap(m_Alloc, rhs.m_Alloc);
285  }
286 
287  private:
288  AL m_Alloc;
289 };
290 
291 template<class AL>
292 class NlistAlloc <true, AL> {
293  public:
294  NlistAlloc() NLIB_NOEXCEPT {}
295  explicit NlistAlloc(const AL& al) NLIB_NOEXCEPT { NLIB_UNUSED(al); }
296 
297  protected:
298  AL _GetNlistAlloc() const NLIB_NOEXCEPT { return AL(); }
299  void _SwapNlistAlloc(NlistAlloc& rhs) NLIB_NOEXCEPT { // NOLINT
300  NLIB_UNUSED(rhs);
301  }
302 };
303 
304 } // namespace nlist
305 
306 template <class T, class AL = std::allocator<char> >
307 class Nlist : public nlist::NlistBaseT<T>,
308  public nlist::NlistAlloc<IsEmpty<AL>::value, AL> {
309  // NOTE:
310  // To develop custom allocators:
311  //
312  // Nlist uses only the subset of std::allocator<T>.
313  // 1) rebind() is not used. the custom allocator does not have to be a class template.
314  // 2) construct(), destroy() are not used.
315  //
316  // You have to implement:
317  // a) void* allocate(size_t nBytes);
318  // b) void deallocate(void* ptr, size_t nBytes);
319  // allocate has to return 8 bytes aligned memory.
320  // And the custom allocator cannot have non-static data members.
321  /*
322  class MyAllocator
323  {
324  public:
325  MyAllocator();
326  MyAllocator(const MyAllocator& rhs);
327  void* allocate(size_t nBytes, void*);
328  void deallocate(void* p, size_t nBytes);
329  };
330  */
331 
332  private:
333  typedef typename nlist::NlistBaseT<T> BaseType;
334  typedef typename nlist::NlistAlloc<IsEmpty<AL>::value, AL> AllocType;
335  using BaseType::m_CurBlk;
336  using BaseType::m_CurIdx;
337  using BaseType::m_CurLevel;
338  using BaseType::m_FirstBlk;
339  using BaseType::ConfirmBack;
340  using BaseType::ClearSimple;
341  using BaseType::BlkBaseIdx;
342  using BaseType::BlkSize;
343  using BaseType::GetItem;
344  using BaseType::Begin;
345  using BaseType::End;
346  typedef typename BaseType::Blk Blk;
347 
348  public:
349  typedef typename BaseType::value_type value_type;
350  typedef AL allocator_type;
351  typedef typename BaseType::size_type size_type;
352  typedef typename BaseType::difference_type difference_type;
353  typedef typename BaseType::reference reference;
354  typedef typename BaseType::reference const_reference;
355  typedef typename BaseType::pointer pointer;
356  typedef typename BaseType::const_pointer const_pointer;
357  typedef typename BaseType::iterator iterator;
358  typedef typename BaseType::const_iterator const_iterator;
359 
360  public:
361  Nlist() NLIB_NOEXCEPT : AllocType(AL()) {}
362  explicit Nlist(const AL& al) NLIB_NOEXCEPT : AllocType(al) {}
363  ~Nlist() NLIB_NOEXCEPT;
364  NLIB_MOVE_MEMBER_HELPER_2(Nlist, BaseType, AllocType)
365  size_type size() const NLIB_NOEXCEPT {
366  return BlkBaseIdx(m_CurLevel) + m_CurIdx;
367  }
368  size_type capacity() const NLIB_NOEXCEPT {
369  size_type lv;
370  return (NULL != this->LastBlock(&lv)) ? BlkBaseIdx(lv + 1) : 0;
371  }
372  bool empty() const NLIB_NOEXCEPT { return m_CurLevel == 0 && m_CurIdx == 0; }
373  bool resize(size_type n) NLIB_NOEXCEPT {
374  return Resize(n, typename IsTriviallyDefaultConstructible<T>::type());
375  }
376  bool reserve(size_type n) NLIB_NOEXCEPT;
377  pointer push_back() {
378  void* p = this->PushBack();
379  if (!p) return NULL;
380  pointer ptr = MyCtor(p, typename IsTriviallyDefaultConstructible<T>::type()); // may throw
381  ++m_CurIdx;
382  return ptr;
383  }
384 #ifdef NLIB_CXX11_RVALUE_REFERENCES
385  pointer push_back(T&& rhs) NLIB_NOEXCEPT { // NOLINT
386 #if defined(NLIB_HAS_NATIVE_TYPETRAITS) && !defined(NLIB_HAS_TR1_TYPETRAITS)
387  NLIB_STATIC_ASSERT(std::is_nothrow_move_constructible<T>::value);
388 #endif
389  void* p = this->PushBack();
390  if (!p) return NULL;
391  pointer ptr = new (p) T(std::forward<T>(rhs));
392  ++m_CurIdx;
393  return ptr;
394  }
395 #endif
396  pointer push_back(const T& rhs) {
397  void* p = this->PushBack();
398  if (!p) return NULL;
399  pointer ptr = new (p) T(rhs); // may throw
400  ++m_CurIdx;
401  return ptr;
402  }
403  bool pop_back() NLIB_NOEXCEPT {
404  return this->pop_back_(typename IsTriviallyDestructible<T>::type());
405  }
406 
407  void swap(Nlist& rhs) NLIB_NOEXCEPT { // NOLINT
408  using std::swap;
409  swap(m_CurBlk, rhs.m_CurBlk);
410  swap(m_CurLevel, rhs.m_CurLevel);
411  swap(m_CurIdx, rhs.m_CurIdx);
412  swap(m_FirstBlk, rhs.m_FirstBlk);
413  AllocType::_SwapNlistAlloc(rhs);
414  }
415  void clear() NLIB_NOEXCEPT {
416  Clear(typename IsTriviallyDestructible<T>::type());
417  }
418  allocator_type get_allocator() const NLIB_NOEXCEPT {
419  return AllocType::_GetNlistAlloc();
420  }
421 
422  const_reference back() const {
423  if (m_CurIdx == 0) ConfirmBack();
424  return GetItem(m_CurBlk)[m_CurIdx - 1];
425  }
426  reference back() {
427  if (m_CurIdx == 0) ConfirmBack();
428  return GetItem(m_CurBlk)[m_CurIdx - 1];
429  }
430  const_reference front() const { return GetItem(m_FirstBlk)[0]; }
431  reference front() { return GetItem(m_FirstBlk)[0]; }
432  const_reference operator[](size_type idx) const {
433  NLIB_ASSERT(idx < this->size());
434  return *this->At(idx);
435  }
436  reference operator[](size_type idx) {
437  NLIB_ASSERT(idx < this->size());
438  return *this->At(idx);
439  }
440 
441  iterator begin() NLIB_NOEXCEPT {
442  if (!m_FirstBlk && !ConfirmFirstBlk()) return iterator();
443  return Begin();
444  }
445  const_iterator begin() const NLIB_NOEXCEPT {
446  if (!m_FirstBlk && !ConfirmFirstBlk()) return const_iterator();
447  return Begin();
448  }
449  const_iterator cbegin() const NLIB_NOEXCEPT {
450  if (!m_FirstBlk && !ConfirmFirstBlk()) return const_iterator();
451  return Begin();
452  }
453 
454  iterator end() NLIB_NOEXCEPT {
455  if (!m_FirstBlk && !ConfirmFirstBlk()) return iterator();
456  return End();
457  }
458  const_iterator end() const NLIB_NOEXCEPT {
459  if (!m_FirstBlk && !ConfirmFirstBlk()) return const_iterator();
460  return End();
461  }
462  const_iterator cend() const NLIB_NOEXCEPT {
463  if (!m_FirstBlk && !ConfirmFirstBlk()) return const_iterator();
464  return End();
465  }
466 
467  void shrink_to_fit() NLIB_NOEXCEPT {
468  if (!m_CurBlk) return;
469  Blk* p = m_CurBlk->next;
470  m_CurBlk->next = NULL;
471  DeallocBlkList(p, static_cast<int>(m_CurLevel + 1));
472  }
473 #if defined(NLIB_CXX11_RVALUE_REFERENCES) && defined(NLIB_CXX11_VARIADIC_TEMPLATES)
474  template<class... Args>
475  pointer EmplaceBack(Args&&... args) {
476  void* p = this->PushBack();
477  if (!p) return NULL;
478  pointer ptr = new (p) T(std::forward<Args>(args)...); // may throw
479  ++m_CurIdx;
480  return ptr;
481  }
482 #else
483  template <class A1>
484  pointer EmplaceBack(const A1& a1) {
485  void* p = this->PushBack();
486  if (!p) return NULL;
487  pointer ptr = new (p) T(const_cast<typename RemoveConst<A1>::type&>(a1));
488  ++m_CurIdx;
489  return ptr;
490  }
491  template <class A1, class A2>
492  pointer EmplaceBack(const A1& a1, const A2& a2) {
493  void* p = this->PushBack();
494  if (!p) return NULL;
495  pointer ptr = new (p) T(const_cast<typename RemoveConst<A1>::type&>(a1),
496  const_cast<typename RemoveConst<A2>::type&>(a2));
497  ++m_CurIdx;
498  return ptr;
499  }
500  template <class A1, class A2, class A3>
501  pointer EmplaceBack(const A1& a1, const A2& a2, const A3& a3) {
502  void* p = this->PushBack();
503  if (!p) return NULL;
504  pointer ptr = new (p) T(const_cast<typename RemoveConst<A1>::type&>(a1),
505  const_cast<typename RemoveConst<A2>::type&>(a2),
506  const_cast<typename RemoveConst<A3>::type&>(a3));
507  ++m_CurIdx;
508  return ptr;
509  }
510  template <class A1, class A2, class A3, class A4>
511  pointer EmplaceBack(const A1& a1, const A2& a2, const A3& a3, const A4& a4) {
512  void* p = this->PushBack();
513  if (!p) return NULL;
514  pointer ptr = new (p) T(const_cast<typename RemoveConst<A1>::type&>(a1),
515  const_cast<typename RemoveConst<A2>::type&>(a2),
516  const_cast<typename RemoveConst<A3>::type&>(a3),
517  const_cast<typename RemoveConst<A4>::type&>(a4));
518  ++m_CurIdx;
519  return ptr;
520  }
521  template <class A1, class A2, class A3, class A4, class A5>
522  pointer
523  EmplaceBack(const A1& a1, const A2& a2, const A3& a3, const A4& a4, const A5& a5) {
524  void* p = this->PushBack();
525  if (!p) return NULL;
526  pointer ptr = new (p) T(const_cast<typename RemoveConst<A1>::type&>(a1),
527  const_cast<typename RemoveConst<A2>::type&>(a2),
528  const_cast<typename RemoveConst<A3>::type&>(a3),
529  const_cast<typename RemoveConst<A4>::type&>(a4),
530  const_cast<typename RemoveConst<A5>::type&>(a5));
531  ++m_CurIdx;
532  return ptr;
533  }
534 #endif
535  void Clobber() NLIB_NOEXCEPT {
536  m_CurBlk = NULL;
537  m_CurLevel = 0;
538  m_CurIdx = 0;
539  m_FirstBlk = NULL;
540  }
541 
542  private:
543  // The # of elements in the block increases as 8, 16, 32, 64, ....
544  Blk* AllocBlk(size_t n) const NLIB_NOEXCEPT;
545  void DeallocBlkList(Blk* p, int lv) const NLIB_NOEXCEPT;
546  void DestroyBlk(Blk*, size_t, TrueType) const NLIB_NOEXCEPT {}
547  void DestroyBlk(Blk* p, size_t n, FalseType) const NLIB_NOEXCEPT;
548  void DestroyBlk(Blk* p, size_t n) const NLIB_NOEXCEPT {
549  DestroyBlk(p, n, typename IsTriviallyDestructible<T>::type());
550  }
551  bool ConfirmFirstBlk() const NLIB_NOEXCEPT;
552  void* PushBack() NLIB_NOEXCEPT;
553  void Clear(FalseType) NLIB_NOEXCEPT;
554  void Clear(TrueType) NLIB_NOEXCEPT { ClearSimple(); }
555  bool Resize(size_t n, FalseType) NLIB_NOEXCEPT;
556  bool Resize(size_t n, TrueType) NLIB_NOEXCEPT;
557  T* MyCtor(void* p, TrueType) NLIB_NOEXCEPT {
558  return reinterpret_cast<T*>(p);
559  }
560  T* MyCtor(void* p, FalseType) {
561  T* ptr = new (p) T; // may throw
562  return ptr;
563  }
564  bool pop_back_(FalseType) NLIB_NOEXCEPT {
565  if (m_CurIdx == 0) {
566  if (!ConfirmBack()) return false;
567  }
568  reference item = GetItem(m_CurBlk)[--m_CurIdx];
569  NLIB_UNUSED(item);
570  item.~T();
571  return true;
572  }
573  bool pop_back_(TrueType) NLIB_NOEXCEPT {
574  if (m_CurIdx == 0) {
575  if (!ConfirmBack()) return false;
576  }
577  --m_CurIdx;
578  return true;
579  }
580 
581  private:
583 };
584 
585 template <class T, class AL>
586 inline Nlist<T, AL>::~Nlist() NLIB_NOEXCEPT {
587  this->clear();
588  this->DeallocBlkList(m_FirstBlk, 0);
589 }
590 
591 namespace nlist {
592 
593 template <class T, class AL>
594 class ResizeRewinder {
595  public:
596  ResizeRewinder(Nlist<T, AL>& l) NLIB_NOEXCEPT : m_Count(0), m_List(l) {} // NOLINT
597  void PushBack(size_t n) {
598  for (; m_Count < n; ++m_Count) {
599  m_List.push_back(); // may throw in the default constructor of T
600  }
601  m_Count = 0;
602  }
603  ~ResizeRewinder() NLIB_NOEXCEPT {
604  for (; m_Count > 0; --m_Count) {
605  m_List.pop_back();
606  }
607  }
608 
609  private:
610  size_t m_Count;
611  Nlist<T, AL>& m_List;
612  NLIB_DISALLOW_COPY_AND_ASSIGN(ResizeRewinder);
613 };
614 
615 } // namespace nlist
616 
617 template <class T, class AL>
618 bool Nlist<T, AL>::Resize(size_t n, FalseType) NLIB_NOEXCEPT {
619  // NOTE: This can be optimized.
620  size_t sz = this->size();
621  if (n == sz) return true;
622  if (n < sz) {
623  for (size_t i = sz; i > n; --i) {
624  this->pop_back();
625  }
626  } else {
627  if (!this->reserve(n)) return false;
628  nlist::ResizeRewinder<T, AL> rewinder(*this);
629  rewinder.PushBack(n);
630  }
631  return true;
632 }
633 
634 template <class T, class AL>
635 bool Nlist<T, AL>::Resize(size_t n, TrueType) NLIB_NOEXCEPT {
636  size_type sz = this->size();
637  if (n == sz) return true;
638  if (n < sz) {
639  for (size_type i = sz; i > n; --i) {
640  this->pop_back();
641  }
642  } else {
643  if (!this->reserve(n)) return false;
644  // NOTE:
645  // Just set m_CurLevel, m_CurBlk, m_CurIdx
646  // because we don't have to invoke the constuctor of T.
647  size_t lower = this->BlkBaseIdx(m_CurLevel);
648  size_t upper = this->BlkBaseIdx(m_CurLevel + 1);
649  while (upper > n) {
650  ++m_CurLevel;
651  m_CurBlk = m_CurBlk->next;
652  lower = upper;
653  upper = this->BlkBaseIdx(m_CurLevel + 1);
654  }
655  m_CurIdx = static_cast<size_t>(n - lower);
656  }
657  return true;
658 }
659 
660 template <class T, class AL>
661 bool Nlist<T, AL>::reserve(size_type n) NLIB_NOEXCEPT {
662  if (n == 0 || n <= BlkBaseIdx(m_CurLevel + 1)) return true;
663  if (!m_FirstBlk && !this->ConfirmFirstBlk()) return false;
664  size_t lv;
665  Blk* blk = this->LastBlock(&lv);
666  for (;;) {
667  if (n <= BlkBaseIdx(lv + 1)) return true;
668  ++lv;
669  Blk* p = this->AllocBlk(BlkSize(lv));
670  if (!p) return false;
671  blk->next = p;
672  blk = p;
673  }
674 }
675 
676 template <class T, class AL>
677 typename Nlist<T, AL>::Blk* Nlist<T, AL>::AllocBlk(size_t n) const NLIB_NOEXCEPT {
678  NLIB_STATIC_ASSERT(NLIB_ALIGNOF(T) == 1 || NLIB_ALIGNOF(T) == 2 ||
679  NLIB_ALIGNOF(T) == 4 || NLIB_ALIGNOF(T) == 8);
680  NLIB_STATIC_ASSERT(sizeof(Blk) % 8 == 0);
681  size_t sz = sizeof(Blk) + n * sizeof(T);
682  void* pp;
683  NLIB_TRY {
684  pp = AllocType::_GetNlistAlloc().allocate(sz); // must be 8 bytes aligned
685  }
686 #ifdef NLIB_EXCEPTION_ENABLED
687  NLIB_CATCH(const std::bad_alloc&) { return NULL; }
688 #endif
689  if (!pp) return NULL;
690  Blk* p = reinterpret_cast<Blk*>(pp);
691  p->next = NULL;
692  p->item = reinterpret_cast<T*>(p + 1);
693  return p;
694 }
695 
696 template <class T, class AL>
697 void Nlist<T, AL>::DeallocBlkList(Blk* p, int lv) const NLIB_NOEXCEPT {
698  while (p) {
699  size_t n = BlkSize(lv);
700  Blk* pp = p;
701  p = pp->next;
702 
703  // DeallocBlock
704  AllocType::_GetNlistAlloc().deallocate(reinterpret_cast<char*>(pp),
705  sizeof(Blk) + n * sizeof(T));
706  ++lv;
707  }
708 }
709 
710 template <class T, class AL>
711 void Nlist<T, AL>::DestroyBlk(Blk* p, size_t n, FalseType) const NLIB_NOEXCEPT {
712  // NOTE:
713  // Do not use std::allocator::destroy() because destroy() is not required.
714  // invoke the destructor directly.
715  T* base = reinterpret_cast<T*>(p->item);
716  NLIB_UNUSED(base);
717  for (size_t i = 0; i < n; ++i) {
718  (base + i)->~T();
719  }
720 }
721 
722 template <class T, class AL>
723 bool Nlist<T, AL>::ConfirmFirstBlk() const NLIB_NOEXCEPT {
724  Blk* p = AllocBlk(BlkSize(0));
725  if (!p) return false;
726  m_FirstBlk = p;
727  m_CurBlk = p;
728  m_CurIdx = 0;
729  m_CurLevel = 0;
730  return true;
731 }
732 
733 template <class T, class AL>
734 void* Nlist<T, AL>::PushBack() NLIB_NOEXCEPT {
735  if (!m_FirstBlk && !ConfirmFirstBlk()) return NULL;
736  if (m_CurIdx == BlkSize(m_CurLevel)) {
737  if (!m_CurBlk->next) {
738  Blk* p = AllocBlk(BlkSize(m_CurLevel + 1));
739  if (!p) return NULL;
740  m_CurBlk->next = p;
741  }
742  ++m_CurLevel;
743  m_CurBlk = m_CurBlk->next;
744  m_CurIdx = 0;
745  }
746 
747  // NOTE:
748  // If m_CurIdx is incremented here,
749  // The state will be inconsisitent when T's constructor throws an exception.
750  T& item = GetItem(m_CurBlk)[m_CurIdx];
751  return &item;
752 }
753 
754 template <class T, class AL>
755 void Nlist<T, AL>::Clear(FalseType) NLIB_NOEXCEPT {
756  int lv = 0;
757  Blk* p = m_FirstBlk;
758  if (!p) return;
759  while (p != m_CurBlk) {
760  size_t cnt = BlkSize(lv);
761  DestroyBlk(p, cnt);
762  ++lv;
763  p = p->next;
764  }
765  if (p == m_CurBlk) {
766  DestroyBlk(p, m_CurIdx);
767  }
768  ClearSimple();
769 }
770 
771 template <class T, class AL1, class AL2>
772 inline bool operator==(const Nlist<T, AL1>& lhs,
773  const Nlist<T, AL2>& rhs) NLIB_NOEXCEPT {
774  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
775 }
776 
777 template <class T, class AL1, class AL2>
778 inline bool operator!=(const Nlist<T, AL1>& lhs,
779  const Nlist<T, AL2>& rhs) NLIB_NOEXCEPT {
780  return !(lhs == rhs);
781 }
782 
783 template <class T, class AL1, class AL2>
784 inline bool operator<(const Nlist<T, AL1>& lhs,
785  const Nlist<T, AL2>& rhs) NLIB_NOEXCEPT {
786  return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
787 }
788 
789 template <class T, class AL1, class AL2>
790 inline bool operator>(const Nlist<T, AL1>& lhs,
791  const Nlist<T, AL2>& rhs) NLIB_NOEXCEPT {
792  return (rhs < lhs);
793 }
794 
795 template <class T, class AL1, class AL2>
796 inline bool operator<=(const Nlist<T, AL1>& lhs,
797  const Nlist<T, AL2>& rhs) NLIB_NOEXCEPT {
798  return (!(rhs < lhs));
799 }
800 
801 template <class T, class AL1, class AL2>
802 inline bool operator>=(const Nlist<T, AL1>& lhs,
803  const Nlist<T, AL2>& rhs) NLIB_NOEXCEPT {
804  return (!(lhs < rhs));
805 }
806 
807 template <class AL = std::allocator<char> >
808 class StringList {
809  typedef Nlist<char*, AL> ContainerType;
810 
811  public:
812  typedef AL allocator_type;
813  typedef typename ContainerType::iterator iterator;
814  typedef typename ContainerType::const_iterator const_iterator;
815 
816  public:
817  StringList() NLIB_NOEXCEPT : m_List() {}
818  explicit StringList(const AL& al) : m_List(al) {}
819  ~StringList() NLIB_NOEXCEPT;
820  size_t size() const NLIB_NOEXCEPT { return m_List.size(); }
821  size_t capacity() const NLIB_NOEXCEPT { return m_List.capacity(); }
822  bool empty() const NLIB_NOEXCEPT { return m_List.empty(); }
823  bool reserve(size_t n) { return m_List.reserve(n); }
824  bool resize(size_t n) { return m_List.resize(n); }
825 
826  char** push_back(const char* str);
827  template <class Iterator>
828  char** push_back(Iterator first, Iterator last);
829 
830  bool pop_back() NLIB_NOEXCEPT;
831  void swap(StringList& rhs) NLIB_NOEXCEPT { m_List.swap(rhs.m_List); } // NOLINT
832  void clear() NLIB_NOEXCEPT { m_List.clear(); }
833  allocator_type get_allocator() const { return m_List.get_allocator(); }
834 
835  const char* back() const { return m_List.back(); }
836  char* back() { return m_List.back(); }
837  const char* front() const { return m_List.front(); }
838  char* front() { return m_List.front(); }
839  const char* operator[](size_t idx) const { return m_List[idx]; }
840  char* operator[](size_t idx) { return m_List[idx]; }
841  iterator begin() NLIB_NOEXCEPT { return m_List.begin(); }
842  const_iterator begin() const NLIB_NOEXCEPT { return m_List.begin(); }
843  const_iterator cbegin() NLIB_NOEXCEPT { return m_List.cbegin(); }
844 
845  iterator end() NLIB_NOEXCEPT { return m_List.end(); }
846  const_iterator end() const NLIB_NOEXCEPT { return m_List.end(); }
847  const_iterator cend() NLIB_NOEXCEPT { return m_List.cend(); }
848 
849  void shrink_to_fit() { m_List.shrink_to_fit(); }
850  void Clobber() NLIB_NOEXCEPT { m_List.clobber(); }
851 
852  char** Replace(iterator it, const char* str);
853  char** Replace(size_t idx, const char* str) {
854  if (idx >= m_List.size()) return NULL;
855  iterator it = m_List.begin();
856  it.Advance(idx);
857  return this->Replace(it, str);
858  }
859 
860  private:
861  void Dealloc(const char* ptr) const {
862  if (ptr) {
863  // NOTE: note that size info is not supplied.
864  this->get_allocator().deallocate(const_cast<char*>(ptr), 0);
865  }
866  }
867  char* StrDup(const char* ptr) const;
868  char* Alloc(size_t nBytes) const {
869  return this->get_allocator().allocate(nBytes);
870  }
871 
872  private:
873  ContainerType m_List;
874  NLIB_DISALLOW_COPY_AND_ASSIGN(StringList);
875 };
876 
877 template <class AL>
878 char* StringList<AL>::StrDup(const char* ptr) const {
879  size_t nBytes = nlib_strlen(ptr) + 1;
880  void* p = this->Alloc(nBytes);
881  if (!p) return NULL;
882  nlib_memcpy(p, nBytes, ptr, nBytes);
883  return reinterpret_cast<char*>(p);
884 }
885 
886 template <class AL>
887 StringList<AL>::~StringList() NLIB_NOEXCEPT {
888  const_iterator it = this->cbegin();
889  const_iterator it_end = this->cend();
890  while (it != it_end) {
891  Dealloc(*it);
892  ++it;
893  }
894 }
895 
896 template <class AL>
897 char** StringList<AL>::push_back(const char* str) {
898  char* dup;
899  if (str) {
900  dup = this->StrDup(str);
901  if (!dup) return NULL;
902  } else {
903  dup = NULL;
904  }
905  char** ptrStr = m_List.push_back(dup);
906  if (!ptrStr) this->Dealloc(dup);
907  return ptrStr;
908 }
909 
910 template <class AL>
911 template <class Iterator>
912 char** StringList<AL>::push_back(Iterator first, Iterator last) {
913  typename std::iterator_traits<Iterator>::difference_type n = std::distance(first, last);
914  char* str = this->Alloc(n + 1);
915  if (!str) return NULL;
916  std::copy(first, last, str);
917  str[n] = '\0';
918  char** rval = m_List.push_back(str);
919  if (!rval) this->Dealloc(str);
920  return rval;
921 }
922 
923 template <class AL>
924 bool StringList<AL>::pop_back() NLIB_NOEXCEPT {
925  if (m_List.empty()) return false;
926  Dealloc(m_List.back());
927  return m_List.pop_back();
928 }
929 
930 template <class AL>
931 char** StringList<AL>::Replace(iterator it, const char* str) {
932  char* dup;
933  if (str) {
934  dup = this->StrDup(str);
935  if (!dup) return NULL;
936  } else {
937  dup = NULL;
938  }
939  Dealloc(*it);
940  *it = dup;
941  return &*it;
942 }
943 
944 template <class AL>
945 bool AppendString(Nlist<char, AL>* obj, const char* str) {
946  size_t n = nlib_strlen(str);
947  if (!obj->reserve(obj->size() + n)) return false;
948  while (*str) {
949  obj->push_back(*str);
950  ++str;
951  }
952  return true;
953 }
954 
955 NLIB_NAMESPACE_END
956 
957 namespace std {
958 
959 template <class T, class Distance>
960 inline void advance(::nlib_ns::nlist::NlistIterator<T>& pos, // NOLINT
961  Distance n) {
962  pos.Advance(static_cast<size_t>(n));
963 }
964 
965 template <class T>
966 inline std::ptrdiff_t distance(const ::nlib_ns::nlist::NlistIterator<T>& first,
967  const ::nlib_ns::nlist::NlistIterator<T>& last) {
968  return first.Distance(last);
969 }
970 
971 } // namespace std
972 
973 #ifndef NLIB_STD_SWAP_WORKAROUND
974 NLIB_NAMESPACE_BEGIN
975 #else
976 NLIB_DEFINE_STD_SWAP_T_BEGIN1(std) // NOLINT
977 #endif
978 
979 NLIB_DEFINE_STD_SWAP_T2(T, AL, NLIB_NS::Nlist) // NOLINT
980 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::StringList) // NOLINT
981 
982 #ifndef NLIB_STD_SWAP_WORKAROUND
983 NLIB_NAMESPACE_END
984 #else
985 NLIB_DEFINE_STD_SWAP_T_END1(std) // NOLINT
986 #endif
987 
988 #endif // INCLUDE_NN_NLIB_NLIST_H_
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Platform.h:2151
Nlist(const AL &al) noexcept
アロケータを指定します。空のコンテナを作成します。
Definition: Nlist.h:362
void swap(Nlist &rhs) noexcept
コンテナをスワップします。
Definition: Nlist.h:407
BaseType::const_pointer const_pointer
const T*
Definition: Nlist.h:356
reference back()
末尾の要素の参照を返します。
Definition: Nlist.h:426
BaseType::pointer pointer
T*.
Definition: Nlist.h:355
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
Nlist() noexcept
デフォルトコンストラクタです。空のコンテナを作成します。
Definition: Nlist.h:361
const_iterator begin() const noexcept
コンテナの先頭を指す反復子を返します。
Definition: Nlist.h:445
BaseType::reference reference
T&.
Definition: Nlist.h:353
#define NLIB_CATCH(x)
例外が有効なときはcatch(x), そうでなければif (true)が定義されます。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:126
bool operator>=(const Nlist< T, AL1 > &lhs, const Nlist< T, AL2 > &rhs) noexcept
2つのリストを辞書順で比較します。
Definition: Nlist.h:802
const_reference front() const
front()と同様です。
Definition: Nlist.h:430
pointer EmplaceBack(const A1 &a1, const A2 &a2, const A3 &a3)
インプレイスで要素を追加します。
Definition: Nlist.h:501
BaseType::size_type size_type
符号なし整数型(size_t)
Definition: Nlist.h:351
bool operator>(const Nlist< T, AL1 > &lhs, const Nlist< T, AL2 > &rhs) noexcept
2つのリストを辞書順で比較します。
Definition: Nlist.h:790
iterator begin() noexcept
コンテナの先頭を指す反復子を返します。
Definition: Nlist.h:441
STL namespace.
void shrink_to_fit() noexcept
可能ならばアロケートされたメモリを返却します。
Definition: Nlist.h:467
#define NLIB_TRY
例外が有効なときはtry, そうでなければif (true)が定義されます。
bool operator==(const HeapHash &rhs, const HeapHash &lhs)
2つのサマリを比較して等価ならば、trueを返します。
Definition: NMalloc.h:101
bool operator!=(const HeapHash &rhs, const HeapHash &lhs)
2つのサマリを比較して等価でなければ、trueを返します。
Definition: NMalloc.h:106
const_reference back() const
back()と同様です。
Definition: Nlist.h:422
const_iterator cend() const noexcept
コンテナの末尾を指す反復子を返します。
Definition: Nlist.h:462
size_type capacity() const noexcept
アロケート済みの要素の個数を返します。
Definition: Nlist.h:368
bool empty() const noexcept
コンテナが空かどうかを調べます。
Definition: Nlist.h:372
BaseType::const_iterator const_iterator
読み取り専用フォワードイテレータ
Definition: Nlist.h:358
bool resize(size_type n) noexcept
コンテナをリサイズします。
Definition: Nlist.h:373
pointer push_back()
末尾に要素を追加してデフォルトコンストラクタで初期化します。
Definition: Nlist.h:377
const_reference operator[](size_type idx) const
operator[](size_t idx) と同様です。
Definition: Nlist.h:432
reference operator[](size_type idx)
インデックスで要素を参照します。
Definition: Nlist.h:436
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
pointer EmplaceBack(const A1 &a1, const A2 &a2, const A3 &a3, const A4 &a4)
インプレイスで要素を追加します。
Definition: Nlist.h:511
const_iterator end() const noexcept
コンテナの末尾を指す反復子を返します。
Definition: Nlist.h:458
void clear() noexcept
コンテナをクリアします。
Definition: Nlist.h:415
const_iterator cbegin() const noexcept
コンテナの先頭を指す反復子を返します。
Definition: Nlist.h:449
reference front()
先頭の要素の参照を返します。
Definition: Nlist.h:431
BaseType::iterator iterator
フォワードイテレータ
Definition: Nlist.h:357
BaseType::difference_type difference_type
符号つき整数型(ptrdiff_t)
Definition: Nlist.h:352
BaseType::value_type value_type
要素型 T
Definition: Nlist.h:349
開発環境別の設定が書かれるファイルです。
TimeSpan operator*(int i, const TimeSpan &rhs) noexcept
rhs を i 倍します。
Definition: DateTime.h:213
pointer EmplaceBack(const A1 &a1)
インプレイスで要素を追加します。
Definition: Nlist.h:484
void Clobber() noexcept
要素のデストラクタを呼んだりコンテナのメモリを解放することなく、コンテナを空に戻す。 ...
Definition: Nlist.h:535
std::vectorに似た、コピーコンストラクタを持たないオブジェクトを格納可能なコンテナ類似クラスです。 ...
Definition: Nlist.h:19
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:51
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:117
#define NLIB_ALIGNOF(tp)
alignof(tp)又は同等の定義がされます。
Definition: Config.h:210
pointer EmplaceBack(const A1 &a1, const A2 &a2)
インプレイスで要素を追加します。
Definition: Nlist.h:492
pointer EmplaceBack(const A1 &a1, const A2 &a2, const A3 &a3, const A4 &a4, const A5 &a5)
インプレイスで要素を追加します。
Definition: Nlist.h:523
AL allocator_type
アロケータの型 AL
Definition: Nlist.h:350
BaseType::reference const_reference
const T&
Definition: Nlist.h:354
errno_t nlib_memcpy(void *s1, size_t s1max, const void *s2, size_t n)
N1078のmemcpy_sに相当する実装です。
Definition: Platform.h:2095
iterator end() noexcept
コンテナの末尾を指す反復子を返します。
Definition: Nlist.h:454
bool pop_back() noexcept
末尾の要素を削除します。
Definition: Nlist.h:403
allocator_type get_allocator() const noexcept
アロケータを取得します。
Definition: Nlist.h:418