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