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 <string.h>
  31
  32 #include "tlog.h"
  33 #include "tmalloc.h"
  34 #include "sfxstr.h"
  35
  36 #define EN_VAL  0x01
  37 #define EN_CHLD 0x02
  38 #define EN_DATA 0x04
  39
  40 static SFSNode* enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd);
  41 static SFSNode* addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level);
  42
  43 #define STRNCMP(p1,p2,n) ( ((n)==1) ? ( *((char*)(p1))==*((char*)(p2)) ) : (strncmp((char*)(p1), (char*)(p2), (n))==0) )
  44
  45 SFSTree*
  46 SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in) {
  47         if ( datasize % sizeof(u_int32_t) )
  48                 tlog(TL_ALARM|TL_EXIT,"SFSInit_dp: datasize(%d) should be divided by sizeof(u_int32_t)", datasize);
  49
  50         if (!info)
  51                 info=(SFSTree*)tmalloc(sizeof(SFSTree));
  52         memset(info,0,sizeof(SFSTree));
  53
  54         info->datasize = datasize;
  55
  56         while(in && in->key) {
  57                 SFSAdd(info, in);
  58                 in++;
  59         }
  60
  61         return info;
  62 }
  63
  64 SFSTree*
  65 SFSInit_c(SFSTree *info, char **in) {
  66         char **ptr=in;
  67         SFSDataIO  d;
  68
  69         if (!info)
  70                 info=(SFSTree*)tmalloc(sizeof(SFSTree));
  71         memset(info,0,sizeof(SFSTree));
  72
  73         while(ptr && *ptr) {
  74                 d.key=*ptr;
  75                 d.keylen=0;
  76                 SFSAdd(info, &d);
  77                 ptr++;
  78         }
  79
  80         return info;
  81 }
  82
  83 void*
  84 SFSFindData(SFSTree *info, char *word) {
  85         SFSNode *node = info->node;
  86         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
  87         u_int8_t *ptr =(u_int8_t*)word;
  88
  89         while( node && *ptr ) {
  90                 if ( node->isskip ) {
  91                         if ( STRNCMP(ptr, ((char*)node)+node->dataptr, node->nchar) ) {
  92                                 ptr+=node->nchar;
  93                                 if ( *ptr=='\0' && node->isword) {
  94                                         return (void*) ( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0) );
  95                                 } else if ( node->haschild ) {
  96                                         node = *(SFSNode**)(node->data);
  97                                 } else {
  98                                         return NULL;
  99                                 }
 100                         } else
 101                                 return NULL;
 102                 } else {
 103                         StopLow = node->data;
 104                         StopHigh = StopLow + node->nchar;
 105                         while (StopLow < StopHigh) {
 106                                StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
 107                                if ( StopMiddle->val == *ptr ) {
 108                                        ptr++;
 109                                        if ( *ptr=='\0' && StopMiddle->isword ) {
 110                                                 return (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
 111                                         } else if ( StopMiddle->haschild ) {
 112                                                 node=*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child );
 113                                         } else {
 114                                                 return NULL;
 115                                         }
 116                                         break;
 117                                 } else if ( StopMiddle->val < *ptr ) {
 118                                         StopLow = StopMiddle + 1;
 119                                 } else {
 120                                         StopHigh = StopMiddle;
 121                                 }
 122                         }
 123                         if ( StopLow >= StopHigh )
 124                                 return NULL;
 125                 }
 126         }
 127         return NULL;
 128 }
 129
 130 static void
 131 freeFSFNode(SFSTree *info, SFSNode *node, void (*freefunc)(void*)) {
 132         u_int32_t i;
 133
 134         if ( node->isskip ) {
 135                 if (node->haschild)
 136                         freeFSFNode(info, *(SFSNode**)(node->data), freefunc);
 137                 if (freefunc && node->isword && info->datasize)
 138                         (*freefunc)( (void*)( ((char*)(node->data))+ (node->haschild) ? sizeof(SFSNode*) : 0 ) );
 139         } else {
 140                 SFSNodeData *nd = node->data;
 141                 char *data= ((char*)node) + node->dataptr;
 142
 143                 for(i=0;i<node->nchar;i++) {
 144                         if (nd->haschild)
 145                                 freeFSFNode(info, *(SFSNode**)( ((char*)nd) + nd->child ), freefunc);
 146                         if (freefunc && nd->isword && info->datasize) {
 147                                 (*freefunc)( (void*)data );
 148                                 data+=info->datasize;
 149                         }
 150                         nd++;
 151                 }
 152         }
 153
 154         tfree(node);
 155 }
 156
 157 void
 158 SFSFree(SFSTree *info, void (*freefunc)(void*)) {
 159         SFSNodeStack *s=info->stack;
 160
 161         if (info->node) freeFSFNode(info, info->node, freefunc);
 162         if (info->buf) tfree(info->buf);
 163         info->buf = NULL;
 164         info->tlen=0;
 165         info->node = NULL;
 166
 167         while(s) {
 168                 info->stack=s->next;
 169                 tfree(s);
 170                 s=info->stack;
 171         }
 172 }
 173
 174 static SFSNode*
 175 makeSkipNode(SFSTree *info, SFSDataIO *io, int level) {
 176         u_int32_t len;
 177         int size;
 178         SFSNode *res;
 179
 180         io->key+=level;
 181         io->keylen-=level;
 182
 183         len = (io->keylen > 255) ? 255 : io->keylen;
 184         size = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize) + len;
 185
 186         res = (SFSNode*)tmalloc(size);
 187
 188         info->nnodes++;
 189         info->totalen+=size;
 190
 191         res->isskip=1;
 192         res->nchar=len;
 193         res->dataptr = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize);
 194         memcpy(((char*)res) + res->dataptr, io->key, len);
 195
 196         if ( io->keylen > 255 ) {
 197                 res->haschild=1;
 198                 res->isword=0;
 199                 io->key = io->key+len;
 200                 io->keylen = io->keylen - len;
 201                 *(SFSNode**)(res->data) = makeSkipNode(info, io, 0);
 202                 io->key = io->key-len;
 203                 io->keylen = io->keylen + len;
 204         } else {
 205                 res->haschild=0;
 206                 res->isword=1;
 207                 if (info->datasize) {
 208                         memcpy( res->data, io->data, info->datasize );
 209                 }
 210         }
 211
 212         io->key-=level;
 213         io->keylen+=level;
 214
 215         return res;
 216 }
 217
 218 static SFSNode*
 219 splitSkipNode(SFSTree *info, SFSNode* node, SFSDataIO *io, int level) {
 220         SFSNode *res;
 221         int prefixlen=0;
 222         char *s1,*s2;
 223         SFSNodeData     *ndata;
 224
 225         tassert(node->isskip);
 226         io->key+=level;
 227         io->keylen-=level;
 228
 229         s1=((char*)node) + node->dataptr;
 230         s2=io->key;
 231
 232         while( s1 - (((char*)node) + node->dataptr) < node->nchar && s2 - io->key < io->keylen && *s1==*s2) {
 233                 s1++;
 234                 s2++;
 235         }
 236
 237         prefixlen = s2 - io->key;
 238
 239         if ( prefixlen==0 ) {
 240                 if ( node->nchar == 1 ) {
 241                         int flag = EN_VAL | ((node->isword) ? EN_DATA : 0) | ((node->haschild) ? EN_CHLD : 0);
 242                         res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), flag, &ndata);
 243                         if ( node->isword ) {
 244                                 if ( info->datasize )
 245                                         memcpy(
 246                                                 ((char*)res) + res->dataptr + info->datasize * ndata->data,
 247                                                 ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0),
 248                                                 info->datasize
 249                                         );
 250                         }
 251                         if ( node->haschild )
 252                                 *(SFSNode**)( ((char*)ndata) + ndata->child ) = *(SFSNode**)( node->data );
 253                         info->totalen -= SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
 254                                 ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar;
 255                         info->nnodes--;
 256                         tfree(node);
 257                 } else {
 258                         res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), EN_VAL|EN_CHLD, &ndata);
 259                         node->nchar--;
 260                         memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + 1, node->nchar);
 261                         info->totalen--;
 262                         *(SFSNode**)( ((char*)ndata) + ndata->child ) = (SFSNode*)trealloc(node,
 263                                 SFSNHRDSZ + ((node->haschild) ? sizeof(SFSNode*) : 0) +
 264                                 ((node->isword) ? info->datasize : 0 )+ node->nchar);
 265                 }
 266                 res = addRecord(info, res, io, 0);
 267         } else if (prefixlen==io->keylen) {
 268                 if (prefixlen==node->nchar) {
 269                         if ( node->isword || info->datasize==0) {
 270                                 if (info->datasize)
 271                                         memcpy( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNodeData*) : 0),
 272                                                 io->data,
 273                                                 info->datasize);
 274                                 node->isword=1;
 275                                 res=node;
 276                         } else {
 277                                 int size = SFSNHRDSZ + info->datasize + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar;
 278
 279                                 info->totalen+=info->datasize;
 280                                 res=(SFSNode*)trealloc(node,size);
 281                                 res->dataptr=SFSNHRDSZ + info->datasize + ((res->haschild) ? sizeof(SFSNodeData*) : 0);
 282                                 res->isword=1;
 283                                 memmove(((char*)res) + res->dataptr,
 284                                         ((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), res->nchar);
 285                                 memcpy(((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), io->data, info->datasize);
 286                         }
 287                 } else {
 288                         int size = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*) + prefixlen;
 289                         info->totalen+=size;
 290                         info->nnodes++;
 291                         res = (SFSNode*)tmalloc(size);
 292                         res->isskip=1;
 293                         res->isword=1;
 294                         res->haschild=1;
 295                         res->nchar = prefixlen;
 296                         res->dataptr = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*);
 297                         memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
 298                         if (info->datasize)
 299                                 memcpy(((char*)(res->data)) + sizeof(SFSNodeData*), io->data, info->datasize);
 300                         node->nchar-=prefixlen;
 301                         memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
 302                         info->totalen-=prefixlen;
 303                         *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
 304                                 ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
 305                 }
 306         } else if ( prefixlen==node->nchar ) {
 307                 int size = SFSNHRDSZ + info->datasize +  sizeof(SFSNode*) + node->nchar;
 308                 info->totalen+=sizeof(SFSNode*);
 309                 res=(SFSNode*)trealloc(node,size);
 310                 memmove( ((char*)(res->data)) + sizeof(SFSNode*), res->data, info->datasize + res->nchar);
 311                 res->haschild=1;
 312                 res->dataptr+=sizeof(SFSNode*);
 313                 *(SFSNode**)(res->data) = makeSkipNode(info, io, prefixlen);
 314         } else {
 315                 int size = SFSNHRDSZ + sizeof(SFSNodeData*) + prefixlen;
 316                 info->totalen+=size;
 317                 info->nnodes++;
 318                 res = (SFSNode*)tmalloc(size);
 319                 res->isskip=1;
 320                 res->isword=0;
 321                 res->haschild=1;
 322                 res->nchar = prefixlen;
 323                 res->dataptr = SFSNHRDSZ + sizeof(SFSNodeData*);
 324                 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
 325
 326                 node->nchar-=prefixlen;
 327                 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
 328                 info->totalen-=prefixlen;
 329
 330                 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node,
 331                         SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
 332                                 ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar
 333                 );
 334                 *(SFSNode**)(res->data) = splitSkipNode(info, *(SFSNode**)(res->data), io, prefixlen);
 335
 336         }
 337
 338         io->key-=level;
 339         io->keylen+=level;
 340         return res;
 341 }
 342
 343
 344 static SFSNode*
 345 enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd) {
 346         u_int32_t nchild=0, nchar=0, nfound=0, i;
 347         SFSNode *rs,**chld;
 348         SFSNodeData *data;
 349         int sizenode;
 350         char *dataptr;
 351
 352
 353         if ( node ) {
 354                 nchar=node->nchar;
 355                 nchild=node->nchild;
 356                 data=node->data;
 357
 358                 for(i=0;i<nchar;i++) {
 359                         nfound += data->isword;
 360                         data++;
 361                 }
 362         }
 363
 364         if ( node )
 365                 info->totalen -= SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
 366
 367         if ( flag & EN_VAL )   nchar++;
 368         if ( flag & EN_CHLD ) nchild++;
 369         if ( flag & EN_DATA )  nfound++;
 370
 371
 372         sizenode = SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
 373
 374         info->totalen+=sizenode;
 375         if ( !node ) info->nnodes++;
 376         rs=(SFSNode*)tmalloc(sizenode);
 377
 378         rs->isskip = 0;
 379         rs->nchar = nchar;
 380         rs->nchild = nchild;
 381         rs->dataptr=SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*);
 382         dataptr=((char*)rs) + rs->dataptr;
 383         chld = (SFSNode**)( ((char*)rs)+SFSNHRDSZ+nchar*sizeof(SFSNodeData) );
 384         data=rs->data;
 385
 386         if (node) {
 387                 SFSNode **ochld=(SFSNode**)( ((char*)node)+SFSNHRDSZ+node->nchar*sizeof(SFSNodeData) );
 388                 SFSNodeData *odata = node->data;
 389                 char *odataptr=((char*)node) + node->dataptr;
 390                 int wasins=0;
 391
 392                 for(i=0;i<node->nchar;i++) {
 393                         if ( val > odata->val ) {
 394                                 *(u_int32_t*)data = *(u_int32_t*)odata;
 395                                 if ( odata->haschild ) {
 396                                         *chld=*ochld;
 397                                         data->child = ((char*)chld) - ((char*)data);
 398                                         chld++; ochld++;
 399                                 }
 400                                 if ( odata->isword && info->datasize ) {
 401                                         memcpy(dataptr, odataptr, info->datasize);
 402                                         data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
 403                                         dataptr += info->datasize; odataptr += info->datasize;
 404                                 }
 405                                 data++; odata++;
 406                         } else if ( val == odata->val ) {
 407                                 tassert ( (flag&EN_VAL)==0 );
 408                                 *(u_int32_t*)data = *(u_int32_t*)odata;
 409                                 wasins=1;
 410                                 if ( odata->haschild || flag & EN_CHLD ) {
 411                                         if (odata->haschild) *chld=*ochld;
 412                                         data->child = ((char*)chld) - ((char*)data);
 413                                         data->haschild=1;
 414                                         chld++; if (odata->haschild) ochld++;
 415                                 } else
 416                                         data->haschild=0;
 417                                 if ( odata->isword || flag & EN_DATA ) {
 418                                         data->isword=1;
 419                                         if ( info->datasize && odata->isword ) {
 420                                                 memcpy(dataptr, odataptr, info->datasize);
 421                                                 odataptr += info->datasize;
 422                                         }
 423                                         data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
 424                                         dataptr += info->datasize;
 425                                 } else
 426                                         data->isword=0;
 427                                 *nd = data;
 428                                 data++; odata++;
 429                         } else {
 430                                 if ( wasins==0 ) {
 431                                         tassert ( flag&EN_VAL );
 432                                         data->val = val;
 433                                         if ( flag & EN_CHLD ) {
 434                                                 data->haschild=1;
 435                                                 data->child = ((char*)chld) - ((char*)data);
 436                                                 chld++;
 437                                         } else
 438                                                 data->haschild=0;
 439                                         if ( flag & EN_DATA ) {
 440                                                 data->isword=1;
 441                                                 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
 442                                                 dataptr += info->datasize;
 443                                         } else
 444                                                 data->isword=0;
 445                                         *nd = data;
 446                                         data++;
 447                                         wasins=1;
 448                                         i--;
 449                                 } else {
 450                                         *(u_int32_t*)data = *(u_int32_t*)odata;
 451                                         if ( odata->haschild ) {
 452                                                 *chld=*ochld;
 453                                                 data->child = ((char*)chld) - ((char*)data);
 454                                                 chld++; ochld++;
 455                                         }
 456                                         if ( odata->isword && info->datasize ) {
 457                                                 memcpy(dataptr, odataptr, info->datasize);
 458                                                 data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
 459                                                 dataptr += info->datasize; odataptr += info->datasize;
 460                                         }
 461                                         data++; odata++;
 462                                 }
 463                         }
 464                 }
 465                 if ( wasins==0 ) {
 466                         tassert ( flag&EN_VAL );
 467                         data->val = val;
 468                         if ( flag & EN_CHLD ) {
 469                                 data->haschild=1;
 470                                 data->child = ((char*)chld) - ((char*)data);
 471                                 chld++;
 472                         } else
 473                                 data->haschild=0;
 474                         if ( flag & EN_DATA ) {
 475                                 data->isword=1;
 476                                 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
 477                                 dataptr += info->datasize;
 478                         } else
 479                                 data->isword=0;
 480                         *nd = data;
 481                 }
 482         } else {
 483                 tassert ( flag & EN_VAL );
 484                 data->val = val;
 485                 if ( flag & EN_CHLD ) {
 486                         data->haschild=1;
 487                         data->child = ((char*)chld) - ((char*)data);
 488                 } else
 489                         data->haschild=0;
 490                 if ( flag & EN_DATA ) {
 491                         data->isword=1;
 492                         data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
 493                 } else
 494                         data->isword=0;
 495                 *nd = data;
 496         }
 497         if (node) tfree(node);
 498         return rs;
 499 }
 500
 501 static SFSNode*
 502 addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level) {
 503         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
 504         u_int8_t *ptr = ((u_int8_t*)in->key) + level;
 505
 506
 507         if ( node ) {
 508                 if ( node->isskip ) {
 509                         if ( node->haschild && in->keylen-level > node->nchar &&
 510                                         strncmp(in->key+level, ((char*)node)+node->dataptr, node->nchar)==0 )
 511                                 *(SFSNode**)( node->data ) = addRecord(info, *(SFSNode**)( node->data ), in, level+node->nchar);
 512                         else
 513                                 node = splitSkipNode(info, node, in, level);
 514                 } else {
 515                         StopLow = node->data;
 516                         StopHigh = StopLow + node->nchar;
 517                         while (StopLow < StopHigh) {
 518                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
 519                                 if ( StopMiddle->val == *ptr ) {
 520                                         if ( *(ptr+1)=='\0' ) {
 521                                                 if ( StopMiddle->isword ) {
 522                                                         /* already exists */
 523                                                         if ( info->datasize )
 524                                                                 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
 525                                                                         in->data, info->datasize );
 526                                                 } else {
 527                                                         /* not exist word */
 528                                                         if (info->datasize) {
 529                                                                 node = enlargeNode(info, node, *ptr, EN_DATA, &StopMiddle);
 530                                                                 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
 531                                                                         in->data, info->datasize );
 532                                                         }
 533                                                         StopMiddle->isword = 1;
 534                                                 }
 535                                         } else if ( StopMiddle->haschild ) {
 536                                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
 537                                                         addRecord(info, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), in, level+1);
 538                                         } else {
 539                                                 node = enlargeNode(info, node, *ptr, EN_CHLD, &StopMiddle);
 540                                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
 541                                                         makeSkipNode(info, in, level+1);
 542                                         }
 543                                         return node;
 544                                 } else if ( StopMiddle->val < *ptr ) {
 545                                         StopLow = StopMiddle + 1;
 546                                 } else {
 547                                         StopHigh = StopMiddle;
 548                                 }
 549                         }
 550                         if ( *(ptr+1)=='\0' ) {
 551                                 node = enlargeNode(info, node, *ptr, EN_VAL|EN_DATA, &StopMiddle);
 552                                 if ( info->datasize )
 553                                         memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
 554                                         in->data, info->datasize );
 555                         } else {
 556                                 node = enlargeNode(info, node, *ptr, EN_VAL|EN_CHLD, &StopMiddle);
 557                                 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
 558                                         makeSkipNode(info, in, level+1);
 559                         }
 560                 }
 561         } else
 562                 node = makeSkipNode(info, in, level);
 563
 564
 565         return node;
 566
 567 }
 568
 569 void
 570 SFSAdd(SFSTree *info, SFSDataIO *in) {
 571         if (in->keylen<=0)
 572                 in->keylen=strlen(in->key);
 573         info->node = addRecord(info, info->node, in, 0);
 574 }
 575
 576 static SFSNodeStack*
 577 pushStack(SFSNodeStack *top, SFSNode *node, int level ) {
 578         SFSNodeStack *r=(SFSNodeStack*)tmalloc(sizeof(SFSNodeStack));
 579
 580         r->next = top;
 581         r->node=node;
 582         r->data=node->data;
 583         r->level=level;
 584         r->checkedchild = 0;
 585         r->checkedval = 0;
 586
 587         return r;
 588 }
 589
 590 void
 591 SFSIteratorStart(SFSTree *info) {
 592         if ( !info->buf ) {
 593                 info->tlen = 32;
 594                 info->buf = (char*)tmalloc(info->tlen);
 595         }
 596         info->stack = pushStack(NULL, info->node, 0);
 597         info->hasword=0;
 598 }
 599
 600 void
 601 SFSPrefixIteratorStart(SFSTree *info, char *word) {
 602         SFSNode *node = info->node;
 603         SFSNodeData *StopLow, *StopHigh, *StopMiddle;
 604         u_int8_t *ptr =(u_int8_t*)word;
 605         int len,wlen=strlen(word);
 606
 607         if ( wlen+1>=info->tlen ) {
 608                 info->tlen = 2*wlen;
 609                 info->buf = (info->buf) ?
 610                                 (char*)trealloc(info->buf,info->tlen)
 611                         :
 612                                 (char*)tmalloc(info->tlen);
 613         }
 614
 615         info->hasword=0;
 616         while( node && *ptr) {
 617                 len = wlen - (((char*)ptr)-word);
 618                 if ( node->isskip ) {
 619                         if ( STRNCMP(ptr, ((char*)node)+node->dataptr, (len<node->nchar) ? len : node->nchar) ) {
 620                                 if ( len<=node->nchar ) {
 621                                         strcpy(info->buf,word);
 622                                         info->stack = pushStack(NULL, node, ((char*)ptr) - word);
 623                                         return;
 624                                 } else if ( node->haschild ) {
 625                                         ptr+=node->nchar;
 626                                         node = *(SFSNode**)(node->data);
 627                                 } else {
 628                                         return;
 629                                 }
 630                         } else
 631                                 return;
 632                 } else {
 633                         StopLow = node->data;
 634                         StopHigh = StopLow + node->nchar;
 635                         while (StopLow < StopHigh) {
 636                                 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
 637                                 if ( StopMiddle->val == *ptr ) {
 638                                         if ( *(ptr+1)=='\0' ) {
 639                                                 len =((char*)ptr)-word+1;
 640                                                 strcpy(info->buf,word);
 641                                                 if ( StopMiddle->isword ) {
 642                                                         info->hasword=1;
 643                                                         info->wdata = (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
 644                                                 }
 645                                                 if ( StopMiddle->haschild )
 646                                                         info->stack = pushStack(NULL, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), len);
 647                                                 return;
 648                                         } else if ( StopMiddle->haschild ) {
 649                                                 node=*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child );
 650                                         } else {
 651                                                 return;
 652                                         }
 653                                         ptr++;
 654                                         break;
 655                                 } else if ( StopMiddle->val < *ptr ) {
 656                                         StopLow = StopMiddle + 1;
 657                                 } else {
 658                                         StopHigh = StopMiddle;
 659                                 }
 660                         }
 661                         if ( StopLow >= StopHigh )
 662                                 break;
 663                 }
 664         }
 665         return;
 666 }
 667
 668 int
 669 SFSIterate(SFSTree *info, SFSDataIO *out) {
 670         SFSNodeStack *s=info->stack;
 671
 672         if ( info->hasword ) {
 673                 out->key = info->buf;
 674                 out->keylen = strlen(out->key);
 675                 out->data = info->wdata;
 676                 info->hasword = 0;
 677                 return 1;
 678         }
 679
 680         if ( s == NULL || s->node == NULL)
 681                 return 0;
 682
 683         while ( s->level + s->node->nchar + 1 >= info->tlen ) {
 684                 info->tlen *= 2;
 685                 info->buf = (char*)trealloc(info->buf, info->tlen);
 686         }
 687
 688         if ( s->node->isskip ) {
 689                 memcpy( info->buf + s->level, ((char*)s->node) + s->node->dataptr, s->node->nchar );
 690                 if ( s->node->isword && !s->checkedval) {
 691                         info->buf[ s->level+s->node->nchar ] = '\0';
 692                         out->key = info->buf;
 693                         out->keylen = s->level+s->node->nchar;
 694                         out->data =((char*)(s->node->data)) + ((s->node->haschild) ? sizeof(SFSNode*) : 0);
 695                         s->checkedval=1;
 696                         return 1;
 697                 }
 698                 if ( s->node->haschild && !s->checkedchild) {
 699                         info->stack = pushStack(s, *(SFSNode**)( (char*)(s->node->data) ), s->level+s->node->nchar);
 700                         s->checkedchild=1;
 701                         if ( SFSIterate(info, out) )
 702                                 return 1;
 703                 }
 704         } else {
 705                 while( s->data - s->node->data < s->node->nchar ) {
 706                         info->buf[ s->level ] = (char)s->data->val;
 707                         if ( s->checkedval==0 && s->data->isword ) {
 708                                 info->buf[ s->level+1 ] = '\0';
 709                                 out->key = info->buf;
 710                                 out->keylen = s->level+1;
 711                                 out->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
 712                                 s->checkedval = 1;
 713                                 return 1;
 714                         }
 715                         if ( s->checkedchild==0 && s->data->haschild ) {
 716                                 info->stack = pushStack(s, *(SFSNode**)( ((char*)s->data) + s->data->child ), s->level+1);
 717                                 s->checkedchild=1;
 718                                 if ( SFSIterate(info, out) )
 719                                         return 1;
 720                         }
 721                         s->checkedval = s->checkedchild = 0;
 722                         s->data++;
 723                 }
 724         }
 725         info->stack = s->next;
 726         tfree(s);
 727
 728         return SFSIterate(info, out);
 729 }
 730
 731 int
 732 SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l) {
 733         SFSNodeStack *s=info->stack;
 734
 735         SFSPrefixIteratorStart(info, word);
 736         s=info->stack;
 737
 738         if ( SFSIterate(info, f) ) {
 739                 SFSNodeStack *sptr = info->stack, *stmp;
 740                 while( sptr && sptr!=s ) {
 741                         stmp=sptr->next;
 742                         tfree(sptr);
 743                         sptr=stmp;
 744                 }
 745
 746                 if ( s == NULL ) {
 747                         memcpy(l,f,sizeof(SFSDataIO));
 748                         return 1;
 749                 }
 750         } else
 751                 return 0;
 752
 753         info->stack=NULL;
 754
 755         while( f->keylen +  s->level + 2 >= info->tlen ) {
 756                 info->tlen *= 2;
 757                 info->buf = (char*)trealloc(info->buf, info->tlen);
 758         }
 759
 760         f->key = info->buf;
 761         l->key = info->buf + f->keylen + 1;
 762         memcpy(l->key, f->key, f->keylen + 1);
 763
 764         while(s->node) {
 765                 while( f->keylen + 1 + s->level + s->node->nchar + 1 >= info->tlen ) {
 766                         info->tlen *= 2;
 767                         info->buf = (char*)trealloc(info->buf, info->tlen);
 768                 }
 769                 if ( s->node->isskip ) {
 770                         memcpy(info->buf + f->keylen + 1 + s->level,
 771                                 ((char*)(s->node))+s->node->dataptr, s->node->nchar);
 772                         s->level+=s->node->nchar;
 773                         if (s->node->haschild) {
 774                                 s->node=*(SFSNode**)( s->node->data );
 775                         } else { /* if (s->node->isword) */
 776                                 info->buf[ f->keylen + 1 + s->level + 1 ] = '\0';
 777                                 l->data = (void*)(s->node->data);
 778                                 l->keylen = s->level+1;
 779                                 break;
 780                         }
 781                 } else {
 782                         s->data = s->node->data + s->node->nchar - 1;
 783                         while( s->data - s->node->data >= 0 ) {
 784                                 info->buf[ f->keylen + 1 + s->level ] = (char)s->data->val;
 785                                 if ( s->data->haschild ) {
 786                                         s->node = *(SFSNode**)( ((char*)s->data) + s->data->child );
 787                                         s->level++;
 788                                         break;
 789                                 }
 790                                 if ( s->data->isword ) {
 791                                         info->buf[ f->keylen + 1 + s->level+1 ] = '\0';
 792                                         l->keylen = s->level+1;
 793                                         l->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
 794                                         s->node=NULL;
 795                                         break;
 796                                 }
 797                                 s->data--;
 798                         }
 799                 }
 800         }
 801         f->key = info->buf;
 802         l->key = info->buf + f->keylen + 1;
 803         tfree(s);
 804
 805         return 1;
 806 }