[PD-cvs] externals/grill/flext/source flmap.cpp, NONE, 1.1 flmap.h, 1.16, 1.17
Thomas Grill
xovo at users.sourceforge.net
Tue Apr 19 15:29:58 CEST 2005
Update of /cvsroot/pure-data/externals/grill/flext/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23509/source
Modified Files:
flmap.h
Added Files:
flmap.cpp
Log Message:
fixed typo
added profiling flags for OSX
small fixes
Index: flmap.h
===================================================================
RCS file: /cvsroot/pure-data/externals/grill/flext/source/flmap.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** flmap.h 18 Apr 2005 22:05:52 -0000 1.16
--- flmap.h 19 Apr 2005 13:29:56 -0000 1.17
***************
*** 10,14 ****
/*! \file flmap.h
! \brief special map class for all 32-bit key/value-pairs
*/
--- 10,14 ----
/*! \file flmap.h
! \brief special map class (faster and less memory-consuming than std::map)
*/
***************
*** 38,42 ****
TableAnyMap(TableAnyMap *p,Data *dt)
: data(dt)
! , parent(p),left(NULL),right(NULL)
, n(0)
{}
--- 38,42 ----
TableAnyMap(TableAnyMap *p,Data *dt)
: data(dt)
! , parent(p),left(0),right(0)
, n(0)
{}
***************
*** 44,48 ****
virtual ~TableAnyMap();
! #if 0
void check(int tsize) { if(n) _check(tsize); }
#else
--- 44,48 ----
virtual ~TableAnyMap();
! #if 0 // set 1 for asserting the map structure (very cpu-intensive!)
void check(int tsize) { if(n) _check(tsize); }
#else
***************
*** 57,61 ****
else {
data[n++](k,t);
! r = NULL;
}
check(tsize);
--- 57,61 ----
else {
data[n++](k,t);
! r = 0;
}
check(tsize);
***************
*** 63,69 ****
}
! void *find(int tsize,size_t k) const { return n?_find(tsize,k):NULL; }
! void *remove(int tsize,size_t k) { void *r = n?_remove(tsize,k):NULL; check(tsize); return r; }
virtual void clear();
--- 63,74 ----
}
! 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):0;
! check(tsize);
! return r;
! }
virtual void clear();
***************
*** 72,76 ****
{
public:
! iterator(): map(NULL) {}
iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
iterator(iterator &it): map(it.map),ix(it.ix) {}
--- 77,81 ----
{
public:
! iterator(): map(0) {}
iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
iterator(iterator &it): map(it.map),ix(it.ix) {}
***************
*** 91,99 ****
// search smallest branch (go left as far as possible)
const TableAnyMap *nmap;
! while((nmap = map->left) != NULL) map = nmap;
}
void forward();
const TableAnyMap *map;
int ix;
--- 96,105 ----
// search smallest branch (go left as far as possible)
const TableAnyMap *nmap;
! while((nmap = map->left) != 0) map = nmap;
}
void forward();
+ // pointers to map and index within
const TableAnyMap *map;
int ix;
***************
*** 110,114 ****
else {
(left = _newmap(this))->_init(k,t);
! return NULL;
}
}
--- 116,120 ----
else {
(left = _newmap(this))->_init(k,t);
! return 0;
}
}
***************
*** 120,124 ****
else {
(right = _newmap(this))->_init(k,t);
! return NULL;
}
}
--- 126,130 ----
else {
(right = _newmap(this))->_init(k,t);
! return 0;
}
}
***************
*** 137,164 ****
Data *const data;
TableAnyMap *parent,*left,*right;
! short n;
//! return index of data item with key <= k
//! \note index can point past the last item!
! 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;
! }
! }
! }
return ix;
}
--- 143,165 ----
Data *const data;
TableAnyMap *parent,*left,*right;
! int n;
//! return index of data item with key <= k
//! \note index can point past the last item!
! unsigned int _tryix(size_t k) const
{
! 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;
}
***************
*** 168,172 ****
if(!b->n) {
// remove empty branch
! _delmap(b); b = NULL;
}
}
--- 169,173 ----
if(!b->n) {
// remove empty branch
! _delmap(b); b = 0;
}
}
***************
*** 181,185 ****
{
public:
! TablePtrMap(): TableAnyMap(NULL,slots),count(0) {}
virtual ~TablePtrMap() { clear(); }
--- 182,186 ----
{
public:
! TablePtrMap(): TableAnyMap(0,slots),count(0) {}
virtual ~TablePtrMap() { clear(); }
--- NEW FILE: flmap.cpp ---
/*
flext - C++ layer for Max/MSP and pd (pure data) externals
Copyright (c) 2001-2005 Thomas Grill (gr at 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;
}
}
}
}
}
}
More information about the Pd-cvs
mailing list