Rudiments
dynamicarrayinlines.h
1 // Copyright (c) 2015 David Muse
2 // See the COPYING file for more information.
3 
4 #include <rudiments/private/rudimentsinlines.h>
5 #include <rudiments/private/new.h>
6 
7 template< class valuetype >
8 RUDIMENTS_TEMPLATE_INLINE
10  init(128,32);
11 }
12 
13 template< class valuetype >
14 RUDIMENTS_TEMPLATE_INLINE
16  uint64_t increment) {
17  init((initialsize)?initialsize:128,(increment)?increment:32);
18 }
19 
20 template< class valuetype >
21 RUDIMENTS_TEMPLATE_INLINE
23  init(v.initial,v.extsize);
24  dynamicarrayClone(v);
25 }
26 
27 template< class valuetype >
28 RUDIMENTS_TEMPLATE_INLINE
30  const dynamicarray<valuetype> &v) {
31  if (this!=&v) {
32  clearExtentList();
33  init(v.initial,v.extsize);
34  dynamicarrayClone(v);
35  }
36  return *this;
37 }
38 
39 template< class valuetype >
40 RUDIMENTS_TEMPLATE_INLINE
41 void dynamicarray<valuetype>::init(uint64_t initialsize,
42  uint64_t increment) {
43  size=0;
44  len=0;
45  initial=initialsize;
46  extsize=increment;
47  extend(initialsize);
48  curext=extents.getFirst();
49  curind=0;
50 }
51 
52 template< class valuetype >
53 RUDIMENTS_TEMPLATE_INLINE
55  const dynamicarray<valuetype> &v) {
56 
57  // extend storage to fit (do this before setting size)
58  extend(v.len);
59 
60  // clone sizes and positions
61  size=v.size;
62  len=v.len;
63  initial=v.initial;
64  extsize=v.extsize;
65 
66  // clone the data
67  for (uint64_t i=0; i<v.getLength(); i++) {
68 
69  // Why not just:
70  // this[i]=v[i];
71  //
72  // Some compilers don't allow v[] because the operator[] method
73  // isn't const, but v is.
74  //
75  // Also, some compilers get confused and think that
76  // this[i]=v[i]
77  // means
78  // (this[i])->operator=(v[i])
79  // and no carefully placed parentheses help.
80  //
81  // This silliness sorts both issues out.
82  find(i)=((dynamicarray<valuetype> *)&v)->find(i);
83  }
84 
85  // clone positions
86  curind=v.curind;
87  curext=extents.getFirst();
88  for (uint64_t eind=0; eind<curind; eind++) {
89  curext=curext->getNext();
90  }
91 }
92 
93 template< class valuetype >
94 RUDIMENTS_TEMPLATE_INLINE
96  clearExtentList();
97 }
98 
99 template< class valuetype >
100 RUDIMENTS_TEMPLATE_INLINE
101 valuetype &dynamicarray<valuetype>::operator[](uint64_t index) {
102  extend(index+1);
103  if (index>=len) {
104  len=index+1;
105  }
106  return find(index);
107 }
108 
109 template< class valuetype >
110 RUDIMENTS_TEMPLATE_INLINE
112  return len;
113 }
114 
115 template< class valuetype >
116 RUDIMENTS_TEMPLATE_INLINE
117 void dynamicarray<valuetype>::extend(uint64_t size) {
118  uint64_t inc=(extents.getLength())?extsize:initial;
119  while (this->size<size) {
120  valuetype *newext=new valuetype[inc];
121  extents.append(newext);
122  this->size=this->size+inc;
123  inc=extsize;
124  }
125 }
126 
127 template< class valuetype >
128 RUDIMENTS_TEMPLATE_INLINE
129 valuetype &dynamicarray<valuetype>::find(uint64_t index) {
130 
131  // move to the extent that contains the specified index
132  // (also calculate the index of the first element of the extent)
133  size_t eind;
134  if (index<initial) {
135  curext=extents.getFirst();
136  curind=0;
137  eind=0;
138  } else {
139  uint64_t targetind=(index-initial+extsize)/extsize;
140  while (curind>targetind) {
141  curext=curext->getPrevious();
142  curind--;
143  }
144  while (curind<targetind) {
145  curext=curext->getNext();
146  curind++;
147  }
148  eind=initial+extsize*(curind-1);
149  }
150 
151  // return the value
152  return curext->getValue()[index-eind];
153 }
154 
155 template< class valuetype >
156 RUDIMENTS_TEMPLATE_INLINE
158  curext=extents.getFirst();
159  while (curext) {
160  linkedlistnode<valuetype *> *next=curext->getNext();
161  valuetype *ext=curext->getValue();
162  delete[] ext;
163  extents.remove(curext);
164  curext=next;
165  }
166 }
167 
168 template< class valuetype >
169 RUDIMENTS_TEMPLATE_INLINE
171 
172  // remove all but the first extent
173  curext=extents.getLast();
174  while (curext!=extents.getFirst()) {
175  linkedlistnode<valuetype *> *prev=curext->getPrevious();
176  valuetype *ext=curext->getValue();
177  delete[] ext;
178  extents.remove(curext);
179  curext=prev;
180  }
181 
182  // reinit first extent
183  valuetype *ext=curext->getValue();
184  for (uint64_t i=0; i<initial; i++) {
185  ext[i].~valuetype();
186  new(&(ext[i])) valuetype;
187  }
188 
189  // reset sizes and positions
190  size=0;
191  len=0;
192  curind=0;
193 }
~dynamicarray()
Definition: dynamicarrayinlines.h:95
uint64_t getLength() const
Definition: dynamicarrayinlines.h:111
dynamicarray< valuetype > & operator=(const dynamicarray< valuetype > &v)
Definition: dynamicarrayinlines.h:29
Definition: linkedlist.h:11
valuetype & operator[](uint64_t index)
Definition: dynamicarrayinlines.h:101
Definition: dynamicarray.h:40
void clear()
Definition: dynamicarrayinlines.h:170
dynamicarray()
Definition: dynamicarrayinlines.h:9