flmap.h
Go to the documentation of this file.
/*
flext - C++ layer for Max and Pure Data externals
Copyright (c) 2001-2015 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.
*/
#ifndef __FLMAP_H
#define __FLMAP_H
#include "flprefix.h"
#include "flpushns.h"
FLEXT_TEMPLATE
class FLEXT_SHARE TableAnyMap
{
public:
virtual TableAnyMap *_newmap(TableAnyMap *parent) = 0;
virtual void _delmap(TableAnyMap *map) = 0;
struct Data {
void operator()(size_t k,void *v) { key = k,value = v; }
void operator =(void *v) { value = v; }
size_t key;
void *value;
};
protected:
// constructor and destructor are protected so that they can't be directly instantiated
TableAnyMap(TableAnyMap *p,Data *dt)
: data(dt)
, parent(p),left(0),right(0)
, n(0)
{}
virtual ~TableAnyMap();
public:
#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) {}
#endif
void *insert(int tsize,size_t k,void *t)
{
void *r;
if(LIKELY(n))
r = _set(tsize,k,t);
else {
data[n++](k,t);
r = 0;
}
// check(tsize);
return r;
}
void *find(int tsize,size_t k) const { return LIKELY(n)?_find(tsize,k):0; }
void *remove(int tsize,size_t k)
{
void *r = LIKELY(n)?_remove(tsize,k):0;
// check(tsize);
return r;
}
virtual void clear();
class FLEXT_SHARE iterator
{
public:
iterator(): map(0) {}
iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
iterator(const iterator &it): map(it.map),ix(it.ix) {}
iterator &operator =(const iterator &it) { map = it.map,ix = it.ix; return *this; }
operator bool() const { return map && ix < map->n; }
// no checking here!
void *data() const { return map->data[ix].value; }
size_t key() const { return map->data[ix].key; }
iterator &operator ++() { forward(); return *this; }
protected:
void leftmost()
{
// 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;
};
void _init(size_t k,void *t) { data[0](k,t); n = 1; }
void *_toleft(int tsize,size_t k,void *t)
{
if(left)
return left->_set(tsize,k,t);
else {
(left = _newmap(this))->_init(k,t);
return 0;
}
}
void *_toright(int tsize,size_t k,void *t)
{
if(right)
return right->_set(tsize,k,t);
else {
(right = _newmap(this))->_init(k,t);
return 0;
}
}
void *_toleft(int tsize,Data &v) { return _toleft(tsize,v.key,v.value); }
void *_toright(int tsize,Data &v) { return _toright(tsize,v.key,v.value); }
void *_set(int tsize,size_t k,void *t);
void *_find(int tsize,size_t k) const;
void *_remove(int tsize,size_t k);
#ifdef FLEXT_DEBUG
void _check(int tsize);
#endif
Data *data;
TableAnyMap *parent,*left,*right;
int n;
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;
}
void _eraseempty(TableAnyMap *&b)
{
if(!b->n) {
// remove empty branch
_delmap(b); b = 0;
}
}
void _getsmall(Data &dt);
void _getbig(Data &dt);
private:
// hide, so that it can't be used.....
explicit TableAnyMap(const TableAnyMap &): data(NULL) {}
TableAnyMap &operator =(const TableAnyMap &) { return *this; }
};
template <typename K,typename T,int N = 8>
class TablePtrMap
:
#if (defined(_MSC_VER) && _MSC_VER < 1300) || defined(__BORLANDC__) || defined(__MWERKS__)
public // necessary for VC6
#endif
FLEXT_TEMPINST(TableAnyMap)
{
public:
TablePtrMap(): TableAnyMap(0,slots),count(0) {}
virtual ~TablePtrMap() { clear(); }
virtual void clear() { TableAnyMap::clear(); count = 0; }
inline int size() const { return count; }
inline T insert(K k,T t)
{
void *d = TableAnyMap::insert(N,*(size_t *)&k,(void *)t);
if(!d) ++count;
return (T)d;
}
inline T find(K k) const { return (T)TableAnyMap::find(N,*(size_t *)&k); }
inline T remove(K k)
{
void *d = TableAnyMap::remove(N,*(size_t *)&k);
if(LIKELY(d)) --count;
return (T)d;
}
class iterator
: TableAnyMap::iterator
{
public:
iterator() {}
iterator(const TablePtrMap &m): TableAnyMap::iterator(m) {}
iterator(const iterator &it): TableAnyMap::iterator(it) {}
// this ugly syntax (cast to parent class) is needed for MSVC6
inline iterator &operator =(const iterator &it) { ((TableAnyMap::iterator &)*this) = it; return *this; }
inline operator bool() const { return (bool)((TableAnyMap::iterator &)*this); }
inline T data() const { return (T)(((TableAnyMap::iterator &)*this).data()); }
inline K key() const { return (K)(((TableAnyMap::iterator &)*this).key()); }
inline iterator &operator ++() { ++((TableAnyMap::iterator &)*this); return *this; }
};
protected:
TablePtrMap(TableAnyMap *p): TableAnyMap(p,slots),count(0) {}
virtual TableAnyMap *_newmap(TableAnyMap *parent) { return new TablePtrMap(parent); }
virtual void _delmap(TableAnyMap *map) { delete (TablePtrMap *)map; }
int count;
Data slots[N];
private:
explicit TablePtrMap(const TableAnyMap &p) {}
};
#include "flpopns.h"
#endif
TableAnyMap::find
void * find(int tsize, size_t k) const
Definition: flmap.h:72
TablePtrMap
Definition: flmap.h:190
TableAnyMap::remove
void * remove(int tsize, size_t k)
Definition: flmap.h:74
TableAnyMap
Definition: flmap.h:25
TableAnyMap::_toright
void * _toright(int tsize, size_t k, void *t)
Definition: flmap.h:127
TablePtrMap::TablePtrMap
TablePtrMap(const TableAnyMap &p)
Definition: flmap.h:251
TableAnyMap::Data::value
void * value
Definition: flmap.h:37
TableAnyMap::data
Data * data
Definition: flmap.h:148
TableAnyMap::Data::operator()
void operator()(size_t k, void *v)
Definition: flmap.h:33
TablePtrMap::iterator::key
K key() const
Definition: flmap.h:236
flpopns.h
TablePtrMap::find
T find(K k) const
Definition: flmap.h:212
TableAnyMap::Data
Definition: flmap.h:32
TableAnyMap::parent
TableAnyMap * parent
Definition: flmap.h:149
TableAnyMap::right
TableAnyMap * right
Definition: flmap.h:149
TablePtrMap::iterator::iterator
iterator()
Definition: flmap.h:226
TableAnyMap::iterator::iterator
iterator()
Definition: flmap.h:86
TablePtrMap::slots
Data slots[N]
Definition: flmap.h:248
TableAnyMap::iterator::ix
int ix
Definition: flmap.h:112
TableAnyMap::Data::key
size_t key
Definition: flmap.h:36
TablePtrMap::TablePtrMap
TablePtrMap(TableAnyMap *p)
Definition: flmap.h:242
TableAnyMap::iterator::map
const TableAnyMap * map
Definition: flmap.h:111
LIKELY
#define LIKELY(expression)
Definition: flprefix.h:440
TablePtrMap::iterator::data
T data() const
Definition: flmap.h:235
TableAnyMap::clear
virtual void clear()
Definition: flmap.cpp:23
TablePtrMap::_newmap
virtual TableAnyMap * _newmap(TableAnyMap *parent)
Definition: flmap.h:244
FLEXT_TEMPLATE
#define FLEXT_TEMPLATE
Definition: flprefix.h:455
TablePtrMap::_delmap
virtual void _delmap(TableAnyMap *map)
Definition: flmap.h:245
TablePtrMap::TablePtrMap
TablePtrMap()
Definition: flmap.h:198
TableAnyMap::iterator
Definition: flmap.h:83
TableAnyMap::iterator::key
size_t key() const
Definition: flmap.h:96
TablePtrMap::count
int count
Definition: flmap.h:247
TablePtrMap::~TablePtrMap
virtual ~TablePtrMap()
Definition: flmap.h:199
TablePtrMap::size
int size() const
Definition: flmap.h:203
TableAnyMap::iterator::leftmost
void leftmost()
Definition: flmap.h:101
TablePtrMap::iterator::operator++
iterator & operator++()
Definition: flmap.h:238
TablePtrMap::remove
T remove(K k)
Definition: flmap.h:214
TableAnyMap::TableAnyMap
TableAnyMap(const TableAnyMap &)
Definition: flmap.h:185
TableAnyMap::n
int n
Definition: flmap.h:150
TablePtrMap::iterator::iterator
iterator(const TablePtrMap &m)
Definition: flmap.h:227
TableAnyMap::insert
void * insert(int tsize, size_t k, void *t)
Definition: flmap.h:59
TablePtrMap::iterator::operator=
iterator & operator=(const iterator &it)
Definition: flmap.h:232
TableAnyMap::_toleft
void * _toleft(int tsize, size_t k, void *t)
Definition: flmap.h:117
FLEXT_SHARE
#define FLEXT_SHARE
Definition: flprefix.h:418
flpushns.h
TableAnyMap::iterator::iterator
iterator(const TableAnyMap &m)
Definition: flmap.h:87
TableAnyMap::_init
void _init(size_t k, void *t)
Definition: flmap.h:115
TableAnyMap::_toleft
void * _toleft(int tsize, Data &v)
Definition: flmap.h:137
TableAnyMap::_tryix
unsigned int _tryix(size_t k) const
Definition: flmap.h:154
TablePtrMap::insert
T insert(K k, T t)
Definition: flmap.h:205
TablePtrMap::clear
virtual void clear()
Definition: flmap.h:201
TableAnyMap::_toright
void * _toright(int tsize, Data &v)
Definition: flmap.h:138
FLEXT_TEMPINST
#define FLEXT_TEMPINST(fun)
Definition: flprefix.h:457
TablePtrMap::iterator
Definition: flmap.h:222
TableAnyMap::left
TableAnyMap * left
Definition: flmap.h:149
TableAnyMap::iterator::data
void * data() const
Definition: flmap.h:95
TablePtrMap::iterator::iterator
iterator(const iterator &it)
Definition: flmap.h:228
TableAnyMap::TableAnyMap
TableAnyMap(TableAnyMap *p, Data *dt)
Definition: flmap.h:43
TableAnyMap::_eraseempty
void _eraseempty(TableAnyMap *&b)
Definition: flmap.h:172
TableAnyMap::iterator::iterator
iterator(const iterator &it)
Definition: flmap.h:88
flprefix.h
Try to find out the platform.