Evo C++ Library v0.5.1
ptrlist.h
Go to the documentation of this file.
1 // Evo C++ Library
2 /* Copyright 2019 Justin Crowell
3 Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
4 */
6 
7 #pragma once
8 #ifndef INCL_evo_ptrlist_h
9 #define INCL_evo_ptrlist_h
10 
11 #include "impl/container.h"
12 #include "impl/iter.h"
13 
14 // Disable certain MSVC warnings for this file
15 #if defined(_MSC_VER)
16  #pragma warning(push)
17  #pragma warning(disable:4457)
18 #endif
19 
20 namespace evo {
23 
25 
26 // Internal implementation macros -- only used in this file
28 // Alloc+Copy items
29 #define EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY(DEST, SRC, FIRST, LAST) { \
30  Item item; \
31  for (Size i=FIRST; i<=LAST; ++i) { \
32  if (SRC[i] == NULL) { \
33  DEST[i] = NULL; \
34  } else { \
35  DEST[i] = item = EVO_IMPL_CONTAINER_MEM_ALLOC1(Value); \
36  new(item) T(*SRC[i]); \
37  } \
38  } \
39 }
40 // Zero new items after Alloc+Copy
41 #define EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY_ZERO_NEW(FIRST, LAST) { \
42  if (FIRST > 0) \
43  memset(data_, 0, sizeof(Item*)*FIRST); \
44  Size end = LAST + 1; \
45  if (end < size_) \
46  memset(data_+end, 0, sizeof(Item*)*(size_-end)); \
47 }
48 
49 // Alloc/Realloc/Free buffer
50 // Assumes buffer is already freed/null
51 #define EVO_IMPL_PTRLIST_ALLOC(HDR, DATA, SIZE) { \
52  assert( SIZE > 0 ); \
53  HDR = (Header*)::malloc( sizeof(Header) + (SIZE*sizeof(T*)) ); \
54  assert( HDR != NULL ); \
55  HDR->size = SIZE; \
56  HDR->refs = 1; \
57  DATA = (Item*)(HDR + 1); \
58 }
59 // Assumes buffer is already freed/null and size_ is already set
60 #define EVO_IMPL_PTRLIST_ALLOC_COPY(SRC_HDR, SRC_DATA) { \
61  EVO_IMPL_PTRLIST_ALLOC(header_, data_, size_); \
62  header_->used = SRC_HDR->used; \
63  header_->first = SRC_HDR->first; \
64  header_->last = SRC_HDR->last; \
65  if (header_->used > 0) { \
66  Size last = header_->last; \
67  EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY(data_, SRC_DATA, header_->first, last); \
68  EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY_ZERO_NEW(header_->first, last); \
69  } else \
70  memset(data_, 0, sizeof(Item*)*size_); \
71 }
72 // Assumes buffer is already allocated
73 #define EVO_IMPL_PTRLIST_REALLOC(HDR, DATA, SIZE) { \
74  assert( (size_t)HDR > sizeof(Header) ); \
75  assert( DATA != NULL ); \
76  assert( SIZE > 0 ); \
77  HDR = (Header*)::realloc( HDR, sizeof(Header) + (SIZE*sizeof(T*)) ); \
78  assert( HDR != NULL ); \
79  HDR->size = SIZE; \
80  DATA = (Item*)(HDR+1); \
81 }
82 // Assumes buffer is already allocated
83 #define EVO_IMPL_PTRLIST_CLEAR(HDR) { \
84  if (HDR->used > 0) { \
85  assert( HDR->first <= HDR->last ); \
86  Item* data = (Item*)(HDR+1); \
87  Item* end = data + HDR->last; \
88  for (data += HDR->first; data <= end; ++data) \
89  if (*data != NULL) { \
90  (**data).~T(); \
91  EVO_IMPL_CONTAINER_MEM_FREE(*data); \
92  } \
93  } \
94 }
95 // Assumes buffer is already allocated
96 #define EVO_IMPL_PTRLIST_FREEMEM(HDR) { \
97  assert( (size_t)HDR > sizeof(Header) ); \
98  ::free(HDR); \
99 }
100 // Assumes buffer is already allocated
101 #define EVO_IMPL_PTRLIST_FREE(HDR) { \
102  if (HDR != NULL && --HDR->refs == 0) { \
103  EVO_IMPL_PTRLIST_CLEAR(HDR); \
104  EVO_IMPL_PTRLIST_FREEMEM(HDR); \
105  } \
106 }
107 
109 
199 template<class T,class TSize=SizeT>
200 class PtrList {
201 public:
202  EVO_CONTAINER_TYPE;
203  typedef TSize Size;
204  typedef Size Key;
205  typedef T Value;
206  typedef T* Item;
207 
208  typedef PtrList<T,Size> ThisType;
209 
210  // Iterator support types
212  typedef Key IterKey;
213  typedef Value IterItem;
216  typedef typename IteratorRa<ThisType>::Const Iter;
217  typedef IteratorRa<ThisType> IterM;
218 
220  PtrList() {
221  header_ = NULL;
222  data_ = NULL;
223  size_ = 0;
224  }
225 
231  PtrList(const ThisType& data) {
232  if (data.size_ > 0) {
233  header_ = data.header_;
234  data_ = data.data_;
235  ++header_->refs;
236  } else {
237  header_ = NULL;
238  data_ = data.data_;
239  }
240  size_ = data.size_;
241  }
242 
244  ~PtrList()
245  { EVO_IMPL_PTRLIST_FREE(header_); }
246 
247 #if defined(EVO_CPP11)
248 
251  PtrList(std::initializer_list<T> init) : PtrList() {
252  assert( init.size() < IntegerT<Size>::MAX );
253  resize((Size)init.size());
254  Size i = 0;
255  for (const auto& val : init)
256  get(i++) = val;
257  }
258 
262  PtrList(ThisType&& src) {
263  header_ = src.header_;
264  data_ = src.data_;
265  size_ = src.size_;
266  src.header_ = NULL;
267  src.data_ = NULL;
268  src.size_ = 0;
269  }
270 
275  ThisType& operator=(ThisType&& src) {
276  EVO_IMPL_PTRLIST_FREE(header_);
277  header_ = src.header_;
278  data_ = src.data_;
279  size_ = src.size_;
280  src.header_ = NULL;
281  src.data_ = NULL;
282  src.size_ = 0;
283  return *this;
284  }
285 #endif
286 
292  const ThisType& asconst() const {
293  return *this;
294  }
295 
296  // SET
297 
304  ThisType& operator=(const ThisType& data)
305  { return set(data); }
306 
313  ThisType& clear() {
314  if (size_ > 0) {
315  assert( header_ != NULL );
316  if (header_->refs > 1) {
317  // Detach from shared
318  --header_->refs;
319  header_ = NULL;
320  data_ = EVO_PPEMPTY;
321  } else if (header_->used > 0) {
322  // Unique, clear items
323  assert( data_ != NULL );
324  Item* start = data_ + header_->first;
325  Size len = (header_->last - header_->first) + 1;
326  EVO_IMPL_PTRLIST_CLEAR(header_);
327  memset(start, 0, len*sizeof(Item*));
328  header_->used = 0;
329  header_->first = 0;
330  header_->last = 0;
331  }
332  }
333  return *this;
334  }
335 
339  ThisType& set() {
340  if (size_ > 0) {
341  assert( header_ != NULL );
342  if (header_->refs > 1) {
343  // Detach from shared
344  --header_->refs;
345  } else {
346  // Unique, clear items
347  assert( data_ != NULL );
348  EVO_IMPL_PTRLIST_CLEAR(header_);
349  EVO_IMPL_PTRLIST_FREEMEM(header_);
350  }
351  header_ = NULL;
352  data_ = NULL;
353  size_ = 0;
354  } else
355  data_ = NULL;
356  return *this;
357  }
358 
365  ThisType& set(const ThisType& data) {
366  if (data_ != data.data_) {
367  if (size_ > 0)
368  EVO_IMPL_PTRLIST_FREE(header_);
369  if (data.size_ > 0) {
370  header_ = data.header_;
371  data_ = data.data_;
372  ++header_->refs;
373  } else {
374  header_ = NULL;
375  data_ = data.data_;
376  }
377  size_ = data.size_;
378  }
379  return *this;
380  }
381 
385  ThisType& setempty() {
386  if (data_ == NULL)
387  data_ = EVO_PPEMPTY;
388  else
389  clear();
390  return *this;
391  }
392 
393  // INFO
394 
400  bool null() const
401  { return (data_ == NULL); }
402 
408  bool empty() const
409  { return (size_ == 0 || header_ == NULL || header_->used == 0); }
410 
414  Size size() const
415  { return size_; }
416 
420  Size used() const
421  { return (header_ == NULL ? 0 : header_->used); }
422 
428  bool shared() const
429  { return (header_ != NULL && header_->refs > 1); }
430 
437  const Item* data() const
438  { return data_; }
439 
447  const Item operator[](Key index) const {
448  assert( header_ != NULL );
449  assert( data_ != NULL );
450  assert( index < size_ );
451  return data_[index];
452  }
453 
461  const Item item(Key index) const {
462  assert( header_ != NULL );
463  assert( data_ != NULL );
464  assert( index < size_ );
465  return data_[index];
466  }
467 
474  const Item first() const
475  { return (header_ != NULL && header_->used > 0 ? data_[header_->first] : NULL); }
476 
483  const Item last() const
484  { return (header_ != NULL && header_->used > 0 ? data_[header_->last] : NULL); }
485 
493  Key iend(Size offset=0) const
494  { return (offset < size_ ? size_-1-offset : END); }
495 
496  // COMPARE
497 
502  int compare(const ThisType& data) const {
503  int result;
504  if (data_ == NULL)
505  result = (data.data_ == NULL ? 0 : -1);
506  else if (data.data_ == NULL)
507  result = 1;
508  else if (header_ == NULL || header_->used == 0)
509  result = (data.header_ != NULL && data.header_->used > 0 ? -1 : 0);
510  else if (data.header_ == NULL || data.header_->used == 0)
511  result = 1;
512  else {
513  if (header_->first == data.header_->first) {
514  result = 0;
515  Item item1, item2;
516  Size last1 = header_->last;
517  Size last2 = data.header_->last;
518  for (Size i=header_->first;; ++i) {
519  if (i > last1)
520  { result = (last1 == last2 ? 0 : -1); break; }
521  if (i > last2)
522  { result = 1; break; }
523  item1 = data_[i];
524  item2 = data.data_[i];
525  if (item1 == NULL) {
526  if (item2 != NULL)
527  { result = -1; break; }
528  } else if (item2 == NULL)
529  { result = 1; break; }
530  else if ((result=DataCompare<Value>::compare(*item1, *item2)) != 0)
531  break;
532  }
533  } else
534  result = (header_->first < data.header_->first ? 1 : -1);
535  }
536  return result;
537  }
538 
545  bool operator==(const ThisType& data) const {
546  bool result;
547  if (data_ == NULL)
548  result = (data.data_ == NULL);
549  else if (data.data_ == NULL)
550  result = false;
551  else if (data_ == data.data_)
552  result = true;
553  else if (header_ == NULL || header_->used == 0)
554  result = (data.header_ == NULL || data.header_->used == 0);
555  else if (data.header_ == NULL || data.header_->used == 0)
556  result = false;
557  else {
558  if ( header_->used == data.header_->used &&
559  header_->first == data.header_->first &&
560  header_->last == data.header_->last ) {
561  result = true;
562  Item item1, item2;
563  for (Size i=header_->first, last=header_->last; i<=last; ++i) {
564  item1 = data_[i];
565  item2 = data.data_[i];
566  if (item1 == NULL) {
567  if (item2 != NULL)
568  { result = false; break; }
569  } else if (item2 == NULL || !(*item1 == *item2))
570  { result = false; break; }
571  }
572  } else
573  result = false;
574  }
575  return result;
576  }
577 
584  bool operator!=(const ThisType& data) const {
585  bool result;
586  if (data_ == NULL)
587  result = (data.data_ != NULL);
588  else if (data.data_ == NULL)
589  result = true;
590  else if (data_ == data.data_)
591  result = false;
592  else if (header_ == NULL || header_->used == 0)
593  result = (data.header_ != NULL && data.header_->used > 0);
594  else if (data.header_ == NULL || data.header_->used == 0)
595  result = true;
596  else {
597  if ( header_->used == data.header_->used &&
598  header_->first == data.header_->first &&
599  header_->last == data.header_->last ) {
600  result = false;
601  Item item1, item2;
602  for (Size i=header_->first, last=header_->last; i<=last; ++i) {
603  item1 = data_[i];
604  item2 = data.data_[i];
605  if (item1 == NULL) {
606  if (item2 != NULL)
607  { result = true; break; }
608  } else if (item2 == NULL || !(*item1 == *item2))
609  { result = true; break; }
610  }
611  } else
612  result = true;
613  }
614  return result;
615  }
616 
617  // FIND
618 
620  Iter cbegin() const
621  { return Iter(*this); }
622 
624  Iter cend() const
625  { return Iter(); }
626 
628  IterM begin()
629  { return IterM(*this); }
630 
632  Iter begin() const
633  { return Iter(*this); }
634 
636  IterM end()
637  { return IterM(); }
638 
640  Iter end() const
641  { return Iter(); }
642 
652  Key find(const Value& value, Key start=0, Key end=END) const {
653  Key result = (Key)NONE;
654  if (header_ != NULL && header_->used > 0) {
655  if (start < header_->first)
656  start = header_->first;
657  if (end > header_->last + 1)
658  end = header_->last + 1;
659  Item item;
660  for (; start<end; ++start) {
661  item = data_[start];
662  if (item != NULL && *item == value)
663  { result = start; break; }
664  }
665  }
666  return result;
667  }
668 
679  Key findr(const T& value, Key start=0, Key end=END) const {
680  Key result = (Key)NONE;
681  if (header_ != NULL && header_->used > 0) {
682  if (start < header_->first)
683  start = header_->first;
684  if (end > header_->last + 1)
685  end = header_->last + 1;
686  Item item;
687  while (end>start) {
688  item = data_[--end];
689  if (item != NULL && *item == value)
690  { result = end; break; }
691  }
692  }
693  return result;
694  }
695 
696  // INFO_SET
697 
705  Item* dataM()
706  { unshare(); return data_; }
707 
717  Item getitem(const Key& key, bool* created=NULL) {
718  Item result;
719  if (key >= size_) {
720  resize(key+1);
721  goto newitem;
722  } else {
723  unshare();
724  result = data_[key];
725  }
726  if (result == NULL) {
727  // Create new item
728  newitem: // used to skip NULL check
729  data_[key] = result = EVO_IMPL_CONTAINER_MEM_ALLOC1(Value);
730  DataInit<T>::init_safe(result);
731  if (++header_->used == 1)
732  header_->first = header_->last = key;
733  else if (key < header_->first)
734  header_->first = key;
735  else if (key > header_->last)
736  header_->last = key;
737  assert( header_->first <= header_->last );
738  if (created != NULL)
739  *created = true;
740  } else if (created != NULL)
741  *created = false;
742  return result;
743  }
744 
754  Value& get(const Key& key, bool* created=NULL)
755  { return *getitem(key, created); }
756 
767  Item operator()(Key index)
768  { assert( index < size_ ); unshare(); return data_[index]; }
769 
780  Item itemM(Key index)
781  { assert( index < size_ ); unshare(); return data_[index]; }
782 
790  ThisType& unshare() {
791  if (size_ > 0) {
792  assert( header_ != NULL );
793  if (header_->refs > 1) {
794  --header_->refs;
795  Header* oldheader = header_;
796  Item* olddata = data_;
797  EVO_IMPL_PTRLIST_ALLOC_COPY(oldheader, olddata);
798  }
799  }
800  return *this;
801  }
802 
803  // RESIZE
804 
814  ThisType& resize(Size newsize) {
815  if (newsize == size_) {
816  unshare();
817  } else {
818  if (newsize == 0) {
819  EVO_IMPL_PTRLIST_FREE(header_);
820  header_ = NULL;
821  data_ = EVO_PPEMPTY;
822  size_ = 0;
823  return *this;
824  } else if (size_ > 0) {
825  assert( header_ != NULL );
826  if (header_->refs > 1) {
827  // Shared: Unshare
828  --header_->refs;
829  Size used = header_->used;
830  Size first = header_->first;
831  if (used > 0 && first < newsize) {
832  // There are items to copy from original list (otherwise create new empty list below)
833  Header* oldheader = header_;
834  Item* olddata = data_;
835  if (newsize > size_) {
836  // New null items
837  size_ = newsize;
838  EVO_IMPL_PTRLIST_ALLOC_COPY(oldheader, olddata);
839  } else {
840  // Truncate
841  Size last = header_->last;
842  if (newsize <= last) {
843  // Find new used count (after truncation)
844  {
845  Item* data = data_ + newsize;
846  if ((newsize + 1 - first) < (size_- newsize)) {
847  // Count items not truncated (less pointers to check)
848  used = 1; // safe to assume item at first is not null
849  for (Item* start=data_+first; --data > start; )
850  if (*data != NULL)
851  ++used;
852  } else {
853  // Count items truncated (less pointers to check)
854  --used; // safe to assume item at last is not null
855  for (Item* end=data_+last; data < end; ++data)
856  if (*data != NULL)
857  --used;
858  }
859  }
860  assert( used > 0 ); // always true since first < newsize
861 
862  // Find new last item (after truncation)
863  last = newsize;
864  while (--last > first && data_[last] == NULL)
865  { }
866  }
867 
868  // Create new list, copying up to newsize
869  size_ = newsize;
870  EVO_IMPL_PTRLIST_ALLOC(header_, data_, size_);
871  header_->used = used;
872  header_->first = first;
873  header_->last = last;
874  EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY(data_, olddata, first, last);
875  EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY_ZERO_NEW(first, last);
876  }
877  return *this;
878  } // else create new list (below)
879  } else {
880  // Unique
881  if (newsize > size_) {
882  // New null items
883  EVO_IMPL_PTRLIST_REALLOC(header_, data_, newsize);
884  memset(data_+size_, 0, sizeof(Item)*(newsize-size_));
885  size_ = newsize;
886  } else {
887  // Truncate
888  Size used = header_->used;
889  Size last = header_->last;
890  if (used > 0 && newsize <= last) {
891  // Truncate items
892  {
893  Item* data = data_ + newsize;
894  for (Item* end=data_+last; data <= end; ++data)
895  if (*data != NULL) {
896  (**data).~T();
897  EVO_IMPL_CONTAINER_MEM_FREE(*data);
898  --used;
899  }
900  }
901 
902  // Find new last item, update header
903  if (used > 0) {
904  Size first = header_->first;
905  last = newsize;
906  while (--last > first && data_[last] == NULL)
907  { }
908  header_->used = used;
909  header_->last = last;
910  } else {
911  header_->used = 0;
912  header_->first = 0;
913  header_->last = 0;
914  }
915 
916  // Realloc
917  EVO_IMPL_PTRLIST_REALLOC(header_, data_, newsize);
918  size_ = newsize;
919  } else {
920  // Truncate null items
921  EVO_IMPL_PTRLIST_REALLOC(header_, data_, newsize);
922  size_ = newsize;
923  }
924  }
925  return *this;
926  }
927  } // else create new list (below)
928 
929  // New list
930  EVO_IMPL_PTRLIST_ALLOC(header_, data_, newsize);
931  memset(data_, 0, sizeof(Item)*newsize);
932  header_->used = 0;
933  header_->first = 0;
934  header_->last = 0;
935  size_ = newsize;
936  }
937  return *this;
938  }
939 
946  ThisType& resizemin(Size minsize) {
947  if (minsize > size_)
948  resize(minsize);
949  return *this;
950  }
951 
952  // COPY
953 
960  ThisType& copy(const ThisType& data) {
961  if (data_ == data.data_) {
962  unshare();
963  } else {
964  if (size_ > 0)
965  EVO_IMPL_PTRLIST_FREE(header_);
966  if (data.size_ > 0) {
967  size_ = data.size_;
968  EVO_IMPL_PTRLIST_ALLOC_COPY(data.header_, data.data_);
969  } else {
970  header_ = NULL;
971  data_ = (data.data_ == NULL ? NULL : EVO_PPEMPTY);
972  size_ = 0;
973  }
974  }
975  return *this;
976  }
977 
978  // REMOVE
979 
987  ThisType& remove(Key key) {
988  if (key < size_) {
989  assert( header_ != NULL );
990  if (key < header_->first || key > header_->last) {
991  // No item, unshare
992  unshare();
993  } else if (header_->refs > 1) {
994  // Shared: Unshare
995  if (data_[key] != NULL) {
996  --header_->refs;
997  if (header_->used == 1) {
998  // New list
999  EVO_IMPL_PTRLIST_ALLOC(header_, data_, size_);
1000  memset(data_, 0, sizeof(Item)*size_);
1001  header_->used = 0;
1002  header_->first = 0;
1003  header_->last = 0;
1004  } else {
1005  // New list, minus removed item
1006  Header* oldheader = header_;
1007  Item* olddata = data_;
1008  Size first = header_->first;
1009  Size last = header_->last;
1010 
1011  // Variation of: EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY(data_, olddata, header_->first, last);
1012  EVO_IMPL_PTRLIST_ALLOC(header_, data_, size_);
1013  header_->used = oldheader->used - 1;
1014  header_->first = first;
1015  header_->last = last;
1016  Item item;
1017  for (Size i=first, last_copy=i; i<=last; ++i) {
1018  if (i == key) {
1019  data_[i] = NULL;
1020  if (i == first) {
1021  // Find new first item then continue copying
1022  while (++i <= last)
1023  if (olddata[i] != NULL) {
1024  header_->first = i;
1025  data_[i] = item = EVO_IMPL_CONTAINER_MEM_ALLOC1(Value);
1026  new(item) T(*olddata[i]);
1027  break; // no need to set last_copy since not removing last item
1028  } else
1029  data_[i] = NULL;
1030  assert( i <= last ); // used > 1, so always another first item
1031  } else if (i == last) {
1032  // New last item
1033  assert( last_copy > 0 && last_copy < last ); // used > 1 so last_copy already set
1034  header_->last = last_copy;
1035  }
1036  } else if (olddata[i] == NULL) {
1037  data_[i] = NULL;
1038  } else {
1039  data_[i] = item = EVO_IMPL_CONTAINER_MEM_ALLOC1(Value);
1040  new(item) T(*olddata[i]);
1041  last_copy = i;
1042  }
1043  }
1044  EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY_ZERO_NEW(first, last);
1045  }
1046  }
1047  } else {
1048  // Unique
1049  Item& item = data_[key];
1050  if (item != NULL) {
1051  (*item).~T();
1052  EVO_IMPL_CONTAINER_MEM_FREE(item);
1053  item = NULL;
1054  if (--header_->used == 0)
1055  // Empty
1056  header_->first = header_->last = 0;
1057  else if (key == header_->first) {
1058  // Find new first item
1059  const Size last = header_->last;
1060  while (++key < last && data_[key] == NULL)
1061  { }
1062  header_->first = key;
1063  } else if (key == header_->last) {
1064  // Find new last item
1065  const Size first = header_->first;
1066  while (--key > first && data_[key] == NULL)
1067  { }
1068  header_->last = key;
1069  }
1070  }
1071  }
1072  } else
1073  // No item, unshare
1074  unshare();
1075  return *this;
1076  }
1077 
1078  // SWAP
1079 
1085  void swap(ThisType& list)
1086  { EVO_IMPL_CONTAINER_SWAP(this, &list, ThisType); }
1087 
1088  // INTERNAL
1089 
1090  // Iterator support methods
1092  void iterInitMutable()
1093  { unshare(); }
1094  const IterItem* iterFirst(IterKey& key) const {
1095  const IterItem* result;
1096  if (header_ != NULL && header_->used > 0) {
1097  key = header_->first;
1098  result = data_[key];
1099  } else {
1100  key = END;
1101  result = NULL;
1102  }
1103  return result;
1104  }
1105  const IterItem* iterNext(IterKey& key) const {
1106  const IterItem* result;
1107  if (key != END && header_ != NULL && header_->used > 0) {
1108  const Size last = header_->last;
1109  if (key < last) {
1110  for (;;)
1111  if (++key == last || data_[key] != NULL)
1112  { result = data_[key]; break; }
1113  } else
1114  { key = END; result = NULL; }
1115  } else
1116  result = NULL;
1117  return result;
1118  }
1119  const IterItem* iterNext(Size count, IterKey& key) const {
1120  const IterItem* result;
1121  if (key != END && header_ != NULL && header_->used > 0 && count > 0) {
1122  const Size last = header_->last;
1123  if (key < last) {
1124  for (;;)
1125  if (++key == last) {
1126  if (--count > 0)
1127  { key = END; result = NULL; break; }
1128  result = data_[key];
1129  break;
1130  } else if (data_[key] != NULL && --count == 0)
1131  { result = data_[key]; break; }
1132  } else
1133  { key = END; result = NULL; }
1134  } else
1135  result = NULL;
1136  return result;
1137  }
1138  const IterItem* iterLast(IterKey& key) const {
1139  const IterItem* result;
1140  if (header_ != NULL && header_->used > 0) {
1141  key = header_->last;
1142  result = data_[key];
1143  } else {
1144  key = END;
1145  result = NULL;
1146  }
1147  return result;
1148  }
1149  const IterItem* iterPrev(IterKey& key) const {
1150  const IterItem* result;
1151  if (key != END && header_ != NULL && header_->used > 0) {
1152  const Size first = header_->first;
1153  if (key > first) {
1154  for (;;)
1155  if (--key == first || data_[key] != NULL)
1156  { result = data_[key]; break; }
1157  } else
1158  { key = END; result = NULL; }
1159  } else
1160  result = NULL;
1161  return result;
1162  }
1163  const IterItem* iterPrev(Size count, IterKey& key) const {
1164  const IterItem* result;
1165  if (key != END && header_ != NULL && header_->used > 0 && count > 0) {
1166  const Size first = header_->first;
1167  if (key > first) {
1168  for (;;)
1169  if (--key == first) {
1170  if (--count > 0)
1171  { key = END; result = NULL; break; }
1172  result = data_[key];
1173  break;
1174  } else if (data_[key] != NULL && --count == 0)
1175  { result = data_[key]; break; }
1176  } else
1177  { key = END; result = NULL; }
1178  } else
1179  result = NULL;
1180  return result;
1181  }
1182  Size iterCount() const
1183  { return (header_ != NULL ? header_->used : 0); }
1184  const IterItem* iterSet(IterKey& key) const {
1185  const IterItem* result;
1186  if (header_ != NULL && header_->used > 0) {
1187  if (key >= header_->first) {
1188  const Size last = header_->last;
1189  for (;; ++key)
1190  if (key > last)
1191  { key = END; result = NULL; break; }
1192  else if (data_[key] != NULL)
1193  { result = data_[key]; break; }
1194  } else
1195  { key = header_->first; result = data_[key]; }
1196  } else
1197  result = NULL;
1198  return result;
1199  }
1202 protected:
1204  struct Header {
1205  Size size;
1206  Size used;
1207  Size first;
1208  Size last;
1209  Size refs;
1210  };
1211 
1212  // States:
1213  // null: data=NULL, size=0
1214  // empty: data=1 or data=buffer, size=0
1215  // buffer: data=buffer, size>0, header.refs>=1
1216  Header* header_;
1217  Item* data_;
1218  Size size_;
1219 };
1220 
1222 
1223 // Remove implementation macros
1224 #undef EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY
1225 #undef EVO_IMPL_PTRLIST_ITEMS_ALLOC_COPY_ZERO_NEW
1226 #undef EVO_IMPL_PTRLIST_ALLOC
1227 #undef EVO_IMPL_PTRLIST_ALLOC_COPY
1228 #undef EVO_IMPL_PTRLIST_REALLOC
1229 #undef EVO_IMPL_PTRLIST_CLEAR
1230 #undef EVO_IMPL_PTRLIST_FREEMEM
1231 #undef EVO_IMPL_PTRLIST_FREE
1232 
1234 
1235 }
1236 #if defined(_MSC_VER)
1237  #pragma warning(pop)
1238 #endif
1239 #endif
evo::PtrList::cend
Iter cend() const
Get iterator at end (const).
Definition: ptrlist.h:624
evo::PtrList::begin
Iter begin() const
Get iterator at first item (const).
Definition: ptrlist.h:632
evo::PtrList::used
Size used() const
Get list used size, number of non-null items.
Definition: ptrlist.h:420
evo::PtrList::Value
T Value
Value type (Item dereferenced, same as T)
Definition: ptrlist.h:205
evo::PtrList::~PtrList
~PtrList()
Destructor.
Definition: ptrlist.h:244
evo::PtrList::getitem
Item getitem(const Key &key, bool *created=NULL)
Get item for key, creating if needed (mutable).
Definition: ptrlist.h:717
evo::PtrList::resizemin
ThisType & resizemin(Size minsize)
Resize to minimum size while preserving existing data (modifier).
Definition: ptrlist.h:946
evo::PtrList::operator[]
const Item operator[](Key index) const
Get item at position (const).
Definition: ptrlist.h:447
evo::PtrList::asconst
const ThisType & asconst() const
Explicitly use a const reference to this.
Definition: ptrlist.h:292
EVO_CONTAINER_TYPE
#define EVO_CONTAINER_TYPE
Identify current class/struct as an EvoContainer.
Definition: meta.h:482
evo::PtrList::end
IterM end()
Get iterator at end.
Definition: ptrlist.h:636
evo::IteratorRa
Random access iterator.
Definition: iter.h:904
evo::PtrList::operator()
Item operator()(Key index)
Get item at position (mutable).
Definition: ptrlist.h:767
evo::PtrList::Size
TSize Size
List size integer type
Definition: ptrlist.h:203
evo::PtrList::Header::refs
Size refs
Buffer reference count.
Definition: ptrlist.h:1209
evo::PtrList::operator==
bool operator==(const ThisType &data) const
Equality operator.
Definition: ptrlist.h:545
evo::PtrList::unshare
ThisType & unshare()
Make sure data is not shared by allocating new buffer if needed (modifier).
Definition: ptrlist.h:790
evo::PtrList::findr
Key findr(const T &value, Key start=0, Key end=END) const
Find last occurrence of item with reverse search.
Definition: ptrlist.h:679
evo::PtrList::ThisType
PtrList< T, Size > ThisType
This list type.
Definition: ptrlist.h:208
evo::PtrList::PtrList
PtrList()
Default constructor sets as null.
Definition: ptrlist.h:220
evo::IntegerT
Basic integer type.
Definition: type.h:980
evo::PtrList::iend
Key iend(Size offset=0) const
Get index for last item position using offset.
Definition: ptrlist.h:493
evo::DataCompare
Data comparison helpers.
Definition: container.h:753
evo::PtrList::IterM
IteratorRa< ThisType > IterM
Iterator (mutable) - IteratorRa.
Definition: ptrlist.h:217
evo::PtrList::cbegin
Iter cbegin() const
Get iterator at first item (const).
Definition: ptrlist.h:620
evo::PtrList::data_
Item * data_
Data pointer, NULL if null, can be 1 if empty (size_=0)
Definition: ptrlist.h:1217
evo::PtrList::compare
int compare(const ThisType &data) const
Comparison.
Definition: ptrlist.h:502
evo::PtrList::null
bool null() const
Get whether null.
Definition: ptrlist.h:400
iter.h
Evo implementation detail: Container iterators.
evo::PtrList::resize
ThisType & resize(Size newsize)
Resize while preserving existing data (modifier).
Definition: ptrlist.h:814
evo::PtrList::PtrList
PtrList(std::initializer_list< T > init)
Sequence constructor (C++11).
Definition: ptrlist.h:251
evo::PtrList::copy
ThisType & copy(const ThisType &data)
Set as full (unshared) copy using data pointer (modifier).
Definition: ptrlist.h:960
evo::PtrList::Item
T * Item
Item type (pointer to Value)
Definition: ptrlist.h:206
evo::PtrList::swap
void swap(ThisType &list)
Swap with another list.
Definition: ptrlist.h:1085
evo::PtrList::PtrList
PtrList(const ThisType &data)
Copy constructor.
Definition: ptrlist.h:231
evo::PtrList::setempty
ThisType & setempty()
Set as empty but not null.
Definition: ptrlist.h:385
evo::END
static const EndT END
Special integer value for indicating end of items or no item.
Definition: type.h:1846
evo::PtrList::Header::last
Size last
Index of last used item, 0 if used=0.
Definition: ptrlist.h:1208
container.h
Evo container foundation types and macros.
evo::PtrList::end
Iter end() const
Get iterator at end (const).
Definition: ptrlist.h:640
evo::PtrList::Header::size
Size size
Buffer size allocated as item count (capacity)
Definition: ptrlist.h:1205
evo::PtrList::Header
List data header.
Definition: ptrlist.h:1204
evo::PtrList::shared
bool shared() const
Get whether shared.
Definition: ptrlist.h:428
evo
Evo C++ Library namespace.
Definition: alg.h:11
evo::PtrList::Iter
IteratorRa< ThisType >::Const Iter
Iterator (const) - IteratorRa.
Definition: ptrlist.h:216
evo::PtrList::operator!=
bool operator!=(const ThisType &data) const
Inequality operator.
Definition: ptrlist.h:584
evo::NONE
static const EndT NONE
Special integer value for indicating no item or unknown item.
Definition: type.h:1832
evo::PtrList::Header::used
Size used
Buffer size used/initialized as item count.
Definition: ptrlist.h:1206
evo::PtrList::operator=
ThisType & operator=(ThisType &&src)
Move assignment operator (C++11).
Definition: ptrlist.h:275
evo::PtrList::size_
Size size_
Data size (same as header.size), 0 if empty.
Definition: ptrlist.h:1218
evo::PtrList::first
const Item first() const
Get first non-null item (const).
Definition: ptrlist.h:474
evo::PtrList::itemM
Item itemM(Key index)
Get item at position (mutable).
Definition: ptrlist.h:780
evo::PtrList::Key
Size Key
Key type (item index)
Definition: ptrlist.h:204
evo::PtrList::find
Key find(const Value &value, Key start=0, Key end=END) const
Find first occurrence of item with forward search.
Definition: ptrlist.h:652
EVO_PPEMPTY
#define EVO_PPEMPTY
Special pointer value for empty but not NULL (used in containers).
Definition: type.h:1863
evo::PtrList::header_
Header * header_
Data header pointer, NULL if no buffer allocated.
Definition: ptrlist.h:1216
evo::PtrList::clear
ThisType & clear()
Clear by removing all items.
Definition: ptrlist.h:313
evo::PtrList::PtrList
PtrList(ThisType &&src)
Move constructor (C++11).
Definition: ptrlist.h:262
evo::DataInit::init_safe
static void init_safe(Item *data, ulong size=1)
Initialize data using default constructor.
Definition: container.h:159
evo::PtrList::item
const Item item(Key index) const
Get item at position (const).
Definition: ptrlist.h:461
evo::PtrList::last
const Item last() const
Get last non-null item (const).
Definition: ptrlist.h:483
evo::PtrList::operator=
ThisType & operator=(const ThisType &data)
Assignment operator.
Definition: ptrlist.h:304
evo::PtrList::size
Size size() const
Get list size.
Definition: ptrlist.h:414
evo::PtrList::data
const Item * data() const
Get data pointer for direct access (const).
Definition: ptrlist.h:437
evo::PtrList
Sequential list of managed pointers with random access.
Definition: ptrlist.h:200
evo::PtrList::begin
IterM begin()
Get iterator at first item (mutable).
Definition: ptrlist.h:628
evo::PtrList::empty
bool empty() const
Get whether empty.
Definition: ptrlist.h:408
evo::PtrList::dataM
Item * dataM()
Get data pointer (mutable).
Definition: ptrlist.h:705
evo::PtrList::Header::first
Size first
Index of first used item, 0 if used=0.
Definition: ptrlist.h:1207
Generated on Tue May 7 2019 18:17:27 for Evo C++ Library v0.5.1 by   doxygen 1.8.13