Update of /cvsroot/pure-data/externals/grill/flext/source In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23666/source
Modified Files: flsupport.cpp Log Message:
Index: flsupport.cpp =================================================================== RCS file: /cvsroot/pure-data/externals/grill/flext/source/flsupport.cpp,v retrieving revision 1.51 retrieving revision 1.52 diff -C2 -d -r1.51 -r1.52 *** flsupport.cpp 23 Apr 2005 09:06:25 -0000 1.51 --- flsupport.cpp 23 Apr 2005 09:14:20 -0000 1.52 *************** *** 327,562 **** }
- - 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; - } - } - } - } - } - } - --- 327,328 ----