1 /* vim:set ts=8 sts=4 sw=4 tw=0: */
2 /*
3 * mnode.c - mnode interfaces.
4 *
5 * Written By: MURAOKA Taro <koron@tka.att.ne.jp>
6 * Last Change: 04-May-2004.
7 */
8
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #include <ctype.h>
13
14 #include "dbg.h"
15 #include "wordlist.h"
16 #include "wordbuf.h"
17 #include "mnode.h"
18
19 #define MTREE_MNODE_N 1024
20 struct _mtree_t
21 {
22 mtree_p active;
23 int used;
24 mnode nodes[MTREE_MNODE_N];
25 mtree_p next;
26 };
27
28 #define MNODE_BUFSIZE 16384
29
30 #if defined(_MSC_VER) || defined(__GNUC__)
31 # define INLINE __inline
32 #else
33 # define INLINE
34 #endif
35
36 int n_mnode_new = 0;
37 int n_mnode_delete = 0;
38
39 INLINE static mnode*
mnode_new(mtree_p mtree)40 mnode_new(mtree_p mtree)
41 {
42 mtree_p active = mtree->active;
43
44 if (active->used >= MTREE_MNODE_N)
45 {
46 active->next = (mtree_p)calloc(1, sizeof(*active->next));
47 /* TODO: �G���[���� */
48 mtree->active = active->next;
49 active = active->next;
50 }
51 ++n_mnode_new;
52 return &active->nodes[active->used++];
53 }
54
55 static void
mnode_delete(mnode * p)56 mnode_delete(mnode* p)
57 {
58 while (p)
59 {
60 mnode* child = p->child;
61
62 if (p->list)
63 wordlist_close(p->list);
64 if (p->next)
65 mnode_delete(p->next);
66 /*free(p);*/
67 p = child;
68 ++n_mnode_delete;
69 }
70 }
71
72
73 void
mnode_print_stub(mnode * vp,unsigned char * p)74 mnode_print_stub(mnode* vp, unsigned char* p)
75 {
76 static unsigned char buf [256];
77
78 if (!vp)
79 return;
80 if (!p)
81 p = &buf[0];
82 p[0] = MNODE_GET_CH(vp);
83 p[1] = '\0';
84 if (vp->list)
85 printf("%s (list=%p)\n", buf, vp->list);
86 if (vp->child)
87 mnode_print_stub(vp->child, p + 1);
88 if (vp->next)
89 mnode_print_stub(vp->next, p);
90 }
91
92 void
mnode_print(mtree_p mtree,unsigned char * p)93 mnode_print(mtree_p mtree, unsigned char* p)
94 {
95 if (mtree && mtree->used > 0)
96 mnode_print_stub(&mtree->nodes[0], p);
97 }
98
99 void
mnode_close(mtree_p mtree)100 mnode_close(mtree_p mtree)
101 {
102 if (mtree)
103 {
104 mtree_p next;
105
106 if (mtree->used > 0)
107 mnode_delete(&mtree->nodes[0]);
108
109 while (mtree)
110 {
111 next = mtree->next;
112 free(mtree);
113 mtree = next;
114 }
115 }
116 }
117
118 INLINE static mnode*
search_or_new_mnode(mtree_p mtree,wordbuf_p buf)119 search_or_new_mnode(mtree_p mtree, wordbuf_p buf)
120 {
121 /* ���x���P�ꂪ���肵���猟���ɒlj� */
122 int ch;
123 unsigned char *word;
124 mnode **ppnext;
125 mnode **res = NULL; /* To suppress warning for GCC */
126 mnode *root;
127
128 word = WORDBUF_GET(buf);
129 root = mtree->used > 0 ? &mtree->nodes[0] : NULL;
130 ppnext = &root;
131 while ((ch = *word) != 0)
132 {
133 res = ppnext;
134 if (! *res)
135 {
136 *res = mnode_new(mtree);
137 MNODE_SET_CH(*res, ch);
138 }
139 else if (MNODE_GET_CH(*res) != ch)
140 {
141 ppnext = &(*res)->next;
142 continue;
143 }
144 ppnext = &(*res)->child;
145 ++word;
146 }
147
148 _ASSERT(*res != NULL);
149 return *res;
150 }
151
152 /*
153 * �����̃m�[�h�Ƀt�@�C������f�[�^���܂Ƃ߂Ēlj�����B
154 */
155 mtree_p
mnode_load(mtree_p mtree,FILE * fp)156 mnode_load(mtree_p mtree, FILE* fp)
157 {
158 mnode *pp = NULL;
159 int mode = 0;
160 int ch;
161 wordbuf_p buf;
162 wordbuf_p prevlabel;
163 wordlist_p *ppword = NULL; /* To suppress warning for GCC */
164 /* �ǂݍ��݃o�b�t�@�p�ϐ� */
165 unsigned char cache[MNODE_BUFSIZE];
166 unsigned char *cache_ptr = cache;
167 unsigned char *cache_tail = cache;
168
169 buf = wordbuf_open();
170 prevlabel = wordbuf_open();
171 if (!fp || !buf || !prevlabel)
172 {
173 goto END_MNODE_LOAD;
174 }
175
176 /*
177 * EOF�̏������B���B�s���Ȍ`���̃t�@�C�����������ꍇ���l�����Ă��Ȃ��B�e
178 * ���[�h����EOF�̓���p�ӂ��Ȃ��Ɛ������Ȃ����c�ʓ|�Ȃ̂ł��Ȃ��B�f�[
179 * �^�t�@�C���͐�ɊԈ���Ă��Ȃ��Ƃ����O���u���B
180 */
181 do
182 {
183 if (cache_ptr >= cache_tail)
184 {
185 cache_ptr = cache;
186 cache_tail = cache + fread(cache, 1, MNODE_BUFSIZE, fp);
187 ch = (cache_tail <= cache && feof(fp)) ? EOF : *cache_ptr;
188 }
189 else
190 ch = *cache_ptr;
191 ++cache_ptr;
192
193 /* ���:mode�̃I�[�g�}�g�� */
194 switch (mode)
195 {
196 case 0: /* ���x���P�ꌟ�����[�h */
197 /* ���̓��x���P��ɂȂ肦�܂��� */
198 if (isspace(ch) || ch == EOF)
199 continue;
200 /* �R�����g���C���`�F�b�N */
201 else if (ch == ';')
202 {
203 mode = 2; /* �s���܂ŐH���ׂ����[�h �ֈڍs */
204 continue;
205 }
206 else
207 {
208 mode = 1; /* ���x���P��̓Ǎ����[�h �ֈڍs*/
209 wordbuf_reset(buf);
210 wordbuf_add(buf, (unsigned char)ch);
211 }
212 break;
213
214 case 1: /* ���x���P��̓Ǎ����[�h */
215 /* ���x���̏I�������o */
216 switch (ch)
217 {
218 default:
219 wordbuf_add(buf, (unsigned char)ch);
220 break;
221 case '\t':
222 pp = search_or_new_mnode(mtree, buf);
223 wordbuf_reset(buf);
224 mode = 3; /* �P��O���ǔ�����[�h �ֈڍs */
225 break;
226 }
227 break;
228
229 case 2: /* �s���܂ŐH���ׂ����[�h */
230 if (ch == '\n')
231 {
232 wordbuf_reset(buf);
233 mode = 0; /* ���x���P�ꌟ�����[�h �֖߂� */
234 }
235 break;
236
237 case 3: /* �P��O���ǂݔ�����[�h */
238 if (ch == '\n')
239 {
240 wordbuf_reset(buf);
241 mode = 0; /* ���x���P�ꌟ�����[�h �֖߂� */
242 }
243 else if (ch != '\t')
244 {
245 /* �P��o�b�t�@���Z�b�g */
246 wordbuf_reset(buf);
247 wordbuf_add(buf, (unsigned char)ch);
248 /* �P�ꃊ�X�g�̍Ō������(���ꃉ�x����������) */
249 ppword = &pp->list;
250 while (*ppword)
251 ppword = &(*ppword)->next;
252 mode = 4; /* �P��̓ǂݍ��݃��[�h �ֈڍs */
253 }
254 break;
255
256 case 4: /* �P��̓ǂݍ��݃��[�h */
257 switch (ch)
258 {
259 case '\t':
260 case '\n':
261 /* �P����L�� */
262 *ppword = wordlist_open_len(WORDBUF_GET(buf),
263 WORDBUF_LEN(buf));
264 wordbuf_reset(buf);
265
266 if (ch == '\t')
267 {
268 ppword = &(*ppword)->next;
269 mode = 3; /* �P��O���ǂݔ�����[�h �֖߂� */
270 }
271 else
272 {
273 ppword = NULL;
274 mode = 0; /* ���x���P�ꌟ�����[�h �֖߂� */
275 }
276 break;
277 default:
278 wordbuf_add(buf, (unsigned char)ch);
279 break;
280 }
281 break;
282 }
283 }
284 while (ch != EOF);
285
286 END_MNODE_LOAD:
287 wordbuf_close(buf);
288 wordbuf_close(prevlabel);
289 return mtree;
290 }
291
292 mtree_p
mnode_open(FILE * fp)293 mnode_open(FILE* fp)
294 {
295 mtree_p mtree;
296
297 mtree = (mtree_p)calloc(1, sizeof(*mtree));
298 mtree->active = mtree;
299 if (mtree && fp)
300 mnode_load(mtree, fp);
301
302 return mtree;
303 }
304
305 #if 0
306 static int
307 mnode_size(mnode* p)
308 {
309 return p ? mnode_size(p->child) + mnode_size(p->next) + 1 : 0;
310 }
311 #endif
312
313 static mnode*
mnode_query_stub(mnode * node,const unsigned char * query)314 mnode_query_stub(mnode* node, const unsigned char* query)
315 {
316 while (1)
317 {
318 if (*query == MNODE_GET_CH(node))
319 return (*++query == '\0') ? node :
320 (node->child ? mnode_query_stub(node->child, query) : NULL);
321 if (!(node = node->next))
322 break;
323 }
324 return NULL;
325 }
326
327 mnode*
mnode_query(mtree_p mtree,const unsigned char * query)328 mnode_query(mtree_p mtree, const unsigned char* query)
329 {
330 return (query && *query != '\0' && mtree)
331 ? mnode_query_stub(&mtree->nodes[0], query) : 0;
332 }
333
334 static void
mnode_traverse_stub(mnode * node,MNODE_TRAVERSE_PROC proc,void * data)335 mnode_traverse_stub(mnode* node, MNODE_TRAVERSE_PROC proc, void* data)
336 {
337 while (1)
338 {
339 if (node->child)
340 mnode_traverse_stub(node->child, proc, data);
341 proc(node, data);
342 if (!(node = node->next))
343 break;
344 }
345 }
346
347 void
mnode_traverse(mnode * node,MNODE_TRAVERSE_PROC proc,void * data)348 mnode_traverse(mnode *node, MNODE_TRAVERSE_PROC proc, void* data)
349 {
350 if (node && proc)
351 {
352 proc(node, data);
353 if (node->child)
354 mnode_traverse_stub(node->child, proc, data);
355 }
356 }
357