tests fixes
[tedtools.git] / sfxstr.c
1 /*
2  * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *      notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *      notice, this list of conditions and the following disclaimer in the
12  *      documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the author nor the names of any co-contributors
14  *      may be used to endorse or promote products derived from this software
15  *      without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
18  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #include <string.h>
31
32 #include "tlog.h"
33 #include "tmalloc.h"
34 #include "sfxstr.h"
35
36 #define EN_VAL  0x01
37 #define EN_CHLD 0x02
38 #define EN_DATA 0x04
39
40 static SFSNode* enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd);
41 static SFSNode* addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level);
42
43 #define STRNCMP(p1,p2,n) ( ((n)==1) ? ( *((char*)(p1))==*((char*)(p2)) ) : (strncmp((char*)(p1), (char*)(p2), (n))==0) )
44
45 SFSTree* 
46 SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in) {
47         if ( datasize % sizeof(u_int32_t) )
48                 tlog(TL_ALARM|TL_EXIT,"SFSInit_dp: datasize(%d) should be divided by sizeof(u_int32_t)", datasize);
49  
50         if (!info) 
51                 info=(SFSTree*)tmalloc(sizeof(SFSTree));
52         memset(info,0,sizeof(SFSTree));
53
54         info->datasize = datasize;
55
56         while(in && in->key) {
57                 SFSAdd(info, in);
58                 in++;
59         }
60
61         return info;    
62 }
63
64 SFSTree* 
65 SFSInit_c(SFSTree *info, char **in) {
66         char **ptr=in;
67         SFSDataIO  d;
68
69         if (!info) 
70                 info=(SFSTree*)tmalloc(sizeof(SFSTree));
71         memset(info,0,sizeof(SFSTree));
72
73         while(ptr && *ptr) {
74                 d.key=*ptr;
75                 d.keylen=0;
76                 SFSAdd(info, &d);
77                 ptr++;
78         }
79
80         return info;
81 }
82
83 void*
84 SFSFindData(SFSTree *info, char *word) {
85         SFSNode *node = info->node;
86         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
87         u_int8_t *ptr =(u_int8_t*)word;
88
89         while( node && *ptr ) {
90                 if ( node->isskip ) {
91                         if ( STRNCMP(ptr, ((char*)node)+node->dataptr, node->nchar) ) {
92                                 ptr+=node->nchar;
93                                 if ( *ptr=='\0' && node->isword) {
94                                         return (void*) ( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0) );
95                                 } else if ( node->haschild ) {
96                                         node = *(SFSNode**)(node->data);
97                                 } else {
98                                         return NULL;
99                                 }
100                         } else
101                                 return NULL;
102                 } else {
103                         StopLow = node->data;
104                         StopHigh = StopLow + node->nchar;
105                         while (StopLow < StopHigh) {
106                                StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
107                                if ( StopMiddle->val == *ptr ) {
108                                        ptr++;
109                                        if ( *ptr=='\0' && StopMiddle->isword ) {
110                                                 return (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
111                                         } else if ( StopMiddle->haschild ) {
112                                                 node=*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child );
113                                         } else {
114                                                 return NULL;
115                                         }
116                                         break;
117                                 } else if ( StopMiddle->val < *ptr ) {
118                                         StopLow = StopMiddle + 1;
119                                 } else {
120                                         StopHigh = StopMiddle;
121                                 }
122                         }
123                         if ( StopLow >= StopHigh )
124                                 return NULL;
125                 }
126         }
127         return NULL;
128 }
129
130 static void
131 freeFSFNode(SFSTree *info, SFSNode *node, void (*freefunc)(void*)) {
132         u_int32_t i;
133  
134         if ( node->isskip ) {
135                 if (node->haschild)
136                         freeFSFNode(info, *(SFSNode**)(node->data), freefunc);
137                 if (freefunc && node->isword && info->datasize)
138                         (*freefunc)( (void*)( ((char*)(node->data))+ (node->haschild) ? sizeof(SFSNode*) : 0 ) );
139         } else {
140                 SFSNodeData *nd = node->data;
141                 char *data= ((char*)node) + node->dataptr;
142         
143                 for(i=0;i<node->nchar;i++) {
144                         if (nd->haschild)
145                                 freeFSFNode(info, *(SFSNode**)( ((char*)nd) + nd->child ), freefunc);
146                         if (freefunc && nd->isword && info->datasize) {
147                                 (*freefunc)( (void*)data );
148                                 data+=info->datasize;
149                         }
150                         nd++;
151                 }
152         }
153
154         tfree(node);
155 }
156
157 void 
158 SFSFree(SFSTree *info, void (*freefunc)(void*)) {
159         SFSNodeStack *s=info->stack;
160
161         if (info->node) freeFSFNode(info, info->node, freefunc);
162         if (info->buf) tfree(info->buf);
163         info->buf = NULL;
164         info->tlen=0;
165         info->node = NULL;
166
167         while(s) {
168                 info->stack=s->next;
169                 tfree(s);
170                 s=info->stack;
171         }
172 }
173
174 static SFSNode*
175 makeSkipNode(SFSTree *info, SFSDataIO *io, int level) {
176         u_int32_t len;
177         int size;
178         SFSNode *res;
179
180         io->key+=level;
181         io->keylen-=level;
182
183         len = (io->keylen > 255) ? 255 : io->keylen;
184         size = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize) + len;
185
186         res = (SFSNode*)tmalloc(size);
187
188         info->nnodes++;
189         info->totalen+=size;
190
191         res->isskip=1;
192         res->nchar=len;
193         res->dataptr = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize);
194         memcpy(((char*)res) + res->dataptr, io->key, len);
195
196         if ( io->keylen > 255 ) {
197                 res->haschild=1;
198                 res->isword=0;
199                 io->key = io->key+len;
200                 io->keylen = io->keylen - len;
201                 *(SFSNode**)(res->data) = makeSkipNode(info, io, 0);
202                 io->key = io->key-len;
203                 io->keylen = io->keylen + len;
204         } else {
205                 res->haschild=0;
206                 res->isword=1;
207                 if (info->datasize) {
208                         memcpy( res->data, io->data, info->datasize );
209                 }
210         }
211
212         io->key-=level;
213         io->keylen+=level;
214
215         return res;
216 }
217
218 static SFSNode*
219 splitSkipNode(SFSTree *info, SFSNode* node, SFSDataIO *io, int level) {
220         SFSNode *res;
221         int prefixlen=0;
222         char *s1,*s2;
223         SFSNodeData     *ndata;
224
225         tassert(node->isskip);
226         io->key+=level;
227         io->keylen-=level;
228
229         s1=((char*)node) + node->dataptr;
230         s2=io->key;
231
232         while( s1 - (((char*)node) + node->dataptr) < node->nchar && s2 - io->key < io->keylen && *s1==*s2) {
233                 s1++;
234                 s2++;
235         }
236
237         prefixlen = s2 - io->key;
238
239         if ( prefixlen==0 ) {
240                 if ( node->nchar == 1 ) {
241                         int flag = EN_VAL | ((node->isword) ? EN_DATA : 0) | ((node->haschild) ? EN_CHLD : 0);
242                         res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), flag, &ndata);
243                         if ( node->isword ) {
244                                 if ( info->datasize ) 
245                                         memcpy(
246                                                 ((char*)res) + res->dataptr + info->datasize * ndata->data,
247                                                 ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0),
248                                                 info->datasize
249                                         );
250                         }
251                         if ( node->haschild ) 
252                                 *(SFSNode**)( ((char*)ndata) + ndata->child ) = *(SFSNode**)( node->data );
253                         info->totalen -= SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
254                                 ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar;
255                         info->nnodes--;
256                         tfree(node);
257                 } else {
258                         res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), EN_VAL|EN_CHLD, &ndata);
259                         node->nchar--;
260                         memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + 1, node->nchar);
261                         info->totalen--;
262                         *(SFSNode**)( ((char*)ndata) + ndata->child ) = (SFSNode*)trealloc(node,
263                                 SFSNHRDSZ + ((node->haschild) ? sizeof(SFSNode*) : 0) + 
264                                 ((node->isword) ? info->datasize : 0 )+ node->nchar);
265                 }
266                 res = addRecord(info, res, io, 0);
267         } else if (prefixlen==io->keylen) {
268                 if (prefixlen==node->nchar) {
269                         if ( node->isword || info->datasize==0) {
270                                 if (info->datasize)
271                                         memcpy( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNodeData*) : 0),
272                                                 io->data,
273                                                 info->datasize);
274                                 node->isword=1;
275                                 res=node;
276                         } else {
277                                 int size = SFSNHRDSZ + info->datasize + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar;
278
279                                 info->totalen+=info->datasize;
280                                 res=(SFSNode*)trealloc(node,size);
281                                 res->dataptr=SFSNHRDSZ + info->datasize + ((res->haschild) ? sizeof(SFSNodeData*) : 0);
282                                 res->isword=1;
283                                 memmove(((char*)res) + res->dataptr,
284                                         ((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), res->nchar);
285                                 memcpy(((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), io->data, info->datasize);
286                         }
287                 } else {
288                         int size = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*) + prefixlen;
289                         info->totalen+=size;
290                         info->nnodes++;
291                         res = (SFSNode*)tmalloc(size);
292                         res->isskip=1;
293                         res->isword=1;
294                         res->haschild=1;
295                         res->nchar = prefixlen;
296                         res->dataptr = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*);
297                         memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
298                         if (info->datasize)
299                                 memcpy(((char*)(res->data)) + sizeof(SFSNodeData*), io->data, info->datasize);
300                         node->nchar-=prefixlen;
301                         memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
302                         info->totalen-=prefixlen;
303                         *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
304                                 ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
305                 }
306         } else if ( prefixlen==node->nchar ) {
307                 int size = SFSNHRDSZ + info->datasize +  sizeof(SFSNode*) + node->nchar;
308                 info->totalen+=sizeof(SFSNode*);
309                 res=(SFSNode*)trealloc(node,size);
310                 memmove( ((char*)(res->data)) + sizeof(SFSNode*), res->data, info->datasize + res->nchar);
311                 res->haschild=1;
312                 res->dataptr+=sizeof(SFSNode*);
313                 *(SFSNode**)(res->data) = makeSkipNode(info, io, prefixlen); 
314         } else { 
315                 int size = SFSNHRDSZ + sizeof(SFSNodeData*) + prefixlen;
316                 info->totalen+=size;
317                 info->nnodes++;
318                 res = (SFSNode*)tmalloc(size);
319                 res->isskip=1;
320                 res->isword=0;
321                 res->haschild=1;
322                 res->nchar = prefixlen;
323                 res->dataptr = SFSNHRDSZ + sizeof(SFSNodeData*);
324                 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
325
326                 node->nchar-=prefixlen;
327                 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
328                 info->totalen-=prefixlen;
329
330                 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, 
331                         SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
332                                 ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar
333                 );
334                 *(SFSNode**)(res->data) = splitSkipNode(info, *(SFSNode**)(res->data), io, prefixlen); 
335
336         }
337
338         io->key-=level;
339         io->keylen+=level;
340         return res;
341 }
342
343
344 static SFSNode*
345 enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd) {
346         u_int32_t nchild=0, nchar=0, nfound=0, i;
347         SFSNode *rs,**chld;
348         SFSNodeData *data;
349         int sizenode;
350         char *dataptr;
351
352
353         if ( node ) {
354                 nchar=node->nchar;
355                 nchild=node->nchild;
356                 data=node->data;
357
358                 for(i=0;i<nchar;i++) {
359                         nfound += data->isword;
360                         data++;
361                 }
362         }
363
364         if ( node )
365                 info->totalen -= SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
366
367         if ( flag & EN_VAL )   nchar++; 
368         if ( flag & EN_CHLD ) nchild++; 
369         if ( flag & EN_DATA )  nfound++;        
370
371
372         sizenode = SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
373
374         info->totalen+=sizenode;
375         if ( !node ) info->nnodes++;
376         rs=(SFSNode*)tmalloc(sizenode);
377
378         rs->isskip = 0;
379         rs->nchar = nchar;
380         rs->nchild = nchild;
381         rs->dataptr=SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*);
382         dataptr=((char*)rs) + rs->dataptr;
383         chld = (SFSNode**)( ((char*)rs)+SFSNHRDSZ+nchar*sizeof(SFSNodeData) );
384         data=rs->data;
385
386         if (node) {
387                 SFSNode **ochld=(SFSNode**)( ((char*)node)+SFSNHRDSZ+node->nchar*sizeof(SFSNodeData) );
388                 SFSNodeData *odata = node->data;
389                 char *odataptr=((char*)node) + node->dataptr;
390                 int wasins=0;
391
392                 for(i=0;i<node->nchar;i++) {
393                         if ( val > odata->val ) {
394                                 *(u_int32_t*)data = *(u_int32_t*)odata;
395                                 if ( odata->haschild ) {
396                                         *chld=*ochld;
397                                         data->child = ((char*)chld) - ((char*)data);
398                                         chld++; ochld++;
399                                 }
400                                 if ( odata->isword && info->datasize ) {
401                                         memcpy(dataptr, odataptr, info->datasize);
402                                         data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
403                                         dataptr += info->datasize; odataptr += info->datasize;
404                                 }
405                                 data++; odata++; 
406                         } else if ( val == odata->val ) {
407                                 tassert ( (flag&EN_VAL)==0 );
408                                 *(u_int32_t*)data = *(u_int32_t*)odata;
409                                 wasins=1;
410                                 if ( odata->haschild || flag & EN_CHLD ) {
411                                         if (odata->haschild) *chld=*ochld;
412                                         data->child = ((char*)chld) - ((char*)data);
413                                         data->haschild=1;
414                                         chld++; if (odata->haschild) ochld++;
415                                 } else
416                                         data->haschild=0;
417                                 if ( odata->isword || flag & EN_DATA ) {
418                                         data->isword=1;
419                                         if ( info->datasize && odata->isword ) {
420                                                 memcpy(dataptr, odataptr, info->datasize);
421                                                 odataptr += info->datasize;
422                                         }
423                                         data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
424                                         dataptr += info->datasize;
425                                 } else
426                                         data->isword=0;
427                                 *nd = data;
428                                 data++; odata++; 
429                         } else {
430                                 if ( wasins==0 ) {
431                                         tassert ( flag&EN_VAL );
432                                         data->val = val;
433                                         if ( flag & EN_CHLD ) {
434                                                 data->haschild=1;
435                                                 data->child = ((char*)chld) - ((char*)data);
436                                                 chld++;
437                                         } else
438                                                 data->haschild=0;
439                                         if ( flag & EN_DATA ) {
440                                                 data->isword=1;
441                                                 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
442                                                 dataptr += info->datasize;
443                                         } else
444                                                 data->isword=0;
445                                         *nd = data;
446                                         data++;
447                                         wasins=1;
448                                         i--;
449                                 } else {
450                                         *(u_int32_t*)data = *(u_int32_t*)odata;
451                                         if ( odata->haschild ) {
452                                                 *chld=*ochld;
453                                                 data->child = ((char*)chld) - ((char*)data);
454                                                 chld++; ochld++;
455                                         }
456                                         if ( odata->isword && info->datasize ) {
457                                                 memcpy(dataptr, odataptr, info->datasize);
458                                                 data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
459                                                 dataptr += info->datasize; odataptr += info->datasize;
460                                         }
461                                         data++; odata++; 
462                                 }
463                         } 
464                 }
465                 if ( wasins==0 ) {
466                         tassert ( flag&EN_VAL );
467                         data->val = val;
468                         if ( flag & EN_CHLD ) {
469                                 data->haschild=1;
470                                 data->child = ((char*)chld) - ((char*)data);
471                                 chld++;
472                         } else
473                                 data->haschild=0;
474                         if ( flag & EN_DATA ) {
475                                 data->isword=1;
476                                 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
477                                 dataptr += info->datasize;
478                         } else 
479                                 data->isword=0;
480                         *nd = data;
481                 }
482         } else {
483                 tassert ( flag & EN_VAL );
484                 data->val = val;
485                 if ( flag & EN_CHLD ) {
486                         data->haschild=1;
487                         data->child = ((char*)chld) - ((char*)data);
488                 } else
489                         data->haschild=0;
490                 if ( flag & EN_DATA ) {
491                         data->isword=1;
492                         data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
493                 } else
494                         data->isword=0;
495                 *nd = data;
496         }
497         if (node) tfree(node);
498         return rs;
499 }
500
501 static SFSNode*
502 addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level) {
503         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
504         u_int8_t *ptr = ((u_int8_t*)in->key) + level;
505
506
507         if ( node ) {
508                 if ( node->isskip ) {
509                         if ( node->haschild && in->keylen-level > node->nchar && 
510                                         strncmp(in->key+level, ((char*)node)+node->dataptr, node->nchar)==0 ) 
511                                 *(SFSNode**)( node->data ) = addRecord(info, *(SFSNode**)( node->data ), in, level+node->nchar); 
512                         else 
513                                 node = splitSkipNode(info, node, in, level); 
514                 } else {
515                         StopLow = node->data;   
516                         StopHigh = StopLow + node->nchar;
517                         while (StopLow < StopHigh) {
518                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
519                                 if ( StopMiddle->val == *ptr ) {
520                                         if ( *(ptr+1)=='\0' ) {
521                                                 if ( StopMiddle->isword ) {
522                                                         /* already exists */
523                                                         if ( info->datasize ) 
524                                                                 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
525                                                                         in->data, info->datasize );
526                                                 } else {
527                                                         /* not exist word */
528                                                         if (info->datasize) {
529                                                                 node = enlargeNode(info, node, *ptr, EN_DATA, &StopMiddle);
530                                                                 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
531                                                                         in->data, info->datasize );
532                                                         }
533                                                         StopMiddle->isword = 1;
534                                                 }
535                                         } else if ( StopMiddle->haschild ) {
536                                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) = 
537                                                         addRecord(info, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), in, level+1);
538                                         } else {
539                                                 node = enlargeNode(info, node, *ptr, EN_CHLD, &StopMiddle);
540                                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
541                                                         makeSkipNode(info, in, level+1);
542                                         }
543                                         return node;
544                                 } else if ( StopMiddle->val < *ptr ) {
545                                         StopLow = StopMiddle + 1;
546                                 } else {
547                                         StopHigh = StopMiddle;
548                                 }
549                         }
550                         if ( *(ptr+1)=='\0' ) {
551                                 node = enlargeNode(info, node, *ptr, EN_VAL|EN_DATA, &StopMiddle);
552                                 if ( info->datasize )
553                                         memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
554                                         in->data, info->datasize );
555                         } else {
556                                 node = enlargeNode(info, node, *ptr, EN_VAL|EN_CHLD, &StopMiddle);
557                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) = 
558                                         makeSkipNode(info, in, level+1);
559                         }
560                 }
561         } else 
562                 node = makeSkipNode(info, in, level); 
563
564
565         return node;
566
567 }
568
569 void
570 SFSAdd(SFSTree *info, SFSDataIO *in) {
571         if (in->keylen<=0)
572                 in->keylen=strlen(in->key);
573         info->node = addRecord(info, info->node, in, 0);
574 }
575
576 static SFSNodeStack*
577 pushStack(SFSNodeStack *top, SFSNode *node, int level ) {
578         SFSNodeStack *r=(SFSNodeStack*)tmalloc(sizeof(SFSNodeStack));
579
580         r->next = top;
581         r->node=node;
582         r->data=node->data;
583         r->level=level;
584         r->checkedchild = 0;
585         r->checkedval = 0;
586
587         return r;
588 }
589
590 void 
591 SFSIteratorStart(SFSTree *info) {
592         if ( !info->buf ) {
593                 info->tlen = 32;
594                 info->buf = (char*)tmalloc(info->tlen);
595         } 
596         info->stack = pushStack(NULL, info->node, 0);
597         info->hasword=0; 
598 }
599
600 void
601 SFSPrefixIteratorStart(SFSTree *info, char *word) {
602         SFSNode *node = info->node;
603         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
604         u_int8_t *ptr =(u_int8_t*)word;
605         int len,wlen=strlen(word);
606
607         if ( wlen+1>=info->tlen ) {
608                 info->tlen = 2*wlen;
609                 info->buf = (info->buf) ?
610                                 (char*)trealloc(info->buf,info->tlen)
611                         :
612                                 (char*)tmalloc(info->tlen);
613         }
614
615         info->hasword=0;
616         while( node && *ptr) {
617                 len = wlen - (((char*)ptr)-word);
618                 if ( node->isskip ) {
619                         if ( STRNCMP(ptr, ((char*)node)+node->dataptr, (len<node->nchar) ? len : node->nchar) ) {
620                                 if ( len<=node->nchar ) {
621                                         strcpy(info->buf,word);
622                                         info->stack = pushStack(NULL, node, ((char*)ptr) - word);
623                                         return;
624                                 } else if ( node->haschild ) {
625                                         ptr+=node->nchar;
626                                         node = *(SFSNode**)(node->data);
627                                 } else {
628                                         return;
629                                 }
630                         } else
631                                 return;
632                 } else {
633                         StopLow = node->data;
634                         StopHigh = StopLow + node->nchar;
635                         while (StopLow < StopHigh) {
636                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
637                                 if ( StopMiddle->val == *ptr ) {
638                                         if ( *(ptr+1)=='\0' ) {
639                                                 len =((char*)ptr)-word+1;
640                                                 strcpy(info->buf,word);
641                                                 if ( StopMiddle->isword ) {
642                                                         info->hasword=1;
643                                                         info->wdata = (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
644                                                 }
645                                                 if ( StopMiddle->haschild )
646                                                         info->stack = pushStack(NULL, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), len);
647                                                 return;
648                                         } else if ( StopMiddle->haschild ) {
649                                                 node=*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child );
650                                         } else {
651                                                 return;
652                                         }
653                                         ptr++;
654                                         break;
655                                 } else if ( StopMiddle->val < *ptr ) {
656                                         StopLow = StopMiddle + 1;
657                                 } else {
658                                         StopHigh = StopMiddle;
659                                 }
660                         }
661                         if ( StopLow >= StopHigh )
662                                 break;
663                 }
664         }
665         return;
666 }
667
668 int
669 SFSIterate(SFSTree *info, SFSDataIO *out) {
670         SFSNodeStack *s=info->stack;
671
672         if ( info->hasword ) {
673                 out->key = info->buf;
674                 out->keylen = strlen(out->key);
675                 out->data = info->wdata;
676                 info->hasword = 0;
677                 return 1;
678         }
679
680         if ( s == NULL || s->node == NULL)
681                 return 0;
682                                                          
683         while ( s->level + s->node->nchar + 1 >= info->tlen ) {
684                 info->tlen *= 2;
685                 info->buf = (char*)trealloc(info->buf, info->tlen);
686         }
687
688         if ( s->node->isskip ) {
689                 memcpy( info->buf + s->level, ((char*)s->node) + s->node->dataptr, s->node->nchar );
690                 if ( s->node->isword && !s->checkedval) {
691                         info->buf[ s->level+s->node->nchar ] = '\0';
692                         out->key = info->buf;
693                         out->keylen = s->level+s->node->nchar;
694                         out->data =((char*)(s->node->data)) + ((s->node->haschild) ? sizeof(SFSNode*) : 0);
695                         s->checkedval=1;
696                         return 1;
697                 }
698                 if ( s->node->haschild && !s->checkedchild) {
699                         info->stack = pushStack(s, *(SFSNode**)( (char*)(s->node->data) ), s->level+s->node->nchar);
700                         s->checkedchild=1;
701                         if ( SFSIterate(info, out) )
702                                 return 1;
703                 }
704         } else {
705                 while( s->data - s->node->data < s->node->nchar ) {
706                         info->buf[ s->level ] = (char)s->data->val;
707                         if ( s->checkedval==0 && s->data->isword ) {
708                                 info->buf[ s->level+1 ] = '\0';  
709                                 out->key = info->buf;
710                                 out->keylen = s->level+1;
711                                 out->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
712                                 s->checkedval = 1;
713                                 return 1;
714                         }
715                         if ( s->checkedchild==0 && s->data->haschild ) {
716                                 info->stack = pushStack(s, *(SFSNode**)( ((char*)s->data) + s->data->child ), s->level+1);
717                                 s->checkedchild=1;
718                                 if ( SFSIterate(info, out) )
719                                         return 1;
720                         }
721                         s->checkedval = s->checkedchild = 0;
722                         s->data++;
723                 }
724         }
725         info->stack = s->next;
726         tfree(s);
727
728         return SFSIterate(info, out);
729 }
730
731 int
732 SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l) {
733         SFSNodeStack *s=info->stack;
734
735         SFSPrefixIteratorStart(info, word);
736         s=info->stack;
737
738         if ( SFSIterate(info, f) ) {
739                 SFSNodeStack *sptr = info->stack, *stmp;
740                 while( sptr && sptr!=s ) {
741                         stmp=sptr->next;
742                         tfree(sptr);
743                         sptr=stmp;
744                 }
745          
746                 if ( s == NULL ) {
747                         memcpy(l,f,sizeof(SFSDataIO));
748                         return 1;
749                 }
750         } else
751                 return 0;
752                                                          
753         info->stack=NULL;
754
755         while( f->keylen +  s->level + 2 >= info->tlen ) {
756                 info->tlen *= 2;
757                 info->buf = (char*)trealloc(info->buf, info->tlen);
758         }
759
760         f->key = info->buf;
761         l->key = info->buf + f->keylen + 1;
762         memcpy(l->key, f->key, f->keylen + 1);
763                         
764         while(s->node) {
765                 while( f->keylen + 1 + s->level + s->node->nchar + 1 >= info->tlen ) {
766                         info->tlen *= 2;
767                         info->buf = (char*)trealloc(info->buf, info->tlen);
768                 }
769                 if ( s->node->isskip ) {
770                         memcpy(info->buf + f->keylen + 1 + s->level,
771                                 ((char*)(s->node))+s->node->dataptr, s->node->nchar);
772                         s->level+=s->node->nchar;
773                         if (s->node->haschild) {
774                                 s->node=*(SFSNode**)( s->node->data );  
775                         } else { /* if (s->node->isword) */
776                                 info->buf[ f->keylen + 1 + s->level  ] = '\0';
777                                 l->data = (void*)(s->node->data);
778                                 l->keylen = s->level+1;
779                                 break;
780                         }
781                 } else {
782                         s->data = s->node->data + s->node->nchar - 1;
783                         while( s->data - s->node->data >= 0 ) {
784                                 info->buf[ f->keylen + 1 + s->level ] = (char)s->data->val;
785                                 if ( s->data->haschild ) {
786                                         s->node = *(SFSNode**)( ((char*)s->data) + s->data->child );
787                                         s->level++;
788                                         break;
789                                 }
790                                 if ( s->data->isword ) {
791                                         info->buf[ f->keylen + 1 + s->level ] = '\0';
792                                         l->keylen = s->level+1;
793                                         l->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
794                                         s->node=NULL;
795                                         break;
796                                 }
797                                 s->data--;
798                         }
799                 }
800         }               
801         f->key = info->buf;
802         l->key = info->buf + f->keylen + 1;
803         tfree(s); 
804
805         return 1;
806 }