Fix memory leaks and mistypes
[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 <errno.h>
31 #include <string.h>
32 #include <stdint.h>
33 #include <sys/types.h>
34 #include <sys/file.h>
35 #include <sys/uio.h>
36 #include <unistd.h>
37 #include <fcntl.h>
38
39 #include "tlog.h"
40 #include "tmalloc.h"
41 #include "sfxstr.h"
42 #include "tools.h"
43
44 #define EN_VAL  0x01
45 #define EN_CHLD 0x02
46 #define EN_DATA 0x04
47
48 #define SFSTREE_VERSION         0x0100
49
50 typedef uintptr_t Opaque;  /* XXX sizeof(Opaque) == sizeof(void *) */
51
52 #define CHECK_MEMORY(tree)      ( ( (tree)->plainmemory ) ? \
53         tlog(TL_CRIT|TL_EXIT, "Tree in plain memory - read only access") : (void)0 ) 
54
55 static __inline__ int
56 getNodeSize(SFSTree *info, SFSNode *node) {
57         int size =      SFSNHRDSZ;
58
59         if ( node->isskip ) {
60                 if ( node->isword )
61                         size += info->datasize;
62                 if ( node->haschild )
63                         size += sizeof(SFSNode*);
64                 size += node->nchar;
65         } else {
66                 u_int32_t       i;
67                 u_int32_t       nfound = 0;
68                 SFSNodeData *data = node->data;
69
70                 size += sizeof(SFSNodeData) * node->nchar;
71                 size += sizeof(SFSNode*) * node->nchild;
72
73                 for(i=0;i<node->nchar;i++) 
74                         nfound += data[i].isword;
75
76                 size += nfound*info->datasize;
77         }
78
79         return PTRALIGN(size);
80 }
81
82 static __inline__ SFSNode*
83 getChildPointer(SFSTree *info, SFSNodeData *nodedata) {
84         char *p = ((char*)nodedata) + nodedata->child; 
85
86         if ( info->plainmemory ) 
87                 return (SFSNode*) ( ((char*)(info->node)) + *(Opaque*)p );
88
89         return *(SFSNode**)p;
90 }
91
92 static __inline__ SFSNode*
93 getSkipChildPointer(SFSTree *info, SFSNode *node) {
94         if ( info->plainmemory )
95                 return (SFSNode*) ( ((char*)(info->node)) + *(Opaque*)node->data );
96
97         return *(SFSNode**)( (char*)(node->data) );
98 }
99
100 static SFSNode* enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd);
101 static SFSNode* addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level);
102
103 #define STRNCMP(p1,p2,n) ( ((n)==1) ? ( *((char*)(p1))==*((char*)(p2)) ) : (strncmp((char*)(p1), (char*)(p2), (n))==0) )
104
105 SFSTree* 
106 SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in) {
107         if ( datasize % sizeof(u_int32_t) )
108                 tlog(TL_ALARM|TL_EXIT,"SFSInit_dp: datasize(%d) should be divided by sizeof(u_int32_t)", datasize);
109  
110         if (!info) 
111                 info=(SFSTree*)tmalloc(sizeof(SFSTree));
112         memset(info,0,sizeof(SFSTree));
113
114         info->datasize = datasize;
115
116         while(in && in->key) {
117                 SFSAdd(info, in);
118                 in++;
119         }
120
121         return info;    
122 }
123
124 SFSTree* 
125 SFSInit_c(SFSTree *info, char **in) {
126         char **ptr=in;
127         SFSDataIO  d;
128
129         if (!info) 
130                 info=(SFSTree*)tmalloc(sizeof(SFSTree));
131         memset(info,0,sizeof(SFSTree));
132
133         while(ptr && *ptr) {
134                 d.key=*ptr;
135                 d.keylen=0;
136                 SFSAdd(info, &d);
137                 ptr++;
138         }
139
140         return info;
141 }
142
143 #define ISEND(p,w,l)    ( (l>0) ? ( ((char*)(p))-(w) >= (l) ) : ( *(p) == '\0' ) )
144
145 void*
146 SFSFindData(SFSTree *info, char *word, int len) {
147         SFSDataIO       in;
148
149         in.key = word;
150         in.keylen = len;
151
152         return SFSFindDataFromSavedOrSave(info, &in, NULL);
153 }
154
155 void*
156 SFSFindDataOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position) {
157         if ( position )
158                 memset(position, 0, sizeof(position));
159
160         return SFSFindDataFromSavedOrSave(info, in, position); 
161 }
162
163 void*
164 SFSFindDataFromSavedOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position) {
165         SFSNode *node = info->node;
166         SFSNode **pnode = &(info->node);
167         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
168         u_int8_t *ptr =(u_int8_t*)in->key;
169
170         if ( position && position->nodeptr && position->node && in->keylen > position->level ) {
171                 node = position->node;
172                 pnode = position->nodeptr;
173                 ptr += position->level;
174         }
175
176         while( node && !ISEND(ptr, in->key, in->keylen) ) {
177                 if ( position ) {
178                         position->nodeptr = pnode;
179                         position->node = node;
180                         position->level =  ((char*)ptr) - in->key;
181                 }
182
183                 if ( node->isskip ) {
184                         if ( in->keylen>0 &&  in->keylen - (((char*)ptr) - in->key) < node->nchar )
185                                 return NULL;
186                         else if ( STRNCMP(ptr, ((char*)node)+node->dataptr, node->nchar) ) {
187                                 ptr+=node->nchar;
188                                 if ( ISEND(ptr, in->key, in->keylen) && node->isword) {
189                                         return (void*) ( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0) );
190                                 } else if ( node->haschild ) {
191                                         node = getSkipChildPointer(info, node);
192                                         pnode = (SFSNode**)( (char*)(node->data) );
193                                 } else {
194                                         return NULL;
195                                 }
196                         } else
197                                 return NULL;
198                 } else {
199                         StopLow = node->data;
200                         StopHigh = StopLow + node->nchar;
201                         while (StopLow < StopHigh) {
202                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
203                                 if ( StopMiddle->val == *ptr ) {
204                                         ptr++;
205                                         if ( ISEND(ptr, in->key, in->keylen) && StopMiddle->isword ) {
206                                                 return (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
207                                         } else if ( StopMiddle->haschild ) {
208                                                 node = getChildPointer(info, StopMiddle);
209                                                 pnode = (SFSNode**)(((char*)StopMiddle) + StopMiddle->child);
210                                         } else {
211                                                 return NULL;
212                                         }
213                                         break;
214                                 } else if ( StopMiddle->val < *ptr ) {
215                                         StopLow = StopMiddle + 1;
216                                 } else {
217                                         StopHigh = StopMiddle;
218                                 }
219                         }
220                         if ( StopLow >= StopHigh )
221                                 return NULL;
222                 }
223         }
224         return NULL;
225 }
226
227 void
228 SFSAddSaved(SFSTree *info, SFSDataIO *in, SFSTreePosition *position) {
229         CHECK_MEMORY(info);
230
231         if ( !(position->nodeptr && position->node) ) {
232                 SFSAdd(info, in);
233                 return;
234         }
235
236         position->node = *(position->nodeptr) = addRecord(info, position->node, in, position->level);
237 }
238
239 static void
240 freeFSFNode(SFSTree *info, SFSNode *node, void (*freefunc)(void*)) {
241         u_int32_t i;
242  
243         if ( node->isskip ) {
244                 if (node->haschild)
245                         freeFSFNode(info, *(SFSNode**)(node->data), freefunc);
246                 if (freefunc && node->isword && info->datasize)
247                         (*freefunc)( (void*)( ((char*)(node->data))+ (node->haschild) ? sizeof(SFSNode*) : 0 ) );
248         } else {
249                 SFSNodeData *nd = node->data;
250                 char *data= ((char*)node) + node->dataptr;
251         
252                 for(i=0;i<node->nchar;i++) {
253                         if (nd->haschild)
254                                 freeFSFNode(info, *(SFSNode**)( ((char*)nd) + nd->child ), freefunc);
255                         if (freefunc && nd->isword && info->datasize) {
256                                 (*freefunc)( (void*)data );
257                                 data+=info->datasize;
258                         }
259                         nd++;
260                 }
261         }
262
263         tfree(node);
264 }
265
266 void 
267 SFSFree(SFSTree *info, void (*freefunc)(void*)) {
268         SFSNodeStack *s=info->stack;
269
270         if (info->node && !info->plainmemory) freeFSFNode(info, info->node, freefunc);
271         if (info->buf) tfree(info->buf);
272         info->buf = NULL;
273         info->tlen=0;
274         info->node = NULL;
275
276         while(s) {
277                 info->stack=s->next;
278                 tfree(s);
279                 s=info->stack;
280         }
281 }
282
283 static SFSNode*
284 makeSkipNode(SFSTree *info, SFSDataIO *io, int level) {
285         u_int32_t len;
286         int size;
287         SFSNode *res;
288
289         io->key+=level;
290         io->keylen-=level;
291
292         len = (io->keylen > 255) ? 255 : io->keylen;
293         size = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize) + len;
294         size = PTRALIGN(size);
295
296         res = (SFSNode*)tmalloc(size);
297         info->nnodes++;
298         info->totalen+=size;
299
300         res->isskip=1;
301         res->nchar=len;
302         res->dataptr = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize);
303         memcpy(((char*)res) + res->dataptr, io->key, len);
304
305         if ( io->keylen > 255 ) {
306                 res->haschild=1;
307                 res->isword=0;
308                 io->key = io->key+len;
309                 io->keylen = io->keylen - len;
310                 *(SFSNode**)(res->data) = makeSkipNode(info, io, 0);
311                 io->key = io->key-len;
312                 io->keylen = io->keylen + len;
313         } else {
314                 res->haschild=0;
315                 res->isword=1;
316                 if (info->datasize) {
317                         memcpy( res->data, io->data, info->datasize );
318                 }
319         }
320
321         io->key-=level;
322         io->keylen+=level;
323
324         return res;
325 }
326
327 static SFSNode*
328 splitSkipNode(SFSTree *info, SFSNode* node, SFSDataIO *io, int level) {
329         SFSNode *res;
330         int prefixlen=0;
331         char *s1,*s2;
332         SFSNodeData     *ndata;
333
334         tassert(node->isskip);
335         io->key+=level;
336         io->keylen-=level;
337
338         s1=((char*)node) + node->dataptr;
339         s2=io->key;
340
341         while( s1 - (((char*)node) + node->dataptr) < node->nchar && s2 - io->key < io->keylen && *s1==*s2) {
342                 s1++;
343                 s2++;
344         }
345
346         prefixlen = s2 - io->key;
347
348         if ( prefixlen==0 ) {
349                 if ( node->nchar == 1 ) {
350                         int flag = EN_VAL | ((node->isword) ? EN_DATA : 0) | ((node->haschild) ? EN_CHLD : 0);
351                         res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), flag, &ndata);
352                         if ( node->isword ) {
353                                 if ( info->datasize ) 
354                                         memcpy(
355                                                 ((char*)res) + res->dataptr + info->datasize * ndata->data,
356                                                 ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0),
357                                                 info->datasize
358                                         );
359                         }
360                         if ( node->haschild ) 
361                                 *(SFSNode**)( ((char*)ndata) + ndata->child ) = *(SFSNode**)( node->data );
362                         info->totalen -= getNodeSize(info, node);
363                         info->nnodes--;
364                         tfree(node);
365                 } else {
366                         int size;
367
368                         res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), EN_VAL|EN_CHLD, &ndata);
369
370                         size = getNodeSize(info,node);
371                         info->totalen-=size;
372
373                         node->nchar--;
374                         memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + 1, node->nchar);
375
376                         size = getNodeSize(info,node);
377                         info->totalen+=size;
378
379                         *(SFSNode**)( ((char*)ndata) + ndata->child ) = (SFSNode*)trealloc(node, size);
380                 }
381                 res = addRecord(info, res, io, 0);
382         } else if (prefixlen==io->keylen) {
383                 if (prefixlen==node->nchar) {
384                         if ( node->isword || info->datasize==0) {
385                                 if (info->datasize)
386                                         memcpy( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNodeData*) : 0),
387                                                 io->data,
388                                                 info->datasize);
389                                 node->isword=1;
390                                 res=node;
391                         } else {
392                                 int osize = PTRALIGN(SFSNHRDSZ + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
393                                 int nsize = PTRALIGN(SFSNHRDSZ + info->datasize + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
394
395                                 info->totalen += nsize - osize;
396
397                                 res=(SFSNode*)trealloc(node,nsize);
398                                 res->dataptr=SFSNHRDSZ + info->datasize + ((res->haschild) ? sizeof(SFSNodeData*) : 0);
399                                 res->isword=1;
400                                 memmove(((char*)res) + res->dataptr,
401                                         ((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), res->nchar);
402                                 memcpy(((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), io->data, info->datasize);
403                         }
404                 } else {
405                         int size = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*) + prefixlen;
406                         size = PTRALIGN(size);
407
408                         info->totalen+=size;
409                         info->nnodes++;
410                         res = (SFSNode*)tmalloc(size);
411                         res->isskip=1;
412                         res->isword=1;
413                         res->haschild=1;
414                         res->nchar = prefixlen;
415                         res->dataptr = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*);
416                         memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
417                         if (info->datasize)
418                                 memcpy(((char*)(res->data)) + sizeof(SFSNodeData*), io->data, info->datasize);
419                         info->totalen-=getNodeSize(info,node);
420                         node->nchar-=prefixlen;
421                         memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
422                         size = getNodeSize(info,node);
423                         info->totalen+=size;
424                         *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, size);
425                 }
426         } else if ( prefixlen==node->nchar ) {
427                 int size = SFSNHRDSZ + info->datasize +  sizeof(SFSNode*) + node->nchar;
428                 info->totalen+=sizeof(SFSNode*);
429                 res=(SFSNode*)trealloc(node,size);
430                 memmove( ((char*)(res->data)) + sizeof(SFSNode*), res->data, info->datasize + res->nchar);
431                 res->haschild=1;
432                 res->dataptr+=sizeof(SFSNode*);
433                 *(SFSNode**)(res->data) = makeSkipNode(info, io, prefixlen); 
434         } else { 
435                 int size = SFSNHRDSZ + sizeof(SFSNodeData*) + prefixlen;
436                 size = PTRALIGN(size);
437                 info->totalen+=size;
438                 info->nnodes++;
439                 res = (SFSNode*)tmalloc(size);
440                 res->isskip=1;
441                 res->isword=0;
442                 res->haschild=1;
443                 res->nchar = prefixlen;
444                 res->dataptr = SFSNHRDSZ + sizeof(SFSNodeData*);
445                 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
446
447                 info->totalen-= getNodeSize(info,node);
448                 node->nchar-=prefixlen;
449
450                 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
451
452                 size = getNodeSize(info,node);
453                 info->totalen+= size;
454
455                 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, size);
456                 *(SFSNode**)(res->data) = splitSkipNode(info, *(SFSNode**)(res->data), io, prefixlen); 
457         }
458
459         io->key-=level;
460         io->keylen+=level;
461         return res;
462 }
463
464
465 static SFSNode*
466 enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd) {
467         u_int32_t nchild=0, nchar=0, nfound=0, i;
468         SFSNode *rs,**chld;
469         SFSNodeData *data;
470         int sizenode;
471         char *dataptr;
472
473
474         if ( node ) {
475                 nchar=node->nchar;
476                 nchild=node->nchild;
477                 data=node->data;
478
479                 for(i=0;i<nchar;i++) {
480                         nfound += data->isword;
481                         data++;
482                 }
483         }
484
485         if ( node )
486                 /*info->totalen -= PTRALIGN(SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize);*/
487                 info->totalen -= getNodeSize(info, node);
488
489         if ( flag & EN_VAL )   nchar++; 
490         if ( flag & EN_CHLD ) nchild++; 
491         if ( flag & EN_DATA )  nfound++;        
492
493
494         sizenode = SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
495         sizenode = PTRALIGN(sizenode);
496
497         info->totalen+=sizenode;
498         if ( !node ) info->nnodes++;
499         rs=(SFSNode*)tmalloc(sizenode);
500
501         rs->isskip = 0;
502         rs->nchar = nchar;
503         rs->nchild = nchild;
504         rs->dataptr=SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*);
505         dataptr=((char*)rs) + rs->dataptr;
506         chld = (SFSNode**)( ((char*)rs)+SFSNHRDSZ+nchar*sizeof(SFSNodeData) );
507         data=rs->data;
508
509         if (node) {
510                 SFSNode **ochld=(SFSNode**)( ((char*)node)+SFSNHRDSZ+node->nchar*sizeof(SFSNodeData) );
511                 SFSNodeData *odata = node->data;
512                 char *odataptr=((char*)node) + node->dataptr;
513                 int wasins=0;
514
515                 for(i=0;i<node->nchar;i++) {
516                         if ( val > odata->val ) {
517                                 *(u_int32_t*)data = *(u_int32_t*)odata;
518                                 if ( odata->haschild ) {
519                                         *chld=*ochld;
520                                         data->child = ((char*)chld) - ((char*)data);
521                                         chld++; ochld++;
522                                 }
523                                 if ( odata->isword && info->datasize ) {
524                                         memcpy(dataptr, odataptr, info->datasize);
525                                         data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
526                                         dataptr += info->datasize; odataptr += info->datasize;
527                                 }
528                                 data++; odata++; 
529                         } else if ( val == odata->val ) {
530                                 tassert ( (flag&EN_VAL)==0 );
531                                 *(u_int32_t*)data = *(u_int32_t*)odata;
532                                 wasins=1;
533                                 if ( odata->haschild || flag & EN_CHLD ) {
534                                         if (odata->haschild) *chld=*ochld;
535                                         data->child = ((char*)chld) - ((char*)data);
536                                         data->haschild=1;
537                                         chld++; if (odata->haschild) ochld++;
538                                 } else
539                                         data->haschild=0;
540                                 if ( odata->isword || flag & EN_DATA ) {
541                                         data->isword=1;
542                                         if ( info->datasize && odata->isword ) {
543                                                 memcpy(dataptr, odataptr, info->datasize);
544                                                 odataptr += info->datasize;
545                                         }
546                                         data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
547                                         dataptr += info->datasize;
548                                 } else
549                                         data->isword=0;
550                                 *nd = data;
551                                 data++; odata++; 
552                         } else {
553                                 if ( wasins==0 ) {
554                                         tassert ( flag&EN_VAL );
555                                         data->val = val;
556                                         if ( flag & EN_CHLD ) {
557                                                 data->haschild=1;
558                                                 data->child = ((char*)chld) - ((char*)data);
559                                                 chld++;
560                                         } else
561                                                 data->haschild=0;
562                                         if ( flag & EN_DATA ) {
563                                                 data->isword=1;
564                                                 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
565                                                 dataptr += info->datasize;
566                                         } else
567                                                 data->isword=0;
568                                         *nd = data;
569                                         data++;
570                                         wasins=1;
571                                         i--;
572                                 } else {
573                                         *(u_int32_t*)data = *(u_int32_t*)odata;
574                                         if ( odata->haschild ) {
575                                                 *chld=*ochld;
576                                                 data->child = ((char*)chld) - ((char*)data);
577                                                 chld++; ochld++;
578                                         }
579                                         if ( odata->isword && info->datasize ) {
580                                                 memcpy(dataptr, odataptr, info->datasize);
581                                                 data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
582                                                 dataptr += info->datasize; odataptr += info->datasize;
583                                         }
584                                         data++; odata++; 
585                                 }
586                         } 
587                 }
588                 if ( wasins==0 ) {
589                         tassert ( flag&EN_VAL );
590                         data->val = val;
591                         if ( flag & EN_CHLD ) {
592                                 data->haschild=1;
593                                 data->child = ((char*)chld) - ((char*)data);
594                                 chld++;
595                         } else
596                                 data->haschild=0;
597                         if ( flag & EN_DATA ) {
598                                 data->isword=1;
599                                 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
600                                 dataptr += info->datasize;
601                         } else 
602                                 data->isword=0;
603                         *nd = data;
604                 }
605         } else {
606                 tassert ( flag & EN_VAL );
607                 data->val = val;
608                 if ( flag & EN_CHLD ) {
609                         data->haschild=1;
610                         data->child = ((char*)chld) - ((char*)data);
611                 } else
612                         data->haschild=0;
613                 if ( flag & EN_DATA ) {
614                         data->isword=1;
615                         data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
616                 } else
617                         data->isword=0;
618                 *nd = data;
619         }
620         if (node) tfree(node);
621         return rs;
622 }
623
624 static SFSNode*
625 addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level) {
626         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
627         u_int8_t *ptr = ((u_int8_t*)in->key) + level;
628
629         if ( node ) {
630                 if ( node->isskip ) {
631                         if ( node->haschild && in->keylen-level > node->nchar && 
632                                         strncmp(in->key+level, ((char*)node)+node->dataptr, node->nchar)==0 ) 
633                                 *(SFSNode**)( node->data ) = addRecord(info, *(SFSNode**)( node->data ), in, level+node->nchar); 
634                         else 
635                                 node = splitSkipNode(info, node, in, level); 
636                 } else {
637                 StopLow = node->data;   
638                         StopHigh = StopLow + node->nchar;
639                         while (StopLow < StopHigh) {
640                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
641                         if ( StopMiddle->val == *ptr ) {
642                                         if ( *(ptr+1)=='\0' ) {
643                                                 if ( StopMiddle->isword ) {
644                                                         /* already exists */
645                                                         if ( info->datasize ) 
646                                                                 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
647                                                                         in->data, info->datasize );
648                                                 } else {
649                                                         /* not exist word */
650                                                         if (info->datasize) {
651                                                                 node = enlargeNode(info, node, *ptr, EN_DATA, &StopMiddle);
652                                                                 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
653                                                                         in->data, info->datasize );
654                                                         }
655                                                         StopMiddle->isword = 1;
656                                                 }
657                                         } else if ( StopMiddle->haschild ) {
658                                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) = 
659                                                         addRecord(info, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), in, level+1);
660                                         } else {
661                                                 node = enlargeNode(info, node, *ptr, EN_CHLD, &StopMiddle);
662                                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
663                                                         makeSkipNode(info, in, level+1);
664                                         }
665                                         return node;
666                                 } else if ( StopMiddle->val < *ptr ) {
667                                         StopLow = StopMiddle + 1;
668                                 } else {
669                                         StopHigh = StopMiddle;
670                                 }
671                         }
672                         if ( *(ptr+1)=='\0' ) {
673                                 node = enlargeNode(info, node, *ptr, EN_VAL|EN_DATA, &StopMiddle);
674                                 if ( info->datasize )
675                                         memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
676                                         in->data, info->datasize );
677                         } else {
678                                 node = enlargeNode(info, node, *ptr, EN_VAL|EN_CHLD, &StopMiddle);
679                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) = 
680                                         makeSkipNode(info, in, level+1);
681                         }
682                 }
683         } else 
684                 node = makeSkipNode(info, in, level);
685
686         return node;
687
688 }
689
690 void
691 SFSAdd(SFSTree *info, SFSDataIO *in) {
692         CHECK_MEMORY(info);
693         if (in->keylen<=0)
694                 in->keylen=strlen(in->key);
695         info->node = addRecord(info, info->node, in, 0);
696 }
697
698 static SFSNodeStack*
699 pushStack(SFSNodeStack *top, SFSNode *node, int level ) {
700         SFSNodeStack *r=(SFSNodeStack*)tmalloc(sizeof(SFSNodeStack));
701
702         r->next = top;
703         r->node=node;
704         r->data=node->data;
705         r->level=level;
706         r->checkedchild = 0;
707         r->checkedval = 0;
708
709         return r;
710 }
711
712 void 
713 SFSIteratorStart(SFSTree *info) {
714         if ( !info->buf ) {
715                 info->tlen = 32;
716                 info->buf = (char*)tmalloc(info->tlen);
717         } 
718         info->stack = pushStack(NULL, info->node, 0);
719         info->hasword=0; 
720 }
721
722 void
723 SFSPrefixIteratorStart(SFSTree *info, char *word) {
724         SFSNode *node = info->node;
725         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
726         u_int8_t *ptr =(u_int8_t*)word;
727         int len,wlen=strlen(word);
728
729         if ( wlen+1>=info->tlen ) {
730                 info->tlen = 2*wlen;
731                 info->buf = (info->buf) ?
732                                 (char*)trealloc(info->buf,info->tlen)
733                         :
734                                 (char*)tmalloc(info->tlen);
735         }
736
737         info->hasword=0;
738         while( node && *ptr) {
739                 len = wlen - (((char*)ptr)-word);
740                 if ( node->isskip ) {
741                         if ( STRNCMP(ptr, ((char*)node)+node->dataptr, (len<node->nchar) ? len : node->nchar) ) {
742                                 if ( len<=node->nchar ) {
743                                         strcpy(info->buf,word);
744                                         info->stack = pushStack(NULL, node, ((char*)ptr) - word);
745                                         return;
746                                 } else if ( node->haschild ) {
747                                         ptr+=node->nchar;
748                                         node = getSkipChildPointer(info, node);
749                                 } else {
750                                         return;
751                                 }
752                         } else
753                                 return;
754                 } else {
755                         StopLow = node->data;
756                         StopHigh = StopLow + node->nchar;
757                         while (StopLow < StopHigh) {
758                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
759                                 if ( StopMiddle->val == *ptr ) {
760                                         if ( *(ptr+1)=='\0' ) {
761                                                 len =((char*)ptr)-word+1;
762                                                 strcpy(info->buf,word);
763                                                 if ( StopMiddle->isword ) {
764                                                         info->hasword=1;
765                                                         info->wdata = (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
766                                                 }
767                                                 if ( StopMiddle->haschild )
768                                                         info->stack = pushStack(NULL, getChildPointer( info, StopMiddle ), len);
769                                                 return;
770                                         } else if ( StopMiddle->haschild ) {
771                                                 node = getChildPointer( info, StopMiddle ); 
772                                         } else {
773                                                 return;
774                                         }
775                                         ptr++;
776                                         break;
777                                 } else if ( StopMiddle->val < *ptr ) {
778                                         StopLow = StopMiddle + 1;
779                                 } else {
780                                         StopHigh = StopMiddle;
781                                 }
782                         }
783                         if ( StopLow >= StopHigh )
784                                 break;
785                 }
786         }
787         return;
788 }
789
790 int
791 SFSIterate(SFSTree *info, SFSDataIO *out) {
792         SFSNodeStack *s=info->stack;
793
794         if ( info->hasword ) {
795                 out->key = info->buf;
796                 out->keylen = strlen(out->key);
797                 out->data = info->wdata;
798                 info->hasword = 0;
799                 return 1;
800         }
801
802         if ( s == NULL )
803                 return 0;
804         if ( s->node == NULL ) {
805                 info->stack = s->next;
806                 tfree(s);
807                 return SFSIterate(info, out);
808         }
809                                                          
810         while ( s->level + s->node->nchar + 1 >= info->tlen ) {
811                 info->tlen *= 2;
812                 info->buf = (char*)trealloc(info->buf, info->tlen);
813         }
814
815         if ( s->node->isskip ) {
816                 memcpy( info->buf + s->level, ((char*)s->node) + s->node->dataptr, s->node->nchar );
817                 if ( s->node->isword && !s->checkedval) {
818                         info->buf[ s->level+s->node->nchar ] = '\0';
819                         out->key = info->buf;
820                         out->keylen = s->level+s->node->nchar;
821                         out->data =((char*)(s->node->data)) + ((s->node->haschild) ? sizeof(SFSNode*) : 0);
822                         s->checkedval=1;
823                         return 1;
824                 }
825                 if ( s->node->haschild && !s->checkedchild) {
826                         info->stack = pushStack(s, getSkipChildPointer(info, s->node), s->level+s->node->nchar);
827                         s->checkedchild=1;
828                         if ( SFSIterate(info, out) )
829                                 return 1;
830                 }
831         } else {
832                 while( s->data - s->node->data < s->node->nchar ) {
833                         info->buf[ s->level ] = (char)s->data->val;
834                         if ( s->checkedval==0 && s->data->isword ) {
835                                 info->buf[ s->level+1 ] = '\0';  
836                                 out->key = info->buf;
837                                 out->keylen = s->level+1;
838                                 out->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
839                                 s->checkedval = 1;
840                                 return 1;
841                         }
842                         if ( s->checkedchild==0 && s->data->haschild ) {
843                                 info->stack = pushStack(s,
844                                         getChildPointer( info, s->data ), s->level+1);
845                                 s->checkedchild=1;
846                                 if ( SFSIterate(info, out) )
847                                         return 1;
848                         }
849                         s->checkedval = s->checkedchild = 0;
850                         s->data++;
851                 }
852         }
853         info->stack = s->next;
854         tfree(s);
855
856         return SFSIterate(info, out);
857 }
858
859 int
860 SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l) {
861         SFSNodeStack *s=info->stack;
862
863         SFSPrefixIteratorStart(info, word);
864         s=info->stack;
865
866         if ( SFSIterate(info, f) ) {
867                 SFSNodeStack *sptr = info->stack, *stmp;
868                 while( sptr && sptr!=s ) {
869                         stmp=sptr->next;
870                         tfree(sptr);
871                         sptr=stmp;
872                 }
873          
874                 if ( s == NULL ) {
875                         memcpy(l,f,sizeof(SFSDataIO));
876                         return 1;
877                 }
878         } else
879                 return 0;
880                                                          
881         info->stack=NULL;
882
883         while( f->keylen +  s->level + 2 >= info->tlen ) {
884                 info->tlen *= 2;
885                 info->buf = (char*)trealloc(info->buf, info->tlen);
886         }
887
888         f->key = info->buf;
889         l->key = info->buf + f->keylen + 1;
890         memcpy(l->key, f->key, f->keylen + 1);
891                         
892         while(s->node) {
893                 while( f->keylen + 1 + s->level + s->node->nchar + 1 >= info->tlen ) {
894                         info->tlen *= 2;
895                         info->buf = (char*)trealloc(info->buf, info->tlen);
896                 }
897                 if ( s->node->isskip ) {
898                         memcpy(info->buf + f->keylen + 1 + s->level,
899                                 ((char*)(s->node))+s->node->dataptr, s->node->nchar);
900                         s->level+=s->node->nchar;
901                         if (s->node->haschild) {
902                                 s->node=getSkipChildPointer(info, s->node);
903                         } else { /* if (s->node->isword) */
904                                 info->buf[ f->keylen + 1 + s->level  ] = '\0';
905                                 l->data = (void*)(s->node->data);
906                                 l->keylen = s->level+1;
907                                 break;
908                         }
909                 } else {
910                         s->data = s->node->data + s->node->nchar - 1;
911                         while( s->data - s->node->data >= 0 ) {
912                                 info->buf[ f->keylen + 1 + s->level ] = (char)s->data->val;
913                                 if ( s->data->haschild ) {
914                                         s->node = getChildPointer( info, s->data ); 
915                                         s->level++;
916                                         break;
917                                 }
918                                 if ( s->data->isword ) {
919                                         info->buf[ f->keylen + 1 + s->level ] = '\0';
920                                         l->keylen = s->level+1;
921                                         l->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
922                                         s->node=NULL;
923                                         break;
924                                 }
925                                 s->data--;
926                         }
927                 }
928         }               
929         f->key = info->buf;
930         l->key = info->buf + f->keylen + 1;
931         tfree(s); 
932
933         return 1;
934 }
935
936 typedef struct WorkPlain {
937         SFSTree                 *info;
938         char                    *node;
939         off_t                   offset;
940 } WorkPlain;
941
942 static Opaque
943 plainNode(WorkPlain *wp, SFSNode *node) {
944         int     size = getNodeSize(wp->info, node);
945         off_t   myoffset = wp->offset;
946
947         memcpy( wp->node + wp->offset, node, size );
948         wp->offset += size;
949
950         tassert( wp->offset <= wp->info->totalen );
951
952         if ( node->isskip ) {
953                 if (node->haschild) 
954                         *(Opaque*)(wp->node + myoffset + SFSNHRDSZ) = 
955                                         plainNode(wp, getSkipChildPointer(wp->info, node));
956         } else {
957                 SFSNodeData *nd = node->data;
958                 u_int32_t       i;
959
960                 for(i=0;i<node->nchar;i++) {
961                         if (nd->haschild)
962                                 *(Opaque*)(wp->node + myoffset + ( ((char*)nd) - ((char*)node) ) + nd->child) =
963                                                 plainNode(wp, getChildPointer( wp->info, nd ) );        
964                         nd++;
965                 }
966         }
967  
968         tfree(node);
969
970         return myoffset;
971 }
972
973 void
974 SFSMakePlain(SFSTree *info, void *pointer) {
975         WorkPlain       wp;
976
977         if ( info->plainmemory )
978                 return;
979
980         wp.info = info;
981         wp.offset = 0;
982         if ( pointer )
983                 wp.node = (char*)pointer;
984         else
985                 wp.node = (char*)tmalloc(sizeof(char*) * info->totalen);
986
987         plainNode(&wp, info->node);
988         tassert( wp.offset == info->totalen );
989
990         info->node = (SFSNode*)wp.node; 
991         info->plainmemory = 1;
992 }
993
994 static SFSNode*
995 revertNode(SFSTree *info, SFSNode* node) {
996         int size = getNodeSize(info, node);
997         SFSNode *newnode;
998
999         newnode = (SFSNode*)tmalloc( size );
1000         memcpy(newnode, node, size);
1001
1002         if ( node->isskip ) {
1003                 if (node->haschild)
1004                         *(SFSNode**)( (char*)(newnode->data) ) = 
1005                                 revertNode(info, getSkipChildPointer(info, node));
1006         } else {
1007                 SFSNodeData *nd = node->data;
1008                 SFSNodeData *nnd = newnode->data;
1009                 u_int32_t   i;
1010
1011                 for(i=0;i<node->nchar;i++) {
1012                         if (nd->haschild)
1013                                 *(SFSNode**) (((char*)nnd) + nnd->child ) = 
1014                                         revertNode(info, getChildPointer( info, nd ));
1015                         nd++; nnd++;
1016                 }
1017         }
1018
1019         return newnode;
1020 }
1021
1022 void *
1023 SFSRevertPlain(SFSTree *info) {
1024         void *pointer = info->node;
1025
1026         if (! info->plainmemory )
1027                 return NULL;
1028
1029         info->node = revertNode(info, info->node);
1030         info->plainmemory = 0;
1031
1032         return pointer;
1033 }
1034
1035 static Opaque
1036 writeNode(WorkPlain *wp, int fd, SFSNode *node, u_int32_t extrasize) {
1037         int     size = getNodeSize(wp->info, node);
1038         SFSNode  *wnode = (SFSNode*)tmalloc(size);
1039         off_t   myoffset = wp->offset;
1040
1041         memcpy( wnode, node, size );
1042         wp->offset += size;
1043
1044         tassert( wp->offset <= wp->info->totalen );
1045
1046         if ( node->isskip ) {
1047                 if (node->haschild) 
1048                         *(Opaque*)( ((char*)wnode) + SFSNHRDSZ) = 
1049                                         writeNode(wp, fd, getSkipChildPointer(wp->info, node), extrasize);
1050         } else {
1051                 SFSNodeData *nd = node->data;
1052                 u_int32_t       i;
1053
1054                 for(i=0;i<node->nchar;i++) {
1055                         if (nd->haschild)
1056                                 *(Opaque*)(((char*)wnode) + ( ((char*)nd) - ((char*)node) ) + nd->child) =
1057                                                 writeNode(wp, fd, getChildPointer( wp->info, nd ), extrasize ); 
1058                         nd++;
1059                 }
1060         }
1061
1062         if ( lseek(fd, myoffset + SFSTDHSZ + extrasize, SEEK_SET) < 0 )
1063                 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1064         if ( write(fd, wnode, size) != size )
1065                 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1066         
1067         tfree(wnode);
1068
1069         return myoffset;
1070 }
1071
1072 void 
1073 SFSWriteDump(SFSTree *info, char *filename, void *extradata, u_int32_t extrasize) {
1074         int                             fd;
1075         off_t                           size = info->totalen + SFSTDHSZ;
1076         SFSTreeDumpHeader       dh;
1077
1078         if ( (fd = open(filename, O_RDWR|O_CREAT|O_TRUNC, 0666)) < 0 )
1079                 tlog(TL_CRIT|TL_EXIT, "Can not open file '%s': %s", filename, strerror(errno));
1080
1081         if ( flock(fd, LOCK_EX) < 0 )
1082                 tlog(TL_CRIT|TL_EXIT, "flock failed: %s", strerror(errno));
1083
1084         if ( extrasize == 0 )
1085                 extradata = NULL;
1086         else if ( extradata == NULL )
1087                 extrasize = 0;
1088
1089         if ( lseek(fd, size + MAXALIGN(extrasize) , SEEK_SET) < 0 )
1090                 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1091
1092         dh.version = SFSTREE_VERSION;
1093         dh.opaquesize = sizeof(Opaque);
1094         dh.headersize = SFSTDHSZ;
1095         dh.datasize = info->datasize;
1096         dh.totalen = info->totalen;
1097         dh.nnodes = info->nnodes;
1098         dh.extrasize = extrasize;
1099
1100         if ( lseek(fd, 0, SEEK_SET) < 0 )
1101                 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1102         if ( write(fd, &dh, SFSTDHSZ) != SFSTDHSZ )
1103                 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1104
1105         if ( extrasize ) {
1106                 if ( write(fd, extradata, extrasize) != extrasize )
1107                         tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1108                 if ( extrasize != MAXALIGN(extrasize) ) {
1109                         char dummy[8] = {0,0,0,0,0,0,0,0};
1110                         if ( write(fd, dummy, MAXALIGN(extrasize) - extrasize ) != MAXALIGN(extrasize) - extrasize )
1111                                 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1112
1113                         extrasize = MAXALIGN(extrasize);
1114                 }
1115         }
1116
1117         if ( info->plainmemory ) {
1118                 if ( write(fd, info->node, info->totalen) != info->totalen )
1119                         tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1120         } else {
1121                 WorkPlain       wp;
1122
1123                 wp.info = info;
1124                 wp.offset = 0;
1125                 
1126                 writeNode(&wp, fd, info->node, extrasize);
1127         }
1128         
1129         flock(fd, LOCK_UN);
1130         close(fd);
1131 }
1132
1133 static SFSNode*
1134 readNode(SFSTree *info, int fd, char *buf, int bufsize, int extrasize) {
1135         SFSNode *node;
1136         int             size;
1137
1138         size = read(fd, buf, bufsize );
1139         if ( size < SFSNHRDSZ + sizeof(void*) )
1140                 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1141
1142         size = getNodeSize(info, (SFSNode*)buf);
1143         tassert( size <= bufsize );
1144         node = (SFSNode*)tmalloc( size );
1145         memcpy(node, buf, size);
1146
1147         if ( node->isskip ) {
1148                 if (node->haschild) {
1149                         if ( lseek(fd, *(Opaque*)node->data + SFSTDHSZ + extrasize, SEEK_SET) < 0 )
1150                                 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1151                         *(SFSNode**)( (char*)(node->data) ) = 
1152                                 readNode(info, fd, buf, bufsize, extrasize);
1153                 }
1154         } else {
1155                 SFSNodeData *nd = node->data;
1156                 u_int32_t   i;
1157
1158                 for(i=0;i<node->nchar;i++) {
1159                         if (nd->haschild) {
1160                                 if ( lseek(fd, *(Opaque*)(((char*)nd) + nd->child ) + SFSTDHSZ + extrasize, SEEK_SET) < 0 )
1161                                         tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1162                                 *(SFSNode**) (((char*)nd) + nd->child ) = 
1163                                         readNode(info, fd, buf, bufsize, extrasize);
1164                         }
1165                         nd++;
1166                 }
1167         }
1168
1169         return node;
1170 }
1171
1172 void
1173 SFSReadDump(SFSTree *info, char *filename, void **extradata, u_int32_t *extrasize) {
1174         int                 fd;
1175         SFSTreeDumpHeader   dh;
1176         char                            *buf;
1177         int                                     bufsize;
1178
1179         if ( extradata )
1180                 *extradata = NULL;
1181         if (extrasize )
1182                 *extrasize = 0;
1183
1184         memset(info,0,sizeof(SFSTree));
1185
1186         if ( (fd = open(filename, O_RDONLY)) < 0 )
1187                 tlog(TL_CRIT|TL_EXIT, "Can not open file '%s': %s", strerror(errno));
1188         if ( flock(fd, LOCK_SH) < 0 )
1189                 tlog(TL_CRIT|TL_EXIT, "flock failed: %s", strerror(errno));
1190
1191         if ( read(fd, &dh, SFSTDHSZ) != SFSTDHSZ )
1192                 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1193
1194         if ( dh.version != SFSTREE_VERSION )
1195                 tlog(TL_CRIT|TL_EXIT, "Tree version mismatch (should be 0x%04x but 0x%04x)", SFSTREE_VERSION, dh.version);
1196         if ( dh.opaquesize != sizeof(Opaque) )
1197                 tlog(TL_CRIT|TL_EXIT, "sizeof(Opaque) mismatch");
1198         if ( dh.headersize != SFSTDHSZ )
1199                 tlog(TL_CRIT|TL_EXIT, "Tree's header size mismatch (should be %d but %d bytes)", SFSTDHSZ, dh.headersize);
1200
1201         info->totalen = dh.totalen;
1202         info->nnodes = dh.nnodes;
1203         info->datasize = dh.datasize;
1204
1205         if ( dh.extrasize ) {
1206                 void    *pointer = tmalloc( MAXALIGN(dh.extrasize) );
1207
1208                 if ( read(fd, pointer, MAXALIGN(dh.extrasize)) != MAXALIGN(dh.extrasize) )
1209                         tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1210
1211                 if ( extradata )
1212                         *extradata = pointer;
1213                 else 
1214                         tfree(pointer);
1215
1216                 if ( extrasize )
1217                         *extrasize = dh.extrasize;
1218         }
1219
1220         /* allocate buffer with max allowed size */
1221         bufsize = SFSNHRDSZ + 256*(sizeof(SFSNodeData) + sizeof(void*) + info->datasize);
1222         buf = tmalloc( bufsize );
1223         info->node = readNode(info, fd, buf, bufsize, MAXALIGN(dh.extrasize));
1224         tfree(buf);
1225
1226         flock(fd, LOCK_UN);
1227         close(fd);
1228 }
1229
1230 void
1231 SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size, void **extradata, u_int32_t *extrasize) {
1232         SFSTreeDumpHeader       *dh;
1233
1234         if ( extradata )
1235                 *extradata = NULL;
1236         if (extrasize )
1237                 *extrasize = 0;
1238
1239         memset(info,0,sizeof(SFSTree));
1240
1241         if ( size && size < SFSTDHSZ )
1242                 tlog(TL_CRIT|TL_EXIT, "Memsize too small");
1243
1244         dh = (SFSTreeDumpHeader*)pointer;
1245         
1246         if ( dh->version != SFSTREE_VERSION )
1247                 tlog(TL_CRIT|TL_EXIT, "Tree version mismatch (should be 0x%04x but 0x%04x)", SFSTREE_VERSION, dh->version);
1248         if ( dh->opaquesize != sizeof(Opaque) )
1249                 tlog(TL_CRIT|TL_EXIT, "sizeof(Opaque) mismatch");
1250         if ( dh->headersize != SFSTDHSZ )
1251                 tlog(TL_CRIT|TL_EXIT, "Tree's header size mismatch (should be %d but %d bytes)", SFSTDHSZ, dh->headersize);
1252         if ( size && size != dh->totalen + SFSTDHSZ  + MAXALIGN(dh->extrasize) )
1253                 tlog(TL_CRIT|TL_EXIT, "Memory size mismatch (should be %d but %d bytes)", dh->totalen + SFSTDHSZ + dh->extrasize , size);
1254
1255         info->totalen = dh->totalen;
1256         info->nnodes = dh->nnodes;
1257         info->datasize = dh->datasize;
1258         info->plainmemory = 1;
1259
1260         if ( dh->extrasize ) {
1261                 if ( extradata )
1262                         *extradata = ((char*)pointer) + SFSTDHSZ;
1263
1264                 if ( extrasize )
1265                         *extrasize = dh->extrasize;
1266         }
1267
1268         if ( info->totalen && info->nnodes ) 
1269                 info->node = (SFSNode*)( ((char*)pointer) + SFSTDHSZ + MAXALIGN(dh->extrasize) );
1270 }