aboutsummaryrefslogtreecommitdiff
path: root/externals/grill/flext/source
diff options
context:
space:
mode:
authorThomas Grill <xovo@users.sourceforge.net>2005-03-31 03:52:38 +0000
committerThomas Grill <xovo@users.sourceforge.net>2005-03-31 03:52:38 +0000
commit3363199f5b126d2f0305a57f6a61fb2dd8007e10 (patch)
tree04498fea38eb3d91e455fc1cca91c8879140daeb /externals/grill/flext/source
parentb3cfaffbe0124254f5da70857f6c1cec59184897 (diff)
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
Diffstat (limited to 'externals/grill/flext/source')
-rw-r--r--externals/grill/flext/source/flattr.cpp2
-rw-r--r--externals/grill/flext/source/flclass.h4
-rwxr-xr-xexternals/grill/flext/source/flitem.cpp9
-rwxr-xr-xexternals/grill/flext/source/fllib.cpp2
-rw-r--r--externals/grill/flext/source/flmap.h181
-rwxr-xr-xexternals/grill/flext/source/flmeth.cpp2
-rwxr-xr-xexternals/grill/flext/source/flprefix.h21
-rw-r--r--externals/grill/flext/source/flstdc.h19
-rw-r--r--externals/grill/flext/source/flsupport.cpp193
-rw-r--r--externals/grill/flext/source/flsupport.h4
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)); }