1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5//
6// clr_std/vector
7//
8// Copy of some key Standard Template Library functionality
9//
10
11#ifdef _MSC_VER
12#pragma once
13#endif
14
15#ifdef USE_STL
16#include <vector>
17#else
18#ifndef __clr_std_vector_h__
19#define __clr_std_vector_h__
20
21// This is defined in the debugmacrosext.h header, but don't take a dependency on that.
22#ifndef INDEBUG
23#ifdef _DEBUG
24#define INDEBUG(x) x
25#else
26#define INDEBUG(x)
27#endif
28#endif // !def INDEBUG
29
30namespace std
31{
32 template <class T>
33 class vector
34 {
35 public:
36 class const_iterator;
37
38 class iterator
39 {
40 friend class std::vector<T>::const_iterator;
41 public:
42 typedef T value_type;
43 typedef ptrdiff_t difference_type;
44 typedef T* pointer;
45 typedef T& reference;
46
47 typedef class vector<T>::iterator _MyIter;
48
49 _MyIter &operator++()
50 {
51 m_ptr++;
52 return *this;
53 }
54
55 _MyIter operator++(int)
56 {
57 // post-increment ++
58 _MyIter myiter(m_ptr);
59 m_ptr++;
60 return myiter;
61 }
62
63 _MyIter &operator--()
64 {
65 m_ptr--;
66 return *this;
67 }
68
69 _MyIter operator--(int)
70 {
71 // post-decrement --
72 _MyIter myiter(m_ptr);
73 m_ptr--;
74 return myiter;
75 }
76
77 _MyIter operator- (ptrdiff_t n)
78 {
79 _MyIter myiter(m_ptr);
80 myiter.m_ptr -= n;
81 return myiter;
82 }
83
84 ptrdiff_t operator- (_MyIter right)
85 {
86 _MyIter myiter(m_ptr);
87 return myiter.m_ptr - right.m_ptr;
88 }
89
90 _MyIter operator+ (ptrdiff_t n)
91 {
92 _MyIter myiter(m_ptr);
93 myiter.m_ptr += n;
94 return myiter;
95 }
96
97 T* operator->() const
98 {
99 return m_ptr;
100 }
101
102 T & operator*() const
103 {
104 return *m_ptr;
105 }
106
107 bool operator==(const _MyIter& _Right) const
108 {
109 bool equals = this->m_ptr == _Right.m_ptr;
110 return equals;
111 }
112
113 bool operator!=(const _MyIter& _Right) const
114 {
115 bool equals = this->m_ptr == _Right.m_ptr;
116 return !equals;
117 }
118
119 bool operator<(const _MyIter& _Right) const
120 {
121 return this->m_ptr < _Right.m_ptr;
122 }
123
124 bool operator>(const _MyIter& _Right) const
125 {
126 return this->m_ptr > _Right.m_ptr;
127 }
128 public:
129 explicit iterator(T* ptr)
130 {
131 m_ptr = ptr;
132 }
133
134 private:
135 T* m_ptr;
136 }; // class iterator
137
138 class const_iterator
139 {
140 public:
141 typedef class vector<T>::const_iterator _MyIter;
142 typedef class vector<T>::iterator _MyNonConstIter;
143
144 _MyIter &operator++()
145 {
146 m_ptr++;
147 return *this;
148 }
149
150 _MyIter operator++(int)
151 {
152 // post-increment ++
153 _MyIter myiter(m_ptr);
154 m_ptr++;
155 return myiter;
156 }
157
158 const T* operator->() const
159 {
160 return m_ptr;
161 }
162
163 const T & operator*() const
164 {
165 return *m_ptr;
166 }
167
168 bool operator==(const _MyIter& _Right) const
169 {
170 bool equals = this->m_ptr == _Right.m_ptr;
171 return equals;
172 }
173
174 bool operator!=(const _MyIter& _Right) const
175 {
176 bool equals = this->m_ptr == _Right.m_ptr;
177 return !equals;
178 }
179
180 public:
181 explicit const_iterator(T* ptr)
182 {
183 m_ptr = ptr;
184 }
185 const_iterator(const _MyNonConstIter &nonConstIterator)
186 {
187 m_ptr = nonConstIterator.m_ptr;
188 }
189
190 private:
191 T* m_ptr;
192 }; // class const iterator
193
194
195 public:
196 explicit vector(size_t n = 0)
197 {
198 m_size = 0;
199 m_capacity = 0;
200 m_pelements = NULL;
201 m_isBufferOwner = true;
202 resize(n);
203 }
204
205 ~vector()
206 {
207 if (m_isBufferOwner)
208 {
209 erase(m_pelements, 0, m_size);
210 delete [] (BYTE*)m_pelements; // cast to BYTE* as we don't want this delete to invoke T's dtor
211 }
212 else
213 {
214 m_size = 0;
215 m_capacity = 0;
216 }
217 }
218
219
220 size_t size() const
221 {
222 return m_size;
223 }
224
225 T & operator[](size_t iIndex)
226 {
227 assert(iIndex < m_size);
228 return m_pelements[iIndex];
229 }
230
231 T & operator[](size_t iIndex) const
232 {
233 assert(iIndex < m_size);
234 return m_pelements[iIndex];
235 }
236
237 void resize(size_t newsize)
238 {
239 assert(m_isBufferOwner);
240 size_t oldsize = this->size();
241 resize_noinit(newsize);
242 if (newsize > oldsize)
243 {
244 fill_uninitialized_with_default_value(m_pelements, oldsize, newsize);
245 }
246 }
247
248 void clear()
249 {
250 assert(m_isBufferOwner);
251 resize(0);
252 }
253
254 void resize(size_t newsize, T c)
255 {
256 assert(m_isBufferOwner);
257 size_t oldsize = this->size();
258 resize_noinit(newsize);
259 if (newsize > oldsize)
260 {
261 for (size_t i = oldsize; i < newsize; i++)
262 {
263 m_pelements[i] = c;
264 }
265 }
266 }
267
268 void wrap(size_t numElements, T* pElements)
269 {
270 m_size = numElements;
271 m_pelements = pElements;
272 m_isBufferOwner = false;
273 }
274
275 void resize_noinit(size_t newsize)
276 {
277 assert(m_isBufferOwner);
278 size_t oldsize = this->size();
279 if (newsize < oldsize)
280 {
281 // Shrink
282 erase(m_pelements, newsize, oldsize);
283 }
284 else if (newsize > oldsize)
285 {
286 // Grow
287 reserve(newsize);
288 }
289 m_size = newsize;
290 }
291
292 void push_back(const T & val)
293 {
294 assert(m_isBufferOwner);
295 if (m_size + 1 < m_size)
296 {
297 assert("push_back: overflow");
298 // @todo: how to throw.
299 }
300 resize(m_size + 1, val);
301 }
302
303 void reserve(size_t newcapacity)
304 {
305 assert(m_isBufferOwner);
306 if (newcapacity > m_capacity)
307 {
308 // To avoid resizing for every element that gets added to a vector, we
309 // allocate at least twice the old capacity, or 16 elements, whichever is greater.
310 newcapacity = max(newcapacity, max(m_capacity * 2, 16));
311
312 size_t bytesNeeded = newcapacity * sizeof(T);
313 if (bytesNeeded / sizeof(T) != newcapacity)
314 {
315 assert("resize: overflow");
316 // @todo: how to throw something here?
317 }
318
319
320 T *pelements = (T*)(new BYTE[bytesNeeded]); // Allocate as BYTE array to avoid automatic construction
321 INDEBUG(memset(pelements, 0xcc, bytesNeeded));
322 for (size_t i = 0; i < m_size; i++)
323 {
324 pelements[i] = m_pelements[i];
325 }
326
327 erase(m_pelements, 0, m_size);
328 delete [] (BYTE*)m_pelements; // cast to BYTE* as we don't want this delete to invoke T's dtor
329
330 m_pelements = pelements;
331 m_capacity = newcapacity;
332 }
333 }
334
335 iterator begin()
336 {
337 return iterator(m_pelements);
338 }
339
340 iterator end()
341 {
342 return iterator(m_pelements + m_size);
343 }
344
345 const_iterator cbegin() const
346 {
347 return const_iterator(m_pelements);
348 }
349
350 const_iterator cend() const
351 {
352 return const_iterator(m_pelements + m_size);
353 }
354
355 iterator erase(iterator position)
356 {
357 assert(m_isBufferOwner);
358 assert((position > begin() || position == begin()) && position < end());
359 ptrdiff_t index = position - begin();
360 erase(m_pelements, index, index + 1);
361 memcpy(&m_pelements[index], &m_pelements[index + 1], sizeof(T) * (m_size - index - 1));
362 --m_size;
363 return iterator(m_pelements + (position - begin()));
364 }
365
366 iterator erase(iterator position, iterator positionEnd)
367 {
368 assert(m_isBufferOwner);
369 assert((position > begin() || position == begin()) && position < end());
370 ptrdiff_t index = position - begin();
371 ptrdiff_t elements = positionEnd - position;
372 erase(m_pelements, index, index + elements);
373 memcpy(&m_pelements[index], &m_pelements[index + elements], sizeof(T) * (m_size - index - elements));
374 m_size -= elements;
375 return iterator(m_pelements + (position - begin()));
376 }
377
378 const T* data() const
379 {
380 return m_pelements;
381 }
382
383 private:
384 // Transition a subset of the array from uninitialized to initialized with default value for T.
385 static void fill_uninitialized_with_default_value(T* pelements, size_t startIdx, size_t endIdx)
386 {
387 assert(startIdx <= endIdx);
388 assert(pelements != NULL || startIdx == endIdx);
389 for (size_t i = startIdx; i < endIdx; i++)
390 {
391 INDEBUG(assert(0xcc == *((BYTE*)&pelements[i])));
392 pelements[i] = T();
393 }
394 }
395
396 // Transition a subset of the array from a valid value of T to uninitialized.
397 static void erase(T* pelements, size_t startIdx, size_t endIdx)
398 {
399 assert(startIdx <= endIdx);
400 assert(pelements != NULL || startIdx == endIdx);
401 for (size_t i = startIdx; i < endIdx; i++)
402 {
403 pelements[i].~T();
404 }
405
406 INDEBUG(memset(&pelements[startIdx], 0xcc, (endIdx - startIdx) * sizeof(T)));
407 }
408
409 private:
410 size_t m_size; //# of elements
411 size_t m_capacity; //# of elements allocated
412 T *m_pelements; //actual array
413 // invariants:
414 // dimensions == m_capacity
415 // elements 0 thru m_size-1 always contain constructed T values.
416 // elements from m_size thru m_capacity - 1 contain memory garbage (0xcc in DEBUG).
417 bool m_isBufferOwner; // indicate if this vector creates its own buffer, or wraps an existing buffer.
418
419
420
421
422 }; // class vector
423
424}; // namespace std
425
426#endif /* __clr_std_vector_h__ */
427
428#endif // !USE_STL
429
430// Help the VIM editor figure out what kind of file this no-extension file is.
431// vim: filetype=cpp
432