fixed typo

fixed bugs in TableMaps
fixes for OSX
restructured TableMap type (doesn't own pointers any more)

svn path=/trunk/; revision=2782

4 files changed, 119 insertions, 176 deletions

diff --git a/externals/grill/flext/flext.vcproj b/externals/grill/flext/flext.vcproj
index 19e5986f..49f30ac1 100644
--- a/externals/grill/flext/flext.vcproj
+++ b/externals/grill/flext/flext.vcproj
@@ -172,7 +172,7 @@
 				Name="VCCLCompilerTool"
 				Optimization="0"
 				AdditionalIncludeDirectories="c:\programme\audio\pd\src;c:\data\prog\audio\sndobj\include;c:\data\prog\audio\stk\include"
-				PreprocessorDefinitions="WIN32;_DEBUG;_LIB;FLEXT_SYS=2;FLEXT_USE_SIMD;FLEXT_EXPORTS"
+				PreprocessorDefinitions="WIN32;_DEBUG;_LIB;FLEXT_SYS=2;FLEXT_USE_SIMD;FLEXT_EXPORTS;FLEXT_DEBUGMEM"
 				StringPooling="TRUE"
 				BasicRuntimeChecks="3"
 				RuntimeLibrary="1"
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 <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
 {
 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 <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
 
 #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); }