1//
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions
4// are met:
5// * Redistributions of source code must retain the above copyright
6// notice, this list of conditions and the following disclaimer.
7// * Redistributions in binary form must reproduce the above copyright
8// notice, this list of conditions and the following disclaimer in the
9// documentation and/or other materials provided with the distribution.
10// * Neither the name of NVIDIA CORPORATION nor the names of its
11// contributors may be used to endorse or promote products derived
12// from this software without specific prior written permission.
13//
14// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
15// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
18// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25//
26// Copyright (c) 2008-2021 NVIDIA Corporation. All rights reserved.
27// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
28// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
29
30#ifndef PSFOUNDATION_PSARRAY_H
31#define PSFOUNDATION_PSARRAY_H
32
33#include "foundation/PxAssert.h"
34#include "foundation/PxIntrinsics.h"
35#include "PsAllocator.h"
36#include "PsBasicTemplates.h"
37
38namespace physx
39{
40namespace shdfnd
41{
42template <class Serializer>
43void exportArray(Serializer& stream, const void* data, uint32_t size, uint32_t sizeOfElement, uint32_t capacity);
44char* importArray(char* address, void** data, uint32_t size, uint32_t sizeOfElement, uint32_t capacity);
45
46/*!
47An array is a sequential container.
48
49Implementation note
50* entries between 0 and size are valid objects
51* we use inheritance to build this because the array is included inline in a lot
52 of objects and we want the allocator to take no space if it's not stateful, which
53 aggregation doesn't allow. Also, we want the metadata at the front for the inline
54 case where the allocator contains some inline storage space
55*/
56template <class T, class Alloc = typename AllocatorTraits<T>::Type>
57class Array : protected Alloc
58{
59 public:
60 typedef T* Iterator;
61 typedef const T* ConstIterator;
62
63 explicit Array(const PxEMPTY v) : Alloc(v)
64 {
65 if(mData)
66 mCapacity |= PX_SIGN_BITMASK;
67 }
68
69 /*!
70 Default array constructor. Initialize an empty array
71 */
72 PX_INLINE explicit Array(const Alloc& alloc = Alloc()) : Alloc(alloc), mData(0), mSize(0), mCapacity(0)
73 {
74 }
75
76 /*!
77 Initialize array with given capacity
78 */
79 PX_INLINE explicit Array(uint32_t size, const T& a = T(), const Alloc& alloc = Alloc())
80 : Alloc(alloc), mData(0), mSize(0), mCapacity(0)
81 {
82 resize(size, a);
83 }
84
85 /*!
86 Copy-constructor. Copy all entries from other array
87 */
88 template <class A>
89 PX_INLINE explicit Array(const Array<T, A>& other, const Alloc& alloc = Alloc())
90 : Alloc(alloc)
91 {
92 copy(other);
93 }
94
95 // This is necessary else the basic default copy constructor is used in the case of both arrays being of the same
96 // template instance
97 // The C++ standard clearly states that a template constructor is never a copy constructor [2]. In other words,
98 // the presence of a template constructor does not suppress the implicit declaration of the copy constructor.
99 // Also never make a copy constructor explicit, or copy-initialization* will no longer work. This is because
100 // 'binding an rvalue to a const reference requires an accessible copy constructor' (http://gcc.gnu.org/bugs/)
101 // *http://stackoverflow.com/questions/1051379/is-there-a-difference-in-c-between-copy-initialization-and-assignment-initializ
102 PX_INLINE Array(const Array& other, const Alloc& alloc = Alloc()) : Alloc(alloc)
103 {
104 copy(other);
105 }
106
107 /*!
108 Initialize array with given length
109 */
110 PX_INLINE explicit Array(const T* first, const T* last, const Alloc& alloc = Alloc())
111 : Alloc(alloc), mSize(last < first ? 0 : uint32_t(last - first)), mCapacity(mSize)
112 {
113 mData = allocate(size: mSize);
114 copy(mData, mData + mSize, first);
115 }
116
117 /*!
118 Destructor
119 */
120 PX_INLINE ~Array()
121 {
122 destroy(first: mData, last: mData + mSize);
123
124 if(capacity() && !isInUserMemory())
125 deallocate(mem: mData);
126 }
127
128 /*!
129 Assignment operator. Copy content (deep-copy)
130 */
131 template <class A>
132 PX_INLINE Array& operator=(const Array<T, A>& rhs)
133 {
134 if(&rhs == this)
135 return *this;
136
137 clear();
138 reserve(capacity: rhs.mSize);
139 copy(mData, mData + rhs.mSize, rhs.mData);
140
141 mSize = rhs.mSize;
142 return *this;
143 }
144
145 PX_INLINE Array& operator=(const Array& t) // Needs to be declared, see comment at copy-constructor
146 {
147 return operator=<Alloc>(t);
148 }
149
150 /*!
151 Array indexing operator.
152 \param i
153 The index of the element that will be returned.
154 \return
155 The element i in the array.
156 */
157 PX_FORCE_INLINE const T& operator[](uint32_t i) const
158 {
159 PX_ASSERT(i < mSize);
160 return mData[i];
161 }
162
163 /*!
164 Array indexing operator.
165 \param i
166 The index of the element that will be returned.
167 \return
168 The element i in the array.
169 */
170 PX_FORCE_INLINE T& operator[](uint32_t i)
171 {
172 PX_ASSERT(i < mSize);
173 return mData[i];
174 }
175
176 /*!
177 Returns a pointer to the initial element of the array.
178 \return
179 a pointer to the initial element of the array.
180 */
181 PX_FORCE_INLINE ConstIterator begin() const
182 {
183 return mData;
184 }
185
186 PX_FORCE_INLINE Iterator begin()
187 {
188 return mData;
189 }
190
191 /*!
192 Returns an iterator beyond the last element of the array. Do not dereference.
193 \return
194 a pointer to the element beyond the last element of the array.
195 */
196
197 PX_FORCE_INLINE ConstIterator end() const
198 {
199 return mData + mSize;
200 }
201
202 PX_FORCE_INLINE Iterator end()
203 {
204 return mData + mSize;
205 }
206
207 /*!
208 Returns a reference to the first element of the array. Undefined if the array is empty.
209 \return a reference to the first element of the array
210 */
211
212 PX_FORCE_INLINE const T& front() const
213 {
214 PX_ASSERT(mSize);
215 return mData[0];
216 }
217
218 PX_FORCE_INLINE T& front()
219 {
220 PX_ASSERT(mSize);
221 return mData[0];
222 }
223
224 /*!
225 Returns a reference to the last element of the array. Undefined if the array is empty
226 \return a reference to the last element of the array
227 */
228
229 PX_FORCE_INLINE const T& back() const
230 {
231 PX_ASSERT(mSize);
232 return mData[mSize - 1];
233 }
234
235 PX_FORCE_INLINE T& back()
236 {
237 PX_ASSERT(mSize);
238 return mData[mSize - 1];
239 }
240
241 /*!
242 Returns the number of entries in the array. This can, and probably will,
243 differ from the array capacity.
244 \return
245 The number of of entries in the array.
246 */
247 PX_FORCE_INLINE uint32_t size() const
248 {
249 return mSize;
250 }
251
252 /*!
253 Clears the array.
254 */
255 PX_INLINE void clear()
256 {
257 destroy(first: mData, last: mData + mSize);
258 mSize = 0;
259 }
260
261 /*!
262 Returns whether the array is empty (i.e. whether its size is 0).
263 \return
264 true if the array is empty
265 */
266 PX_FORCE_INLINE bool empty() const
267 {
268 return mSize == 0;
269 }
270
271 /*!
272 Finds the first occurrence of an element in the array.
273 \param a
274 The element to find.
275 */
276
277 PX_INLINE Iterator find(const T& a)
278 {
279 uint32_t index;
280 for(index = 0; index < mSize && mData[index] != a; index++)
281 ;
282 return mData + index;
283 }
284
285 PX_INLINE ConstIterator find(const T& a) const
286 {
287 uint32_t index;
288 for(index = 0; index < mSize && mData[index] != a; index++)
289 ;
290 return mData + index;
291 }
292
293 /////////////////////////////////////////////////////////////////////////
294 /*!
295 Adds one element to the end of the array. Operation is O(1).
296 \param a
297 The element that will be added to this array.
298 */
299 /////////////////////////////////////////////////////////////////////////
300
301 PX_FORCE_INLINE T& pushBack(const T& a)
302 {
303 if(capacity() <= mSize)
304 return growAndPushBack(a);
305
306 PX_PLACEMENT_NEW(reinterpret_cast<void*>(mData + mSize), T)(a);
307
308 return mData[mSize++];
309 }
310
311 /////////////////////////////////////////////////////////////////////////
312 /*!
313 Returns the element at the end of the array. Only legal if the array is non-empty.
314 */
315 /////////////////////////////////////////////////////////////////////////
316 PX_INLINE T popBack()
317 {
318 PX_ASSERT(mSize);
319 T t = mData[mSize - 1];
320
321 mData[--mSize].~T();
322
323 return t;
324 }
325
326 /////////////////////////////////////////////////////////////////////////
327 /*!
328 Construct one element at the end of the array. Operation is O(1).
329 */
330 /////////////////////////////////////////////////////////////////////////
331 PX_INLINE T& insert()
332 {
333 if(capacity() <= mSize)
334 grow(capacity: capacityIncrement());
335
336 T* ptr = mData + mSize++;
337 new (ptr) T; // not 'T()' because PODs should not get default-initialized.
338 return *ptr;
339 }
340
341 /////////////////////////////////////////////////////////////////////////
342 /*!
343 Subtracts the element on position i from the array and replace it with
344 the last element.
345 Operation is O(1)
346 \param i
347 The position of the element that will be subtracted from this array.
348 */
349 /////////////////////////////////////////////////////////////////////////
350 PX_INLINE void replaceWithLast(uint32_t i)
351 {
352 PX_ASSERT(i < mSize);
353 mData[i] = mData[--mSize];
354
355 mData[mSize].~T();
356 }
357
358 PX_INLINE void replaceWithLast(Iterator i)
359 {
360 replaceWithLast(static_cast<uint32_t>(i - mData));
361 }
362
363 /////////////////////////////////////////////////////////////////////////
364 /*!
365 Replaces the first occurrence of the element a with the last element
366 Operation is O(n)
367 \param a
368 The position of the element that will be subtracted from this array.
369 \return true if the element has been removed.
370 */
371 /////////////////////////////////////////////////////////////////////////
372
373 PX_INLINE bool findAndReplaceWithLast(const T& a)
374 {
375 uint32_t index = 0;
376 while(index < mSize && mData[index] != a)
377 ++index;
378 if(index == mSize)
379 return false;
380 replaceWithLast(index);
381 return true;
382 }
383
384 /////////////////////////////////////////////////////////////////////////
385 /*!
386 Subtracts the element on position i from the array. Shift the entire
387 array one step.
388 Operation is O(n)
389 \param i
390 The position of the element that will be subtracted from this array.
391 */
392 /////////////////////////////////////////////////////////////////////////
393 PX_INLINE void remove(uint32_t i)
394 {
395 PX_ASSERT(i < mSize);
396
397 T* it = mData + i;
398 it->~T();
399 while (++i < mSize)
400 {
401 new (it) T(mData[i]);
402 ++it;
403 it->~T();
404 }
405 --mSize;
406 }
407
408 /////////////////////////////////////////////////////////////////////////
409 /*!
410 Removes a range from the array. Shifts the array so order is maintained.
411 Operation is O(n)
412 \param begin
413 The starting position of the element that will be subtracted from this array.
414 \param count
415 The number of elments that will be subtracted from this array.
416 */
417 /////////////////////////////////////////////////////////////////////////
418 PX_INLINE void removeRange(uint32_t begin, uint32_t count)
419 {
420 PX_ASSERT(begin < mSize);
421 PX_ASSERT((begin + count) <= mSize);
422
423 for(uint32_t i = 0; i < count; i++)
424 mData[begin + i].~T(); // call the destructor on the ones being removed first.
425
426 T* dest = &mData[begin]; // location we are copying the tail end objects to
427 T* src = &mData[begin + count]; // start of tail objects
428 uint32_t move_count = mSize - (begin + count); // compute remainder that needs to be copied down
429
430 for(uint32_t i = 0; i < move_count; i++)
431 {
432 new (dest) T(*src); // copy the old one to the new location
433 src->~T(); // call the destructor on the old location
434 dest++;
435 src++;
436 }
437 mSize -= count;
438 }
439
440 //////////////////////////////////////////////////////////////////////////
441 /*!
442 Resize array
443 */
444 //////////////////////////////////////////////////////////////////////////
445 PX_NOINLINE void resize(const uint32_t size, const T& a = T());
446
447 PX_NOINLINE void resizeUninitialized(const uint32_t size);
448
449 //////////////////////////////////////////////////////////////////////////
450 /*!
451 Resize array such that only as much memory is allocated to hold the
452 existing elements
453 */
454 //////////////////////////////////////////////////////////////////////////
455 PX_INLINE void shrink()
456 {
457 recreate(capacity: mSize);
458 }
459
460 //////////////////////////////////////////////////////////////////////////
461 /*!
462 Deletes all array elements and frees memory.
463 */
464 //////////////////////////////////////////////////////////////////////////
465 PX_INLINE void reset()
466 {
467 resize(size: 0);
468 shrink();
469 }
470
471 //////////////////////////////////////////////////////////////////////////
472 /*!
473 Ensure that the array has at least size capacity.
474 */
475 //////////////////////////////////////////////////////////////////////////
476 PX_INLINE void reserve(const uint32_t capacity)
477 {
478 if(capacity > this->capacity())
479 grow(capacity);
480 }
481
482 //////////////////////////////////////////////////////////////////////////
483 /*!
484 Query the capacity(allocated mem) for the array.
485 */
486 //////////////////////////////////////////////////////////////////////////
487 PX_FORCE_INLINE uint32_t capacity() const
488 {
489 return mCapacity & ~PX_SIGN_BITMASK;
490 }
491
492 //////////////////////////////////////////////////////////////////////////
493 /*!
494 Unsafe function to force the size of the array
495 */
496 //////////////////////////////////////////////////////////////////////////
497 PX_FORCE_INLINE void forceSize_Unsafe(uint32_t size)
498 {
499 PX_ASSERT(size <= mCapacity);
500 mSize = size;
501 }
502
503 //////////////////////////////////////////////////////////////////////////
504 /*!
505 Swap contents of an array without allocating temporary storage
506 */
507 //////////////////////////////////////////////////////////////////////////
508 PX_INLINE void swap(Array<T, Alloc>& other)
509 {
510 shdfnd::swap(mData, other.mData);
511 shdfnd::swap(mSize, other.mSize);
512 shdfnd::swap(mCapacity, other.mCapacity);
513 }
514
515 //////////////////////////////////////////////////////////////////////////
516 /*!
517 Assign a range of values to this vector (resizes to length of range)
518 */
519 //////////////////////////////////////////////////////////////////////////
520 PX_INLINE void assign(const T* first, const T* last)
521 {
522 resizeUninitialized(size: uint32_t(last - first));
523 copy(begin(), end(), first);
524 }
525
526 // We need one bit to mark arrays that have been deserialized from a user-provided memory block.
527 // For alignment & memory saving purpose we store that bit in the rarely used capacity member.
528 PX_FORCE_INLINE uint32_t isInUserMemory() const
529 {
530 return mCapacity & PX_SIGN_BITMASK;
531 }
532
533 /// return reference to allocator
534 PX_INLINE Alloc& getAllocator()
535 {
536 return *this;
537 }
538
539 protected:
540 // constructor for where we don't own the memory
541 Array(T* memory, uint32_t size, uint32_t capacity, const Alloc& alloc = Alloc())
542 : Alloc(alloc), mData(memory), mSize(size), mCapacity(capacity | PX_SIGN_BITMASK)
543 {
544 }
545
546 template <class A>
547 PX_NOINLINE void copy(const Array<T, A>& other);
548
549 PX_INLINE T* allocate(uint32_t size)
550 {
551 if(size > 0)
552 {
553 T* p = reinterpret_cast<T*>(Alloc::allocate(sizeof(T) * size, __FILE__, __LINE__));
554/**
555Mark a specified amount of memory with 0xcd pattern. This is used to check that the meta data
556definition for serialized classes is complete in checked builds.
557*/
558#if PX_CHECKED
559 if(p)
560 {
561 for(uint32_t i = 0; i < (sizeof(T) * size); ++i)
562 reinterpret_cast<uint8_t*>(p)[i] = 0xcd;
563 }
564#endif
565 return p;
566 }
567 return 0;
568 }
569
570 PX_INLINE void deallocate(void* mem)
571 {
572 Alloc::deallocate(mem);
573 }
574
575 static PX_INLINE void create(T* first, T* last, const T& a)
576 {
577 for(; first < last; ++first)
578 ::new (first) T(a);
579 }
580
581 static PX_INLINE void copy(T* first, T* last, const T* src)
582 {
583 if(last <= first)
584 return;
585
586 for(; first < last; ++first, ++src)
587 ::new (first) T(*src);
588 }
589
590 static PX_INLINE void destroy(T* first, T* last)
591 {
592 for(; first < last; ++first)
593 first->~T();
594 }
595
596 /*!
597 Called when pushBack() needs to grow the array.
598 \param a The element that will be added to this array.
599 */
600 PX_NOINLINE T& growAndPushBack(const T& a);
601
602 /*!
603 Resizes the available memory for the array.
604
605 \param capacity
606 The number of entries that the set should be able to hold.
607 */
608 PX_INLINE void grow(uint32_t capacity)
609 {
610 PX_ASSERT(this->capacity() < capacity);
611 recreate(capacity);
612 }
613
614 /*!
615 Creates a new memory block, copies all entries to the new block and destroys old entries.
616
617 \param capacity
618 The number of entries that the set should be able to hold.
619 */
620 PX_NOINLINE void recreate(uint32_t capacity);
621
622 // The idea here is to prevent accidental bugs with pushBack or insert. Unfortunately
623 // it interacts badly with InlineArrays with smaller inline allocations.
624 // TODO(dsequeira): policy template arg, this is exactly what they're for.
625 PX_INLINE uint32_t capacityIncrement() const
626 {
627 const uint32_t capacity = this->capacity();
628 return capacity == 0 ? 1 : capacity * 2;
629 }
630
631 T* mData;
632 uint32_t mSize;
633 uint32_t mCapacity;
634};
635
636template <class T, class Alloc>
637PX_NOINLINE void Array<T, Alloc>::resize(const uint32_t size, const T& a)
638{
639 reserve(capacity: size);
640 create(first: mData + mSize, last: mData + size, a);
641 destroy(first: mData + size, last: mData + mSize);
642 mSize = size;
643}
644
645template <class T, class Alloc>
646template <class A>
647PX_NOINLINE void Array<T, Alloc>::copy(const Array<T, A>& other)
648{
649 if(!other.empty())
650 {
651 mData = allocate(size: mSize = mCapacity = other.size());
652 copy(mData, mData + mSize, other.begin());
653 }
654 else
655 {
656 mData = NULL;
657 mSize = 0;
658 mCapacity = 0;
659 }
660
661 // mData = allocate(other.mSize);
662 // mSize = other.mSize;
663 // mCapacity = other.mSize;
664 // copy(mData, mData + mSize, other.mData);
665}
666
667template <class T, class Alloc>
668PX_NOINLINE void Array<T, Alloc>::resizeUninitialized(const uint32_t size)
669{
670 reserve(capacity: size);
671 mSize = size;
672}
673
674template <class T, class Alloc>
675PX_NOINLINE T& Array<T, Alloc>::growAndPushBack(const T& a)
676{
677 uint32_t capacity = capacityIncrement();
678
679 T* newData = allocate(size: capacity);
680 PX_ASSERT((!capacity) || (newData && (newData != mData)));
681 copy(newData, newData + mSize, mData);
682
683 // inserting element before destroying old array
684 // avoids referencing destroyed object when duplicating array element.
685 PX_PLACEMENT_NEW(reinterpret_cast<void*>(newData + mSize), T)(a);
686
687 destroy(first: mData, last: mData + mSize);
688 if(!isInUserMemory())
689 deallocate(mem: mData);
690
691 mData = newData;
692 mCapacity = capacity;
693
694 return mData[mSize++];
695}
696
697template <class T, class Alloc>
698PX_NOINLINE void Array<T, Alloc>::recreate(uint32_t capacity)
699{
700 T* newData = allocate(size: capacity);
701 PX_ASSERT((!capacity) || (newData && (newData != mData)));
702
703 copy(newData, newData + mSize, mData);
704 destroy(first: mData, last: mData + mSize);
705 if(!isInUserMemory())
706 deallocate(mem: mData);
707
708 mData = newData;
709 mCapacity = capacity;
710}
711
712template <class T, class Alloc>
713PX_INLINE void swap(Array<T, Alloc>& x, Array<T, Alloc>& y)
714{
715 x.swap(y);
716}
717
718} // namespace shdfnd
719} // namespace physx
720
721#endif // #ifndef PSFOUNDATION_PSARRAY_H
722

source code of qtquick3dphysics/src/3rdparty/PhysX/source/foundation/include/PsArray.h