From 3363199f5b126d2f0305a57f6a61fb2dd8007e10 Mon Sep 17 00:00:00 2001 From: Thomas Grill Date: Thu, 31 Mar 2005 03:52:38 +0000 Subject: 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 --- externals/grill/flext/source/flattr.cpp | 2 +- externals/grill/flext/source/flclass.h | 4 +- externals/grill/flext/source/flitem.cpp | 9 +- externals/grill/flext/source/fllib.cpp | 2 +- externals/grill/flext/source/flmap.h | 181 +++++++++++++++++++-------- externals/grill/flext/source/flmeth.cpp | 2 +- externals/grill/flext/source/flprefix.h | 21 ++++ externals/grill/flext/source/flstdc.h | 19 --- externals/grill/flext/source/flsupport.cpp | 193 ++++++++++++++++++++--------- externals/grill/flext/source/flsupport.h | 4 +- 10 files changed, 294 insertions(+), 143 deletions(-) (limited to 'externals/grill/flext') 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 AttrList; + typedef TablePtrMap 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 ItemSet; + typedef TablePtrMapOwned ItemSet; /*! This class holds hashed item entries \note not thread-safe! @@ -775,7 +775,7 @@ protected: ~AttrDataCont(); }; */ - typedef TableMap AttrDataCont; + typedef TablePtrMapOwned 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 ClassMap; +typedef TablePtrMap 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 LibMap; +typedef TablePtrMap 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 -class TableMap + void _getsmall(Data &dt); + void _getbig(Data &dt); +}; + +template +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 +class TablePtrMapOwned + : public TablePtrMap +{ +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 MethList; + typedef TablePtrMap 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)); } -- cgit v1.2.1