From c44cd878e455d0ff2462233525d728e73fea1e9d Mon Sep 17 00:00:00 2001 From: Thomas Grill Date: Tue, 19 Apr 2005 13:29:56 +0000 Subject: fixed typo added profiling flags for OSX small fixes svn path=/trunk/; revision=2790 --- externals/grill/flext/build.txt | 2 +- externals/grill/flext/buildsys/gnumake.inc | 4 + externals/grill/flext/buildsys/mac/gnumake-gcc.inc | 11 +- externals/grill/flext/package.txt | 2 +- externals/grill/flext/source/flmap.cpp | 249 +++++++++++++++++++++ externals/grill/flext/source/flmap.h | 65 +++--- 6 files changed, 297 insertions(+), 36 deletions(-) create mode 100644 externals/grill/flext/source/flmap.cpp diff --git a/externals/grill/flext/build.txt b/externals/grill/flext/build.txt index 35baf4de..3f1073d2 100644 --- a/externals/grill/flext/build.txt +++ b/externals/grill/flext/build.txt @@ -66,7 +66,7 @@ By default, this resides in a file called package.txt Please note, that the build system is shell-oriented, which means, that you'll have to launch a command prompt (cmd.exe under Windows) and probably also set some -environment variables for your development system (e.g. run vcvars32.bat for Microsoft Visual Studio) +environment variables for your development system (e.g. run vcvars32.bat included with Microsoft Visual Studio) By invoking one of the build scripts (e.g. with "bash build.sh" under unix, or just "build" unter Windows) you'll get some lines of help. diff --git a/externals/grill/flext/buildsys/gnumake.inc b/externals/grill/flext/buildsys/gnumake.inc index a52d437f..93203f36 100644 --- a/externals/grill/flext/buildsys/gnumake.inc +++ b/externals/grill/flext/buildsys/gnumake.inc @@ -7,8 +7,12 @@ CFLAGS += $(UFLAGS) ifdef DEBUG CFLAGS += -D_DEBUG $(DFLAGS) else +ifdef PROFILE +CFLAGS += -DNDEBUG $(OFLAGS) +else CFLAGS += -DNDEBUG $(OFLAGS) endif +endif ifdef SHARED diff --git a/externals/grill/flext/buildsys/mac/gnumake-gcc.inc b/externals/grill/flext/buildsys/mac/gnumake-gcc.inc index 4e7f84af..1c85ac76 100644 --- a/externals/grill/flext/buildsys/mac/gnumake-gcc.inc +++ b/externals/grill/flext/buildsys/mac/gnumake-gcc.inc @@ -18,12 +18,19 @@ FLEXTBIN=$(FLEXTPREFIX)/bin ############################################## -LDFLAGS += -dynamic -Wl,-x -framework ApplicationServices -framework vecLib +LDFLAGS += -dynamic -framework ApplicationServices -framework vecLib ############################################## ifdef DEBUG CFLAGS += -g +LDFLAGS += -g else -LDFLAGS += -Wl,-S +ifdef PROFILE +CFLAGS += -g +LDFLAGS += -g +else +LDFLAGS += -Wl,-x -Wl,-S endif +endif + diff --git a/externals/grill/flext/package.txt b/externals/grill/flext/package.txt index e3033816..01f0d076 100644 --- a/externals/grill/flext/package.txt +++ b/externals/grill/flext/package.txt @@ -31,7 +31,7 @@ SRCS= \ flxlet.cpp flattr.cpp flattr_ed.cpp flsupport.cpp \ flutil.cpp flatom.cpp flatom_pr.cpp flthr.cpp fltimer.cpp flsimd.cpp flout.cpp \ flatom_part.cpp flitem.cpp flmeth.cpp flmsg.cpp \ - flproxy.cpp flqueue.cpp flbind.cpp + flproxy.cpp flqueue.cpp flbind.cpp flmap.cpp HDRS= \ flprefix.h flstdc.h flbase.h flclass.h flext.h flsupport.h flmap.h fldsp.h flinternal.h flcontainers.h \ fldefs.h fldefs_hdr.h fldefs_setup.h \ 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; } -- cgit v1.2.1