fixed typo

added profiling flags for OSX
small fixes

svn path=/trunk/; revision=2790

2 files changed, 282 insertions, 32 deletions

diff --git a/externals/grill/flext/source/flmap.cpp b/externals/grill/flext/source/flmap.cpp
new file mode 100644
index 00000000..117f0896
--- /dev/null
+++ b/externals/grill/flext/source/flmap.cpp
@@ -0,0 +1,249 @@
+/* 
+
+flext - C++ layer for Max/MSP and pd (pure data) externals
+
+Copyright (c) 2001-2005 Thomas Grill (gr@grrrr.org)
+For information on usage and redistribution, and for a DISCLAIMER OF ALL
+WARRANTIES, see the file, "license.txt," in this distribution.  
+
+*/
+
+/*! \file flmap.cpp
+    \brief flext container classes.
+*/
+ 
+#include "flext.h"
+#include "flmap.h"
+
+TableAnyMap::~TableAnyMap() { clear(); }
+
+void TableAnyMap::clear() 
+{
+    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);
+
+    if(n < tsize) {
+        // fall through
+    }
+    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);
+    if(ix >= n) {
+        FLEXT_ASSERT(ix == n);
+        // after last entry
+        data[n++](k,t);
+        return NULL;
+    }
+
+    size_t dk = data[ix].key;
+    if(k == dk) {
+        // update data in existing slot (same key)
+        void *a = data[ix].value;
+        data[ix] = t;
+        return a;
+    }
+    else {
+        // insert new slot by shifting the higher ones
+        FLEXT_ASSERT(k < dk);
+        void *a;
+        if(n == tsize)
+            a = _toright(tsize,data[tsize-1]);
+        else {
+            ++n;
+            a = NULL;
+        }
+
+        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(int tsize,size_t k) const
+{
+    FLEXT_ASSERT(n);
+    if(n < tsize) {
+        // fall through
+    }
+    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);
+    return ix < n && data[ix].key == k?data[ix].value:NULL;
+}
+
+#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(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;
+    }
+
+    const int ix = _tryix(k);
+    if(ix >= n || 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;
+        }
+
+        return ret;
+    }
+}
+
+void TableAnyMap::_getbig(Data &dt)
+{
+    FLEXT_ASSERT(n);
+
+    if(right) {
+        right->_getbig(dt);
+        _eraseempty(right);
+    }
+    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;
+    }
+}
+
+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;
+    }
+}
+
+void TableAnyMap::iterator::forward() 
+{ 
+    if(map || ix >= map->n) {
+        if(++ix >= map->n) {
+            TableAnyMap *nmap;
+
+            // we reached the end of the slots
+            if(map->right) {
+                // climb up one
+                map = map->right;
+                leftmost();
+                ix = 0;
+            }
+            else {
+                // fall back
+                for(;;) {
+                    nmap = map->parent;
+                    if(!nmap) break; // no parent
+                    if(nmap->left == map) {
+                        // ok, we are in front of the slots now
+                        ix = 0;
+                        map = nmap;
+                        break;
+                    }
+                    else {
+                        FLEXT_ASSERT(nmap->right == map);
+                        ix = (map = nmap)->n;
+                    }
+                }
+            }
+        }
+    }
+}
diff --git a/externals/grill/flext/source/flmap.h b/externals/grill/flext/source/flmap.h
index 0d82ad7f..f0cb01be 100644
--- a/externals/grill/flext/source/flmap.h
+++ b/externals/grill/flext/source/flmap.h
@@ -9,7 +9,7 @@ WARRANTIES, see the file, "license.txt," in this distribution.
 */
 
 /*! \file flmap.h
-	\brief special map class for all 32-bit key/value-pairs   
+	\brief special map class (faster and less memory-consuming than std::map)   
 */
 
 #ifndef __FLMAP_H
@@ -37,13 +37,13 @@ protected:
 
     TableAnyMap(TableAnyMap *p,Data *dt)
         : data(dt)
-        , parent(p),left(NULL),right(NULL) 
+        , parent(p),left(0),right(0) 
         , n(0)
     {}
 
     virtual ~TableAnyMap();
 
-#if 0
+#if 0 // set 1 for asserting the map structure (very cpu-intensive!)
     void check(int tsize) { if(n) _check(tsize); }
 #else
     void check(int tsize) {}
@@ -56,22 +56,27 @@ protected:
             r = _set(tsize,k,t);
         else {
             data[n++](k,t);
-            r = NULL;
+            r = 0;
         }
         check(tsize);
         return r;
     }
 
-    void *find(int tsize,size_t k) const { return n?_find(tsize,k):NULL; }
+    void *find(int tsize,size_t k) const { return n?_find(tsize,k):0; }
 
-    void *remove(int tsize,size_t k) { void *r = n?_remove(tsize,k):NULL; check(tsize); return r; }
+    void *remove(int tsize,size_t k) 
+	{ 
+		void *r = n?_remove(tsize,k):0; 
+		check(tsize); 
+		return r; 
+	}
 
     virtual void clear();
 
     class FLEXT_SHARE iterator
     {
     public:
-        iterator(): map(NULL) {}
+        iterator(): map(0) {}
         iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
         iterator(iterator &it): map(it.map),ix(it.ix) {}
     
@@ -90,11 +95,12 @@ protected:
         {
             // search smallest branch (go left as far as possible)
             const TableAnyMap *nmap;
-            while((nmap = map->left) != NULL) map = nmap;
+            while((nmap = map->left) != 0) map = nmap;
         }
 
         void forward();
 
+		// pointers to map and index within
         const TableAnyMap *map;
         int ix;
     };
@@ -109,7 +115,7 @@ private:
             return left->_set(tsize,k,t);
         else {
             (left = _newmap(this))->_init(k,t);
-            return NULL;
+            return 0;
         }
     }
 
@@ -119,7 +125,7 @@ private:
             return right->_set(tsize,k,t);
         else {
             (right = _newmap(this))->_init(k,t);
-            return NULL;
+            return 0;
         }
     }
 
@@ -136,30 +142,25 @@ private:
 
     Data *const data;
     TableAnyMap *parent,*left,*right;
-    short n;
+    int n;
 
     //! return index of data item with key <= k
     //! \note index can point past the last item!
-    int _tryix(size_t k) const
+    unsigned int _tryix(size_t k) const
     {
-        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;
-                }
-            }
-        }
+        unsigned int ix = 0,b = n;
+		while(ix != b) {
+			const unsigned int c = (ix+b)>>1;
+			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
+				return b;
+		}
         return ix;
     }
 
@@ -167,7 +168,7 @@ private:
     {
         if(!b->n) { 
             // remove empty branch
-            _delmap(b); b = NULL; 
+            _delmap(b); b = 0; 
         }
     }
 
@@ -180,7 +181,7 @@ class TablePtrMap
     : TableAnyMap
 {
 public:
-    TablePtrMap(): TableAnyMap(NULL,slots),count(0) {}
+    TablePtrMap(): TableAnyMap(0,slots),count(0) {}
     virtual ~TablePtrMap() { clear(); }
 
     virtual void clear() { TableAnyMap::clear(); count = 0; }