summaryrefslogtreecommitdiff
path: root/core/dvector.h
diff options
context:
space:
mode:
Diffstat (limited to 'core/dvector.h')
-rw-r--r--core/dvector.h480
1 files changed, 324 insertions, 156 deletions
diff --git a/core/dvector.h b/core/dvector.h
index 9e0090fb7c..f109f842a2 100644
--- a/core/dvector.h
+++ b/core/dvector.h
@@ -30,6 +30,46 @@
#define DVECTOR_H
#include "os/memory.h"
+#include "os/copymem.h"
+#include "pool_allocator.h"
+#include "safe_refcount.h"
+#include "os/rw_lock.h"
+
+struct MemoryPool {
+
+ //avoid accessing these directly, must be public for template access
+
+ static PoolAllocator *memory_pool;
+ static uint8_t *pool_memory;
+ static size_t *pool_size;
+
+
+ struct Alloc {
+
+ SafeRefCount refcount;
+ uint32_t lock;
+ void *mem;
+ PoolAllocator::ID pool_id;
+ size_t size;
+
+ Alloc *free_list;
+
+ Alloc() { mem=NULL; lock=0; pool_id=POOL_ALLOCATOR_INVALID_ID; size=0; free_list=NULL; }
+ };
+
+
+ static Alloc *allocs;
+ static Alloc *free_list;
+ static uint32_t alloc_count;
+ static uint32_t allocs_used;
+ static Mutex *alloc_mutex;
+ static size_t total_memory;
+ static size_t max_memory;
+
+
+ static void setup(uint32_t p_max_allocs=(1<<16));
+ static void cleanup();
+};
/**
@@ -37,182 +77,274 @@
*/
-extern Mutex* dvector_lock;
-
template<class T>
-class DVector {
+class PoolVector {
+
+ MemoryPool::Alloc *alloc;
- mutable MID mem;
+ void _copy_on_write() {
- void copy_on_write() {
- if (!mem.is_valid())
+ if (!alloc)
return;
- if (dvector_lock)
- dvector_lock->lock();
+ ERR_FAIL_COND(alloc->lock>0);
- MID_Lock lock( mem );
+ if (alloc->refcount.get()==1)
+ return; //nothing to do
- if ( *(int*)lock.data() == 1 ) {
- // one reference, means no refcount changes
- if (dvector_lock)
- dvector_lock->unlock();
- return;
+ //must allocate something
+
+ MemoryPool::alloc_mutex->lock();
+ if (MemoryPool::allocs_used==MemoryPool::alloc_count) {
+ MemoryPool::alloc_mutex->unlock();
+ ERR_EXPLAINC("All memory pool allocations are in use, can't COW.");
+ ERR_FAIL();
}
- MID new_mem= dynalloc( mem.get_size() );
+ MemoryPool::Alloc *old_alloc = alloc;
+
+ //take one from the free list
+ alloc = MemoryPool::free_list;
+ MemoryPool::free_list = alloc->free_list;
+ //increment the used counter
+ MemoryPool::allocs_used++;
- if (!new_mem.is_valid()) {
+ //copy the alloc data
+ alloc->size=old_alloc->size;
+ alloc->refcount.init();
+ alloc->pool_id=POOL_ALLOCATOR_INVALID_ID;
+ alloc->lock=0;
- if (dvector_lock)
- dvector_lock->unlock();
- ERR_FAIL_COND( new_mem.is_valid() ); // out of memory
+#ifdef DEBUG_ENABLED
+ MemoryPool::total_memory+=alloc->size;
+ if (MemoryPool::total_memory>MemoryPool::max_memory) {
+ MemoryPool::max_memory=MemoryPool::total_memory;
}
+#endif
- MID_Lock dst_lock( new_mem );
+ MemoryPool::alloc_mutex->unlock();
- int *rc = (int*)dst_lock.data();
+ if (MemoryPool::memory_pool) {
- *rc=1;
- T * dst = (T*)(rc + 1 );
+ } else {
+ alloc->mem = memalloc( alloc->size );
+ copymem( alloc->mem, old_alloc->mem, alloc->size );
+ }
- T * src =(T*) ((int*)lock.data() + 1 );
+ if (old_alloc->refcount.unref()) {
+ //this should never happen but..
- int count = (mem.get_size() - sizeof(int)) / sizeof(T);
+#ifdef DEBUG_ENABLED
+ MemoryPool::alloc_mutex->lock();
+ MemoryPool::total_memory-=old_alloc->size;
+ MemoryPool::alloc_mutex->unlock();
+#endif
- for (int i=0;i<count;i++) {
- memnew_placement( &dst[i], T(src[i]) );
- }
+ if (MemoryPool::memory_pool) {
+ //resize memory pool
+ //if none, create
+ //if some resize
+ } else {
- (*(int*)lock.data())--;
+ memfree( old_alloc->mem );
+ old_alloc->mem=NULL;
+ old_alloc->size=0;
- // unlock all
- dst_lock=MID_Lock();
- lock=MID_Lock();
- mem=new_mem;
+ MemoryPool::alloc_mutex->lock();
+ old_alloc->free_list=MemoryPool::free_list;
+ MemoryPool::free_list=old_alloc;
+ MemoryPool::allocs_used--;
+ MemoryPool::alloc_mutex->unlock();
+ }
- if (dvector_lock)
- dvector_lock->unlock();
+ }
}
- void reference( const DVector& p_dvector ) {
+ void _reference( const PoolVector& p_dvector ) {
- unreference();
+ if (alloc==p_dvector.alloc)
+ return;
- if (dvector_lock)
- dvector_lock->lock();
+ _unreference();
- if (!p_dvector.mem.is_valid()) {
+ if (!p_dvector.alloc) {
+ return;
+ }
- if (dvector_lock)
- dvector_lock->unlock();
+ if (p_dvector.alloc->refcount.ref()) {
+ alloc=p_dvector.alloc;
+ }
+
+ }
+
+
+ void _unreference() {
+
+ if (!alloc)
+ return;
+
+ if (!alloc->refcount.unref()) {
+ alloc=NULL;
return;
}
- MID_Lock lock(p_dvector.mem);
+ //must be disposed!
- int * rc = (int*)lock.data();
- (*rc)++;
+ {
+ int cur_elements = alloc->size/sizeof(T);
+ Write w;
+ for (int i=0;i<cur_elements;i++) {
- lock = MID_Lock();
- mem=p_dvector.mem;
+ w[i].~T();
+ }
- if (dvector_lock)
- dvector_lock->unlock();
+ }
- }
+#ifdef DEBUG_ENABLED
+ MemoryPool::alloc_mutex->lock();
+ MemoryPool::total_memory-=alloc->size;
+ MemoryPool::alloc_mutex->unlock();
+#endif
- void unreference() {
+ if (MemoryPool::memory_pool) {
+ //resize memory pool
+ //if none, create
+ //if some resize
+ } else {
- if (dvector_lock)
- dvector_lock->lock();
+ memfree( alloc->mem );
+ alloc->mem=NULL;
+ alloc->size=0;
- if (!mem.is_valid()) {
- if (dvector_lock)
- dvector_lock->unlock();
- return;
+ MemoryPool::alloc_mutex->lock();
+ alloc->free_list=MemoryPool::free_list;
+ MemoryPool::free_list=alloc;
+ MemoryPool::allocs_used--;
+ MemoryPool::alloc_mutex->unlock();
+
}
- MID_Lock lock(mem);
+ alloc=NULL;
+ }
- int * rc = (int*)lock.data();
- (*rc)--;
+public:
- if (*rc==0) {
- // no one else using it, destruct
+ class Access {
+ friend class PoolVector;
+ protected:
+ MemoryPool::Alloc *alloc;
+ T * mem;
- T * t= (T*)(rc+1);
- int count = (mem.get_size() - sizeof(int)) / sizeof(T);
+ _FORCE_INLINE_ void _ref(MemoryPool::Alloc *p_alloc) {
+ alloc=p_alloc;
+ if (alloc) {
+ if (atomic_increment(&alloc->lock)==1) {
+ if (MemoryPool::memory_pool) {
+ //lock it and get mem
+ }
+ }
- for (int i=0;i<count;i++) {
+ mem = (T*)alloc->mem;
+ }
+ }
- t[i].~T();
+ _FORCE_INLINE_ void _unref() {
+
+
+ if (alloc) {
+ if (atomic_decrement(&alloc->lock)==0) {
+ if (MemoryPool::memory_pool) {
+ //put mem back
+ }
+ }
+
+ mem = NULL;
+ alloc=NULL;
}
+
}
+ Access() {
+ alloc=NULL;
+ mem=NULL;
+ }
- lock = MID_Lock();
- mem = MID ();
+ public:
+ virtual ~Access() {
+ _unref();
+ }
+ };
- if (dvector_lock)
- dvector_lock->unlock();
+ class Read : public Access {
+ public:
- }
+ _FORCE_INLINE_ const T& operator[](int p_index) const { return this->mem[p_index]; }
+ _FORCE_INLINE_ const T *ptr() const { return this->mem; }
-public:
+ void operator=(const Read& p_read) {
+ if (this->alloc==p_read.alloc)
+ return;
+ this->_unref();
+ this->_ref(p_read.alloc);
+ }
- class Read {
- friend class DVector;
- MID_Lock lock;
- const T * mem;
- public:
+ Read(const Read& p_read) {
+ this->_ref(p_read.alloc);
+ }
+
+ Read() {}
- _FORCE_INLINE_ const T& operator[](int p_index) const { return mem[p_index]; }
- _FORCE_INLINE_ const T *ptr() const { return mem; }
- Read() { mem=NULL; }
};
- class Write {
- friend class DVector;
- MID_Lock lock;
- T * mem;
+ class Write : public Access {
public:
- _FORCE_INLINE_ T& operator[](int p_index) { return mem[p_index]; }
- _FORCE_INLINE_ T *ptr() { return mem; }
+ _FORCE_INLINE_ T& operator[](int p_index) const { return this->mem[p_index]; }
+ _FORCE_INLINE_ T *ptr() const { return this->mem; }
+
+ void operator=(const Write& p_read) {
+ if (this->alloc==p_read.alloc)
+ return;
+ this->_unref();
+ this->_ref(p_read.alloc);
+ }
+
+ Write(const Write& p_read) {
+ this->_ref(p_read.alloc);
+ }
+
+ Write() {}
- Write() { mem=NULL; }
};
Read read() const {
Read r;
- if (mem.is_valid()) {
- r.lock = MID_Lock( mem );
- r.mem = (const T*)((int*)r.lock.data()+1);
+ if (alloc) {
+ r._ref(alloc);
}
return r;
+
}
Write write() {
Write w;
- if (mem.is_valid()) {
- copy_on_write();
- w.lock = MID_Lock( mem );
- w.mem = (T*)((int*)w.lock.data()+1);
+ if (alloc) {
+ _copy_on_write(); //make sure there is only one being acessed
+ w._ref(alloc);
}
return w;
}
@@ -250,7 +382,7 @@ public:
void set(int p_index, const T& p_val);
void push_back(const T& p_val);
void append(const T& p_val) { push_back(p_val); }
- void append_array(const DVector<T>& p_arr) {
+ void append_array(const PoolVector<T>& p_arr) {
int ds = p_arr.size();
if (ds==0)
return;
@@ -262,7 +394,7 @@ public:
w[bs+i]=r[i];
}
- DVector<T> subarray(int p_from, int p_to) {
+ PoolVector<T> subarray(int p_from, int p_to) {
if (p_from<0) {
p_from=size()+p_from;
@@ -271,15 +403,15 @@ public:
p_to=size()+p_to;
}
if (p_from<0 || p_from>=size()) {
- DVector<T>& aux=*((DVector<T>*)0); // nullreturn
+ PoolVector<T>& aux=*((PoolVector<T>*)0); // nullreturn
ERR_FAIL_COND_V(p_from<0 || p_from>=size(),aux)
}
if (p_to<0 || p_to>=size()) {
- DVector<T>& aux=*((DVector<T>*)0); // nullreturn
+ PoolVector<T>& aux=*((PoolVector<T>*)0); // nullreturn
ERR_FAIL_COND_V(p_to<0 || p_to>=size(),aux)
}
- DVector<T> slice;
+ PoolVector<T> slice;
int span=1 + p_to - p_from;
slice.resize(span);
Read r = read();
@@ -307,7 +439,7 @@ public:
}
- bool is_locked() const { return mem.is_locked(); }
+ bool is_locked() const { return alloc && alloc->lock>0; }
inline const T operator[](int p_index) const;
@@ -315,27 +447,27 @@ public:
void invert();
- void operator=(const DVector& p_dvector) { reference(p_dvector); }
- DVector() {}
- DVector(const DVector& p_dvector) { reference(p_dvector); }
- ~DVector() { unreference(); }
+ void operator=(const PoolVector& p_dvector) { _reference(p_dvector); }
+ PoolVector() { alloc=NULL; }
+ PoolVector(const PoolVector& p_dvector) { alloc=NULL; _reference(p_dvector); }
+ ~PoolVector() { _unreference(); }
};
template<class T>
-int DVector<T>::size() const {
+int PoolVector<T>::size() const {
- return mem.is_valid() ? ((mem.get_size() - sizeof(int)) / sizeof(T) ) : 0;
+ return alloc ? alloc->size/sizeof(T) : 0;
}
template<class T>
-T DVector<T>::get(int p_index) const {
+T PoolVector<T>::get(int p_index) const {
return operator[](p_index);
}
template<class T>
-void DVector<T>::set(int p_index, const T& p_val) {
+void PoolVector<T>::set(int p_index, const T& p_val) {
if (p_index<0 || p_index>=size()) {
ERR_FAIL_COND(p_index<0 || p_index>=size());
@@ -346,14 +478,14 @@ void DVector<T>::set(int p_index, const T& p_val) {
}
template<class T>
-void DVector<T>::push_back(const T& p_val) {
+void PoolVector<T>::push_back(const T& p_val) {
resize( size() + 1 );
set( size() -1, p_val );
}
template<class T>
-const T DVector<T>::operator[](int p_index) const {
+const T PoolVector<T>::operator[](int p_index) const {
if (p_index<0 || p_index>=size()) {
T& aux=*((T*)0); //nullreturn
@@ -367,94 +499,130 @@ const T DVector<T>::operator[](int p_index) const {
template<class T>
-Error DVector<T>::resize(int p_size) {
+Error PoolVector<T>::resize(int p_size) {
- if (dvector_lock)
- dvector_lock->lock();
- bool same = p_size==size();
+ if (alloc==NULL) {
- if (dvector_lock)
- dvector_lock->unlock();
- // no further locking is necesary because we are supposed to own the only copy of this (using copy on write)
+ if (p_size==0)
+ return OK; //nothing to do here
- if (same)
- return OK;
+ //must allocate something
+ MemoryPool::alloc_mutex->lock();
+ if (MemoryPool::allocs_used==MemoryPool::alloc_count) {
+ MemoryPool::alloc_mutex->unlock();
+ ERR_EXPLAINC("All memory pool allocations are in use.");
+ ERR_FAIL_V(ERR_OUT_OF_MEMORY);
+ }
- if (p_size == 0 ) {
+ //take one from the free list
+ alloc = MemoryPool::free_list;
+ MemoryPool::free_list = alloc->free_list;
+ //increment the used counter
+ MemoryPool::allocs_used++;
- unreference();
- return OK;
+ //cleanup the alloc
+ alloc->size=0;
+ alloc->refcount.init();
+ alloc->pool_id=POOL_ALLOCATOR_INVALID_ID;
+ MemoryPool::alloc_mutex->unlock();
+
+ } else {
+
+ ERR_FAIL_COND_V( alloc->lock>0, ERR_LOCKED ); //can't resize if locked!
}
+ size_t new_size = sizeof(T)*p_size;
- copy_on_write(); // make it unique
+ if (alloc->size==new_size)
+ return OK; //nothing to do
- ERR_FAIL_COND_V( mem.is_locked(), ERR_LOCKED ); // if after copy on write, memory is locked, fail.
+ if (p_size == 0 ) {
+ _unreference();
+ return OK;
+ }
- if (p_size > size() ) {
+ _copy_on_write(); // make it unique
- int oldsize=size();
+#ifdef DEBUG_ENABLED
+ MemoryPool::alloc_mutex->lock();
+ MemoryPool::total_memory-=alloc->size;
+ MemoryPool::total_memory+=new_size;
+ if (MemoryPool::total_memory>MemoryPool::max_memory) {
+ MemoryPool::max_memory=MemoryPool::total_memory;
+ }
+ MemoryPool::alloc_mutex->unlock();
+#endif
- MID_Lock lock;
- if (oldsize==0) {
+ int cur_elements = alloc->size / sizeof(T);
- mem = dynalloc( p_size * sizeof(T) + sizeof(int) );
- lock=MID_Lock(mem);
- int *rc = ((int*)lock.data());
- *rc=1;
+ if (p_size > cur_elements ) {
+ if (MemoryPool::memory_pool) {
+ //resize memory pool
+ //if none, create
+ //if some resize
} else {
- if (dynrealloc( mem, p_size * sizeof(T) + sizeof(int) )!=OK ) {
-
- ERR_FAIL_V(ERR_OUT_OF_MEMORY); // out of memory
+ if (alloc->size==0) {
+ alloc->mem = memalloc( new_size );
+ } else {
+ alloc->mem = memrealloc( alloc->mem, new_size );
}
-
- lock=MID_Lock(mem);
}
+ alloc->size=new_size;
+ Write w = write();
+ for (int i=cur_elements;i<p_size;i++) {
- T *t = (T*)((int*)lock.data() + 1);
-
- for (int i=oldsize;i<p_size;i++) {
-
- memnew_placement(&t[i], T );
+ memnew_placement(&w[i], T );
}
- lock = MID_Lock(); // clear
- } else {
-
- int oldsize=size();
-
- MID_Lock lock(mem);
+ } else {
- T *t = (T*)((int*)lock.data() + 1);
+ {
+ Write w;
+ for (int i=p_size;i<cur_elements;i++) {
- for (int i=p_size;i<oldsize;i++) {
+ w[i].~T();
+ }
- t[i].~T();
}
- lock = MID_Lock(); // clear
+ if (MemoryPool::memory_pool) {
+ //resize memory pool
+ //if none, create
+ //if some resize
+ } else {
+
+ if (new_size==0) {
+ memfree( alloc->mem );
+ alloc->mem=NULL;
+ alloc->size=0;
- if (dynrealloc( mem, p_size * sizeof(T) + sizeof(int) )!=OK ) {
+ MemoryPool::alloc_mutex->lock();
+ alloc->free_list=MemoryPool::free_list;
+ MemoryPool::free_list=alloc;
+ MemoryPool::allocs_used--;
+ MemoryPool::alloc_mutex->unlock();
- ERR_FAIL_V(ERR_OUT_OF_MEMORY); // wtf error
+ } else {
+ alloc->mem = memrealloc( alloc->mem, new_size );
+ alloc->size=new_size;
+ }
}
-
}
return OK;
}
template<class T>
-void DVector<T>::invert() {
+void PoolVector<T>::invert() {
T temp;
Write w = write();
int s = size();
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 04:11:15 +0000