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/source/flmap.cpp | 249 +++++++++++++++++++++++++++++++++ externals/grill/flext/source/flmap.h | 65 ++++----- 2 files changed, 282 insertions(+), 32 deletions(-) create mode 100644 externals/grill/flext/source/flmap.cpp (limited to 'externals/grill/flext/source') 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