Rudiments

- Main Page
- Classes

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
9 dynamicarray<valuetype>::dynamicarray() {
10 init(128,32);
11 }
12
13 template< class valuetype >
14 RUDIMENTS_TEMPLATE_INLINE
15 dynamicarray<valuetype>::dynamicarray(uint64_t initialsize,
16 uint64_t increment) {
17 init((initialsize)?initialsize:128,(increment)?increment:32);
18 }
19
20 template< class valuetype >
21 RUDIMENTS_TEMPLATE_INLINE
22 dynamicarray<valuetype>::dynamicarray(const dynamicarray<valuetype> &v) {
23 init(v.initial,v.extsize);
24 dynamicarrayClone(v);
25 }
26
27 template< class valuetype >
28 RUDIMENTS_TEMPLATE_INLINE
29 dynamicarray<valuetype> &dynamicarray<valuetype>::operator=(
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
54 void dynamicarray<valuetype>::dynamicarrayClone(
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
95 dynamicarray<valuetype>::~dynamicarray() {
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
111 uint64_t dynamicarray<valuetype>::getLength() const {
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 if (curind>targetind) {
142 curext=curext->getPrevious();
143 curind--;
144 } else {
145 curext=curext->getNext();
146 curind++;
147 }
148 }
149 eind=initial+extsize*(curind-1);
150 }
151
152 // return the value
153 return curext->getValue()[index-eind];
154 }
155
156 template< class valuetype >
157 RUDIMENTS_TEMPLATE_INLINE
158 void dynamicarray<valuetype>::clearExtentList() {
159 curext=extents.getFirst();
160 while (curext) {
161 linkedlistnode<valuetype *> *next=curext->getNext();
162 valuetype *ext=curext->getValue();
163 delete[] ext;
164 extents.remove(curext);
165 curext=next;
166 }
167 }
168
169 template< class valuetype >
170 RUDIMENTS_TEMPLATE_INLINE
171 void dynamicarray<valuetype>::clear() {
172
173 // remove all but the first extent
174 curext=extents.getLast();
175 while (curext!=extents.getFirst()) {
176 linkedlistnode<valuetype *> *prev=curext->getPrevious();
177 valuetype *ext=curext->getValue();
178 delete[] ext;
179 extents.remove(curext);
180 curext=prev;
181 }
182
183 // reinit first extent
184 valuetype *ext=curext->getValue();
185 for (uint64_t i=0; i<initial; i++) {
186 ext[i].~valuetype();
187 new(&(ext[i])) valuetype;
188 }
189
190 // reset sizes and positions
191 size=0;
192 len=0;
193 curind=0;
194 }
dynamicarray::~dynamicarray
~dynamicarray()
Definition: dynamicarrayinlines.h:95
dynamicarray::getLength
uint64_t getLength() const
Definition: dynamicarrayinlines.h:111
dynamicarray::operator=
dynamicarray< valuetype > & operator=(const dynamicarray< valuetype > &v)
Definition: dynamicarrayinlines.h:29
linkedlistnode
Definition: linkedlist.h:11
dynamicarray::operator[]
valuetype & operator[](uint64_t index)
Definition: dynamicarrayinlines.h:101
dynamicarray
Definition: dynamicarray.h:40
dynamicarray::clear
void clear()
Definition: dynamicarrayinlines.h:171
dynamicarray::dynamicarray
dynamicarray()
Definition: dynamicarrayinlines.h:9