1 #include <memory.h>
2 #include <assert.h>
3 #include <stdio.h>
4 #include "tmplvect.h"
5 #include "try.h"
6
7 /* PtrTry */
PtrTry(char letter)8 PtrTry::PtrTry(char letter)
9 {
10 _letter = letter;
11 _list = NULL;
12 _next = NULL;
13 }
14
~PtrTry()15 PtrTry::~PtrTry()
16 {
17 if (_next) {
18 int count = _next->Elements();
19 for (int i = 0; i < count; i++) {
20 delete _next->Element(i);
21 }
22 _next->Clear();
23 }
24 if (_list != NULL) _list->Clear();
25 }
26
27 /* ʸ�������ꤷ�ƥǡ������ɲä��� */
Add(void * newobj,char * key)28 void PtrTry::Add(void* newobj, char* key)
29 {
30 if (! *key) {
31 // ʸ����ü �����˥ǡ����ȥ�����
32 if (_list == NULL) _list = new PtrVect<void*>;
33 if (_list->Find(newobj) < 0) _list->Add(newobj);
34 } else {
35 // ����ʸ����õ��
36 if (!_next) {
37 _next = new PtrVect<PtrTry*>;
38 } else {
39 int count = _next->Elements();
40 for (int i = 0; i < count; i++) {
41 if (_next->Element(i)->_letter == *key) {
42 key++;
43 _next->Element(i)->Add(newobj, key);
44 return;
45 }
46 }
47 }
48 PtrTry* newTry = new PtrTry(*key);
49 key++;
50 _next->Add(newTry);
51 newTry->Add(newobj, key);
52 }
53 }
54
55 /* key ��õ������������ꥹ�Ȥ��֤�
56 �ꥹ�Ȥ����ξ�硢 NULL ���֤�
57 �����ͤϰ��פ���ʸ����
58 */
Find(char * key,PtrVect<void * > & result,char cond) const59 int PtrTry::Find(char* key, PtrVect<void*>& result, char cond) const
60 {
61 int matchlen = 0;
62 if (! *key) {
63 // �����ǥޥå�����
64 if (_list != NULL) {
65 result = *_list;
66 return matchlen;
67 }
68 if (cond != MATCH_LONGER) {
69 result.Clear();
70 return matchlen;
71 }
72 result.Clear();
73 if (!_next) return matchlen;
74 int count = _next->Elements();
75 PtrVect<void*> tmplist;
76 for (int i = 0; i < count; i++) {
77 _next->Element(i)->Find(key, tmplist, cond);
78 result += tmplist;
79 }
80 return matchlen;
81 }
82 if (_next == NULL) {
83 // ����ʾ���פ���ꥹ�Ȥ�¸�ߤ��ʤ�
84 if (cond == MATCH_EXACT) {
85 result.Clear();
86 return 0;
87 } else {
88 if (_list) {
89 result = *_list;
90 } else {
91 result.Clear();
92 }
93 return 0;
94 }
95 }
96 // �ޤ����פ���ǡ���������
97 int count = _next->Elements();
98 PtrVect<void*> list;
99 for (int i = 0; i < count; i++) {
100 if (_next->Element(i)->_letter == *key) {
101 key++;
102 matchlen = _next->Element(i)->Find(key, list, cond) + 1;
103 if (list.Elements() > 0 || cond == MATCH_EXACT) {
104 result = list;
105 return matchlen;
106 }
107 if (_list != NULL) {
108 result = *_list;
109 return matchlen;
110 }
111 break;
112 }
113 }
114 if (_list) result = *_list;
115 else result.Clear();
116 return matchlen; // ����ʾ���פ��ʤ��Τǡ���Ĺ���פ��֤�
117 }
118
Remove(void * obj,char * key)119 void PtrTry::Remove(void* obj, char* key)
120 {
121 if (! *key) {
122 if (_list) {
123 _list->Remove(obj);
124 }
125 return;
126 }
127 if (_next == NULL) return;
128 int count = _next->Elements();
129 for (int i = 0; i < count; i++) {
130 if (_next->Element(i)->_letter == *key) {
131 key++;
132 return _next->Element(i)->Remove(obj, key);
133 }
134 }
135 return; // ��������ǡ���̵��
136 }
137
Clear(void)138 void PtrTry::Clear(void)
139 {
140 _letter = 0;
141 delete _list;
142 _list = NULL;
143 if (_next) {
144 _next->ClearElements();
145 }
146 delete _next;
147 _next = NULL;
148 }
149
150 unsigned int statics[STATICS_SIZE];
151
MakeStatics(void)152 void PtrTry::MakeStatics(void)
153 {
154 if (!_next) {
155 statics[0]++;
156 return;
157 }
158 int count = _next->Elements();
159 if (count < STATICS_SIZE - 1) statics[count]++;
160 else statics[STATICS_SIZE - 1]++;
161 for (int i = 0; i < count; i++) {
162 _next->Element(i)->MakeStatics();
163 }
164 }
165
QSort(int (* fcmp)(const void *,const void *))166 void PtrTry::QSort(int (*fcmp)(const void*, const void*))
167 {
168 if (_list) _list->QSort(fcmp);
169 if (_next) {
170 int count = _next->Elements();
171 for (int i = 0; i < count; i++) {
172 _next->Element(i)->QSort(fcmp);
173 }
174 }
175 }
176
177 /* StaticPtrTry */
offset(void * p,long base)178 static void* offset(void* p, long base) {
179 return (void*)((char*)p + base);
180 }
181
StaticPtrTry(PtrTry * key)182 StaticPtrTry::StaticPtrTry(PtrTry* key) {
183 int i;
184 _letter = key->_letter;
185 if (key->_list) {
186 _nList = key->_list->Elements();
187 _pList = (long*)malloc(sizeof(long) * _nList);
188 } else {
189 _nList = 0;
190 _pList = NULL;
191 }
192 if (key->_next) {
193 _nNext = key->_next->Elements();
194 _pNext = (StaticPtrTry**)malloc(sizeof(StaticPtrTry*) * _nNext);
195 } else {
196 _nNext = 0;
197 _pNext = NULL;
198 }
199 for (i = 0; i < _nList; i++) {
200 _pList[i] = long(key->_list->Element(i));
201 }
202 for (i = 0; i < _nNext; i++) {
203 _pNext[i] = new StaticPtrTry(key->_next->Element(i));
204 }
205 }
206
packedSize(void)207 unsigned long StaticPtrTry::packedSize(void) {
208 unsigned long size = sizeof(StaticPtrTry);
209 size += sizeof(long) * this->_nList;
210 size += sizeof(StaticPtrTry*) * this->_nNext;
211 for (int i = 0; i < this->_nNext; i++) {
212 size += this->_pNext[i]->packedSize();
213 }
214 return size;
215 }
216
pack(StaticPtrTry * newaddress,long base)217 StaticPtrTry* StaticPtrTry::pack(StaticPtrTry* newaddress, long base) {
218 int i;
219 char* cp = (char*)newaddress;
220 StaticPtrTry* newnode = (StaticPtrTry*)(offset(newaddress, base));
221 memcpy(newnode, this, sizeof(StaticPtrTry));
222 cp += sizeof(StaticPtrTry);
223 memcpy(offset(cp, base), this->_pList, sizeof(long) * this->_nList);
224 newnode->_pList = (long*)cp;
225 cp += sizeof(long) * this->_nList;
226 newnode->_pNext = (StaticPtrTry**)cp;
227 cp += sizeof(StaticPtrTry*) * this->_nNext;
228
229 StaticPtrTry** pp;
230 for (i = 0; i < this->_nNext; i++) {
231 pp = (StaticPtrTry**)(offset(newnode->_pNext + i, base));
232 *pp = (StaticPtrTry*)cp;
233 cp = (char*)(this->_pNext[i]->pack((StaticPtrTry*)cp, base));
234 }
235 return (StaticPtrTry*)cp;
236 }
237
238 /* key ��õ������������ꥹ�Ȥ��֤�
239 �ꥹ�Ȥ����ξ�硢 NULL ���֤� */
Find(char * key,ObjVect<long> & result,char cond,long base)240 int StaticPtrTry::Find(char* key, ObjVect<long>& result, char cond, long base)
241 {
242 int matchlen = 0;
243 int i;
244 StaticPtrTry* node;
245 if (! *key) {
246 // �����ǥޥå�����
247 if (_nList > 0) {
248 result.Clear();
249 for (i = 0; i < _nList; i++) {
250 result.Add(this->list(i, base));
251 }
252 return matchlen;
253 }
254 if (cond != MATCH_LONGER) {
255 result.Clear();
256 return matchlen;
257 }
258 result.Clear();
259 if (_nNext == 0) return matchlen;
260 int count = _nNext;
261 ObjVect<long> tmplist;
262 for (i = 0; i < count; i++) {
263 node = next(i, base);
264 node->Find(key, tmplist, cond, base);
265 result += tmplist;
266 }
267 return matchlen;
268 }
269 if (_nNext == 0) {
270 // ����ʾ���פ���ꥹ�Ȥ�¸�ߤ��ʤ�
271 if (cond == MATCH_EXACT) {
272 result.Clear();
273 return matchlen;
274 } else {
275 if (_nList > 0) {
276 result.Clear();
277 for (i = 0; i < _nList; i++) {
278 result.Add(this->list(i, base));
279 }
280 } else {
281 result.Clear();
282 }
283 return matchlen;
284 }
285 }
286 int count = _nNext;
287 ObjVect<long> list;
288 StaticPtrTry** pp;
289 for (int i = 0; i < count; i++) {
290 node = this->next(i, base);
291 if (node->_letter == *key) {
292 key++;
293 matchlen = node->Find(key, list, cond, base) + 1;
294 if (list.Elements() > 0 || cond == MATCH_EXACT) {
295 result = list;
296 return matchlen;
297 }
298 if (_nList > 0) {
299 result.Clear();
300 for (i = 0; i < _nList; i++) {
301 result.Add(this->list(i, base));
302 }
303 return matchlen;
304 }
305 break;
306 }
307 }
308 result.Clear();
309 if (_nList > 0) {
310 for (i = 0; i < _nList; i++) {
311 result.Add(this->list(i, base));
312 }
313 }
314 return matchlen; // ����ʾ���פ��ʤ��Τǡ���Ĺ���פ��֤�
315 }
316
list(int i,long base)317 long StaticPtrTry::list(int i, long base) {
318 long l;
319 l = *(long*)(offset(_pList + i, base));
320 return l;
321 }
322
next(int i,long base)323 StaticPtrTry* StaticPtrTry::next(int i, long base) {
324 StaticPtrTry* p;
325 p = *(StaticPtrTry**)(offset(_pNext + i, base));
326 p = (StaticPtrTry*)(offset(p, base));
327 return p;
328 }
329
copy(ObjVect<long> & to,long base)330 int StaticPtrTry::copy(ObjVect<long>& to, long base) {
331 to.Clear();
332 for (int i = 0; i < _nList; i++) {
333 to.Add(list(i, base));
334 }
335 return _nList;
336 }
337
338 /* key ��õ��������������С������뤫�ʤ������֤� */
hasMember(char * key,long base)339 int StaticPtrTry::hasMember(char* key, long base)
340 {
341 int matchlen = 0;
342 int i;
343 StaticPtrTry* node;
344 if (! *key) {
345 return -1;
346 }
347 if (_nNext == 0) {
348 // ����ʾ���פ���ꥹ�Ȥ�¸�ߤ��ʤ�
349 return 0;
350 }
351 int count = _nNext;
352 ObjVect<long> list;
353 StaticPtrTry** pp;
354 for (int i = 0; i < count; i++) {
355 node = this->next(i, base);
356 if (node->_letter == *key) {
357 key++;
358 return node->hasMember(key, base);
359 }
360 }
361 return 0;
362 }
363
364