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