From 213852915e08d6435b451c06045d0c6f5f611467 Mon Sep 17 00:00:00 2001 From: Thomas Grill Date: Mon, 18 Apr 2005 22:05:53 +0000 Subject: fixed typo fixed bugs in TableMaps fixes for OSX restructured TableMap type (doesn't own pointers any more) svn path=/trunk/; revision=2782 --- externals/grill/flext/source/flmap.h | 167 +++++++---------------------- externals/grill/flext/source/flsupport.cpp | 120 ++++++++++++--------- externals/grill/flext/source/flsupport.h | 6 ++ 3 files changed, 118 insertions(+), 175 deletions(-) (limited to 'externals/grill/flext/source') diff --git a/externals/grill/flext/source/flmap.h b/externals/grill/flext/source/flmap.h index 1ca0267d..0d82ad7f 100644 --- a/externals/grill/flext/source/flmap.h +++ b/externals/grill/flext/source/flmap.h @@ -21,71 +21,11 @@ WARRANTIES, see the file, "license.txt," in this distribution. @{ */ -#if 0 - -#include - -//! Key/Value type for AnyMap... must have size of pointer! -typedef size_t AnyMapType; - -//! Base class for maps -class AnyMap: - public std::map -{ - typedef std::map Parent; -public: - AnyMap(); - ~AnyMap(); - iterator find(AnyMapType k); - AnyMapType &operator [](AnyMapType k); - - typedef std::pair pair; -}; - -//! Specialized map class for any 32-bit key/value types -template -class DataMap: - public AnyMap -{ -public: - class iterator: - public AnyMap::iterator - { - public: - iterator() {} -#if defined(_MSC_VER) && (_MSC_VER < 0x1300) - // with the MSVC6 STL implementation iterators can't be initialized... - iterator(AnyMap::iterator it) { static_cast(*this) = it; } -#else - // note: &it doesn't work for gcc (i don't know why it doesn't...) - iterator(AnyMap::iterator it): AnyMap::iterator(it) {} -#endif - - inline K &key() const { return *(K *)&((*this)->first); } - inline T &data() const { return *(T *)&((*this)->second); } - }; - - class pair: - public AnyMap::pair - { - public: - inline K &key() const { return *(K *)&first; } - inline T &data() const { return *(T *)&second; } - }; - - inline iterator find(K k) { return AnyMap::find(*(AnyMapType *)&k); } - inline T &operator [](K k) { return *(T *)&(AnyMap::operator [](*(AnyMapType *)&k)); } - inline void erase(K k) { AnyMap::erase(*(AnyMapType *)&k); } -}; - -#endif - class FLEXT_SHARE TableAnyMap { protected: virtual TableAnyMap *_newmap(TableAnyMap *parent) = 0; virtual void _delmap(TableAnyMap *map) = 0; -// virtual void Free(void *ptr) = 0; struct Data { void operator()(size_t k,void *v) { key = k,value = v; } @@ -95,34 +35,36 @@ protected: void *value; }; - TableAnyMap(TableAnyMap *p,int sz,Data *dt) - : tsize(sz),data(dt) - , n(0) -// , count(0) + TableAnyMap(TableAnyMap *p,Data *dt) + : data(dt) , parent(p),left(NULL),right(NULL) + , n(0) {} virtual ~TableAnyMap(); -// int size() const { return count; } +#if 0 + void check(int tsize) { if(n) _check(tsize); } +#else + void check(int tsize) {} +#endif - void *insert(size_t k,void *t) + void *insert(int tsize,size_t k,void *t) { -// FLEXT_ASSERT(t); + void *r; if(n) - return _set(k,t); + r = _set(tsize,k,t); else { data[n++](k,t); -// ++count; - return NULL; + r = NULL; } + check(tsize); + return r; } - void *find(size_t k) const { return n?_find(k):NULL; } - -// void erase(size_t k) { if(n) { void *s = _remove(k); if(s) Free(s); } } + void *find(int tsize,size_t k) const { return n?_find(tsize,k):NULL; } - void *remove(size_t k) { return n?_remove(k):NULL; } + void *remove(int tsize,size_t k) { void *r = n?_remove(tsize,k):NULL; check(tsize); return r; } virtual void clear(); @@ -135,7 +77,7 @@ protected: iterator &operator =(const iterator &it) { map = it.map,ix = it.ix; return *this; } - operator bool() const { return map && /*ix >= 0 &&*/ ix < map->n; } + operator bool() const { return map && ix < map->n; } // no checking here! void *data() const { return map->data[ix].value; } @@ -158,54 +100,48 @@ protected: }; private: - void _init(size_t k,void *t) { data[0](k,t); n = /*count =*/ 1; } - void *_toleft(size_t k,void *t) + void _init(size_t k,void *t) { data[0](k,t); n = 1; } + + void *_toleft(int tsize,size_t k,void *t) { - if(left) { - void *a = left->_set(k,t); -// if(!a) ++count; - return a; - } + if(left) + return left->_set(tsize,k,t); else { (left = _newmap(this))->_init(k,t); - // ++count; return NULL; } } - void *_toright(size_t k,void *t) + void *_toright(int tsize,size_t k,void *t) { - if(right) { - void *a = right->_set(k,t); -// if(!a) ++count; - return a; - } + if(right) + return right->_set(tsize,k,t); else { (right = _newmap(this))->_init(k,t); -// ++count; return NULL; } } - void *_toleft(Data &v) { return _toleft(v.key,v.value); } - void *_toright(Data &v) { return _toright(v.key,v.value); } + void *_toleft(int tsize,Data &v) { return _toleft(tsize,v.key,v.value); } + void *_toright(int tsize,Data &v) { return _toright(tsize,v.key,v.value); } - void *_set(size_t k,void *t); - void *_find(size_t k) const; - void *_remove(size_t k); + void *_set(int tsize,size_t k,void *t); + void *_find(int tsize,size_t k) const; + void *_remove(int tsize,size_t k); + +#ifdef FLEXT_DEBUG + void _check(int tsize); +#endif - const int tsize; Data *const data; - int n; -// int count; TableAnyMap *parent,*left,*right; + short n; //! return index of data item with key <= k //! \note index can point past the last item! int _tryix(size_t k) const { -// FLEXT_ASSERT(n); int ix = 0; { int b = n; @@ -229,7 +165,6 @@ private: void _eraseempty(TableAnyMap *&b) { -// FLEXT_ASSERT(b); if(!b->n) { // remove empty branch _delmap(b); b = NULL; @@ -245,7 +180,7 @@ class TablePtrMap : TableAnyMap { public: - TablePtrMap(): TableAnyMap(NULL,N,slots),count(0) {} + TablePtrMap(): TableAnyMap(NULL,slots),count(0) {} virtual ~TablePtrMap() { clear(); } virtual void clear() { TableAnyMap::clear(); count = 0; } @@ -254,17 +189,16 @@ public: inline T insert(K k,T t) { - void *d = TableAnyMap::insert(*(size_t *)&k,(void *)t); + void *d = TableAnyMap::insert(N,*(size_t *)&k,(void *)t); if(!d) ++count; return (T)d; } - inline T find(K k) const { return (T)TableAnyMap::find(*(size_t *)&k); } + inline T find(K k) const { return (T)TableAnyMap::find(N,*(size_t *)&k); } -// inline void erase(K k) { TableAnyMap::erase(*(size_t *)&k); } inline T remove(K k) { - void *d = TableAnyMap::remove(*(size_t *)&k); + void *d = TableAnyMap::remove(N,*(size_t *)&k); if(d) --count; return (T)d; } @@ -288,36 +222,15 @@ public: }; protected: - TablePtrMap(TableAnyMap *p): TableAnyMap(p,N,slots),count(0) {} + TablePtrMap(TableAnyMap *p): TableAnyMap(p,slots),count(0) {} virtual TableAnyMap *_newmap(TableAnyMap *parent) { return new TablePtrMap(parent); } virtual void _delmap(TableAnyMap *map) { delete (TablePtrMap *)map; } -// virtual void Free(void *ptr) {} - int count; Data slots[N]; }; -#if 0 -template -class TablePtrMapOwned - : public TablePtrMap -{ -public: - virtual ~TablePtrMapOwned() { TablePtrMapOwned::clear(); } - -protected: -/* - virtual void Free(void *ptr) - { -// FLEXT_ASSERT(ptr); - delete (T)ptr; - } -*/ -}; -#endif - //! @} // FLEXT_SUPPORT #endif diff --git a/externals/grill/flext/source/flsupport.cpp b/externals/grill/flext/source/flsupport.cpp index 5b33352c..3a608fa8 100644 --- a/externals/grill/flext/source/flsupport.cpp +++ b/externals/grill/flext/source/flsupport.cpp @@ -115,10 +115,16 @@ void flext::Setup() #define LARGEALLOC 32000 +#ifdef FLEXT_DEBUGMEM +static const size_t memtest = 0x12345678L; +#endif + void *flext_root::operator new(size_t bytes) { bytes += sizeof(size_t); - +#ifdef FLEXT_DEBUGMEM + bytes += sizeof(memtest)*2; +#endif char *blk; if(bytes >= LARGEALLOC) { #if FLEXT_SYS == FLEXT_SYS_MAX && defined(_SYSMEM_H_) @@ -145,14 +151,25 @@ void *flext_root::operator new(size_t bytes) FLEXT_ASSERT(blk); *(size_t *)blk = bytes; +#ifdef FLEXT_DEBUGMEM + *(size_t *)(blk+sizeof(size_t)) = memtest; + *(size_t *)(blk+bytes-sizeof(memtest)) = memtest; + return blk+sizeof(size_t)+sizeof(memtest); +#else return blk+sizeof(size_t); +#endif } void flext_root::operator delete(void *blk) { FLEXT_ASSERT(blk); + FLEXT_ASSERT(MemCheck(blk)); - char *ori = (char *)blk-sizeof(size_t); +#ifdef FLEXT_DEBUGMEM + char *ori = (char *)blk-sizeof(size_t)-sizeof(memtest); +#else + char *ori = (char *)blk-sizeof(size_t); +#endif size_t bytes = *(size_t *)ori; if(bytes >= LARGEALLOC) { @@ -178,6 +195,18 @@ void flext_root::operator delete(void *blk) } } +#ifdef FLEXT_DEBUGMEM +bool flext_root::MemCheck(void *blk) +{ + char *ori = (char *)blk-sizeof(size_t)-sizeof(memtest); + size_t bytes = *(size_t *)ori; + + return + *(size_t *)((char *)ori+sizeof(size_t)) == memtest && + *(size_t *)((char *)ori+bytes-sizeof(memtest)) == memtest; +} +#endif + void *flext_root::NewAligned(size_t bytes,int bitalign) { const size_t ovh = sizeof(size_t)+sizeof(char *); @@ -297,12 +326,6 @@ void flext_root::error(const char *fmt,...) va_end(ap); } -#if 0 -AnyMap::AnyMap() {} -AnyMap::~AnyMap() {} -AnyMap::iterator AnyMap::find(AnyMapType k) { return Parent::find(k); } -AnyMapType &AnyMap::operator [](AnyMapType k) { return Parent::operator [](k); } -#endif TableAnyMap::~TableAnyMap() { clear(); } @@ -310,25 +333,11 @@ void TableAnyMap::clear() { if(left) { _delmap(left); left = NULL; } if(right) { _delmap(right); right = NULL; } - -// for(int i = 0; i < n; ++i) Free(data[i].value); - /*count = */n = 0; + n = 0; } -/* -int TableAnyMap::size() const -{ - int sz = n; - if(sz >= tsize) { - if(left) sz += left->size(); - if(right) sz += right->size(); - } - FLEXT_ASSERT(sz == count); - return sz; -} -*/ -void *TableAnyMap::_set(size_t k,void *t) +void *TableAnyMap::_set(int tsize,size_t k,void *t) { FLEXT_ASSERT(n); @@ -336,16 +345,15 @@ void *TableAnyMap::_set(size_t k,void *t) // fall through } else if(k < data[0].key) - return _toleft(k,t); + return _toleft(tsize,k,t); else if(k > data[tsize-1].key) - return _toright(k,t); + return _toright(tsize,k,t); int ix = _tryix(k); if(ix >= n) { FLEXT_ASSERT(ix == n); // after last entry data[n++](k,t); -// ++count; return NULL; } @@ -361,10 +369,9 @@ void *TableAnyMap::_set(size_t k,void *t) FLEXT_ASSERT(k < dk); void *a; if(n == tsize) - a = _toright(data[tsize-1]); + a = _toright(tsize,data[tsize-1]); else { ++n; -// ++count; a = NULL; } @@ -375,41 +382,60 @@ void *TableAnyMap::_set(size_t k,void *t) } } -void *TableAnyMap::_find(size_t k) const +void *TableAnyMap::_find(int tsize,size_t k) const { FLEXT_ASSERT(n); if(n < tsize) { // fall through } else if(k < data[0].key) - return left?left->_find(k):NULL; + return left?left->_find(tsize,k):NULL; else if(k > data[n-1].key) - return right?right->_find(k):NULL; + return right?right->_find(tsize,k):NULL; const int ix = _tryix(k); return ix < n && data[ix].key == k?data[ix].value:NULL; } -void *TableAnyMap::_remove(size_t k) +#ifdef FLEXT_DEBUG +void TableAnyMap::_check(int tsize) +{ + FLEXT_ASSERT(n); + + size_t k = data[0].key; + for(int i = 1; i < n; ++i) { + size_t k2 = data[i].key; + FLEXT_ASSERT(k < k2); + k = k2; + } + + if(left || right) FLEXT_ASSERT(n == tsize); + + if(left) { + FLEXT_ASSERT(flext::MemCheck(left)); + left->_check(tsize); + } + if(right) { + FLEXT_ASSERT(flext::MemCheck(right)); + right->_check(tsize); + } +} +#endif + +void *TableAnyMap::_remove(int tsize,size_t k) { FLEXT_ASSERT(n); if(n < tsize) { // fall through } else if(k < data[0].key) { - void *r = left?left->_remove(k):NULL; - if(r) { - _eraseempty(left); -// --count; - } + void *r = left?left->_remove(tsize,k):NULL; + if(r) _eraseempty(left); return r; } else if(k > data[n-1].key) { - void *r = right?right->_remove(k):NULL; - if(r) { - _eraseempty(right); -// --count; - } + void *r = right?right->_remove(tsize,k):NULL; + if(r) _eraseempty(right); return r; } @@ -456,7 +482,6 @@ void *TableAnyMap::_remove(size_t k) --n; } -// --count; return ret; } } @@ -470,15 +495,15 @@ void TableAnyMap::_getbig(Data &dt) _eraseempty(right); } else { + dt = data[n-1]; if(left) { - for(int i = n; i; --i) data[i] = data[i-1]; + for(int i = n-1; i; --i) data[i] = data[i-1]; left->_getbig(data[0]); _eraseempty(left); } else - dt = data[--n]; + --n; } -// --count; } void TableAnyMap::_getsmall(Data &dt) @@ -499,7 +524,6 @@ void TableAnyMap::_getsmall(Data &dt) else --n; } -// --count; } void TableAnyMap::iterator::forward() diff --git a/externals/grill/flext/source/flsupport.h b/externals/grill/flext/source/flsupport.h index ead75804..e38697f4 100644 --- a/externals/grill/flext/source/flsupport.h +++ b/externals/grill/flext/source/flsupport.h @@ -56,6 +56,12 @@ public: inline void *operator new(size_t,void *p) { return p; } inline void operator delete(void *,void *) {} +#ifdef FLEXT_DEBUGMEM + static bool MemCheck(void *blk); +#else + static bool MemCheck(void *) { return true; } +#endif + #ifndef __MRC__ // doesn't allow new[] overloading?! inline void *operator new[](size_t bytes) { return operator new(bytes); } inline void operator delete[](void *blk) { operator delete(blk); } -- cgit v1.2.1