flext 0.6.2
flmap.h
Go to the documentation of this file.
1/*
2flext - C++ layer for Max and Pure Data externals
3
4Copyright (c) 2001-2020 Thomas Grill (gr@grrrr.org)
5For information on usage and redistribution, and for a DISCLAIMER OF ALL
6WARRANTIES, 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{
27public:
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
40protected:
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
51public:
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
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
183private:
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
189template <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{
197public:
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
224 {
225 public:
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
241protected:
243
245 virtual void _delmap(TableAnyMap *map) { delete (TablePtrMap *)map; }
246
247 int count;
249
250private:
251 explicit TablePtrMap(const TableAnyMap &p) { FLEXT_UNUSED(p); }
252};
253
254#include "flpopns.h"
255
257
258#endif
Definition flmap.h:84
void * data() const
Definition flmap.h:95
void leftmost()
Definition flmap.h:101
iterator()
Definition flmap.h:86
const TableAnyMap * map
Definition flmap.h:111
size_t key() const
Definition flmap.h:96
iterator(const TableAnyMap &m)
Definition flmap.h:87
iterator(const iterator &it)
Definition flmap.h:88
int ix
Definition flmap.h:112
Definition flmap.h:26
void * remove(int tsize, size_t k)
Definition flmap.h:74
void * _toleft(int tsize, size_t k, void *t)
Definition flmap.h:117
virtual void _delmap(TableAnyMap *map)=0
void _init(size_t k, void *t)
Definition flmap.h:115
TableAnyMap(const TableAnyMap &)
Definition flmap.h:185
void _eraseempty(TableAnyMap *&b)
Definition flmap.h:172
int n
Definition flmap.h:150
void * _toright(int tsize, Data &v)
Definition flmap.h:138
void * _toleft(int tsize, Data &v)
Definition flmap.h:137
TableAnyMap * left
Definition flmap.h:149
void * _toright(int tsize, size_t k, void *t)
Definition flmap.h:127
Data * data
Definition flmap.h:148
unsigned int _tryix(size_t k) const
Definition flmap.h:154
void * insert(int tsize, size_t k, void *t)
Definition flmap.h:59
virtual TableAnyMap * _newmap(TableAnyMap *parent)=0
void * find(int tsize, size_t k) const
Definition flmap.h:72
TableAnyMap(TableAnyMap *p, Data *dt)
Definition flmap.h:43
virtual void clear()
Definition flmap.cpp:23
Definition flmap.h:224
iterator & operator=(const iterator &it)
Definition flmap.h:232
iterator & operator++()
Definition flmap.h:238
iterator(const TablePtrMap &m)
Definition flmap.h:227
iterator()
Definition flmap.h:226
T data() const
Definition flmap.h:235
iterator(const iterator &it)
Definition flmap.h:228
K key() const
Definition flmap.h:236
Definition flmap.h:196
virtual void clear()
Definition flmap.h:201
T insert(K k, T t)
Definition flmap.h:205
TablePtrMap(const TableAnyMap &p)
Definition flmap.h:251
int count
Definition flmap.h:247
T find(K k) const
Definition flmap.h:212
Data slots[N]
Definition flmap.h:248
T remove(K k)
Definition flmap.h:214
virtual ~TablePtrMap()
Definition flmap.h:199
int size() const
Definition flmap.h:203
TablePtrMap()
Definition flmap.h:198
virtual void _delmap(TableAnyMap *map)
Definition flmap.h:245
virtual TableAnyMap * _newmap(TableAnyMap *_parent)
Definition flmap.h:244
TablePtrMap(TableAnyMap *p)
Definition flmap.h:242
Try to find out the platform.
#define FLEXT_TEMPINST(fun)
Definition flprefix.h:455
#define LIKELY(expression)
Definition flprefix.h:438
#define FLEXT_SHARE
Definition flprefix.h:416
#define FLEXT_TEMPLATE
Definition flprefix.h:453
#define FLEXT_UNUSED(x)
Definition flstdc.h:302
#define FLEXT_CAST
Switch for compilation of derived virtual classes.
Definition fldefs.h:27
Definition flmap.h:32
void * value
Definition flmap.h:37
size_t key
Definition flmap.h:36
void operator()(size_t k, void *v)
Definition flmap.h:33