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