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