externals/grill/flext/source flmap.h, 1.15, 1.16 flsupport.cpp, 1.49, 1.50 flsupport.h, 1.88, 1.89 - Pd-cvs

19 Apr 2005


      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); }