E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsArray.h
Go to the documentation of this file.00001 // This code contains NVIDIA Confidential Information and is disclosed to you 00002 // under a form of NVIDIA software license agreement provided separately to you. 00003 // 00004 // Notice 00005 // NVIDIA Corporation and its licensors retain all intellectual property and 00006 // proprietary rights in and to this software and related documentation and 00007 // any modifications thereto. Any use, reproduction, disclosure, or 00008 // distribution of this software and related documentation without an express 00009 // license agreement from NVIDIA Corporation is strictly prohibited. 00010 // 00011 // ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES 00012 // NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO 00013 // THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, 00014 // MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. 00015 // 00016 // Information and code furnished is believed to be accurate and reliable. 00017 // However, NVIDIA Corporation assumes no responsibility for the consequences of use of such 00018 // information or for any infringement of patents or other rights of third parties that may 00019 // result from its use. No license is granted by implication or otherwise under any patent 00020 // or patent rights of NVIDIA Corporation. Details are subject to change without notice. 00021 // This code supersedes and replaces all information previously supplied. 00022 // NVIDIA Corporation products are not authorized for use as critical 00023 // components in life support devices or systems without express written approval of 00024 // NVIDIA Corporation. 00025 // 00026 // Copyright (c) 2008-2014 NVIDIA Corporation. All rights reserved. 00027 // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved. 00028 // Copyright (c) 2001-2004 NovodeX AG. All rights reserved. 00029 00030 #ifndef PSFOUNDATION_PSARRAY_H 00031 #define PSFOUNDATION_PSARRAY_H 00032 00033 #include "foundation/PxAssert.h" 00034 #include "foundation/PxIntrinsics.h" 00035 #include "PsAllocator.h" 00036 #include "PsBasicTemplates.h" 00037 00038 #if PX_LINUX || PX_ANDROID || (PX_IOS && !PX_A64) || PX_OSX 00039 #include <tr1/type_traits> 00040 #elif PX_WINRT || PX_XBOXONE || (PX_IOS && PX_A64) || PX_WIN64 || PX_WIN32 || PX_PS4 00041 #include <type_traits> 00042 #if PX_IOS && PX_A64 00043 namespace std { namespace tr1 { using std::is_pod; } } 00044 #endif 00045 #else 00046 #error "OS with no defined path to type_traits.h" 00047 #endif 00048 00049 #if PX_VC == 9 || PX_VC == 10 00050 #pragma warning(push) 00051 #pragma warning(disable : 4347) // behavior change: 'function template' is called instead of 'function' 00052 #endif 00053 00054 namespace physx 00055 { 00056 namespace shdfnd 00057 { 00058 template <class Serializer> 00059 void exportArray(Serializer& stream, const void* data, uint32_t size, uint32_t sizeOfElement, uint32_t capacity); 00060 char* importArray(char* address, void** data, uint32_t size, uint32_t sizeOfElement, uint32_t capacity); 00061 00072 template <class T, class Alloc = typename AllocatorTraits<T>::Type> 00073 class Array : protected Alloc 00074 { 00075 public: 00076 typedef T* Iterator; 00077 typedef const T* ConstIterator; 00078 00079 explicit Array(const PxEMPTY v) : Alloc(v) 00080 { 00081 if(mData) 00082 mCapacity |= PX_SIGN_BITMASK; 00083 } 00084 00088 PX_INLINE explicit Array(const Alloc& alloc = Alloc()) : Alloc(alloc), mData(0), mSize(0), mCapacity(0) 00089 { 00090 } 00091 00095 PX_INLINE explicit Array(uint32_t size, const T& a = T(), const Alloc& alloc = Alloc()) 00096 : Alloc(alloc), mData(0), mSize(0), mCapacity(0) 00097 { 00098 resize(size, a); 00099 } 00100 00104 template <class A> 00105 PX_INLINE explicit Array(const Array<T, A>& other, const Alloc& alloc = Alloc()) 00106 : Alloc(alloc) 00107 { 00108 copy(other); 00109 } 00110 00111 // This is necessary else the basic default copy constructor is used in the case of both arrays being of the same 00112 // template instance 00113 // The C++ standard clearly states that a template constructor is never a copy constructor [2]. In other words, 00114 // the presence of a template constructor does not suppress the implicit declaration of the copy constructor. 00115 // Also never make a copy constructor explicit, or copy-initialization* will no longer work. This is because 00116 // 'binding an rvalue to a const reference requires an accessible copy constructor' (http://gcc.gnu.org/bugs/) 00117 // *http://stackoverflow.com/questions/1051379/is-there-a-difference-in-c-between-copy-initialization-and-assignment-initializ 00118 PX_INLINE Array(const Array& other, const Alloc& alloc = Alloc()) : Alloc(alloc) 00119 { 00120 copy(other); 00121 } 00122 00126 PX_INLINE explicit Array(const T* first, const T* last, const Alloc& alloc = Alloc()) 00127 : Alloc(alloc), mSize(last < first ? 0 : uint32_t(last - first)), mCapacity(mSize) 00128 { 00129 mData = allocate(mSize); 00130 copy(mData, mData + mSize, first); 00131 } 00132 00136 PX_INLINE ~Array() 00137 { 00138 destroy(mData, mData + mSize); 00139 00140 if(capacity() && !isInUserMemory()) 00141 deallocate(mData); 00142 } 00143 00147 template <class A> 00148 PX_INLINE Array& operator=(const Array<T, A>& rhs) 00149 { 00150 if(&rhs == this) 00151 return *this; 00152 00153 clear(); 00154 reserve(rhs.mSize); 00155 copy(mData, mData + rhs.mSize, rhs.mData); 00156 00157 mSize = rhs.mSize; 00158 return *this; 00159 } 00160 00161 PX_INLINE Array& operator=(const Array& t) // Needs to be declared, see comment at copy-constructor 00162 { 00163 return operator=<Alloc>(t); 00164 } 00165 00166 PX_FORCE_INLINE static bool isArrayOfPOD() 00167 { 00168 #if PX_VC>=14 00169 return std::is_trivially_copyable<T>::value; 00170 #else 00171 return std::tr1::is_pod<T>::value; 00172 #endif 00173 } 00174 00182 PX_FORCE_INLINE const T& operator[](uint32_t i) const 00183 { 00184 PX_ASSERT(i < mSize); 00185 return mData[i]; 00186 } 00187 00195 PX_FORCE_INLINE T& operator[](uint32_t i) 00196 { 00197 PX_ASSERT(i < mSize); 00198 return mData[i]; 00199 } 00200 00206 PX_FORCE_INLINE ConstIterator begin() const 00207 { 00208 return mData; 00209 } 00210 00211 PX_FORCE_INLINE Iterator begin() 00212 { 00213 return mData; 00214 } 00215 00222 PX_FORCE_INLINE ConstIterator end() const 00223 { 00224 return mData + mSize; 00225 } 00226 00227 PX_FORCE_INLINE Iterator end() 00228 { 00229 return mData + mSize; 00230 } 00231 00237 PX_FORCE_INLINE const T& front() const 00238 { 00239 PX_ASSERT(mSize); 00240 return mData[0]; 00241 } 00242 00243 PX_FORCE_INLINE T& front() 00244 { 00245 PX_ASSERT(mSize); 00246 return mData[0]; 00247 } 00248 00254 PX_FORCE_INLINE const T& back() const 00255 { 00256 PX_ASSERT(mSize); 00257 return mData[mSize - 1]; 00258 } 00259 00260 PX_FORCE_INLINE T& back() 00261 { 00262 PX_ASSERT(mSize); 00263 return mData[mSize - 1]; 00264 } 00265 00272 PX_FORCE_INLINE uint32_t size() const 00273 { 00274 return mSize; 00275 } 00276 00280 PX_INLINE void clear() 00281 { 00282 destroy(mData, mData + mSize); 00283 mSize = 0; 00284 } 00285 00291 PX_FORCE_INLINE bool empty() const 00292 { 00293 return mSize == 0; 00294 } 00295 00302 PX_INLINE Iterator find(const T& a) 00303 { 00304 uint32_t index; 00305 for(index = 0; index < mSize && mData[index] != a; index++) 00306 ; 00307 return mData + index; 00308 } 00309 00310 PX_INLINE ConstIterator find(const T& a) const 00311 { 00312 uint32_t index; 00313 for(index = 0; index < mSize && mData[index] != a; index++) 00314 ; 00315 return mData + index; 00316 } 00317 00319 00324 00325 00326 PX_FORCE_INLINE T& pushBack(const T& a) 00327 { 00328 if(capacity() <= mSize) 00329 return growAndPushBack(a); 00330 00331 PX_PLACEMENT_NEW(reinterpret_cast<void*>(mData + mSize), T)(a); 00332 00333 return mData[mSize++]; 00334 } 00335 00337 00340 00341 PX_INLINE T popBack() 00342 { 00343 PX_ASSERT(mSize); 00344 T t = mData[mSize - 1]; 00345 00346 if (!isArrayOfPOD()) 00347 { 00348 mData[--mSize].~T(); 00349 } 00350 else 00351 { 00352 --mSize; 00353 } 00354 00355 return t; 00356 } 00357 00359 00362 00363 PX_INLINE T& insert() 00364 { 00365 if(capacity() <= mSize) 00366 grow(capacityIncrement()); 00367 00368 T* ptr = mData + mSize++; 00369 new (ptr) T; // not 'T()' because PODs should not get default-initialized. 00370 return *ptr; 00371 } 00372 00374 00381 00382 PX_INLINE void replaceWithLast(uint32_t i) 00383 { 00384 PX_ASSERT(i < mSize); 00385 mData[i] = mData[--mSize]; 00386 00387 if (!isArrayOfPOD()) 00388 { 00389 mData[mSize].~T(); 00390 } 00391 } 00392 00393 PX_INLINE void replaceWithLast(Iterator i) 00394 { 00395 replaceWithLast(static_cast<uint32_t>(i - mData)); 00396 } 00397 00399 00406 00407 00408 PX_INLINE bool findAndReplaceWithLast(const T& a) 00409 { 00410 uint32_t index = 0; 00411 while(index < mSize && mData[index] != a) 00412 ++index; 00413 if(index == mSize) 00414 return false; 00415 replaceWithLast(index); 00416 return true; 00417 } 00418 00420 00427 00428 PX_INLINE void remove(uint32_t i) 00429 { 00430 PX_ASSERT(i < mSize); 00431 00432 if (isArrayOfPOD()) 00433 { 00434 if (i + 1 != mSize) 00435 { 00436 physx::intrinsics::memMove(mData + i, mData + i + 1, (mSize - i - 1) * sizeof(T)); 00437 } 00438 } 00439 else 00440 { 00441 for(T* it = mData + i; it->~T(), ++i < mSize; ++it) 00442 new (it) T(mData[i]); 00443 } 00444 00445 --mSize; 00446 } 00447 00449 00457 00458 PX_INLINE void removeRange(uint32_t begin, uint32_t count) 00459 { 00460 PX_ASSERT(begin < mSize); 00461 PX_ASSERT((begin + count) <= mSize); 00462 00463 if (!isArrayOfPOD()) 00464 { 00465 for(uint32_t i = 0; i < count; i++) 00466 { 00467 mData[begin + i].~T(); // call the destructor on the ones being removed first. 00468 } 00469 } 00470 00471 T* dest = &mData[begin]; // location we are copying the tail end objects to 00472 T* src = &mData[begin + count]; // start of tail objects 00473 uint32_t move_count = mSize - (begin + count); // compute remainder that needs to be copied down 00474 00475 if (isArrayOfPOD()) 00476 { 00477 physx::intrinsics::memMove(dest, src, move_count * sizeof(T)); 00478 } 00479 else 00480 { 00481 for(uint32_t i = 0; i < move_count; i++) 00482 { 00483 new (dest) T(*src); // copy the old one to the new location 00484 src->~T(); // call the destructor on the old location 00485 dest++; 00486 src++; 00487 } 00488 } 00489 mSize -= count; 00490 } 00491 00493 00496 00497 PX_NOINLINE void resize(const uint32_t size, const T& a = T()); 00498 00499 PX_NOINLINE void resizeUninitialized(const uint32_t size); 00500 00502 00506 00507 PX_INLINE void shrink() 00508 { 00509 recreate(mSize); 00510 } 00511 00513 00516 00517 PX_INLINE void reset() 00518 { 00519 resize(0); 00520 shrink(); 00521 } 00522 00524 00527 00528 PX_INLINE void reserve(const uint32_t capacity) 00529 { 00530 if(capacity > this->capacity()) 00531 grow(capacity); 00532 } 00533 00535 00538 00539 PX_FORCE_INLINE uint32_t capacity() const 00540 { 00541 return mCapacity & ~PX_SIGN_BITMASK; 00542 } 00543 00545 00548 00549 PX_FORCE_INLINE void forceSize_Unsafe(uint32_t size) 00550 { 00551 PX_ASSERT(size <= mCapacity); 00552 mSize = size; 00553 } 00554 00556 00559 00560 PX_INLINE void swap(Array<T, Alloc>& other) 00561 { 00562 shdfnd::swap(mData, other.mData); 00563 shdfnd::swap(mSize, other.mSize); 00564 shdfnd::swap(mCapacity, other.mCapacity); 00565 } 00566 00568 00571 00572 PX_INLINE void assign(const T* first, const T* last) 00573 { 00574 resizeUninitialized(uint32_t(last - first)); 00575 copy(begin(), end(), first); 00576 } 00577 00578 // We need one bit to mark arrays that have been deserialized from a user-provided memory block. 00579 // For alignment & memory saving purpose we store that bit in the rarely used capacity member. 00580 PX_FORCE_INLINE uint32_t isInUserMemory() const 00581 { 00582 return mCapacity & PX_SIGN_BITMASK; 00583 } 00584 00586 PX_INLINE Alloc& getAllocator() 00587 { 00588 return *this; 00589 } 00590 00591 protected: 00592 // constructor for where we don't own the memory 00593 Array(T* memory, uint32_t size, uint32_t capacity, const Alloc& alloc = Alloc()) 00594 : Alloc(alloc), mData(memory), mSize(size), mCapacity(capacity | PX_SIGN_BITMASK) 00595 { 00596 } 00597 00598 template <class A> 00599 PX_NOINLINE void copy(const Array<T, A>& other); 00600 00601 PX_INLINE T* allocate(uint32_t size) 00602 { 00603 if(size > 0) 00604 { 00605 T* p = reinterpret_cast<T*>(Alloc::allocate(sizeof(T) * size, __FILE__, __LINE__)); 00610 #if PX_CHECKED 00611 if(p) 00612 { 00613 for(uint32_t i = 0; i < (sizeof(T) * size); ++i) 00614 reinterpret_cast<uint8_t*>(p)[i] = 0xcd; 00615 } 00616 #endif 00617 return p; 00618 } 00619 return 0; 00620 } 00621 00622 PX_INLINE void deallocate(void* mem) 00623 { 00624 Alloc::deallocate(mem); 00625 } 00626 00627 static PX_INLINE bool isZeroInit(const T& object) 00628 { 00629 char ZeroBuffOnStack[sizeof(object)] = {}; 00630 return memcmp(&object, ZeroBuffOnStack, sizeof(object)) == 0; 00631 } 00632 00633 static PX_INLINE void create(T* first, T* last, const T& a) 00634 { 00635 if (isArrayOfPOD() && isZeroInit(a)) 00636 { 00637 if(last>first) 00638 physx::intrinsics::memZero(first, uint32_t((last-first) * sizeof(T))); 00639 } 00640 else 00641 { 00642 for(; first<last; ++first) 00643 ::new(first)T(a); 00644 } 00645 } 00646 00647 static PX_INLINE void copy(T* first, T* last, const T* src) 00648 { 00649 if (last <= first) 00650 return; 00651 00652 if (isArrayOfPOD()) 00653 { 00654 physx::intrinsics::memCopy(first, src, uint32_t((last-first) * sizeof(T))); 00655 } 00656 else 00657 { 00658 for(; first<last; ++first, ++src) 00659 ::new (first)T(*src); 00660 } 00661 } 00662 00663 static PX_INLINE void destroy(T* first, T* last) 00664 { 00665 if (!isArrayOfPOD()) 00666 { 00667 for(; first < last; ++first) 00668 first->~T(); 00669 } 00670 } 00671 00676 PX_NOINLINE T& growAndPushBack(const T& a); 00677 00684 PX_INLINE void grow(uint32_t capacity) 00685 { 00686 PX_ASSERT(this->capacity() < capacity); 00687 recreate(capacity); 00688 } 00689 00696 PX_NOINLINE void recreate(uint32_t capacity); 00697 00698 // The idea here is to prevent accidental bugs with pushBack or insert. Unfortunately 00699 // it interacts badly with InlineArrays with smaller inline allocations. 00700 // TODO(dsequeira): policy template arg, this is exactly what they're for. 00701 PX_INLINE uint32_t capacityIncrement() const 00702 { 00703 const uint32_t capacity = this->capacity(); 00704 return capacity == 0 ? 1 : capacity * 2; 00705 } 00706 00707 T* mData; 00708 uint32_t mSize; 00709 uint32_t mCapacity; 00710 }; 00711 00712 template <class T, class Alloc> 00713 PX_NOINLINE void Array<T, Alloc>::resize(const uint32_t size, const T& a) 00714 { 00715 reserve(size); 00716 create(mData + mSize, mData + size, a); 00717 destroy(mData + size, mData + mSize); 00718 mSize = size; 00719 } 00720 00721 template <class T, class Alloc> 00722 template <class A> 00723 PX_NOINLINE void Array<T, Alloc>::copy(const Array<T, A>& other) 00724 { 00725 if(!other.empty()) 00726 { 00727 mData = allocate(mSize = mCapacity = other.size()); 00728 copy(mData, mData + mSize, other.begin()); 00729 } 00730 else 00731 { 00732 mData = NULL; 00733 mSize = 0; 00734 mCapacity = 0; 00735 } 00736 00737 // mData = allocate(other.mSize); 00738 // mSize = other.mSize; 00739 // mCapacity = other.mSize; 00740 // copy(mData, mData + mSize, other.mData); 00741 } 00742 00743 template <class T, class Alloc> 00744 PX_NOINLINE void Array<T, Alloc>::resizeUninitialized(const uint32_t size) 00745 { 00746 reserve(size); 00747 mSize = size; 00748 } 00749 00750 template <class T, class Alloc> 00751 PX_NOINLINE T& Array<T, Alloc>::growAndPushBack(const T& a) 00752 { 00753 uint32_t capacity = capacityIncrement(); 00754 00755 T* newData = allocate(capacity); 00756 PX_ASSERT((!capacity) || (newData && (newData != mData))); 00757 copy(newData, newData + mSize, mData); 00758 00759 // inserting element before destroying old array 00760 // avoids referencing destroyed object when duplicating array element. 00761 PX_PLACEMENT_NEW(reinterpret_cast<void*>(newData + mSize), T)(a); 00762 00763 destroy(mData, mData + mSize); 00764 if(!isInUserMemory()) 00765 deallocate(mData); 00766 00767 mData = newData; 00768 mCapacity = capacity; 00769 00770 return mData[mSize++]; 00771 } 00772 00773 template <class T, class Alloc> 00774 PX_NOINLINE void Array<T, Alloc>::recreate(uint32_t capacity) 00775 { 00776 T* newData = allocate(capacity); 00777 PX_ASSERT((!capacity) || (newData && (newData != mData))); 00778 00779 copy(newData, newData + mSize, mData); 00780 destroy(mData, mData + mSize); 00781 if(!isInUserMemory()) 00782 deallocate(mData); 00783 00784 mData = newData; 00785 mCapacity = capacity; 00786 } 00787 00788 template <class T, class Alloc> 00789 PX_INLINE void swap(Array<T, Alloc>& x, Array<T, Alloc>& y) 00790 { 00791 x.swap(y); 00792 } 00793 00794 } // namespace shdfnd 00795 } // namespace physx 00796 00797 #if PX_VC == 9 || PX_VC == 10 00798 #pragma warning(pop) 00799 #endif 00800 00801 #endif // #ifndef PSFOUNDATION_PSARRAY_H
Generated on Tue Jul 28 14:21:55 2015 for NVIDIA(R) PsFoundation Reference by
![doxygen](doxygen.png)