Revision control
Copy as Markdown
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
#ifndef PX_ARRAY_H
#define PX_ARRAY_H
#include "foundation/PxAssert.h"
#include "foundation/PxMathIntrinsics.h"
#include "foundation/PxAllocator.h"
#include "foundation/PxBasicTemplates.h"
#include "foundation/PxMemory.h"
#include "foundation/PxIO.h"
#if !PX_DOXYGEN
namespace physx
{
#endif
/*!
\brief An array is a sequential container.
Implementation note:
- entries between 0 and size are valid objects
- we use inheritance to build this because the array is included inline in a lot
of objects and we want the allocator to take no space if it's not stateful, which
aggregation doesn't allow. Also, we want the metadata at the front for the inline
case where the allocator contains some inline storage space
\tparam T Element type
\tparam Alloc Allocator type (defaults to PxAllocatorTraits<T>::Type)
*/
#if !PX_DOXYGEN
template <class T, class Alloc = typename PxAllocatorTraits<T>::Type>
class PxArray : protected Alloc
#else
template <class T, class Alloc> class PxArray
#endif
{
public:
typedef T* Iterator;
typedef const T* ConstIterator;
/*!
\brief Deserialization constructor.
\param v Empty tag for deserialization
*/
explicit PxArray(const PxEMPTY v) : Alloc(v)
{
if(mData)
mCapacity |= PX_SIGN_BITMASK;
}
/*!
\brief Default array constructor. Initialize an empty array
\param alloc Allocator to use
*/
PX_INLINE explicit PxArray(const Alloc& alloc = Alloc()) : Alloc(alloc), mData(0), mSize(0), mCapacity(0)
{
}
/*!
\brief Initialize array with given size
\param size Initial size (and capacity) of the array
\param a Default value for elements
\param alloc Allocator to use
*/
PX_INLINE explicit PxArray(uint32_t size, const T& a = T(), const Alloc& alloc = Alloc())
: Alloc(alloc), mData(0), mSize(0), mCapacity(0)
{
resize(size, a);
}
/*!
\brief Copy-constructor. Copy all entries from other array
\param other Source array to copy from
\param alloc Allocator to use
*/
template <class A>
PX_INLINE explicit PxArray(const PxArray<T, A>& other, const Alloc& alloc = Alloc())
: Alloc(alloc)
{
copy(other);
}
// This is necessary else the basic default copy constructor is used in the case of both arrays being of the same
// template instance
// The C++ standard clearly states that a template constructor is never a copy constructor [2]. In other words,
// the presence of a template constructor does not suppress the implicit declaration of the copy constructor.
// Also never make a copy constructor explicit, or copy-initialization* will no longer work. This is because
// 'binding an rvalue to a const reference requires an accessible copy constructor' (http://gcc.gnu.org/bugs/)
PX_INLINE PxArray(const PxArray& other, const Alloc& alloc = Alloc()) : Alloc(alloc)
{
copy(other);
}
/*!
\brief Initialize array with given length
\param first Pointer to the first element to copy
\param last Pointer past the last element to copy
\param alloc Allocator to use
*/
PX_INLINE explicit PxArray(const T* first, const T* last, const Alloc& alloc = Alloc())
: Alloc(alloc), mSize(last < first ? 0 : uint32_t(last - first)), mCapacity(mSize)
{
mData = allocate(mSize);
if(mData)
copy(mData, mData + mSize, first);
}
/*!
\brief Destructor
*/
PX_INLINE ~PxArray()
{
destroy(mData, mData + mSize);
if(capacity() && !isInUserMemory())
deallocate(mData);
}
/*!
\brief Assignment operator. Copy content (deep-copy)
\param rhs Source array to copy from
\return Reference to this array
*/
template <class A>
PX_INLINE PxArray& operator=(const PxArray<T, A>& rhs)
{
if(&rhs == this)
return *this;
clear();
reserve(rhs.mSize);
copy(mData, mData + rhs.mSize, rhs.mData);
mSize = rhs.mSize;
return *this;
}
PX_INLINE PxArray& operator=(const PxArray& t) // Needs to be declared, see comment at copy-constructor
{
return operator=<Alloc>(t);
}
/*!
\brief Array indexing operator.
\param i The index of the element that will be returned.
\return The element i in the array.
*/
PX_FORCE_INLINE const T& operator[](uint32_t i) const
{
PX_ASSERT(i < mSize);
return mData[i];
}
/*!
\brief Array indexing operator.
\param i The index of the element that will be returned.
\return The element i in the array.
*/
PX_FORCE_INLINE T& operator[](uint32_t i)
{
PX_ASSERT(i < mSize);
return mData[i];
}
/*!
\brief Returns a pointer to the first element of the array.
\return Pointer to the first element of the array.
*/
PX_FORCE_INLINE ConstIterator begin() const
{
return mData;
}
PX_FORCE_INLINE Iterator begin()
{
return mData;
}
/*!
\brief Returns a pointer beyond the last element of the array. Do not dereference.
\return Pointer to the element beyond the last element of the array.
*/
PX_FORCE_INLINE ConstIterator end() const
{
return mData + mSize;
}
PX_FORCE_INLINE Iterator end()
{
return mData + mSize;
}
/*!
\brief Returns a reference to the first element of the array. Undefined if the array is empty.
\return Reference to the first element of the array
*/
PX_FORCE_INLINE const T& front() const
{
PX_ASSERT(mSize);
return mData[0];
}
PX_FORCE_INLINE T& front()
{
PX_ASSERT(mSize);
return mData[0];
}
/*!
\brief Returns a reference to the last element of the array. Undefined if the array is empty.
\return Reference to the last element of the array
*/
PX_FORCE_INLINE const T& back() const
{
PX_ASSERT(mSize);
return mData[mSize - 1];
}
PX_FORCE_INLINE T& back()
{
PX_ASSERT(mSize);
return mData[mSize - 1];
}
/*!
\brief Returns the number of entries in the array. This can, and probably will,
differ from the array capacity.
\return The number of entries in the array.
*/
PX_FORCE_INLINE uint32_t size() const
{
return mSize;
}
/*!
\brief Clears the array.
Calls destructor on all elements.
*/
PX_INLINE void clear()
{
destroy(mData, mData + mSize);
mSize = 0;
}
/*!
\brief Returns whether the array is empty (i.e. whether its size is 0).
\return True if the array is empty
*/
PX_FORCE_INLINE bool empty() const
{
return mSize == 0;
}
/*!
\brief Finds the first occurrence of an element in the array.
\param a The element to find.
\return Pointer to the found element or end() if not found
*/
PX_INLINE Iterator find(const T& a)
{
uint32_t index;
for(index = 0; index < mSize && mData[index] != a; index++)
;
return mData + index;
}
PX_INLINE ConstIterator find(const T& a) const
{
uint32_t index;
for(index = 0; index < mSize && mData[index] != a; index++)
;
return mData + index;
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Adds one element to the end of the array. Operation is O(1).
\param a The element that will be added to this array.
\return Pointer to the element that has been added, NULL if operation failed.
*/
/////////////////////////////////////////////////////////////////////////
PX_FORCE_INLINE T* pushBack(const T& a)
{
if(capacity() <= mSize)
return growAndPushBack(a);
PX_PLACEMENT_NEW(reinterpret_cast<void*>(mData + mSize), T)(a);
return &mData[mSize++];
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Removes and returns the element at the end of the array. Only legal if the array is non-empty.
\return The last element of the array
*/
/////////////////////////////////////////////////////////////////////////
PX_INLINE T popBack()
{
PX_ASSERT(mSize);
T t = mData[mSize - 1];
mData[--mSize].~T();
return t;
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Construct one element at the end of the array. Operation is O(1).
\return Pointer to the element that has been inserted, NULL if operation failed.
*/
/////////////////////////////////////////////////////////////////////////
PX_INLINE T* insert()
{
if(capacity() <= mSize)
{
if (!grow(capacityIncrement()))
{
return NULL;
}
}
T* ptr = mData + mSize++;
PX_PLACEMENT_NEW(ptr, T); // not 'T()' because PODs should not get default-initialized.
return ptr;
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Removes the element at position i from the array and replaces it with
the last element. Operation is O(1)
\param i The position of the element that will be removed from this array.
*/
/////////////////////////////////////////////////////////////////////////
PX_INLINE void replaceWithLast(uint32_t i)
{
PX_ASSERT(i < mSize);
mData[i] = mData[--mSize];
mData[mSize].~T();
}
PX_INLINE void replaceWithLast(Iterator i)
{
replaceWithLast(static_cast<uint32_t>(i - mData));
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Replaces the first occurrence of the element a with the last element.
Operation is O(n)
\param a The element to find and remove from this array.
\return True if the element has been removed.
*/
/////////////////////////////////////////////////////////////////////////
PX_INLINE bool findAndReplaceWithLast(const T& a)
{
uint32_t index = 0;
while(index < mSize && mData[index] != a)
++index;
if(index == mSize)
return false;
replaceWithLast(index);
return true;
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Subtracts the element on position i from the array. Shift the entire
array one step. Operation is O(n)
\param i The position of the element that will be subtracted from this array.
*/
/////////////////////////////////////////////////////////////////////////
PX_INLINE void remove(uint32_t i)
{
PX_ASSERT(i < mSize);
T* it = mData + i;
it->~T();
while (++i < mSize)
{
PX_PLACEMENT_NEW(it, T(mData[i]));
++it;
it->~T();
}
--mSize;
}
/////////////////////////////////////////////////////////////////////////
/*!
\brief Removes a range from the array. Shifts the array so order is maintained.
Operation is O(n)
\param begin The starting position of the element that will be subtracted from this array.
\param count The number of elements that will be subtracted from this array.
*/
/////////////////////////////////////////////////////////////////////////
PX_INLINE void removeRange(uint32_t begin, uint32_t count)
{
PX_ASSERT(begin < mSize);
PX_ASSERT((begin + count) <= mSize);
for(uint32_t i = 0; i < count; i++)
mData[begin + i].~T(); // call the destructor on the ones being removed first.
T* dest = &mData[begin]; // location we are copying the tail end objects to
T* src = &mData[begin + count]; // start of tail objects
uint32_t move_count = mSize - (begin + count); // compute remainder that needs to be copied down
for(uint32_t i = 0; i < move_count; i++)
{
PX_PLACEMENT_NEW(dest, T(*src)); // copy the old one to the new location
src->~T(); // call the destructor on the old location
dest++;
src++;
}
mSize -= count;
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Resize array
\param size New size of the array
\param a Default value for new elements
\return True if operation succeeded
*/
//////////////////////////////////////////////////////////////////////////
PX_NOINLINE bool resize(const uint32_t size, const T& a = T());
/*!
\brief Resize array without initializing new elements
\param size New size of the array
\return True if operation succeeded
*/
PX_NOINLINE bool resizeUninitialized(const uint32_t size);
//////////////////////////////////////////////////////////////////////////
/*!
\brief Resize array such that only as much memory is allocated to hold the
existing elements
\return True if operation succeeds, false otherwise.
*/
//////////////////////////////////////////////////////////////////////////
PX_INLINE bool shrink()
{
return recreate(mSize);
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Deletes all array elements and frees memory.
*/
//////////////////////////////////////////////////////////////////////////
PX_INLINE void reset()
{
resize(0);
shrink();
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Resets or clears the array depending on occupancy.
*/
//////////////////////////////////////////////////////////////////////////
PX_INLINE void resetOrClear()
{
const PxU32 c = capacity();
const PxU32 s = size();
if(s>=c/2)
clear();
else
reset();
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Ensure that the array has at least the requested capacity.
\param capacity Minimum capacity to reserve
\return True if operation succeeds, false otherwise.
*/
//////////////////////////////////////////////////////////////////////////
PX_INLINE bool reserve(const uint32_t capacity)
{
if(capacity > this->capacity())
return grow(capacity);
return true;
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Query the capacity(allocated mem) for the array.
\return The capacity of the array
*/
//////////////////////////////////////////////////////////////////////////
PX_FORCE_INLINE uint32_t capacity() const
{
return mCapacity & ~PX_SIGN_BITMASK;
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Unsafe function to force the size of the array
\param size New size to force
*/
//////////////////////////////////////////////////////////////////////////
PX_FORCE_INLINE void forceSize_Unsafe(uint32_t size)
{
PX_ASSERT(size <= capacity());
mSize = size;
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Swap contents of an array without allocating temporary storage
\param other Array to swap with
*/
//////////////////////////////////////////////////////////////////////////
PX_INLINE void swap(PxArray<T, Alloc>& other)
{
PxSwap(mData, other.mData);
PxSwap(mSize, other.mSize);
PxSwap(mCapacity, other.mCapacity);
}
//////////////////////////////////////////////////////////////////////////
/*!
\brief Assign a range of values to this array (resizes to length of range)
\param first Pointer to the first element to copy
\param last Pointer past the last element to copy
\return True if operation succeeds, false otherwise.
*/
//////////////////////////////////////////////////////////////////////////
PX_INLINE bool assign(const T* first, const T* last)
{
if(!resizeUninitialized(uint32_t(last - first)))
return false;
copy(begin(), end(), first);
return true;
}
// We need one bit to mark arrays that have been deserialized from a user-provided memory block.
// For alignment & memory saving purpose we store that bit in the rarely used capacity member.
PX_FORCE_INLINE uint32_t isInUserMemory() const
{
return mCapacity & PX_SIGN_BITMASK;
}
/// return reference to allocator
PX_INLINE Alloc& getAllocator()
{
return *this;
}
protected:
// constructor for where we don't own the memory
PxArray(T* memory, uint32_t size, uint32_t capacity, const Alloc& alloc = Alloc())
: Alloc(alloc), mData(memory), mSize(size), mCapacity(capacity | PX_SIGN_BITMASK)
{
}
template <class A>
PX_NOINLINE void copy(const PxArray<T, A>& other);
PX_INLINE T* allocate(uint32_t size, uint32_t* cookie=NULL)
{
// always call Alloc::allocate to respect cookie logic even if size is 0
T* p = reinterpret_cast<T*>(Alloc::allocate(sizeof(T) * size, PX_FL, cookie));
if(size > 0)
{
if(p)
{
PxMarkSerializedMemory(p, sizeof(T) * size);
}
else
{
PxGetFoundation().error(PxErrorCode::eOUT_OF_MEMORY, PX_FL, "PxArray::allocate: allocator returned null pointer.");
}
}
return p;
}
PX_INLINE void deallocate(void* mem, uint32_t* cookie=NULL)
{
Alloc::deallocate(mem, cookie);
}
static PX_INLINE void create(T* first, T* last, const T& a)
{
for(; first < last; ++first)
::PX_PLACEMENT_NEW(first, T(a));
}
static PX_INLINE void copy(T* first, T* last, const T* src)
{
if(last <= first)
return;
for(; first < last; ++first, ++src)
::PX_PLACEMENT_NEW(first, T(*src));
}
static PX_INLINE void destroy(T* first, T* last)
{
for(; first < last; ++first)
first->~T();
}
/*!
\brief Called when pushBack() needs to grow the array.
\param a The element that will be added to this array.
\return Pointer to the pushed element or NULL if the operation failed
*/
PX_NOINLINE T* growAndPushBack(const T& a);
/*!
\brief Resizes the available memory for the array.
\param capacity The number of entries that the array should be able to hold.
\return True if operation succeeds, false otherwise.
*/
PX_INLINE bool grow(uint32_t capacity)
{
PX_ASSERT(this->capacity() < capacity);
return recreate(capacity);
}
/*!
\brief Creates a new memory block, copies all entries to the new block and destroys old entries.
\param capacity The number of entries that the array should be able to hold.
\return True if operation succeeds, false otherwise.
*/
PX_NOINLINE bool recreate(uint32_t capacity);
// The idea here is to prevent accidental bugs with pushBack or insert. Unfortunately
// it interacts badly with InlineArrays with smaller inline allocations.
// TODO(dsequeira): policy template arg, this is exactly what they're for.
PX_INLINE uint32_t capacityIncrement() const
{
const uint32_t capacity = this->capacity();
return capacity == 0 ? 1 : capacity * 2;
}
T* mData;
uint32_t mSize;
uint32_t mCapacity;
};
template <class T, class Alloc>
PX_NOINLINE bool PxArray<T, Alloc>::resize(const uint32_t size, const T& a)
{
if(!reserve(size))
return false;
create(mData + mSize, mData + size, a);
destroy(mData + size, mData + mSize);
mSize = size;
return true;
}
template <class T, class Alloc>
template <class A>
PX_NOINLINE void PxArray<T, Alloc>::copy(const PxArray<T, A>& other)
{
if(!other.empty())
{
mData = allocate(mSize = mCapacity = other.size());
if(mData)
copy(mData, mData + mSize, other.begin());
}
else
{
mData = NULL;
mSize = 0;
mCapacity = 0;
}
// mData = allocate(other.mSize);
// mSize = other.mSize;
// mCapacity = other.mSize;
// copy(mData, mData + mSize, other.mData);
}
template <class T, class Alloc>
PX_NOINLINE bool PxArray<T, Alloc>::resizeUninitialized(const uint32_t size)
{
if(!reserve(size))
return false;
mSize = size;
return true;
}
template <class T, class Alloc>
PX_NOINLINE T* PxArray<T, Alloc>::growAndPushBack(const T& a)
{
const uint32_t capacity = capacityIncrement();
uint32_t cookie = 0;
T* newData = allocate(capacity, &cookie);
if(!newData)
return NULL;
PX_ASSERT((!capacity) || (newData && (newData != mData)));
copy(newData, newData + mSize, mData);
// inserting element before destroying old array
// avoids referencing destroyed object when duplicating array element.
PX_PLACEMENT_NEW(reinterpret_cast<void*>(newData + mSize), T)(a);
destroy(mData, mData + mSize);
if(!isInUserMemory())
deallocate(mData, &cookie);
mData = newData;
mCapacity = capacity;
return &mData[mSize++];
}
template <class T, class Alloc>
PX_NOINLINE bool PxArray<T, Alloc>::recreate(uint32_t capacity)
{
uint32_t cookie = 0;
T* newData = allocate(capacity, &cookie);
if(capacity && !newData)
return false;
PX_ASSERT((!capacity) || (newData && (newData != mData)));
copy(newData, newData + mSize, mData);
destroy(mData, mData + mSize);
if(!isInUserMemory())
deallocate(mData, &cookie);
mData = newData;
mCapacity = capacity;
return true;
}
template <class T, class Alloc>
PX_INLINE void swap(PxArray<T, Alloc>& x, PxArray<T, Alloc>& y)
{
x.swap(y);
}
#if !PX_DOXYGEN
} // namespace physx
#endif
#endif