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