flext  0.6.0
flmap.h
Go to the documentation of this file.
1 /*
2 flext - C++ layer for Max and Pure Data externals
3 
4 Copyright (c) 2001-2015 Thomas Grill (gr@grrrr.org)
5 For information on usage and redistribution, and for a DISCLAIMER OF ALL
6 WARRANTIES, see the file, "license.txt," in this distribution.
7 */
8 
13 #ifndef __FLMAP_H
14 #define __FLMAP_H
15 
16 #include "flprefix.h"
17 
22 #include "flpushns.h"
23 
26 {
27 public:
28 
29  virtual TableAnyMap *_newmap(TableAnyMap *parent) = 0;
30  virtual void _delmap(TableAnyMap *map) = 0;
31 
32  struct Data {
33  void operator()(size_t k,void *v) { key = k,value = v; }
34  void operator =(void *v) { value = v; }
35 
36  size_t key;
37  void *value;
38  };
39 
40 protected:
41  // constructor and destructor are protected so that they can't be directly instantiated
42 
44  : data(dt)
45  , parent(p),left(0),right(0)
46  , n(0)
47  {}
48 
49  virtual ~TableAnyMap();
50 
51 public:
52 
53 #if 0 // set 1 for asserting the map structure (very cpu-intensive!)
54  void check(int tsize) { if(n) _check(tsize); }
55 #else
56 // void check(int tsize) {}
57 #endif
58 
59  void *insert(int tsize,size_t k,void *t)
60  {
61  void *r;
62  if(LIKELY(n))
63  r = _set(tsize,k,t);
64  else {
65  data[n++](k,t);
66  r = 0;
67  }
68 // check(tsize);
69  return r;
70  }
71 
72  void *find(int tsize,size_t k) const { return LIKELY(n)?_find(tsize,k):0; }
73 
74  void *remove(int tsize,size_t k)
75  {
76  void *r = LIKELY(n)?_remove(tsize,k):0;
77 // check(tsize);
78  return r;
79  }
80 
81  virtual void clear();
82 
84  {
85  public:
86  iterator(): map(0) {}
87  iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
88  iterator(const iterator &it): map(it.map),ix(it.ix) {}
89 
90  iterator &operator =(const iterator &it) { map = it.map,ix = it.ix; return *this; }
91 
92  operator bool() const { return map && ix < map->n; }
93 
94  // no checking here!
95  void *data() const { return map->data[ix].value; }
96  size_t key() const { return map->data[ix].key; }
97 
98  iterator &operator ++() { forward(); return *this; }
99 
100  protected:
101  void leftmost()
102  {
103  // search smallest branch (go left as far as possible)
104  const TableAnyMap *nmap;
105  while((nmap = map->left) != 0) map = nmap;
106  }
107 
108  void forward();
109 
110  // pointers to map and index within
111  const TableAnyMap *map;
112  int ix;
113  };
114 
115  void _init(size_t k,void *t) { data[0](k,t); n = 1; }
116 
117  void *_toleft(int tsize,size_t k,void *t)
118  {
119  if(left)
120  return left->_set(tsize,k,t);
121  else {
122  (left = _newmap(this))->_init(k,t);
123  return 0;
124  }
125  }
126 
127  void *_toright(int tsize,size_t k,void *t)
128  {
129  if(right)
130  return right->_set(tsize,k,t);
131  else {
132  (right = _newmap(this))->_init(k,t);
133  return 0;
134  }
135  }
136 
137  void *_toleft(int tsize,Data &v) { return _toleft(tsize,v.key,v.value); }
138  void *_toright(int tsize,Data &v) { return _toright(tsize,v.key,v.value); }
139 
140  void *_set(int tsize,size_t k,void *t);
141  void *_find(int tsize,size_t k) const;
142  void *_remove(int tsize,size_t k);
143 
144 #ifdef FLEXT_DEBUG
145  void _check(int tsize);
146 #endif
147 
149  TableAnyMap *parent,*left,*right;
150  int n;
151 
154  unsigned int _tryix(size_t k) const
155  {
156  unsigned int ix = 0,b = n;
157  while(ix != b) {
158  const unsigned int c = (ix+b)>>1;
159  const size_t dk = data[c].key;
160  if(k == dk)
161  return c;
162  else if(k < dk)
163  b = c;
164  else if(ix < c)
165  ix = c;
166  else
167  return b;
168  }
169  return ix;
170  }
171 
173  {
174  if(!b->n) {
175  // remove empty branch
176  _delmap(b); b = 0;
177  }
178  }
179 
180  void _getsmall(Data &dt);
181  void _getbig(Data &dt);
182 
183 private:
184  // hide, so that it can't be used.....
185  explicit TableAnyMap(const TableAnyMap &): data(NULL) {}
186  TableAnyMap &operator =(const TableAnyMap &) { return *this; }
187 };
188 
189 template <typename K,typename T,int N = 8>
191  :
192 #if (defined(_MSC_VER) && _MSC_VER < 1300) || defined(__BORLANDC__) || defined(__MWERKS__)
193  public // necessary for VC6
194 #endif
195  FLEXT_TEMPINST(TableAnyMap)
196 {
197 public:
199  virtual ~TablePtrMap() { clear(); }
200 
201  virtual void clear() { TableAnyMap::clear(); count = 0; }
202 
203  inline int size() const { return count; }
204 
205  inline T insert(K k,T t)
206  {
207  void *d = TableAnyMap::insert(N,*(size_t *)&k,(void *)t);
208  if(!d) ++count;
209  return (T)d;
210  }
211 
212  inline T find(K k) const { return (T)TableAnyMap::find(N,*(size_t *)&k); }
213 
214  inline T remove(K k)
215  {
216  void *d = TableAnyMap::remove(N,*(size_t *)&k);
217  if(LIKELY(d)) --count;
218  return (T)d;
219  }
220 
221 
222  class iterator
224  {
225  public:
226  iterator() {}
228  iterator(const iterator &it): TableAnyMap::iterator(it) {}
229 
230  // this ugly syntax (cast to parent class) is needed for MSVC6
231 
232  inline iterator &operator =(const iterator &it) { ((TableAnyMap::iterator &)*this) = it; return *this; }
233 
234  inline operator bool() const { return (bool)((TableAnyMap::iterator &)*this); }
235  inline T data() const { return (T)(((TableAnyMap::iterator &)*this).data()); }
236  inline K key() const { return (K)(((TableAnyMap::iterator &)*this).key()); }
237 
238  inline iterator &operator ++() { ++((TableAnyMap::iterator &)*this); return *this; }
239  };
240 
241 protected:
243 
245  virtual void _delmap(TableAnyMap *map) { delete (TablePtrMap *)map; }
246 
247  int count;
249 
250 private:
251  explicit TablePtrMap(const TableAnyMap &p) {}
252 };
253 
254 #include "flpopns.h"
255 
257 
258 #endif
TableAnyMap::find
void * find(int tsize, size_t k) const
Definition: flmap.h:72
TableAnyMap::_newmap
virtual TableAnyMap * _newmap(TableAnyMap *parent)=0
TablePtrMap
Definition: flmap.h:196
TableAnyMap::remove
void * remove(int tsize, size_t k)
Definition: flmap.h:74
TableAnyMap
Definition: flmap.h:26
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
TableAnyMap::_delmap
virtual void _delmap(TableAnyMap *map)=0
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:447
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:462
TablePtrMap::_delmap
virtual void _delmap(TableAnyMap *map)
Definition: flmap.h:245
TablePtrMap::TablePtrMap
TablePtrMap()
Definition: flmap.h:198
TableAnyMap::iterator
Definition: flmap.h:84
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:425
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:464
TablePtrMap::iterator
Definition: flmap.h:224
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.