1 /*
2 AngelCode Scripting Library
3 Copyright (c) 2003-2015 Andreas Jonsson
4
5 This software is provided 'as-is', without any express or implied
6 warranty. In no event will the authors be held liable for any
7 damages arising from the use of this software.
8
9 Permission is granted to anyone to use this software for any
10 purpose, including commercial applications, and to alter it and
11 redistribute it freely, subject to the following restrictions:
12
13 1. The origin of this software must not be misrepresented; you
14 must not claim that you wrote the original software. If you use
15 this software in a product, an acknowledgment in the product
16 documentation would be appreciated but is not required.
17
18 2. Altered source versions must be plainly marked as such, and
19 must not be misrepresented as being the original software.
20
21 3. This notice may not be removed or altered from any source
22 distribution.
23
24 The original version of this library can be located at:
25 http://www.angelcode.com/angelscript/
26
27 Andreas Jonsson
28 andreas@angelcode.com
29 */
30
31 #ifndef AS_ARRAY_H
32 #define AS_ARRAY_H
33
34 #if !defined(AS_NO_MEMORY_H)
35 #include <memory.h>
36 #endif
37 #include <string.h> // some compilers declare memcpy() here
38
39 #ifdef _MSC_VER
40 #pragma warning(disable:4345) // warning about a change in how the code is handled in this version
41 #endif
42
43 BEGIN_AS_NAMESPACE
44
45 template <class T> class asCArray
46 {
47 public:
48 asCArray();
49 asCArray(const asCArray<T> &);
50 asCArray(asUINT reserve);
51 ~asCArray();
52
53 void Allocate(asUINT numElements, bool keepData);
54 void AllocateNoConstruct(asUINT numElements, bool keepData);
55 asUINT GetCapacity() const;
56
57 void PushLast(const T &element);
58 T PopLast();
59
60 bool SetLength(asUINT numElements);
61 bool SetLengthNoConstruct(asUINT numElements);
62 asUINT GetLength() const;
63
64 void Copy(const T*, asUINT count);
65 asCArray<T> &operator =(const asCArray<T> &);
66 void SwapWith(asCArray<T> &other);
67
68 const T &operator [](asUINT index) const;
69 T &operator [](asUINT index);
70 T *AddressOf();
71 const T *AddressOf() const;
72
73 bool Concatenate(const asCArray<T> &);
74 void Concatenate(T*, unsigned int count);
75
76 bool Exists(const T &element) const;
77 int IndexOf(const T &element) const;
78 void RemoveIndex(asUINT index); // Removes the entry without reordering the array
79 void RemoveValue(const T &element); // Removes the value without reordering the array
80 void RemoveIndexUnordered(asUINT index); // Removes the entry without keeping the order
81
82 bool operator==(const asCArray<T> &) const;
83 bool operator!=(const asCArray<T> &) const;
84
85 protected:
86 T *array;
87 asUINT length; // 32bits is enough for all uses of this array
88 asUINT maxLength;
89 char buf[2*4*AS_PTR_SIZE]; // Avoid dynamically allocated memory for tiny arrays
90 };
91
92 // Implementation
93
94 template <class T>
AddressOf()95 T *asCArray<T>::AddressOf()
96 {
97 return array;
98 }
99
100 template <class T>
AddressOf()101 const T *asCArray<T>::AddressOf() const
102 {
103 return array;
104 }
105
106 template <class T>
asCArray(void)107 asCArray<T>::asCArray(void)
108 {
109 array = 0;
110 length = 0;
111 maxLength = 0;
112 }
113
114 template <class T>
asCArray(const asCArray<T> & copy)115 asCArray<T>::asCArray(const asCArray<T> ©)
116 {
117 array = 0;
118 length = 0;
119 maxLength = 0;
120
121 *this = copy;
122 }
123
124 template <class T>
asCArray(asUINT reserve)125 asCArray<T>::asCArray(asUINT reserve)
126 {
127 array = 0;
128 length = 0;
129 maxLength = 0;
130
131 Allocate(reserve, false);
132 }
133
134 template <class T>
~asCArray(void)135 asCArray<T>::~asCArray(void)
136 {
137 // Allocating a zero length array will free all memory
138 Allocate(0,0);
139 }
140
141 template <class T>
GetLength()142 asUINT asCArray<T>::GetLength() const
143 {
144 return length;
145 }
146
147 template <class T>
148 const T &asCArray<T>::operator [](asUINT index) const
149 {
150 asASSERT(index < length);
151
152 return array[index];
153 }
154
155 template <class T>
156 T &asCArray<T>::operator [](asUINT index)
157 {
158 asASSERT(index < length);
159
160 return array[index];
161 }
162
163 template <class T>
PushLast(const T & element)164 void asCArray<T>::PushLast(const T &element)
165 {
166 if( length == maxLength )
167 {
168 if( maxLength == 0 )
169 Allocate(1, false);
170 else
171 Allocate(2*maxLength, true);
172
173 if( length == maxLength )
174 {
175 // Out of memory. Return without doing anything
176 return;
177 }
178 }
179
180 array[length++] = element;
181 }
182
183 template <class T>
PopLast()184 T asCArray<T>::PopLast()
185 {
186 asASSERT(length > 0);
187
188 return array[--length];
189 }
190
191 template <class T>
Allocate(asUINT numElements,bool keepData)192 void asCArray<T>::Allocate(asUINT numElements, bool keepData)
193 {
194 // We have 4 situations
195 // 1. The previous array is 8 bytes or smaller and the new array is also 8 bytes or smaller
196 // 2. The previous array is 8 bytes or smaller and the new array is larger than 8 bytes
197 // 3. The previous array is larger than 8 bytes and the new array is 8 bytes or smaller
198 // 4. The previous array is larger than 8 bytes and the new array is also larger than 8 bytes
199
200 T *tmp = 0;
201 if( numElements )
202 {
203 if( sizeof(T)*numElements <= sizeof(buf) )
204 // Use the internal buffer
205 tmp = reinterpret_cast<T*>(buf);
206 else
207 {
208 // Allocate the array and construct each of the elements
209 tmp = asNEWARRAY(T,numElements);
210 if( tmp == 0 )
211 {
212 // Out of memory. Return without doing anything
213 return;
214 }
215 }
216
217 if( array == tmp )
218 {
219 // Construct only the newly allocated elements
220 for( asUINT n = length; n < numElements; n++ )
221 new (&tmp[n]) T();
222 }
223 else
224 {
225 // Construct all elements
226 for( asUINT n = 0; n < numElements; n++ )
227 new (&tmp[n]) T();
228 }
229 }
230
231 if( array )
232 {
233 asUINT oldLength = length;
234
235 if( array == tmp )
236 {
237 if( keepData )
238 {
239 if( length > numElements )
240 length = numElements;
241 }
242 else
243 length = 0;
244
245 // Call the destructor for elements that are no longer used
246 for( asUINT n = length; n < oldLength; n++ )
247 array[n].~T();
248 }
249 else
250 {
251 if( keepData )
252 {
253 if( length > numElements )
254 length = numElements;
255
256 for( asUINT n = 0; n < length; n++ )
257 tmp[n] = array[n];
258 }
259 else
260 length = 0;
261
262 // Call the destructor for all elements
263 for( asUINT n = 0; n < oldLength; n++ )
264 array[n].~T();
265
266 if( array != reinterpret_cast<T*>(buf) )
267 asDELETEARRAY(array);
268 }
269 }
270
271 array = tmp;
272 maxLength = numElements;
273 }
274
275 template <class T>
AllocateNoConstruct(asUINT numElements,bool keepData)276 void asCArray<T>::AllocateNoConstruct(asUINT numElements, bool keepData)
277 {
278 // We have 4 situations
279 // 1. The previous array is 8 bytes or smaller and the new array is also 8 bytes or smaller
280 // 2. The previous array is 8 bytes or smaller and the new array is larger than 8 bytes
281 // 3. The previous array is larger than 8 bytes and the new array is 8 bytes or smaller
282 // 4. The previous array is larger than 8 bytes and the new array is also larger than 8 bytes
283
284 T *tmp = 0;
285 if( numElements )
286 {
287 if( sizeof(T)*numElements <= sizeof(buf) )
288 // Use the internal buffer
289 tmp = reinterpret_cast<T*>(buf);
290 else
291 {
292 // Allocate the array and construct each of the elements
293 tmp = asNEWARRAY(T,numElements);
294 if( tmp == 0 )
295 {
296 // Out of memory. Return without doing anything
297 return;
298 }
299 }
300 }
301
302 if( array )
303 {
304 if( array == tmp )
305 {
306 if( keepData )
307 {
308 if( length > numElements )
309 length = numElements;
310 }
311 else
312 length = 0;
313 }
314 else
315 {
316 if( keepData )
317 {
318 if( length > numElements )
319 length = numElements;
320
321 memcpy(tmp, array, sizeof(T)*length);
322 }
323 else
324 length = 0;
325
326 if( array != reinterpret_cast<T*>(buf) )
327 asDELETEARRAY(array);
328 }
329 }
330
331 array = tmp;
332 maxLength = numElements;
333 }
334
335 template <class T>
GetCapacity()336 asUINT asCArray<T>::GetCapacity() const
337 {
338 return maxLength;
339 }
340
341 template <class T>
SetLength(asUINT numElements)342 bool asCArray<T>::SetLength(asUINT numElements)
343 {
344 if( numElements > maxLength )
345 {
346 Allocate(numElements, true);
347 if( numElements > maxLength )
348 {
349 // Out of memory. Return without doing anything
350 return false;
351 }
352 }
353
354 length = numElements;
355 return true;
356 }
357
358 template <class T>
SetLengthNoConstruct(asUINT numElements)359 bool asCArray<T>::SetLengthNoConstruct(asUINT numElements)
360 {
361 if( numElements > maxLength )
362 {
363 AllocateNoConstruct(numElements, true);
364 if( numElements > maxLength )
365 {
366 // Out of memory. Return without doing anything
367 return false;
368 }
369 }
370
371 length = numElements;
372 return true;
373 }
374
375 template <class T>
Copy(const T * data,asUINT count)376 void asCArray<T>::Copy(const T *data, asUINT count)
377 {
378 if( maxLength < count )
379 {
380 Allocate(count, false);
381 if( maxLength < count )
382 {
383 // Out of memory. Return without doing anything
384 return;
385 }
386 }
387
388 for( asUINT n = 0; n < count; n++ )
389 array[n] = data[n];
390
391 length = count;
392 }
393
394 template <class T>
395 asCArray<T> &asCArray<T>::operator =(const asCArray<T> ©)
396 {
397 Copy(copy.array, copy.length);
398
399 return *this;
400 }
401
402 template <class T>
SwapWith(asCArray<T> & other)403 void asCArray<T>::SwapWith(asCArray<T> &other)
404 {
405 T *tmpArray = array;
406 asUINT tmpLength = length;
407 asUINT tmpMaxLength = maxLength;
408 char tmpBuf[sizeof(buf)];
409 memcpy(tmpBuf, buf, sizeof(buf));
410
411 array = other.array;
412 length = other.length;
413 maxLength = other.maxLength;
414 memcpy(buf, other.buf, sizeof(buf));
415
416 other.array = tmpArray;
417 other.length = tmpLength;
418 other.maxLength = tmpMaxLength;
419 memcpy(other.buf, tmpBuf, sizeof(buf));
420
421 // If the data is in the internal buffer, then the array pointer must refer to it
422 if( array == reinterpret_cast<T*>(other.buf) )
423 array = reinterpret_cast<T*>(buf);
424 if( other.array == reinterpret_cast<T*>(buf) )
425 other.array = reinterpret_cast<T*>(other.buf);
426 }
427
428 template <class T>
429 bool asCArray<T>::operator ==(const asCArray<T> &other) const
430 {
431 if( length != other.length ) return false;
432
433 for( asUINT n = 0; n < length; n++ )
434 if( array[n] != other.array[n] )
435 return false;
436
437 return true;
438 }
439
440 template <class T>
441 bool asCArray<T>::operator !=(const asCArray<T> &other) const
442 {
443 return !(*this == other);
444 }
445
446
447 // Returns false if the concatenation wasn't successful due to out of memory
448 template <class T>
Concatenate(const asCArray<T> & other)449 bool asCArray<T>::Concatenate(const asCArray<T> &other)
450 {
451 if( maxLength < length + other.length )
452 {
453 Allocate(length + other.length, true);
454 if( maxLength < length + other.length )
455 {
456 // Out of memory
457 return false;
458 }
459 }
460
461 for( asUINT n = 0; n < other.length; n++ )
462 array[length+n] = other.array[n];
463
464 length += other.length;
465
466 // Success
467 return true;
468 }
469
470 template <class T>
Concatenate(T * other,unsigned int count)471 void asCArray<T>::Concatenate(T* other, unsigned int count)
472 {
473 for( unsigned int c = 0; c < count; c++ )
474 PushLast(other[c]);
475 }
476
477 template <class T>
Exists(const T & e)478 bool asCArray<T>::Exists(const T &e) const
479 {
480 return IndexOf(e) == -1 ? false : true;
481 }
482
483 template <class T>
IndexOf(const T & e)484 int asCArray<T>::IndexOf(const T &e) const
485 {
486 for( asUINT n = 0; n < length; n++ )
487 if( array[n] == e ) return static_cast<int>(n);
488
489 return -1;
490 }
491
492 template <class T>
RemoveIndex(asUINT index)493 void asCArray<T>::RemoveIndex(asUINT index)
494 {
495 if( index < length )
496 {
497 for( asUINT n = index; n < length-1; n++ )
498 array[n] = array[n+1];
499
500 PopLast();
501 }
502 }
503
504 template <class T>
RemoveValue(const T & e)505 void asCArray<T>::RemoveValue(const T &e)
506 {
507 for( asUINT n = 0; n < length; n++ )
508 {
509 if( array[n] == e )
510 {
511 RemoveIndex(n);
512 break;
513 }
514 }
515 }
516
517 template <class T>
RemoveIndexUnordered(asUINT index)518 void asCArray<T>::RemoveIndexUnordered(asUINT index)
519 {
520 if( index == length - 1 )
521 PopLast();
522 else if( index < length )
523 array[index] = PopLast();
524 }
525
526 END_AS_NAMESPACE
527
528 #endif
529