sfxstr.c

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