677 lines
16 KiB
C++
677 lines
16 KiB
C++
// Copyright (C) 2007 Id Software, Inc.
|
|
//
|
|
|
|
|
|
#ifndef __PTRARRAY_H__
|
|
#define __PTRARRAY_H__
|
|
|
|
/*
|
|
===============================================================================
|
|
|
|
Pointer Array template
|
|
Does not allocate memory until the first array element is added.
|
|
|
|
===============================================================================
|
|
*/
|
|
|
|
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArrayCompare( const type *a, const type *b ) {
|
|
return *a - *b;
|
|
}
|
|
|
|
template< class type, int gran=16 >
|
|
class idPtrArray {
|
|
public:
|
|
|
|
typedef int cmp_t( const type *, const type * );
|
|
|
|
idPtrArray( void );
|
|
idPtrArray( const idPtrArray<type,gran> &other );
|
|
~idPtrArray( void );
|
|
|
|
void Clear( void ); // clear the array
|
|
int Num( void ) const; // returns number of elements in array
|
|
|
|
size_t Allocated( void ) const; // returns total size of allocated memory
|
|
size_t Size( void ) const; // returns total size of allocated memory including size of idPtrArray
|
|
size_t MemoryUsed( void ) const; // returns size of the used elements in the array
|
|
|
|
idPtrArray<type,gran> & operator=( const idPtrArray<type,gran> &other );
|
|
const type & operator[]( int index ) const;
|
|
type & operator[]( int index );
|
|
|
|
void Condense( void ); // resizes array to exactly the number of elements it contains
|
|
void Resize( int newsize ); // resizes array to the given number of elements
|
|
void SetNum( int newnum, bool resize = true ); // set number of elements in array and resize to exactly this number if necessary
|
|
void AssureSize( int newSize); // assure array has given number of elements, but leave them uninitialized
|
|
void AssureSize( int newSize, const type &initValue ); // assure array has given number of elements and initialize any new elements
|
|
|
|
type * Ptr( void ); // returns a pointer to the array
|
|
const type * Ptr( void ) const; // returns a pointer to the array
|
|
type & Alloc( void ); // returns reference to a new data element at the end of the array
|
|
int Append( const type & obj ); // append element
|
|
int Append( const idPtrArray<type,gran> &other ); // append array
|
|
int AddUnique( const type & obj ); // add unique element
|
|
int Insert( const type & obj, int index ); // insert the element at the given index
|
|
int FindIndex( const type & obj ) const; // find the index for the given element
|
|
type * Find( type const & obj ) const; // find pointer to the given element
|
|
bool RemoveIndex( int index ); // remove the element at the given index
|
|
bool RemoveIndexFast( int index ); // remove the element at the given index and put the last element into its spot
|
|
bool Remove( const type & obj ); // remove the element
|
|
bool RemoveFast( const type & obj ); // remove the element, move the last element into its spot
|
|
void Sort( cmp_t *compare = idPtrArrayCompare<type,gran> ); // sort the array
|
|
void Swap( idPtrArray<type,gran> &other ); // swap the contents of the lists
|
|
|
|
private:
|
|
int num;
|
|
int size;
|
|
type * array;
|
|
};
|
|
|
|
/*
|
|
================
|
|
idPtrArray::idPtrArray
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE idPtrArray<type,gran>::idPtrArray( void ) {
|
|
num = size = 0;
|
|
array = NULL;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::idPtrArray
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE idPtrArray<type,gran>::idPtrArray( const idPtrArray<type,gran> &other ) {
|
|
num = size = 0;
|
|
array = NULL;
|
|
*this = other;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::~idPtrArray
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE idPtrArray<type,gran>::~idPtrArray( void ) {
|
|
Clear();
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Clear
|
|
|
|
Frees up the memory allocated by the array. Assumes that type automatically handles freeing up memory.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::Clear( void ) {
|
|
if ( array ) {
|
|
delete[] array;
|
|
}
|
|
|
|
array = NULL;
|
|
num = 0;
|
|
size = 0;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Allocated
|
|
|
|
return total memory allocated for the array in bytes, but doesn't take into account additional memory allocated by type
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE size_t idPtrArray<type,gran>::Allocated( void ) const {
|
|
return size * sizeof( type );
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Size
|
|
|
|
return total size of array in bytes, but doesn't take into account additional memory allocated by type
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE size_t idPtrArray<type,gran>::Size( void ) const {
|
|
return sizeof( idPtrArray<type,gran> ) + Allocated();
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::MemoryUsed
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE size_t idPtrArray<type,gran>::MemoryUsed( void ) const {
|
|
return num * sizeof( *array );
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Num
|
|
|
|
Returns the number of elements currently contained in the array.
|
|
Note that this is NOT an indication of the memory allocated.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArray<type,gran>::Num( void ) const {
|
|
return num;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::SetNum
|
|
|
|
Resize to the exact size specified irregardless of gran
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::SetNum( int newnum, bool resize ) {
|
|
assert( newnum >= 0 );
|
|
if ( resize || newnum > size ) {
|
|
Resize( newnum );
|
|
}
|
|
num = newnum;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Condense
|
|
|
|
Resizes the array to exactly the number of elements it contains or frees up memory if empty.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::Condense( void ) {
|
|
if ( array ) {
|
|
if ( num ) {
|
|
Resize( num );
|
|
} else {
|
|
Clear();
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Resize
|
|
|
|
Allocates memory for the amount of elements requested while keeping the contents intact.
|
|
Contents are copied using their = operator so that data is correnctly instantiated.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::Resize( int newsize ) {
|
|
type *temp;
|
|
int i;
|
|
|
|
assert( newsize >= 0 );
|
|
|
|
// free up the array if no data is being reserved
|
|
if ( newsize <= 0 ) {
|
|
Clear();
|
|
return;
|
|
}
|
|
|
|
if ( newsize == size ) {
|
|
// not changing the size, so just exit
|
|
return;
|
|
}
|
|
|
|
temp = array;
|
|
size = newsize;
|
|
if ( size < num ) {
|
|
num = size;
|
|
}
|
|
|
|
// copy the old array into our new one
|
|
array = new type[ size ];
|
|
for( i = 0; i < num; i++ ) {
|
|
array[ i ] = temp[ i ];
|
|
}
|
|
|
|
// delete the old array if it exists
|
|
if ( temp ) {
|
|
delete[] temp;
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::AssureSize
|
|
|
|
Makes sure the array has at least the given number of elements.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::AssureSize( int newSize ) {
|
|
if ( newSize > size ) {
|
|
newSize += gran - 1;
|
|
newSize -= newSize % gran;
|
|
Resize( newSize );
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::AssureSize
|
|
|
|
Makes sure the array has at least the given number of elements and initialize any elements not yet initialized.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::AssureSize( int newSize, const type &initValue ) {
|
|
int oldSize;
|
|
|
|
if ( newSize > size ) {
|
|
|
|
newSize += gran - 1;
|
|
newSize -= newSize % gran;
|
|
oldSize = size;
|
|
Resize( newSize );
|
|
|
|
for ( int i = num; i < newSize; i++ ) {
|
|
array[i] = initValue;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::operator=
|
|
|
|
Copies the contents and size attributes of another array.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE idPtrArray<type,gran> &idPtrArray<type,gran>::operator=( const idPtrArray<type,gran> &other ) {
|
|
int i;
|
|
|
|
Clear();
|
|
|
|
num = other.num;
|
|
size = other.size;
|
|
|
|
if ( size ) {
|
|
array = new type[ size ];
|
|
for( i = 0; i < num; i++ ) {
|
|
array[ i ] = other.array[ i ];
|
|
}
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::operator[] const
|
|
|
|
Access operator. Index must be within range or an assert will be issued in debug builds.
|
|
Release builds do no range checking.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE const type &idPtrArray<type,gran>::operator[]( int index ) const {
|
|
assert( index >= 0 );
|
|
assert( index < num );
|
|
|
|
return array[ index ];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::operator[]
|
|
|
|
Access operator. Index must be within range or an assert will be issued in debug builds.
|
|
Release builds do no range checking.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE type &idPtrArray<type,gran>::operator[]( int index ) {
|
|
assert( index >= 0 );
|
|
assert( index < num );
|
|
|
|
return array[ index ];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Ptr
|
|
|
|
Returns a pointer to the begining of the array. Useful for iterating through the array in loops.
|
|
|
|
Note: may return NULL if the array is empty.
|
|
|
|
FIXME: Create an iterator template for this kind of thing.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE type *idPtrArray<type,gran>::Ptr( void ) {
|
|
return array;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Ptr
|
|
|
|
Returns a pointer to the begining of the array. Useful for iterating through the array in loops.
|
|
|
|
Note: may return NULL if the array is empty.
|
|
|
|
FIXME: Create an iterator template for this kind of thing.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
const ID_INLINE type *idPtrArray<type,gran>::Ptr( void ) const {
|
|
return array;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Alloc
|
|
|
|
Returns a reference to a new data element at the end of the array.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE type &idPtrArray<type,gran>::Alloc( void ) {
|
|
if ( !array ) {
|
|
Resize( gran );
|
|
}
|
|
|
|
if ( num == size ) {
|
|
Resize( size + gran );
|
|
}
|
|
|
|
return array[ num++ ];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Append
|
|
|
|
Increases the size of the array by one element and copies the supplied data into it.
|
|
|
|
Returns the index of the new element.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArray<type,gran>::Append( const type & obj ) {
|
|
if ( !array ) {
|
|
Resize( gran );
|
|
}
|
|
|
|
if ( num == size ) {
|
|
int newsize;
|
|
|
|
newsize = size + gran;
|
|
Resize( newsize - newsize % gran );
|
|
}
|
|
|
|
array[ num ] = obj;
|
|
num++;
|
|
|
|
return num - 1;
|
|
}
|
|
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Insert
|
|
|
|
Increases the size of the array by at leat one element if necessary
|
|
and inserts the supplied data into it.
|
|
|
|
Returns the index of the new element.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArray<type,gran>::Insert( const type & obj, int index ) {
|
|
if ( !array ) {
|
|
Resize( gran );
|
|
}
|
|
|
|
if ( num == size ) {
|
|
int newsize;
|
|
|
|
newsize = size + gran;
|
|
Resize( newsize - newsize % gran );
|
|
}
|
|
|
|
if ( index < 0 ) {
|
|
index = 0;
|
|
}
|
|
else if ( index > num ) {
|
|
index = num;
|
|
}
|
|
for ( int i = num; i > index; --i ) {
|
|
array[i] = array[i-1];
|
|
}
|
|
num++;
|
|
array[index] = obj;
|
|
return index;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Append
|
|
|
|
adds the other array to this one
|
|
|
|
Returns the size of the new combined array
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArray<type,gran>::Append( const idPtrArray<type,gran> &other ) {
|
|
if ( !array ) {
|
|
Resize( gran );
|
|
}
|
|
|
|
int n = other.Num();
|
|
for ( int i = 0; i < n; i++ ) {
|
|
Append( other[i] );
|
|
}
|
|
|
|
return Num();
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::AddUnique
|
|
|
|
Adds the data to the array if it doesn't already exist. Returns the index of the data in the array.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArray<type,gran>::AddUnique( const type & obj ) {
|
|
int index;
|
|
|
|
index = FindIndex( obj );
|
|
if ( index < 0 ) {
|
|
index = Append( obj );
|
|
}
|
|
|
|
return index;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::FindIndex
|
|
|
|
Searches for the specified data in the array and returns it's index. Returns -1 if the data is not found.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE int idPtrArray<type,gran>::FindIndex( const type & obj ) const {
|
|
int i;
|
|
|
|
for( i = 0; i < num; i++ ) {
|
|
if ( array[ i ] == obj ) {
|
|
return i;
|
|
}
|
|
}
|
|
|
|
// Not found
|
|
return -1;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Find
|
|
|
|
Searches for the specified data in the array and returns it's address. Returns NULL if the data is not found.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE type *idPtrArray<type,gran>::Find( const type & obj ) const {
|
|
int i;
|
|
|
|
i = FindIndex( obj );
|
|
if ( i >= 0 ) {
|
|
return &array[ i ];
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::RemoveIndex
|
|
|
|
Removes the element at the specified index and moves all data following the element down to fill in the gap.
|
|
The number of elements in the array is reduced by one. Returns false if the index is outside the bounds of the array.
|
|
Note that the element is not destroyed, so any memory used by it may not be freed until the destruction of the array.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE bool idPtrArray<type,gran>::RemoveIndex( int index ) {
|
|
int i;
|
|
|
|
assert( array != NULL );
|
|
assert( index >= 0 );
|
|
assert( index < num );
|
|
|
|
if ( ( index < 0 ) || ( index >= num ) ) {
|
|
return false;
|
|
}
|
|
|
|
num--;
|
|
for( i = index; i < num; i++ ) {
|
|
array[ i ] = array[ i + 1 ];
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
===============
|
|
idPtrArray::RemoveIndexFast
|
|
|
|
Removes the element at the specified index and moves the last element into
|
|
it's spot, rather than moving the whole array down by one. Of course, this
|
|
doesn't maintain the order of elements!
|
|
The number of elements in the array is reduced by one. Returns false if the
|
|
index is outside the bounds of the array. Note that the element is not destroyed,
|
|
so any memory used by it may not be freed until the destruction of the array.
|
|
===============
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE bool idPtrArray<type,gran>::RemoveIndexFast( int index ) {
|
|
assert( array != NULL );
|
|
assert( index >= 0 );
|
|
assert( index < num );
|
|
|
|
if ( ( index < 0 ) || ( index >= num ) ) {
|
|
return false;
|
|
}
|
|
|
|
num--;
|
|
array[ index ] = array[ num ];
|
|
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Remove
|
|
|
|
Removes the element if it is found within the array and moves all data following the element down to fill in the gap.
|
|
The number of elements in the array is reduced by one. Returns false if the data is not found in the array. Note that
|
|
the element is not destroyed, so any memory used by it may not be freed until the destruction of the array.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE bool idPtrArray<type,gran>::Remove( const type & obj ) {
|
|
int index;
|
|
|
|
index = FindIndex( obj );
|
|
if ( index >= 0 ) {
|
|
return RemoveIndex( index );
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::RemoveFast
|
|
|
|
Removes the element if it is found within the array and moves the last element into the gap.
|
|
The number of elements in the array is reduced by one. Returns false if the data is not found in the array. Note that
|
|
the element is not destroyed, so any memory used by it may not be freed until the destruction of the array.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE bool idPtrArray<type,gran>::RemoveFast( const type & obj ) {
|
|
int index;
|
|
|
|
index = FindIndex( obj );
|
|
if ( index >= 0 ) {
|
|
return RemoveIndexFast( index );
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Sort
|
|
|
|
Performs a qsort on the array using the supplied comparison function. Note that the data is merely moved around the
|
|
array, so any pointers to data within the array may no longer be valid.
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::Sort( cmp_t *compare ) {
|
|
if ( !array ) {
|
|
return;
|
|
}
|
|
typedef int cmp_c(const void *, const void *);
|
|
qsort( ( void * )array, ( size_t )num, sizeof( type ), (cmp_c *)compare );
|
|
}
|
|
|
|
/*
|
|
================
|
|
idPtrArray::Swap
|
|
|
|
Swaps the contents of two lists
|
|
================
|
|
*/
|
|
template< class type, int gran >
|
|
ID_INLINE void idPtrArray<type,gran>::Swap( idPtrArray<type,gran> &other ) {
|
|
idSwap( num, other.num );
|
|
idSwap( size, other.size );
|
|
idSwap( array, other.array );
|
|
}
|
|
|
|
#endif /* !__PTRARRAY_H__ */
|