summaryrefslogtreecommitdiff
path: root/core/dvector.h
diff options
context:
space:
mode:
Diffstat (limited to 'core/dvector.h')
-rw-r--r--core/dvector.h367
1 files changed, 167 insertions, 200 deletions
diff --git a/core/dvector.h b/core/dvector.h
index 456be41289..3f4318216d 100644
--- a/core/dvector.h
+++ b/core/dvector.h
@@ -29,11 +29,11 @@
#ifndef DVECTOR_H
#define DVECTOR_H
-#include "os/memory.h"
#include "os/copymem.h"
+#include "os/memory.h"
+#include "os/rw_lock.h"
#include "pool_allocator.h"
#include "safe_refcount.h"
-#include "os/rw_lock.h"
#include "ustring.h"
struct MemoryPool {
@@ -44,7 +44,6 @@ struct MemoryPool {
static uint8_t *pool_memory;
static size_t *pool_size;
-
struct Alloc {
SafeRefCount refcount;
@@ -55,10 +54,15 @@ struct MemoryPool {
Alloc *free_list;
- Alloc() { mem=NULL; lock=0; pool_id=POOL_ALLOCATOR_INVALID_ID; size=0; free_list=NULL; }
+ 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;
@@ -67,39 +71,33 @@ struct MemoryPool {
static size_t total_memory;
static size_t max_memory;
-
- static void setup(uint32_t p_max_allocs=(1<<16));
+ static void setup(uint32_t p_max_allocs = (1 << 16));
static void cleanup();
};
-
/**
@author Juan Linietsky <reduzio@gmail.com>
*/
-
-template<class T>
+template <class T>
class PoolVector {
MemoryPool::Alloc *alloc;
-
void _copy_on_write() {
-
if (!alloc)
return;
-// ERR_FAIL_COND(alloc->lock>0); should not be illegal to lock this for copy on write, as it's a copy on write after all
+ // ERR_FAIL_COND(alloc->lock>0); should not be illegal to lock this for copy on write, as it's a copy on write after all
- if (alloc->refcount.get()==1)
+ if (alloc->refcount.get() == 1)
return; //nothing to do
-
//must allocate something
MemoryPool::alloc_mutex->lock();
- if (MemoryPool::allocs_used==MemoryPool::alloc_count) {
+ 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();
@@ -114,26 +112,24 @@ class PoolVector {
MemoryPool::allocs_used++;
//copy the alloc data
- alloc->size=old_alloc->size;
+ alloc->size = old_alloc->size;
alloc->refcount.init();
- alloc->pool_id=POOL_ALLOCATOR_INVALID_ID;
- alloc->lock=0;
+ alloc->pool_id = POOL_ALLOCATOR_INVALID_ID;
+ alloc->lock = 0;
#ifdef DEBUG_ENABLED
- MemoryPool::total_memory+=alloc->size;
- if (MemoryPool::total_memory>MemoryPool::max_memory) {
- MemoryPool::max_memory=MemoryPool::total_memory;
+ MemoryPool::total_memory += alloc->size;
+ if (MemoryPool::total_memory > MemoryPool::max_memory) {
+ MemoryPool::max_memory = MemoryPool::total_memory;
}
#endif
MemoryPool::alloc_mutex->unlock();
-
if (MemoryPool::memory_pool) {
-
} else {
- alloc->mem = memalloc( alloc->size );
+ alloc->mem = memalloc(alloc->size);
}
{
@@ -142,21 +138,20 @@ class PoolVector {
Read r;
r._ref(old_alloc);
- int cur_elements = alloc->size/sizeof(T);
- T*dst = (T*)w.ptr();
- const T*src = (const T*)r.ptr();
- for(int i=0;i<cur_elements;i++) {
- memnew_placement(&dst[i],T(src[i]));
+ int cur_elements = alloc->size / sizeof(T);
+ T *dst = (T *)w.ptr();
+ const T *src = (const T *)r.ptr();
+ for (int i = 0; i < cur_elements; i++) {
+ memnew_placement(&dst[i], T(src[i]));
}
}
-
- if (old_alloc->refcount.unref()==true) {
- //this should never happen but..
+ if (old_alloc->refcount.unref() == true) {
+//this should never happen but..
#ifdef DEBUG_ENABLED
MemoryPool::alloc_mutex->lock();
- MemoryPool::total_memory-=old_alloc->size;
+ MemoryPool::total_memory -= old_alloc->size;
MemoryPool::alloc_mutex->unlock();
#endif
@@ -164,12 +159,11 @@ class PoolVector {
Write w;
w._ref(old_alloc);
- int cur_elements = old_alloc->size/sizeof(T);
- T*elems = (T*)w.ptr();
- for(int i=0;i<cur_elements;i++) {
+ int cur_elements = old_alloc->size / sizeof(T);
+ T *elems = (T *)w.ptr();
+ for (int i = 0; i < cur_elements; i++) {
elems[i].~T();
}
-
}
if (MemoryPool::memory_pool) {
@@ -178,26 +172,22 @@ class PoolVector {
//if some resize
} else {
-
- memfree( old_alloc->mem );
- old_alloc->mem=NULL;
- old_alloc->size=0;
-
+ memfree(old_alloc->mem);
+ old_alloc->mem = NULL;
+ old_alloc->size = 0;
MemoryPool::alloc_mutex->lock();
- old_alloc->free_list=MemoryPool::free_list;
- MemoryPool::free_list=old_alloc;
+ old_alloc->free_list = MemoryPool::free_list;
+ MemoryPool::free_list = old_alloc;
MemoryPool::allocs_used--;
MemoryPool::alloc_mutex->unlock();
}
-
}
-
}
- void _reference( const PoolVector& p_dvector ) {
+ void _reference(const PoolVector &p_dvector) {
- if (alloc==p_dvector.alloc)
+ if (alloc == p_dvector.alloc)
return;
_unreference();
@@ -207,108 +197,98 @@ class PoolVector {
}
if (p_dvector.alloc->refcount.ref()) {
- alloc=p_dvector.alloc;
+ alloc = p_dvector.alloc;
}
-
}
-
void _unreference() {
if (!alloc)
return;
- if (alloc->refcount.unref()==false) {
- alloc=NULL;
+ if (alloc->refcount.unref() == false) {
+ alloc = NULL;
return;
}
//must be disposed!
{
- int cur_elements = alloc->size/sizeof(T);
+ int cur_elements = alloc->size / sizeof(T);
Write w = write();
- for (int i=0;i<cur_elements;i++) {
+ for (int i = 0; i < cur_elements; i++) {
w[i].~T();
}
-
}
#ifdef DEBUG_ENABLED
MemoryPool::alloc_mutex->lock();
- MemoryPool::total_memory-=alloc->size;
+ MemoryPool::total_memory -= alloc->size;
MemoryPool::alloc_mutex->unlock();
#endif
-
if (MemoryPool::memory_pool) {
//resize memory pool
//if none, create
//if some resize
} else {
- memfree( alloc->mem );
- alloc->mem=NULL;
- alloc->size=0;
-
+ memfree(alloc->mem);
+ alloc->mem = NULL;
+ alloc->size = 0;
MemoryPool::alloc_mutex->lock();
- alloc->free_list=MemoryPool::free_list;
- MemoryPool::free_list=alloc;
+ alloc->free_list = MemoryPool::free_list;
+ MemoryPool::free_list = alloc;
MemoryPool::allocs_used--;
MemoryPool::alloc_mutex->unlock();
-
}
- alloc=NULL;
+ alloc = NULL;
}
public:
-
class Access {
- friend class PoolVector;
+ friend class PoolVector;
+
protected:
MemoryPool::Alloc *alloc;
- T * mem;
+ T *mem;
_FORCE_INLINE_ void _ref(MemoryPool::Alloc *p_alloc) {
- alloc=p_alloc;
+ alloc = p_alloc;
if (alloc) {
- if (atomic_increment(&alloc->lock)==1) {
+ if (atomic_increment(&alloc->lock) == 1) {
if (MemoryPool::memory_pool) {
//lock it and get mem
}
}
- mem = (T*)alloc->mem;
+ mem = (T *)alloc->mem;
}
}
_FORCE_INLINE_ void _unref() {
-
if (alloc) {
- if (atomic_decrement(&alloc->lock)==0) {
+ if (atomic_decrement(&alloc->lock) == 0) {
if (MemoryPool::memory_pool) {
//put mem back
}
}
mem = NULL;
- alloc=NULL;
+ alloc = NULL;
}
-
-
}
Access() {
- alloc=NULL;
- mem=NULL;
+ alloc = NULL;
+ mem = NULL;
}
-
public:
virtual ~Access() {
_unref();
@@ -317,48 +297,42 @@ public:
class Read : public Access {
public:
-
- _FORCE_INLINE_ const T& operator[](int p_index) const { return this->mem[p_index]; }
+ _FORCE_INLINE_ const T &operator[](int p_index) const { return this->mem[p_index]; }
_FORCE_INLINE_ const T *ptr() const { return this->mem; }
- void operator=(const Read& p_read) {
- if (this->alloc==p_read.alloc)
+ void operator=(const Read &p_read) {
+ if (this->alloc == p_read.alloc)
return;
this->_unref();
this->_ref(p_read.alloc);
}
- Read(const Read& p_read) {
+ Read(const Read &p_read) {
this->_ref(p_read.alloc);
}
Read() {}
-
-
};
class Write : public Access {
public:
-
- _FORCE_INLINE_ T& operator[](int p_index) const { return this->mem[p_index]; }
+ _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)
+ 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) {
+ Write(const Write &p_read) {
this->_ref(p_read.alloc);
}
Write() {}
-
};
-
Read read() const {
Read r;
@@ -366,7 +340,6 @@ public:
r._ref(alloc);
}
return r;
-
}
Write write() {
@@ -378,90 +351,88 @@ public:
return w;
}
- template<class MC>
- void fill_with(const MC& p_mc) {
-
+ template <class MC>
+ void fill_with(const MC &p_mc) {
- int c=p_mc.size();
+ int c = p_mc.size();
resize(c);
- Write w=write();
- int idx=0;
- for(const typename MC::Element *E=p_mc.front();E;E=E->next()) {
+ Write w = write();
+ int idx = 0;
+ for (const typename MC::Element *E = p_mc.front(); E; E = E->next()) {
- w[idx++]=E->get();
+ w[idx++] = E->get();
}
}
-
void remove(int p_index) {
int s = size();
ERR_FAIL_INDEX(p_index, s);
Write w = write();
- for (int i=p_index; i<s-1; i++) {
+ for (int i = p_index; i < s - 1; i++) {
- w[i]=w[i+1];
+ w[i] = w[i + 1];
};
w = Write();
- resize(s-1);
+ resize(s - 1);
}
inline int size() const;
T get(int p_index) const;
- 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 PoolVector<T>& p_arr) {
+ 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 PoolVector<T> &p_arr) {
int ds = p_arr.size();
- if (ds==0)
+ if (ds == 0)
return;
int bs = size();
- resize( bs + ds);
+ resize(bs + ds);
Write w = write();
Read r = p_arr.read();
- for(int i=0;i<ds;i++)
- w[bs+i]=r[i];
+ for (int i = 0; i < ds; i++)
+ w[bs + i] = r[i];
}
PoolVector<T> subarray(int p_from, int p_to) {
- if (p_from<0) {
- p_from=size()+p_from;
+ if (p_from < 0) {
+ p_from = size() + p_from;
}
- if (p_to<0) {
- p_to=size()+p_to;
+ if (p_to < 0) {
+ p_to = size() + p_to;
}
- if (p_from<0 || p_from>=size()) {
- PoolVector<T>& aux=*((PoolVector<T>*)0); // nullreturn
- ERR_FAIL_COND_V(p_from<0 || p_from>=size(),aux)
+ if (p_from < 0 || p_from >= size()) {
+ 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()) {
- PoolVector<T>& aux=*((PoolVector<T>*)0); // nullreturn
- ERR_FAIL_COND_V(p_to<0 || p_to>=size(),aux)
+ if (p_to < 0 || p_to >= size()) {
+ PoolVector<T> &aux = *((PoolVector<T> *)0); // nullreturn
+ ERR_FAIL_COND_V(p_to < 0 || p_to >= size(), aux)
}
PoolVector<T> slice;
- int span=1 + p_to - p_from;
+ int span = 1 + p_to - p_from;
slice.resize(span);
Read r = read();
Write w = slice.write();
- for (int i=0; i<span; ++i) {
- w[i] = r[p_from+i];
+ for (int i = 0; i < span; ++i) {
+ w[i] = r[p_from + i];
}
return slice;
}
- Error insert(int p_pos,const T& p_val) {
+ Error insert(int p_pos, const T &p_val) {
- int s=size();
- ERR_FAIL_INDEX_V(p_pos,s+1,ERR_INVALID_PARAMETER);
- resize(s+1);
+ int s = size();
+ ERR_FAIL_INDEX_V(p_pos, s + 1, ERR_INVALID_PARAMETER);
+ resize(s + 1);
{
Write w = write();
- for (int i=s;i>p_pos;i--)
- w[i]=w[i-1];
- w[p_pos]=p_val;
+ for (int i = s; i > p_pos; i--)
+ w[i] = w[i - 1];
+ w[p_pos] = p_val;
}
return OK;
@@ -471,14 +442,14 @@ public:
String rs = "";
int s = size();
Read r = read();
- for(int i=0;i<s;i++) {
+ for (int i = 0; i < s; i++) {
rs += r[i] + delimiter;
}
- rs.erase( rs.length()-delimiter.length(), delimiter.length());
+ rs.erase(rs.length() - delimiter.length(), delimiter.length());
return rs;
}
- bool is_locked() const { return alloc && alloc->lock>0; }
+ bool is_locked() const { return alloc && alloc->lock > 0; }
inline const T operator[](int p_index) const;
@@ -486,49 +457,51 @@ public:
void invert();
- void operator=(const PoolVector& p_dvector) { _reference(p_dvector); }
- PoolVector() { alloc=NULL; }
- PoolVector(const PoolVector& p_dvector) { alloc=NULL; _reference(p_dvector); }
+ 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>
+template <class T>
int PoolVector<T>::size() const {
- return alloc ? alloc->size/sizeof(T) : 0;
+ return alloc ? alloc->size / sizeof(T) : 0;
}
-template<class T>
+template <class T>
T PoolVector<T>::get(int p_index) const {
return operator[](p_index);
}
-template<class T>
-void PoolVector<T>::set(int p_index, const T& p_val) {
+template <class T>
+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());
+ if (p_index < 0 || p_index >= size()) {
+ ERR_FAIL_COND(p_index < 0 || p_index >= size());
}
Write w = write();
- w[p_index]=p_val;
+ w[p_index] = p_val;
}
-template<class T>
-void PoolVector<T>::push_back(const T& p_val) {
+template <class T>
+void PoolVector<T>::push_back(const T &p_val) {
- resize( size() + 1 );
- set( size() -1, p_val );
+ resize(size() + 1);
+ set(size() - 1, p_val);
}
-template<class T>
+template <class T>
const T PoolVector<T>::operator[](int p_index) const {
- if (p_index<0 || p_index>=size()) {
- T& aux=*((T*)0); //nullreturn
- ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux);
+ if (p_index < 0 || p_index >= size()) {
+ T &aux = *((T *)0); //nullreturn
+ ERR_FAIL_COND_V(p_index < 0 || p_index >= size(), aux);
}
Read r = read();
@@ -536,19 +509,17 @@ const T PoolVector<T>::operator[](int p_index) const {
return r[p_index];
}
-
-template<class T>
+template <class T>
Error PoolVector<T>::resize(int p_size) {
+ if (alloc == NULL) {
- if (alloc==NULL) {
-
- if (p_size==0)
+ if (p_size == 0)
return OK; //nothing to do here
//must allocate something
MemoryPool::alloc_mutex->lock();
- if (MemoryPool::allocs_used==MemoryPool::alloc_count) {
+ 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);
@@ -561,22 +532,22 @@ Error PoolVector<T>::resize(int p_size) {
MemoryPool::allocs_used++;
//cleanup the alloc
- alloc->size=0;
+ alloc->size = 0;
alloc->refcount.init();
- alloc->pool_id=POOL_ALLOCATOR_INVALID_ID;
+ 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!
+ ERR_FAIL_COND_V(alloc->lock > 0, ERR_LOCKED); //can't resize if locked!
}
- size_t new_size = sizeof(T)*p_size;
+ size_t new_size = sizeof(T) * p_size;
- if (alloc->size==new_size)
+ if (alloc->size == new_size)
return OK; //nothing to do
- if (p_size == 0 ) {
+ if (p_size == 0) {
_unreference();
return OK;
}
@@ -585,18 +556,17 @@ Error PoolVector<T>::resize(int p_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::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
-
int cur_elements = alloc->size / sizeof(T);
- if (p_size > cur_elements ) {
+ if (p_size > cur_elements) {
if (MemoryPool::memory_pool) {
//resize memory pool
@@ -604,32 +574,30 @@ Error PoolVector<T>::resize(int p_size) {
//if some resize
} else {
- if (alloc->size==0) {
- alloc->mem = memalloc( new_size );
+ if (alloc->size == 0) {
+ alloc->mem = memalloc(new_size);
} else {
- alloc->mem = memrealloc( alloc->mem, new_size );
+ alloc->mem = memrealloc(alloc->mem, new_size);
}
}
- alloc->size=new_size;
+ alloc->size = new_size;
Write w = write();
- for (int i=cur_elements;i<p_size;i++) {
+ for (int i = cur_elements; i < p_size; i++) {
- memnew_placement(&w[i], T );
+ memnew_placement(&w[i], T);
}
-
} else {
{
Write w = write();
- for (int i=p_size;i<cur_elements;i++) {
+ for (int i = p_size; i < cur_elements; i++) {
w[i].~T();
}
-
}
if (MemoryPool::memory_pool) {
@@ -638,39 +606,38 @@ Error PoolVector<T>::resize(int p_size) {
//if some resize
} else {
- if (new_size==0) {
- memfree( alloc->mem );
- alloc->mem=NULL;
- alloc->size=0;
+ if (new_size == 0) {
+ memfree(alloc->mem);
+ alloc->mem = NULL;
+ alloc->size = 0;
MemoryPool::alloc_mutex->lock();
- alloc->free_list=MemoryPool::free_list;
- MemoryPool::free_list=alloc;
+ alloc->free_list = MemoryPool::free_list;
+ MemoryPool::free_list = alloc;
MemoryPool::allocs_used--;
MemoryPool::alloc_mutex->unlock();
} else {
- alloc->mem = memrealloc( alloc->mem, new_size );
- alloc->size=new_size;
+ alloc->mem = memrealloc(alloc->mem, new_size);
+ alloc->size = new_size;
}
}
-
}
return OK;
}
-template<class T>
+template <class T>
void PoolVector<T>::invert() {
T temp;
Write w = write();
int s = size();
- int half_s = s/2;
+ int half_s = s / 2;
- for(int i=0;i<half_s;i++) {
+ for (int i = 0; i < half_s; i++) {
temp = w[i];
- w[i] = w[s-i-1];
- w[s-i-1] = temp;
+ w[i] = w[s - i - 1];
+ w[s - i - 1] = temp;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 04:03:25 +0000