mirror of
https://github.com/jmarshall23/DoomRTX.git
synced 2026-08-12 16:21:04 +02:00
Justin Marshall
1324 lines
28 KiB
C++
1324 lines
28 KiB
C++
/*
|
|
===========================================================================
|
|
|
|
IceTech GPL Source Code
|
|
Copyright (C) 2026 Justin Marshall
|
|
|
|
This file is part of the IceTech GPL Source Code (?IceTech Source Code?).
|
|
|
|
IceTech Source Code is free software: you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
IceTech Source Code is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with IceTech Source Code. If not, see <http://www.gnu.org/licenses/>.
|
|
|
|
In addition, the IceTech Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the IceTech Source Code. If not, please request a copy in writing from id Software at the address below.
|
|
|
|
If you have questions concerning this license or the applicable additional terms, you may contact in writing Justin Marshall, justinmarshall20@gmail.com
|
|
|
|
===========================================================================
|
|
*/
|
|
|
|
#ifndef __LIST_H__
|
|
#define __LIST_H__
|
|
|
|
/*
|
|
===============================================================================
|
|
|
|
List template
|
|
Does not allocate memory until the first item is added.
|
|
|
|
===============================================================================
|
|
*/
|
|
|
|
|
|
/*
|
|
================
|
|
idListSortCompare<type>
|
|
================
|
|
*/
|
|
#ifdef __INTEL_COMPILER
|
|
// the intel compiler doesn't do the right thing here
|
|
template< class type >
|
|
ID_INLINE int idListSortCompare(const type* a, const type* b) {
|
|
assert(0);
|
|
return 0;
|
|
}
|
|
#else
|
|
template< class type >
|
|
ID_INLINE int idListSortCompare(const type* a, const type* b) {
|
|
return *a - *b;
|
|
}
|
|
#endif
|
|
|
|
/*
|
|
================
|
|
idListNewElement<type>
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE type* idListNewElement(void) {
|
|
return new type;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idSwap<type>
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idSwap(type& a, type& b) {
|
|
type c = a;
|
|
a = b;
|
|
b = c;
|
|
}
|
|
|
|
template< class type >
|
|
class idList {
|
|
public:
|
|
|
|
typedef int cmp_t(const type*, const type*);
|
|
typedef int filter_t(const type*);
|
|
typedef type new_t(void);
|
|
|
|
idList(int newgranularity = 16);
|
|
idList(const idList<type>& other);
|
|
~idList<type>(void);
|
|
|
|
void Clear(void); // clear the list
|
|
int Num(void) const; // returns number of elements in list
|
|
int NumAllocated(void) const; // returns number of elements allocated for
|
|
void SetGranularity(int newgranularity); // set new granularity
|
|
int GetGranularity(void) const; // get the current granularity
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
void SetAllocatorHeap(rvHeap* heap); // set the heap used for all allocations
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
|
|
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 list type
|
|
size_t MemoryUsed(void) const; // returns size of the used elements in the list
|
|
|
|
idList<type>& operator=(const idList<type>& other);
|
|
const type& operator[](int index) const;
|
|
type& operator[](int index);
|
|
|
|
void Condense(void); // resizes list to exactly the number of elements it contains
|
|
void Resize(int newsize); // resizes list to the given number of elements
|
|
void Resize(int newsize, int newgranularity); // resizes list and sets new granularity
|
|
void SetNum(int newnum, bool resize = true); // set number of elements in list and resize to exactly this number if necessary
|
|
void AssureSize(int newSize); // assure list has given number of elements, but leave them uninitialized
|
|
void AssureSize(int newSize, const type& initValue); // assure list has given number of elements and initialize any new elements
|
|
void AssureSizeAlloc(int newSize, new_t* allocator); // assure the pointer list has the given number of elements and allocate any new elements
|
|
|
|
type* Ptr(void); // returns a pointer to the list
|
|
const type* Ptr(void) const; // returns a pointer to the list
|
|
type& Alloc(void); // returns reference to a new data element at the end of the list
|
|
int Append(const type& obj); // append element
|
|
int Append(const idList<type>& other); // append list
|
|
int AddUnique(const type& obj); // add unique element
|
|
int Insert(const type& obj, int index = 0); // 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
|
|
int FindNull(void) const; // find the index for the first NULL pointer in the list
|
|
int IndexOf(const type* obj) const; // returns the index for the pointer to an element in the list
|
|
bool RemoveIndex(int index); // remove the element at the given index
|
|
bool Remove(const type& obj); // remove the element
|
|
void Sort(cmp_t* compare = (cmp_t*)&idListSortCompare<type>);
|
|
void SortSubSection(int startIndex, int endIndex, cmp_t* compare = (cmp_t*)&idListSortCompare<type>);
|
|
void Swap(idList<type>& other); // swap the contents of the lists
|
|
void DeleteContents(bool clear); // delete the contents of the list
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// cdr : added Heap & Stack & Sort functionality
|
|
int FindBinary(const type& key, cmp_t* compare = (cmp_t*)&idListSortCompare<type>) const;
|
|
void StackAdd(const type& obj); // add to the stack
|
|
void StackPop(void); // remove from the stack
|
|
type& StackTop(void); // get the top element of the stack
|
|
void HeapAdd(const type& obj); // add to the heap, and resort
|
|
void HeapPop(void); // pop off the top of the heap & resort
|
|
int TypeSize() const { return sizeof(type); }
|
|
void RemoveNull();
|
|
void RemoveContents(bool clear);
|
|
bool RemoveRange(int low, int high);
|
|
void RemoveDuplicates(void);
|
|
// RAVEN END
|
|
#endif
|
|
|
|
protected:
|
|
int num;
|
|
int size;
|
|
int granularity;
|
|
type* list;
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
rvHeap* allocatorHeap;
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
};
|
|
|
|
/*
|
|
================
|
|
idList<type>::idList( int )
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE idList<type>::idList(int newgranularity) {
|
|
assert(newgranularity > 0);
|
|
|
|
list = NULL;
|
|
granularity = newgranularity;
|
|
Clear();
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
allocatorHeap = 0;
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::idList( const idList<type> &other )
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE idList<type>::idList(const idList<type>& other) {
|
|
list = NULL;
|
|
|
|
#ifdef QUAKE4
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
allocatorHeap = 0;
|
|
#endif
|
|
#endif
|
|
|
|
* this = other;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::~idList<type>
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE idList<type>::~idList(void) {
|
|
Clear();
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Clear
|
|
|
|
Frees up the memory allocated by the list. Assumes that type automatically handles freeing up memory.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::Clear(void) {
|
|
if (list) {
|
|
delete[] list;
|
|
}
|
|
|
|
list = NULL;
|
|
num = 0;
|
|
size = 0;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::DeleteContents
|
|
|
|
Calls the destructor of all elements in the list. Conditionally frees up memory used by the list.
|
|
Note that this only works on lists containing pointers to objects and will cause a compiler error
|
|
if called with non-pointers. Since the list was not responsible for allocating the object, it has
|
|
no information on whether the object still exists or not, so care must be taken to ensure that
|
|
the pointers are still valid when this function is called. Function will set all pointers in the
|
|
list to NULL.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::DeleteContents(bool clear) {
|
|
int i;
|
|
|
|
for (i = 0; i < num; i++) {
|
|
delete list[i];
|
|
list[i] = NULL;
|
|
}
|
|
|
|
if (clear) {
|
|
Clear();
|
|
}
|
|
else {
|
|
memset(list, 0, size * sizeof(type));
|
|
}
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
/*
|
|
================
|
|
idList<type>::RemoveContents
|
|
|
|
Quake 4 compatibility helper. This clears pointer contents from the list without deleting
|
|
the pointed-to objects. Use DeleteContents() when the list owns the pointers.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::RemoveContents(bool clear) {
|
|
int i;
|
|
|
|
for (i = 0; i < num; i++) {
|
|
list[i] = NULL;
|
|
}
|
|
|
|
if (clear) {
|
|
Clear();
|
|
}
|
|
else {
|
|
memset(list, 0, size * sizeof(type));
|
|
num = 0;
|
|
}
|
|
}
|
|
#endif
|
|
|
|
/*
|
|
================
|
|
idList<type>::Allocated
|
|
|
|
return total memory allocated for the list in bytes, but doesn't take into account additional memory allocated by type
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE size_t idList<type>::Allocated(void) const {
|
|
return size * sizeof(type);
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Size
|
|
|
|
return total size of list in bytes, but doesn't take into account additional memory allocated by type
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE size_t idList<type>::Size(void) const {
|
|
return sizeof(idList<type>) + Allocated();
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::MemoryUsed
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE size_t idList<type>::MemoryUsed(void) const {
|
|
return num * sizeof(*list);
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Num
|
|
|
|
Returns the number of elements currently contained in the list.
|
|
Note that this is NOT an indication of the memory allocated.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::Num(void) const {
|
|
return num;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::NumAllocated
|
|
|
|
Returns the number of elements currently allocated for.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::NumAllocated(void) const {
|
|
return size;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::SetNum
|
|
|
|
Resize to the exact size specified irregardless of granularity
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::SetNum(int newnum, bool resize) {
|
|
assert(newnum >= 0);
|
|
if (resize || newnum > size) {
|
|
Resize(newnum);
|
|
}
|
|
num = newnum;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::SetGranularity
|
|
|
|
Sets the base size of the array and resizes the array to match.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::SetGranularity(int newgranularity) {
|
|
int newsize;
|
|
|
|
assert(newgranularity > 0);
|
|
granularity = newgranularity;
|
|
|
|
if (list) {
|
|
// resize it to the closest level of granularity
|
|
newsize = num + granularity - 1;
|
|
newsize -= newsize % granularity;
|
|
if (newsize != size) {
|
|
Resize(newsize);
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::GetGranularity
|
|
|
|
Get the current granularity.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::GetGranularity(void) const {
|
|
return granularity;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Condense
|
|
|
|
Resizes the array to exactly the number of elements it contains or frees up memory if empty.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::Condense(void) {
|
|
if (list) {
|
|
if (num) {
|
|
Resize(num);
|
|
}
|
|
else {
|
|
Clear();
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::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 >
|
|
ID_INLINE void idList<type>::Resize(int newsize) {
|
|
type* temp;
|
|
int i;
|
|
|
|
assert(newsize >= 0);
|
|
|
|
// free up the list if no data is being reserved
|
|
if (newsize <= 0) {
|
|
Clear();
|
|
return;
|
|
}
|
|
|
|
if (newsize == size) {
|
|
// not changing the size, so just exit
|
|
return;
|
|
}
|
|
|
|
temp = list;
|
|
size = newsize;
|
|
if (size < num) {
|
|
num = size;
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
|
|
bool ok = false;
|
|
if (allocatorHeap) {
|
|
RV_PUSH_HEAP_PTR(allocatorHeap);
|
|
ok = true;
|
|
}
|
|
else {
|
|
ok = rvPushHeapContainingMemory(this);
|
|
}
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
|
|
// copy the old list into our new one
|
|
list = new type[size];
|
|
for (i = 0; i < num; i++) {
|
|
list[i] = temp[i];
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
|
|
if (ok) {
|
|
RV_POP_HEAP();
|
|
}
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
|
|
// delete the old list if it exists
|
|
if (temp) {
|
|
delete[] temp;
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::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 >
|
|
ID_INLINE void idList<type>::Resize(int newsize, int newgranularity) {
|
|
type* temp;
|
|
int i;
|
|
|
|
assert(newsize >= 0);
|
|
|
|
assert(newgranularity > 0);
|
|
granularity = newgranularity;
|
|
|
|
// free up the list if no data is being reserved
|
|
if (newsize <= 0) {
|
|
Clear();
|
|
return;
|
|
}
|
|
|
|
temp = list;
|
|
size = newsize;
|
|
if (size < num) {
|
|
num = size;
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
|
|
bool ok = rvPushHeapContainingMemory(this);
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
|
|
// copy the old list into our new one
|
|
list = new type[size];
|
|
for (i = 0; i < num; i++) {
|
|
list[i] = temp[i];
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
|
|
if (ok) {
|
|
RV_POP_HEAP();
|
|
}
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
|
|
// delete the old list if it exists
|
|
if (temp) {
|
|
delete[] temp;
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::AssureSize
|
|
|
|
Makes sure the list has at least the given number of elements.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::AssureSize(int newSize) {
|
|
int newNum = newSize;
|
|
|
|
if (newSize > size) {
|
|
|
|
if (granularity == 0) { // this is a hack to fix our memset classes
|
|
granularity = 16;
|
|
}
|
|
|
|
newSize += granularity - 1;
|
|
newSize -= newSize % granularity;
|
|
Resize(newSize);
|
|
}
|
|
|
|
num = newNum;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::AssureSize
|
|
|
|
Makes sure the list has at least the given number of elements and initialize any elements not yet initialized.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::AssureSize(int newSize, const type& initValue) {
|
|
int newNum = newSize;
|
|
|
|
if (newSize > size) {
|
|
|
|
if (granularity == 0) { // this is a hack to fix our memset classes
|
|
granularity = 16;
|
|
}
|
|
|
|
newSize += granularity - 1;
|
|
newSize -= newSize % granularity;
|
|
num = size;
|
|
Resize(newSize);
|
|
|
|
for (int i = num; i < newSize; i++) {
|
|
list[i] = initValue;
|
|
}
|
|
}
|
|
|
|
num = newNum;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::AssureSizeAlloc
|
|
|
|
Makes sure the list has at least the given number of elements and allocates any elements using the allocator.
|
|
|
|
NOTE: This function can only be called on lists containing pointers. Calling it
|
|
on non-pointer lists will cause a compiler error.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::AssureSizeAlloc(int newSize, new_t* allocator) {
|
|
int newNum = newSize;
|
|
|
|
if (newSize > size) {
|
|
|
|
if (granularity == 0) { // this is a hack to fix our memset classes
|
|
granularity = 16;
|
|
}
|
|
|
|
newSize += granularity - 1;
|
|
newSize -= newSize % granularity;
|
|
num = size;
|
|
Resize(newSize);
|
|
|
|
for (int i = num; i < newSize; i++) {
|
|
list[i] = (*allocator)();
|
|
}
|
|
}
|
|
|
|
num = newNum;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::operator=
|
|
|
|
Copies the contents and size attributes of another list.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE idList<type>& idList<type>::operator=(const idList<type>& other) {
|
|
int i;
|
|
|
|
Clear();
|
|
|
|
num = other.num;
|
|
size = other.size;
|
|
granularity = other.granularity;
|
|
|
|
#ifdef QUAKE4
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
allocatorHeap = other.allocatorHeap;
|
|
#endif
|
|
#endif
|
|
|
|
if (size) {
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
|
|
bool ok = rvPushHeapContainingMemory(this);
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
|
|
list = new type[size];
|
|
for (i = 0; i < num; i++) {
|
|
list[i] = other.list[i];
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
|
|
if (ok) {
|
|
RV_POP_HEAP();
|
|
}
|
|
#endif
|
|
// RAVEN END
|
|
#endif
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::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 >
|
|
ID_INLINE const type& idList<type>::operator[](int index) const {
|
|
assert(index >= 0);
|
|
assert(index < num);
|
|
|
|
return list[index];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::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 >
|
|
ID_INLINE type& idList<type>::operator[](int index) {
|
|
assert(index >= 0);
|
|
assert(index < num);
|
|
|
|
return list[index];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Ptr
|
|
|
|
Returns a pointer to the begining of the array. Useful for iterating through the list in loops.
|
|
|
|
Note: may return NULL if the list is empty.
|
|
|
|
FIXME: Create an iterator template for this kind of thing.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE type* idList<type>::Ptr(void) {
|
|
return list;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Ptr
|
|
|
|
Returns a pointer to the begining of the array. Useful for iterating through the list in loops.
|
|
|
|
Note: may return NULL if the list is empty.
|
|
|
|
FIXME: Create an iterator template for this kind of thing.
|
|
================
|
|
*/
|
|
template< class type >
|
|
const ID_INLINE type* idList<type>::Ptr(void) const {
|
|
return list;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Alloc
|
|
|
|
Returns a reference to a new data element at the end of the list.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE type& idList<type>::Alloc(void) {
|
|
if (!list) {
|
|
Resize(granularity);
|
|
}
|
|
|
|
if (num == size) {
|
|
Resize(size + granularity);
|
|
}
|
|
|
|
return list[num++];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Append
|
|
|
|
Increases the size of the list by one element and copies the supplied data into it.
|
|
|
|
Returns the index of the new element.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::Append(type const& obj) {
|
|
if (!list) {
|
|
Resize(granularity);
|
|
}
|
|
|
|
if (num == size) {
|
|
int newsize;
|
|
|
|
if (granularity == 0) { // this is a hack to fix our memset classes
|
|
granularity = 16;
|
|
}
|
|
newsize = size + granularity;
|
|
Resize(newsize - newsize % granularity);
|
|
}
|
|
|
|
list[num] = obj;
|
|
num++;
|
|
|
|
return num - 1;
|
|
}
|
|
|
|
|
|
/*
|
|
================
|
|
idList<type>::Insert
|
|
|
|
Increases the size of the list by at leat one element if necessary
|
|
and inserts the supplied data into it.
|
|
|
|
Returns the index of the new element.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::Insert(type const& obj, int index) {
|
|
if (!list) {
|
|
Resize(granularity);
|
|
}
|
|
|
|
if (num == size) {
|
|
int newsize;
|
|
|
|
if (granularity == 0) { // this is a hack to fix our memset classes
|
|
granularity = 16;
|
|
}
|
|
newsize = size + granularity;
|
|
Resize(newsize - newsize % granularity);
|
|
}
|
|
|
|
if (index < 0) {
|
|
index = 0;
|
|
}
|
|
else if (index > num) {
|
|
index = num;
|
|
}
|
|
for (int i = num; i > index; --i) {
|
|
list[i] = list[i - 1];
|
|
}
|
|
num++;
|
|
list[index] = obj;
|
|
return index;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Append
|
|
|
|
adds the other list to this one
|
|
|
|
Returns the size of the new combined list
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::Append(const idList<type>& other) {
|
|
if (!list) {
|
|
if (granularity == 0) { // this is a hack to fix our memset classes
|
|
granularity = 16;
|
|
}
|
|
Resize(granularity);
|
|
}
|
|
|
|
int n = other.Num();
|
|
for (int i = 0; i < n; i++) {
|
|
Append(other[i]);
|
|
}
|
|
|
|
return Num();
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::AddUnique
|
|
|
|
Adds the data to the list if it doesn't already exist. Returns the index of the data in the list.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::AddUnique(type const& obj) {
|
|
int index;
|
|
|
|
index = FindIndex(obj);
|
|
if (index < 0) {
|
|
index = Append(obj);
|
|
}
|
|
|
|
return index;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::FindIndex
|
|
|
|
Searches for the specified data in the list and returns it's index. Returns -1 if the data is not found.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::FindIndex(type const& obj) const {
|
|
int i;
|
|
|
|
for (i = 0; i < num; i++) {
|
|
if (list[i] == obj) {
|
|
return i;
|
|
}
|
|
}
|
|
|
|
// Not found
|
|
return -1;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Find
|
|
|
|
Searches for the specified data in the list and returns it's address. Returns NULL if the data is not found.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE type* idList<type>::Find(type const& obj) const {
|
|
int i;
|
|
|
|
i = FindIndex(obj);
|
|
if (i >= 0) {
|
|
return &list[i];
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::FindNull
|
|
|
|
Searches for a NULL pointer in the list. Returns -1 if NULL is not found.
|
|
|
|
NOTE: This function can only be called on lists containing pointers. Calling it
|
|
on non-pointer lists will cause a compiler error.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::FindNull(void) const {
|
|
int i;
|
|
|
|
for (i = 0; i < num; i++) {
|
|
if (list[i] == NULL) {
|
|
return i;
|
|
}
|
|
}
|
|
|
|
// Not found
|
|
return -1;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::IndexOf
|
|
|
|
Takes a pointer to an element in the list and returns the index of the element.
|
|
This is NOT a guarantee that the object is really in the list.
|
|
Function will assert in debug builds if pointer is outside the bounds of the list,
|
|
but remains silent in release builds.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::IndexOf(type const* objptr) const {
|
|
int index;
|
|
|
|
index = objptr - list;
|
|
|
|
assert(index >= 0);
|
|
assert(index < num);
|
|
|
|
return index;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::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 list is reduced by one. Returns false if the index is outside the bounds of the list.
|
|
Note that the element is not destroyed, so any memory used by it may not be freed until the destruction of the list.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE bool idList<type>::RemoveIndex(int index) {
|
|
int i;
|
|
|
|
assert(list != NULL);
|
|
assert(index >= 0);
|
|
assert(index < num);
|
|
|
|
if ((index < 0) || (index >= num)) {
|
|
return false;
|
|
}
|
|
|
|
num--;
|
|
for (i = index; i < num; i++) {
|
|
list[i] = list[i + 1];
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Remove
|
|
|
|
Removes the element if it is found within the list and moves all data following the element down to fill in the gap.
|
|
The number of elements in the list is reduced by one. Returns false if the data is not found in the list. Note that
|
|
the element is not destroyed, so any memory used by it may not be freed until the destruction of the list.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE bool idList<type>::Remove(type const& obj) {
|
|
int index;
|
|
|
|
index = FindIndex(obj);
|
|
if (index >= 0) {
|
|
return RemoveIndex(index);
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Sort
|
|
|
|
Performs a qsort on the list using the supplied comparison function. Note that the data is merely moved around the
|
|
list, so any pointers to data within the list may no longer be valid.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::Sort(cmp_t* compare) {
|
|
if (!list) {
|
|
return;
|
|
}
|
|
typedef int cmp_c(const void*, const void*);
|
|
|
|
cmp_c* vCompare = (cmp_c*)compare;
|
|
qsort((void*)list, (size_t)num, sizeof(type), vCompare);
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::SortSubSection
|
|
|
|
Sorts a subsection of the list.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::SortSubSection(int startIndex, int endIndex, cmp_t* compare) {
|
|
if (!list) {
|
|
return;
|
|
}
|
|
if (startIndex < 0) {
|
|
startIndex = 0;
|
|
}
|
|
if (endIndex >= num) {
|
|
endIndex = num - 1;
|
|
}
|
|
if (startIndex >= endIndex) {
|
|
return;
|
|
}
|
|
typedef int cmp_c(const void*, const void*);
|
|
|
|
cmp_c* vCompare = (cmp_c*)compare;
|
|
qsort((void*)(&list[startIndex]), (size_t)(endIndex - startIndex + 1), sizeof(type), vCompare);
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::Swap
|
|
|
|
Swaps the contents of two lists
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::Swap(idList<type>& other) {
|
|
idSwap(num, other.num);
|
|
idSwap(size, other.size);
|
|
idSwap(granularity, other.granularity);
|
|
idSwap(list, other.list);
|
|
|
|
#ifdef QUAKE4
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
idSwap(allocatorHeap, other.allocatorHeap);
|
|
#endif
|
|
#endif
|
|
}
|
|
|
|
#ifdef QUAKE4
|
|
|
|
// RAVEN BEGIN
|
|
// cdr : added Heap & Stack & Binary Search functionality
|
|
|
|
/*
|
|
================
|
|
idList<type>::FindBinary
|
|
|
|
Assumes the list is sorted and does a binary search for the given key
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE int idList<type>::FindBinary(const type& key, cmp_t* compare) const {
|
|
if (!list || num <= 0) {
|
|
return -1;
|
|
}
|
|
|
|
typedef int cmp_c(const void*, const void*);
|
|
cmp_c* vCompare = (cmp_c*)compare;
|
|
|
|
type* found = (type*)bsearch((void*)(&key), (void*)list, (size_t)num, sizeof(type), vCompare);
|
|
if (found) {
|
|
return IndexOf(found);
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::StackAdd
|
|
|
|
Adds a value to the list as if the list was a stack
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::StackAdd(const type& obj) {
|
|
Append(obj);
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::StackPop
|
|
|
|
Removes a value from the list as if the list was a stack
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::StackPop(void) {
|
|
assert(num > 0);
|
|
if (num <= 0) {
|
|
return;
|
|
}
|
|
|
|
RemoveIndex(num - 1);
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::StackTop
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE type& idList<type>::StackTop(void) {
|
|
assert(num > 0);
|
|
return list[num - 1];
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::HeapAdd
|
|
|
|
Adds a value to the list as if the list was a heap by doing a bubble swap sort.
|
|
First it appends the object, then swaps up the heap at successive parent positions
|
|
as needed.
|
|
|
|
Complexity: O[n log n]
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::HeapAdd(const type& obj) {
|
|
int pos = Append(obj);
|
|
|
|
while (pos && list[((pos - 1) / 2)] < list[pos]) {
|
|
idSwap(list[((pos - 1) / 2)], list[pos]);
|
|
pos = ((pos - 1) / 2);
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::HeapPop
|
|
|
|
Removes the top element from the heap.
|
|
First swaps the top element of the heap with the lowest element,
|
|
destroys the lowest element, and then sorts the new top element down the heap
|
|
as needed.
|
|
|
|
Complexity: O[n log n]
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::HeapPop(void) {
|
|
assert(num > 0);
|
|
if (num <= 0) {
|
|
return;
|
|
}
|
|
|
|
idSwap(list[0], list[num - 1]);
|
|
num--;
|
|
|
|
int pos = 0;
|
|
|
|
int largestChild = pos;
|
|
if (((2 * pos) + 1) < num) {
|
|
if (((2 * pos) + 2) < num) {
|
|
largestChild = ((list[((2 * pos) + 2)] < list[((2 * pos) + 1)]) ? (((2 * pos) + 1)) : (((2 * pos) + 2)));
|
|
}
|
|
else {
|
|
largestChild = ((2 * pos) + 1);
|
|
}
|
|
}
|
|
|
|
while (largestChild != pos && list[pos] < list[largestChild]) {
|
|
idSwap(list[largestChild], list[pos]);
|
|
pos = largestChild;
|
|
|
|
largestChild = pos;
|
|
if (((2 * pos) + 1) < num) {
|
|
if (((2 * pos) + 2) < num) {
|
|
largestChild = ((list[((2 * pos) + 2)] < list[((2 * pos) + 1)]) ? (((2 * pos) + 1)) : (((2 * pos) + 2)));
|
|
}
|
|
else {
|
|
largestChild = ((2 * pos) + 1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::RemoveNull
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::RemoveNull() {
|
|
for (int ix = Num() - 1; ix >= 0; --ix) {
|
|
if (!list[ix]) {
|
|
RemoveIndex(ix);
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::RemoveRange
|
|
|
|
Removes the specified range of elements [low, high].
|
|
Only copies down the array once.
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE bool idList<type>::RemoveRange(int low, int high) {
|
|
int i;
|
|
|
|
assert(list != NULL);
|
|
assert(low >= 0);
|
|
assert(high < num);
|
|
assert(low <= high);
|
|
|
|
if ((low < 0) || (high >= num) || (low > high)) {
|
|
return false;
|
|
}
|
|
|
|
int range = (high - low) + 1;
|
|
num -= range;
|
|
for (i = low; i < num; i++) {
|
|
list[i] = list[i + range];
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
================
|
|
idList<type>::RemoveDuplicates
|
|
================
|
|
*/
|
|
template< class type >
|
|
ID_INLINE void idList<type>::RemoveDuplicates(void) {
|
|
for (int i = 0; i < num; i++) {
|
|
for (int j = num - 1; j > i; j--) {
|
|
if (list[i] == list[j]) {
|
|
RemoveIndex(j);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
// RAVEN END
|
|
|
|
// RAVEN BEGIN
|
|
// mwhitlock: Dynamic memory consolidation
|
|
#if defined(_RV_MEM_SYS_SUPPORT)
|
|
template< class type >
|
|
ID_INLINE void idList<type>::SetAllocatorHeap(rvHeap* heap) {
|
|
assert(heap);
|
|
allocatorHeap = heap;
|
|
}
|
|
#endif
|
|
// RAVEN END
|
|
|
|
#endif // QUAKE4
|
|
|
|
#endif /* !__LIST_H__ */ |