1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
/*
flext - C++ layer for Max/MSP and pd (pure data) externals
Copyright (c) 2001-2003 Thomas Grill (xovo@gmx.net)
For information on usage and redistribution, and for a DISCLAIMER OF ALL
WARRANTIES, see the file, "license.txt," in this distribution.
*/
/*! \file flitem.cpp
\brief Processing of method and attribute lists.
*/
#include "flext.h"
#include <string.h>
flext_base::Item::Item(const t_symbol *t,int inl,AttrItem *a):
tag(t),inlet(inl),attr(a),nxt(NULL)
{}
flext_base::Item::~Item()
{
if(nxt) delete nxt;
}
flext_base::ItemCont::ItemCont():
arr(new Item *[2]),cnt(0),bits(-1)
{
arr[0] = arr[1] = NULL;
}
flext_base::ItemCont::~ItemCont()
{
if(Ready()) {
// if finalized, the array has several slots
int c = Size();
for(int i = 0; i < c; ++i)
if(arr[i]) delete arr[i];
}
else
// the array only has a head (arr[0]) and a tail (arr[1]) pointer
delete arr[0];
delete[] arr;
}
void flext_base::ItemCont::Add(Item *it)
{
if(Ready()) {
// retrieve array index
int ix = Hash(it->tag,it->inlet,bits);
// add to array slot
if(arr[ix]) {
Item *a = arr[ix];
while(a->nxt) a = a->nxt;
a->nxt = it;
}
else arr[ix] = it;
// post("RDY inlet=%i,tag=%s,hash=%i",it->inlet,GetString(it->tag),ix);
}
else {
// post("ADD index=%i,inlet=%i,tag=%s",cnt,it->inlet,GetString(it->tag));
if(arr[0]) arr[1] = arr[1]->nxt = it;
else arr[0] = arr[1] = it;
++cnt;
}
}
bool flext_base::ItemCont::Remove(Item *it)
{
if(Ready()) {
// retrieve array index
int ix = Hash(it->tag,it->inlet,bits);
// remove from array slot
if(arr[ix]) {
Item *a1 = NULL,*a = arr[ix];
while(a && a != it) a1 = a,a = a->nxt;
if(a) { // found (a == it)
if(a1) a1->nxt = it->nxt;
else arr[ix] = it->nxt;
it->nxt = NULL;
return true;
}
else
return false;
}
else
return false;
}
else {
// remove from list
if(!arr[0])
return false;
else {
Item *a1 = NULL,*a = arr[0];
while(a && a != it) a1 = a,a = a->nxt;
if(a) { // found (a == it)
if(a1) a1->nxt = it->nxt;
else arr[0] = it->nxt;
if(!it->nxt) arr[1] = a1;
it->nxt = NULL;
--cnt;
return true;
}
else
return false;
}
}
}
void flext_base::ItemCont::Finalize()
{
if(!Ready()) {
bits = Int2Bits(cnt); // at least enough bits to hold all items
// post("This=%p, Count %i, Bits %i",this,cnt,bits);
int sz = Size();
// save stored item list
Item *lst = arr[0];
delete[] arr;
arr = new Item *[sz];
memset(arr,0,sz*sizeof(*arr));
while(lst) {
Item *l = lst;
lst = lst->nxt;
l->nxt = NULL;
Add(l);
}
#if 0
post("count=%i, bit=%i size=%i",Count(),bits,sz);
if(Count()) {
static char usage[1024];
int c = 0,i;
for(i = 0; i < sz; ++i) {
usage[i] = arr[i]?'x':'.';
if(arr[i]) ++c;
}
usage[i] = 0;
post("USAGE %i/%i - sparse=%i%% %s",c,Count(),(int)((float)c/Count()*100.),usage);
}
#endif
}
}
flext_base::Item *flext_base::ItemCont::Find(const t_symbol *tag,int inlet) const
{
Item *a;
if(!Ready())
a = arr[0];
else if(Count()) {
int ix = Hash(tag,inlet,bits);
a = arr[ix];
// post("FIND tag=%s inlet=%i hash=%i p=%p",GetString(tag),inlet,ix,a);
}
else
a = NULL;
// Search first matching entry
while(a && (a->tag != tag || a->inlet != inlet)) a = a->nxt;
return a;
}
int flext_base::ItemCont::Hash(const t_symbol *tag,int inlet,int bits)
{
unsigned long h = ((reinterpret_cast<unsigned long>(tag)&~7L)<<1)+inlet;
return FoldBits(h,bits);
}
// --- class item lists (methods and attributes) ----------------
class _itemarr
{
public:
enum { HASHBITS=7, HASHSIZE=1<<HASHBITS };
_itemarr(flext_obj::t_classid c,int i);
~_itemarr();
static int Hash(flext_obj::t_classid c,int ix);
int Hash() const { return Hash(clid,ix); }
void Add(_itemarr *a);
flext_obj::t_classid clid;
int ix;
flext_base::ItemCont *arr;
_itemarr *nxt;
};
_itemarr::_itemarr(flext_obj::t_classid c,int i):
clid(c),ix(i),
arr(new flext_base::ItemCont),
nxt(NULL)
{}
_itemarr::~_itemarr()
{
delete arr;
if(nxt) delete nxt;
}
void _itemarr::Add(_itemarr *a)
{
if(nxt) nxt->Add(a);
else nxt = a;
}
int _itemarr::Hash(flext_obj::t_classid c,int ix)
{
unsigned long h = (reinterpret_cast<unsigned long>(c)&~3L)+ix;
return flext::FoldBits(h,HASHBITS);
}
static _itemarr **_arrs = NULL;
flext_base::ItemCont *flext_base::GetClassArr(t_classid c,int ix)
{
if(!_arrs) {
_arrs = new _itemarr *[_itemarr::HASHSIZE];
memset(_arrs,0,_itemarr::HASHSIZE*sizeof(*_arrs));
}
int hash = _itemarr::Hash(c,ix);
_itemarr *a = _arrs[hash];
_itemarr *pa = NULL;
while(a && (a->clid != c || a->ix != ix)) pa = a,a = a->nxt;
// post("GETARR classid=%p ix=%i -> hash=%i,arr=%p",c,ix,hash,a?a->arr:NULL);
if(!a) {
a = new _itemarr(c,ix);
if(pa)
// previous entry... extend
a->nxt = pa->nxt,pa->nxt = a;
else
// new singular entry
_arrs[hash] = a;
}
return a->arr;
}
|
