optimized AtomList functions

moved FLEXT_SHARE definition
smaller changes to TableMap
enhancements and more features for TableMap type
new: FLEXT_WARN, FLEXT_ERROR macros

svn path=/trunk/; revision=2653

10 files changed, 294 insertions, 143 deletions

diff --git a/externals/grill/flext/source/flattr.cpp b/externals/grill/flext/source/flattr.cpp
index f930820a..d0c33ebb 100644
--- a/externals/grill/flext/source/flattr.cpp
+++ b/externals/grill/flext/source/flattr.cpp
@@ -103,7 +103,7 @@ void flext_base::AddAttrib(t_classid c,const t_symbol *attr,metharg tp,methfun g
 
 void flext_base::ListAttrib(AtomList &la) const
 {
-	typedef TableMap<int,t_symbol,32> AttrList;
+	typedef TablePtrMap<int,t_symbol,32> AttrList;
 	AttrList list[2];
 
 	int i;
diff --git a/externals/grill/flext/source/flclass.h b/externals/grill/flext/source/flclass.h
index 351a0bcb..d15ae09d 100644
--- a/externals/grill/flext/source/flclass.h
+++ b/externals/grill/flext/source/flclass.h
@@ -659,7 +659,7 @@ protected:
 		~ItemSet();
 	};
 */
-	typedef TableMap<const t_symbol *,Item,8,true> ItemSet;
+	typedef TablePtrMapOwned<const t_symbol *,Item,8> ItemSet;
 
     /*! This class holds hashed item entries
 		\note not thread-safe!
@@ -775,7 +775,7 @@ protected:
 		~AttrDataCont();
 	};
 */
-	typedef TableMap<const t_symbol *,AttrData,8,true> AttrDataCont;
+	typedef TablePtrMapOwned<const t_symbol *,AttrData,8> AttrDataCont;
 
 	// these outlet functions don't check for thread but send directly to the real-time system
 #if FLEXT_SYS == FLEXT_SYS_PD || FLEXT_SYS == FLEXT_SYS_MAX
diff --git a/externals/grill/flext/source/flitem.cpp b/externals/grill/flext/source/flitem.cpp
index eb307d09..c73ee91a 100755
--- a/externals/grill/flext/source/flitem.cpp
+++ b/externals/grill/flext/source/flitem.cpp
@@ -86,8 +86,11 @@ bool flext_base::ItemCont::Remove(Item *item,const t_symbol *tag,int inlet,bool
         for(Item *prv = NULL; lit; prv = lit,lit = lit->nxt) {
             if(lit == item) {
                 if(prv) prv->nxt = lit->nxt;
-                else set.insert(tag,lit->nxt);
-            
+                else if(lit->nxt)
+                    set.insert(tag,lit->nxt);
+                else
+                    set.erase(tag);
+
                 lit->nxt = NULL; 
                 if(free) delete lit;
                 return true;
@@ -105,7 +108,7 @@ flext_base::Item *flext_base::ItemCont::FindList(const t_symbol *tag,int inlet)
 
 // --- class item lists (methods and attributes) ----------------
 
-typedef TableMap<flext_base::t_classid,flext_base::ItemCont,64> ClassMap;
+typedef TablePtrMap<flext_base::t_classid,flext_base::ItemCont,64> ClassMap;
 
 static ClassMap classarr[2];
 
diff --git a/externals/grill/flext/source/fllib.cpp b/externals/grill/flext/source/fllib.cpp
index 85589679..e98a4137 100755
--- a/externals/grill/flext/source/fllib.cpp
+++ b/externals/grill/flext/source/fllib.cpp
@@ -126,7 +126,7 @@ libclass::libclass(t_class *&cl,flext_obj *(*newf)(int,t_atom *),void (*freef)(f
 {}
 
 
-typedef TableMap<const t_symbol *,libclass,8> LibMap;
+typedef TablePtrMap<const t_symbol *,libclass,8> LibMap;
 
 static LibMap libnames;
 
diff --git a/externals/grill/flext/source/flmap.h b/externals/grill/flext/source/flmap.h
index bcf67c46..c0602378 100644
--- a/externals/grill/flext/source/flmap.h
+++ b/externals/grill/flext/source/flmap.h
@@ -94,66 +94,40 @@ protected:
         void *value;
     };
 
-    TableAnyMap(TableAnyMap *p,int sz,Data *dt,bool o)
-        : owned(o),tsize(sz),data(dt)
-        , n(0),parent(p),left(NULL),right(NULL) 
+    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;
+    int size() const { return count; }
 
     void insert(size_t k,void *t)
     {
-        FLEXT_ASSERT(t);
-        if(n) _set(k,t);
-        else data[n++](k,t);
-    }
-
-    void *find(size_t k) { return n?_find(k):NULL; }
-
-    void clear();
-
-    void _toleft(size_t k,void *t)
-    {
-        if(left)
-            left->_set(k,t);
-        else {
-            left = New(this);
-            left->data[0](k,t);
-            left->n = 1;
-        }
-    }
-
-    void _toright(size_t k,void *t)
-    {
-        if(right) 
-            right->_set(k,t);
+//        FLEXT_ASSERT(t);
+        if(n) 
+            _set(k,t);
         else {
-            right = New(this);
-            right->data[0](k,t);
-            right->n = 1;
+            data[n++](k,t);
+            ++count;
         }
     }
 
-    void _toleft(Data &v) { _toleft(v.key,v.value); }
-    void _toright(Data &v) { _toright(v.key,v.value); }
+    void *find(size_t k) const { return n?_find(k):NULL; }
 
-    void _set(size_t k,void *t);
-    void *_find(size_t k);
+    void erase(size_t k) { if(n) { void *s = _remove(k); if(s) Free(s); } }
 
-    const bool owned;
-    const int tsize;
-    Data *const data;
-    int n;
-    TableAnyMap *parent,*left,*right;
+    void *remove(size_t k) { return n?_remove(k):NULL; }
 
+    void clear();
 
-    class iterator
+    class FLEXT_SHARE iterator
     {
     public:
         iterator(): map(NULL) {}
-        iterator(TableAnyMap &m): map(&m),ix(0) { leftmost(); }
+        iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
         iterator(iterator &it): map(it.map),ix(it.ix) {}
     
         iterator &operator =(const iterator &it) { map = it.map,ix = it.ix; return *this; }
@@ -170,25 +144,105 @@ protected:
         void leftmost()
         {
             // search smallest branch (go left as far as possible)
-            TableAnyMap *nmap;
+            const TableAnyMap *nmap;
             while((nmap = map->left) != NULL) map = nmap;
         }
 
         void forward();
 
-        TableAnyMap *map;
+        const TableAnyMap *map;
         int ix;
     };
-};
 
+private:
+    void _init(size_t k,void *t) { data[0](k,t); n = count = 1; }
+
+    bool _toleft(size_t k,void *t)
+    {
+        if(left) {
+            bool a = left->_set(k,t);
+            if(a) ++count;
+            return a;
+        }
+        else {
+            (left = New(this))->_init(k,t);
+            ++count;
+            return true;
+        }
+    }
+
+    bool _toright(size_t k,void *t)
+    {
+        if(right) {
+            bool a = right->_set(k,t);
+            if(a) ++count;
+            return a;
+        }
+        else {
+            (right = New(this))->_init(k,t);
+            ++count;
+            return true;
+        }
+    }
+
+    bool _toleft(Data &v) { return _toleft(v.key,v.value); }
+    bool _toright(Data &v) { return _toright(v.key,v.value); }
+
+    bool _set(size_t k,void *t);
+    void *_find(size_t k) const;
+    void *_remove(size_t k);
+
+    const int tsize;
+    Data *const data;
+    int count,n;
+    TableAnyMap *parent,*left,*right;
+
+    int _tryix(size_t k) const
+    {
+        //! return index of data item with key <= k
+
+//        FLEXT_ASSERT(n);
+        int ix = 0;
+        {
+            int b = n;
+            while(ix != b) {
+                const int c = (ix+b)/2;
+                const size_t dk = data[c].key;
+                if(k == dk)
+                    return c;
+                else if(k < dk)
+                    b = c;
+                else if(ix < c)
+                    ix = c;
+                else {
+                    ix = b;
+                    break;
+                }
+            }
+        }
+        return ix;
+    }
+
+    static void _eraseempty(TableAnyMap *&b)
+    {
+//        FLEXT_ASSERT(b);
+        if(!b->n) { 
+            // remove empty branch
+            delete b; b = NULL; 
+        }
+    }
 
-template <typename K,typename T,int N = 8,bool O = false>
-class TableMap
+    void _getsmall(Data &dt);
+    void _getbig(Data &dt);
+};
+
+template <typename K,typename T,int N = 8>
+class TablePtrMap
     : TableAnyMap
 {
 public:
-    TableMap(): TableAnyMap(NULL,N,slots,O) {}
-    virtual ~TableMap() { clear(); }
+    TablePtrMap(): TableAnyMap(NULL,N,slots) {}
+    virtual ~TablePtrMap() { clear(); }
 
     inline void clear() { TableAnyMap::clear(); }
 
@@ -196,14 +250,17 @@ public:
 
     inline void insert(K k,T *t) { TableAnyMap::insert(*(size_t *)&k,t); }
 
-    inline T *find(K k) { return (T *)TableAnyMap::find(*(size_t *)&k); }
+    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) { return (T *)TableAnyMap::remove(*(size_t *)&k); }
 
     class iterator
         : TableAnyMap::iterator
     {
     public:
         iterator() {}
-        iterator(TableMap &m): TableAnyMap::iterator(m) {}
+        iterator(const TablePtrMap &m): TableAnyMap::iterator(m) {}
         iterator(iterator &it): TableAnyMap::iterator(it) {}
 
         inline iterator &operator =(const iterator &it) { TableAnyMap::operator =(it); return *this; }
@@ -217,14 +274,30 @@ public:
     };
 
 protected:
-    TableMap(TableAnyMap *p): TableAnyMap(p,N,slots,O) {}
+    TablePtrMap(TableAnyMap *p): TableAnyMap(p,N,slots) {}
+
+    virtual TableAnyMap *New(TableAnyMap *parent) { return new TablePtrMap(parent); }
 
-    virtual TableAnyMap *New(TableAnyMap *parent) { return new TableMap(parent); }
-    virtual void Free(void *ptr) { delete (T *)ptr; }
+    virtual void Free(void *ptr) {}
 
     Data slots[N];
 };
 
+template <typename K,typename T,int N = 8>
+class TablePtrMapOwned
+    : public TablePtrMap<K,T,N>
+{
+public:
+    virtual ~TablePtrMapOwned() { clear(); }
+
+protected:
+    virtual void Free(void *ptr) 
+    { 
+//            FLEXT_ASSERT(ptr);
+        delete (T *)ptr;
+    }
+
+};
 
 //! @} // FLEXT_SUPPORT
 
diff --git a/externals/grill/flext/source/flmeth.cpp b/externals/grill/flext/source/flmeth.cpp
index e93db27a..11b6d42d 100755
--- a/externals/grill/flext/source/flmeth.cpp
+++ b/externals/grill/flext/source/flmeth.cpp
@@ -89,7 +89,7 @@ void flext_base::AddMethod(ItemCont *ma,int inlet,const t_symbol *tag,methfun fu
 
 void flext_base::ListMethods(AtomList &la,int inlet) const
 {
-	typedef TableMap<int,t_symbol,32> MethList;
+	typedef TablePtrMap<int,t_symbol,32> MethList;
     MethList list[2];
 
     int i;
diff --git a/externals/grill/flext/source/flprefix.h b/externals/grill/flext/source/flprefix.h
index d7921d94..4b3e96fb 100755
--- a/externals/grill/flext/source/flprefix.h
+++ b/externals/grill/flext/source/flprefix.h
@@ -372,6 +372,27 @@ WARRANTIES, see the file, "license.txt," in this distribution.
     #define FLEXT_CLASSDEF(CL) CL##_single
 #endif
 
+
+/* Set the right calling convention (and exporting) for the OS */
+
+#ifdef _MSC_VER
+	#ifdef FLEXT_SHARED
+        // for compiling a shared flext library FLEXT_EXPORTS must be defined
+        #ifdef FLEXT_EXPORTS
+		    #define FLEXT_SHARE __declspec(dllexport)
+        #else
+		    #define FLEXT_SHARE __declspec(dllimport)
+        #endif
+	#else
+		#define FLEXT_SHARE
+	#endif
+	#define FLEXT_EXT __declspec(dllexport)
+#else                   // other OS's
+	#define FLEXT_SHARE
+	#define FLEXT_EXT
+#endif
+
+
 // std namespace
 #ifdef __MWERKS__
 #define STD std
diff --git a/externals/grill/flext/source/flstdc.h b/externals/grill/flext/source/flstdc.h
index fcf43934..b8eef0d5 100644
--- a/externals/grill/flext/source/flstdc.h
+++ b/externals/grill/flext/source/flstdc.h
@@ -290,25 +290,6 @@ typedef t_symbol *t_symptr;
 #define ERRINTERNAL() error("flext: Internal error in file " __FILE__ ", line %i - please report",(int)__LINE__)
 
 
-/* Set the right calling convention (and exporting) for the OS */
-
-#ifdef _MSC_VER
-	#ifdef FLEXT_SHARED
-        // for compiling a shared flext library FLEXT_EXPORTS must be defined
-        #ifdef FLEXT_EXPORTS
-		    #define FLEXT_SHARE __declspec(dllexport)
-        #else
-		    #define FLEXT_SHARE __declspec(dllimport)
-        #endif
-	#else
-		#define FLEXT_SHARE
-	#endif
-	#define FLEXT_EXT __declspec(dllexport)
-#else                   // other OS's
-	#define FLEXT_SHARE
-	#define FLEXT_EXT
-#endif
-
 // ----- disable attribute editor for PD version < devel_0_36 or 0.37
 #ifndef PD_MAJOR_VERSION
 #undef FLEXT_NOATTREDIT
diff --git a/externals/grill/flext/source/flsupport.cpp b/externals/grill/flext/source/flsupport.cpp
index 53821157..3d9b1b03 100644
--- a/externals/grill/flext/source/flsupport.cpp
+++ b/externals/grill/flext/source/flsupport.cpp
@@ -310,14 +310,12 @@ void TableAnyMap::clear()
 {
     if(left) { delete left; left = NULL; }
     if(right) { delete right; right = NULL; }
-    if(owned)
-        for(int i = 0; i < n; ++i) {
-            FLEXT_ASSERT(data[i].value);
-            Free(data[i].value);
-        }
-    n = 0;
+
+    for(int i = 0; i < n; ++i) Free(data[i].value);
+    count = n = 0;
 }
 
+/*
 int TableAnyMap::size() const 
 {
     int sz = n;
@@ -325,72 +323,57 @@ int TableAnyMap::size() const
         if(left) sz += left->size();
         if(right) sz += right->size();
     }
+    FLEXT_ASSERT(sz == count);
     return sz;
 }
+*/
 
-void TableAnyMap::_set(size_t k,void *t)
+bool TableAnyMap::_set(size_t k,void *t)
 {
     FLEXT_ASSERT(n);
 
     if(n < tsize) {
         // fall through
     }
-    else if(k < data[0].key) {
-        _toleft(k,t);
-        return;
-    }
-    else if(k > data[tsize-1].key) {
-        _toright(k,t);
-        return;
-    }
-
-    int ix = 0;
-    {
-        int b = n;
-        while(ix != b) {
-            const int c = (ix+b)/2;
-            const size_t dk = data[c].key;
-            if(k == dk) {
-                ix = c;
-                break;
-            }
-            else if(k < dk)
-                b = c;
-            else if(ix < c)
-                ix = c;
-            else {
-                ix = b;
-                break;
-            }
-        }
-    }
+    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);
     size_t dk = data[ix].key;
     if(k == dk) {
         // update data in existing slot (same key)
-        if(owned) Free(data[ix].value);
+        Free(data[ix].value);
         data[ix] = t;
+        return false;
     }
     else if(ix >= n) {
         FLEXT_ASSERT(ix == n);
         // after last entry
         data[n++](k,t);
+        ++count;
+        return true;
     }
     else {
         // insert new slot by shifting the higher ones
         FLEXT_ASSERT(k < dk);
+        bool a;
         if(n == tsize)
-            _toright(data[tsize-1]);
-        else
-            ++n;
+            a = _toright(data[tsize-1]);
+        else {
+            ++n,++count;
+            a = true;
+        }
 
         Data *tg = data+ix;
         for(Data *d = data+n-1; d > tg; d--) d[0] = d[-1];
         (*tg)(k,t);
+        return a;
     }
 }
 
-void *TableAnyMap::_find(size_t k) 
+void *TableAnyMap::_find(size_t k) const
 {
     FLEXT_ASSERT(n);
     if(n < tsize) {
@@ -401,32 +384,120 @@ void *TableAnyMap::_find(size_t k)
     else if(k > data[n-1].key)
         return right?right->_find(k):NULL;
 
-    //! return index of data item with key <= k
+    const int ix = _tryix(k);
+    return data[ix].key == k?data[ix].value:NULL;
+}
 
+void *TableAnyMap::_remove(size_t k)
+{
     FLEXT_ASSERT(n);
-    int ix = 0;
-    {
-        int b = n;
-        while(ix != b) {
-            const int c = (ix+b)/2;
-            const size_t dk = data[c].key;
-            if(k == dk)
-                return data[c].value;
-            else if(k < dk)
-                b = c;
-            else if(ix < c)
-                ix = c;
-            else {
-                ix = b;
-                break;
-            }
+    if(n < tsize) {
+        // fall through
+    }
+    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;
     }
 
-    if(data[ix].key == k)
-        return data[ix].value;
-    else
+    const int ix = _tryix(k);
+    if(data[ix].key != k)
         return NULL;
+    else {
+        // found key in this map
+        void *ret = data[ix].value;
+
+        Data dt;
+        bool fnd,ins = false;
+        if(n >= tsize) {
+            // if this table is full get fill-in elements from branches
+            if(left) {
+                // try to get biggest element from left branch
+                left->_getbig(dt);
+                _eraseempty(left);
+                fnd = true,ins = true;
+            }
+            else if(right) {
+                // try to get smallest element from right branch
+                right->_getsmall(dt);
+                _eraseempty(right);
+                fnd = true;
+            }
+            else
+                fnd = false;
+        }
+        else fnd = false;
+
+        if(ins) {
+            // insert smaller element from left
+            for(int i = ix; i; --i) data[i] = data[i-1];
+            data[0] = dt;
+        }
+        else {
+            // shift elements
+            for(int i = ix+1; i < n; ++i) data[i-1] = data[i];
+            // insert bigger element from right or reduce table size
+            if(fnd)
+                data[n-1] = dt;
+            else
+                --n;
+        }
+
+        --count;
+        return ret;
+    }
+}
+
+void TableAnyMap::_getbig(Data &dt)
+{
+    FLEXT_ASSERT(n);
+
+    if(right) {
+        right->_getbig(dt);
+        _eraseempty(right);
+    }
+    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;
+}
+
+void TableAnyMap::_getsmall(Data &dt)
+{
+    FLEXT_ASSERT(n);
+
+    if(left) {
+        left->_getsmall(dt);
+        _eraseempty(left);
+    }
+    else {
+        dt = data[0];
+        for(int i = 1; i < n; ++i) data[i-1] = data[i];
+        if(right) {
+            right->_getsmall(data[n-1]);
+            _eraseempty(right);
+        }
+        else
+            --n;
+    }
+    --count;
 }
 
 void TableAnyMap::iterator::forward() 
diff --git a/externals/grill/flext/source/flsupport.h b/externals/grill/flext/source/flsupport.h
index 39713b1c..ff27e97c 100644
--- a/externals/grill/flext/source/flsupport.h
+++ b/externals/grill/flext/source/flsupport.h
@@ -378,7 +378,7 @@ public:
 	static const char *GetString(const t_symbol *s) { return s->s_name; }  
 #endif
 	//! Check for symbol and get string
-	static const char *GetAString(const t_symbol *s,const char *def = "") { return s?GetString(s):def; }
+	static const char *GetAString(const t_symbol *s,const char *def = NULL) { return s?GetString(s):def; }
 
 // --- atom stuff ----------------------------------------
 		
@@ -460,6 +460,8 @@ public:
 	//! Access the string value (without type check)
 	static const char *GetString(const t_atom &a) { t_symbol *s = GetSymbol(a); return s?GetString(s):NULL; }  
 	//! Check for a string and get its value 
+    static const char *GetAString(const t_atom &a,const char *def = NULL) { return IsSymbol(a)?GetAString(GetSymbol(a),def):def; }
+	//! Check for a string and get its value 
 	static void GetAString(const t_atom &a,char *buf,size_t szbuf);
 	//! Set the atom to represent a string
 	static void SetString(t_atom &a,const char *c) { SetSymbol(a,MakeSymbol(c)); }