Update of /cvsroot/pure-data/externals/grill/flext/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25304/source
Modified Files:
flmap.h flsupport.cpp flsupport.h
Log Message:
fixed typo
fixed bugs in TableMaps
fixes for OSX
restructured TableMap type (doesn't own pointers any more)
Index: flmap.h
===================================================================
RCS file: /cvsroot/pure-data/externals/grill/flext/source/flmap.h,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -d -r1.15 -r1.16
*** flmap.h 18 Apr 2005 15:07:40 -0000 1.15
--- flmap.h 18 Apr 2005 22:05:52 -0000 1.16
***************
*** 22,84 ****
*/
- #if 0
-
- #include <map>
-
- //! Key/Value type for AnyMap... must have size of pointer!
- typedef size_t AnyMapType;
-
- //! Base class for maps
- class AnyMap:
- public std::map<AnyMapType,AnyMapType>
- {
- typedef std::map<AnyMapType,AnyMapType> Parent;
- public:
- AnyMap();
- ~AnyMap();
- iterator find(AnyMapType k);
- AnyMapType &operator [](AnyMapType k);
-
- typedef std::pair<AnyMapType,AnyMapType> pair;
- };
-
- //! Specialized map class for any 32-bit key/value types
- template <class K,class T>
- 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<AnyMap::iterator &>(*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
{
--- 22,25 ----
***************
*** 86,90 ****
virtual TableAnyMap *_newmap(TableAnyMap *parent) = 0;
virtual void _delmap(TableAnyMap *map) = 0;
- // virtual void Free(void *ptr) = 0;
struct Data {
--- 27,30 ----
***************
*** 96,127 ****
};
! TableAnyMap(TableAnyMap *p,int sz,Data *dt)
! : tsize(sz),data(dt)
! , n(0)
! // , count(0)
, parent(p),left(NULL),right(NULL)
{}
virtual ~TableAnyMap();
! // int size() const { return count; }
! void *insert(size_t k,void *t)
{
! // FLEXT_ASSERT(t);
if(n)
! return _set(k,t);
else {
data[n++](k,t);
! // ++count;
! return NULL;
}
}
! 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 *remove(size_t k) { return n?_remove(k):NULL; }
virtual void clear();
--- 36,69 ----
};
! TableAnyMap(TableAnyMap *p,Data *dt)
! : data(dt)
, parent(p),left(NULL),right(NULL)
+ , n(0)
{}
virtual ~TableAnyMap();
! #if 0
! void check(int tsize) { if(n) _check(tsize); }
! #else
! void check(int tsize) {}
! #endif
! void *insert(int tsize,size_t k,void *t)
{
! void *r;
if(n)
! r = _set(tsize,k,t);
else {
data[n++](k,t);
! r = NULL;
}
+ check(tsize);
+ return r;
}
! void *find(int tsize,size_t k) const { return n?_find(tsize,k):NULL; }
! void *remove(int tsize,size_t k) { void *r = n?_remove(tsize,k):NULL; check(tsize); return r; }
virtual void clear();
***************
*** 136,140 ****
iterator &operator =(const iterator &it) { map = it.map,ix = it.ix; return *this; }
! operator bool() const { return map && /*ix >= 0 &&*/ ix < map->n; }
// no checking here!
--- 78,82 ----
iterator &operator =(const iterator &it) { map = it.map,ix = it.ix; return *this; }
! operator bool() const { return map && ix < map->n; }
// no checking here!
***************
*** 159,204 ****
private:
- void _init(size_t k,void *t) { data[0](k,t); n = /*count =*/ 1; }
! void *_toleft(size_t k,void *t)
{
! if(left) {
! void *a = left->_set(k,t);
! // if(!a) ++count;
! return a;
! }
else {
(left = _newmap(this))->_init(k,t);
- // ++count;
return NULL;
}
}
! void *_toright(size_t k,void *t)
{
! if(right) {
! void *a = right->_set(k,t);
! // if(!a) ++count;
! return a;
! }
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 *_set(size_t k,void *t);
! void *_find(size_t k) const;
! void *_remove(size_t k);
- const int tsize;
Data *const data;
- int n;
- // int count;
TableAnyMap *parent,*left,*right;
//! return index of data item with key <= k
--- 101,141 ----
private:
! void _init(size_t k,void *t) { data[0](k,t); n = 1; }
!
! void *_toleft(int tsize,size_t k,void *t)
{
! if(left)
! return left->_set(tsize,k,t);
else {
(left = _newmap(this))->_init(k,t);
return NULL;
}
}
! void *_toright(int tsize,size_t k,void *t)
{
! if(right)
! return right->_set(tsize,k,t);
else {
(right = _newmap(this))->_init(k,t);
return NULL;
}
}
! 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(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
Data *const data;
TableAnyMap *parent,*left,*right;
+ short n;
//! return index of data item with key <= k
***************
*** 206,210 ****
int _tryix(size_t k) const
{
- // FLEXT_ASSERT(n);
int ix = 0;
{
--- 143,146 ----
***************
*** 230,234 ****
void _eraseempty(TableAnyMap *&b)
{
- // FLEXT_ASSERT(b);
if(!b->n) {
// remove empty branch
--- 166,169 ----
***************
*** 246,250 ****
{
public:
! TablePtrMap(): TableAnyMap(NULL,N,slots),count(0) {}
virtual ~TablePtrMap() { clear(); }
--- 181,185 ----
{
public:
! TablePtrMap(): TableAnyMap(NULL,slots),count(0) {}
virtual ~TablePtrMap() { clear(); }
***************
*** 255,269 ****
inline T insert(K k,T t)
{
! void *d = TableAnyMap::insert(*(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 void erase(K k) { TableAnyMap::erase(*(size_t *)&k); }
inline T remove(K k)
{
! void *d = TableAnyMap::remove(*(size_t *)&k);
if(d) --count;
return (T)d;
--- 190,203 ----
inline T insert(K k,T 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(N,*(size_t *)&k); }
inline T remove(K k)
{
! void *d = TableAnyMap::remove(N,*(size_t *)&k);
if(d) --count;
return (T)d;
***************
*** 289,322 ****
protected:
! TablePtrMap(TableAnyMap *p): TableAnyMap(p,N,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 <typename K,typename T,int N = 8>
- class TablePtrMapOwned
- : public TablePtrMap<K,T,N>
- {
- public:
- virtual ~TablePtrMapOwned() { TablePtrMapOwned<K,T,N>::clear(); }
-
- protected:
- /*
- virtual void Free(void *ptr)
- {
- // FLEXT_ASSERT(ptr);
- delete (T)ptr;
- }
- */
- };
- #endif
-
//! @} // FLEXT_SUPPORT
--- 223,235 ----
protected:
! 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; }
int count;
Data slots[N];
};
//! @} // FLEXT_SUPPORT
Index: flsupport.cpp
===================================================================
RCS file: /cvsroot/pure-data/externals/grill/flext/source/flsupport.cpp,v
retrieving revision 1.49
retrieving revision 1.50
diff -C2 -d -r1.49 -r1.50
*** flsupport.cpp 18 Apr 2005 15:07:41 -0000 1.49
--- flsupport.cpp 18 Apr 2005 22:05:53 -0000 1.50
***************
*** 116,123 ****
#define LARGEALLOC 32000
void *flext_root::operator new(size_t bytes)
{
bytes += sizeof(size_t);
!
char *blk;
if(bytes >= LARGEALLOC) {
--- 116,129 ----
#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) {
***************
*** 146,150 ****
--- 152,162 ----
*(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
}
***************
*** 152,157 ****
{
FLEXT_ASSERT(blk);
! char *ori = (char *)blk-sizeof(size_t);
size_t bytes = *(size_t *)ori;
--- 164,174 ----
{
FLEXT_ASSERT(blk);
+ FLEXT_ASSERT(MemCheck(blk));
! #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;
***************
*** 179,182 ****
--- 196,211 ----
}
+ #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)
{
***************
*** 298,307 ****
}
- #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(); }
--- 327,330 ----
***************
*** 311,333 ****
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;
}
- /*
- 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)
{
FLEXT_ASSERT(n);
--- 334,342 ----
if(left) { _delmap(left); left = NULL; }
if(right) { _delmap(right); right = NULL; }
! n = 0;
}
! void *TableAnyMap::_set(int tsize,size_t k,void *t)
{
FLEXT_ASSERT(n);
***************
*** 337,343 ****
}
else if(k < data[0].key)
! return _toleft(k,t);
else if(k > data[tsize-1].key)
! return _toright(k,t);
int ix = _tryix(k);
--- 346,352 ----
}
else if(k < data[0].key)
! return _toleft(tsize,k,t);
else if(k > data[tsize-1].key)
! return _toright(tsize,k,t);
int ix = _tryix(k);
***************
*** 346,350 ****
// after last entry
data[n++](k,t);
- // ++count;
return NULL;
}
--- 355,358 ----
***************
*** 362,369 ****
void *a;
if(n == tsize)
! a = _toright(data[tsize-1]);
else {
++n;
- // ++count;
a = NULL;
}
--- 370,376 ----
void *a;
if(n == tsize)
! a = _toright(tsize,data[tsize-1]);
else {
++n;
a = NULL;
}
***************
*** 376,380 ****
}
! void *TableAnyMap::_find(size_t k) const
{
FLEXT_ASSERT(n);
--- 383,387 ----
}
! void *TableAnyMap::_find(int tsize,size_t k) const
{
FLEXT_ASSERT(n);
***************
*** 383,389 ****
}
else if(k < data[0].key)
! return left?left->_find(k):NULL;
else if(k > data[n-1].key)
! return right?right->_find(k):NULL;
const int ix = _tryix(k);
--- 390,396 ----
}
else if(k < data[0].key)
! return left?left->_find(tsize,k):NULL;
else if(k > data[n-1].key)
! return right?right->_find(tsize,k):NULL;
const int ix = _tryix(k);
***************
*** 391,395 ****
}
! void *TableAnyMap::_remove(size_t k)
{
FLEXT_ASSERT(n);
--- 398,427 ----
}
! #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);
***************
*** 398,414 ****
}
else if(k < data[0].key) {
! void *r = left?left->_remove(k):NULL;
! if(r) {
! _eraseempty(left);
! // --count;
! }
return r;
}
else if(k > data[n-1].key) {
! void *r = right?right->_remove(k):NULL;
! if(r) {
! _eraseempty(right);
! // --count;
! }
return r;
}
--- 430,440 ----
}
else if(k < data[0].key) {
! 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(tsize,k):NULL;
! if(r) _eraseempty(right);
return r;
}
***************
*** 457,461 ****
}
- // --count;
return ret;
}
--- 483,486 ----
***************
*** 471,483 ****
}
else {
if(left) {
! for(int i = n; i; --i) data[i] = data[i-1];
left->_getbig(data[0]);
_eraseempty(left);
}
else
! dt = data[--n];
}
- // --count;
}
--- 496,508 ----
}
else {
+ dt = data[n-1];
if(left) {
! for(int i = n-1; i; --i) data[i] = data[i-1];
left->_getbig(data[0]);
_eraseempty(left);
}
else
! --n;
}
}
***************
*** 500,504 ****
--n;
}
- // --count;
}
--- 525,528 ----
Index: flsupport.h
===================================================================
RCS file: /cvsroot/pure-data/externals/grill/flext/source/flsupport.h,v
retrieving revision 1.88
retrieving revision 1.89
diff -C2 -d -r1.88 -r1.89
*** flsupport.h 9 Apr 2005 21:09:01 -0000 1.88
--- flsupport.h 18 Apr 2005 22:05:53 -0000 1.89
***************
*** 57,60 ****
--- 57,66 ----
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); }