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