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