2 * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
32 #include <sys/types.h>
47 #define SFSTREE_VERSION 0x0100
49 typedef unsigned long Opaque; /* XXX sizeof(Opaque) == sizeof(void *) */
51 #define CHECK_MEMORY(tree) ( ( (tree)->plainmemory ) ? \
52 tlog(TL_CRIT|TL_EXIT, "Tree in plain memory - read only access") : (void)0 )
55 getNodeSize(SFSTree *info, SFSNode *node) {
60 size += info->datasize;
62 size += sizeof(SFSNode*);
67 SFSNodeData *data = node->data;
69 size += sizeof(SFSNodeData) * node->nchar;
70 size += sizeof(SFSNode*) * node->nchild;
72 for(i=0;i<node->nchar;i++)
73 nfound += data[i].isword;
75 size += nfound*info->datasize;
78 return PTRALIGN(size);
81 static __inline__ SFSNode*
82 getChildPointer(SFSTree *info, SFSNodeData *nodedata) {
83 char *p = ((char*)nodedata) + nodedata->child;
85 if ( info->plainmemory )
86 return (SFSNode*) ( ((char*)(info->node)) + *(Opaque*)p );
91 static __inline__ SFSNode*
92 getSkipChildPointer(SFSTree *info, SFSNode *node) {
93 if ( info->plainmemory )
94 return (SFSNode*) ( ((char*)(info->node)) + *(Opaque*)node->data );
96 return *(SFSNode**)( (char*)(node->data) );
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);
102 #define STRNCMP(p1,p2,n) ( ((n)==1) ? ( *((char*)(p1))==*((char*)(p2)) ) : (strncmp((char*)(p1), (char*)(p2), (n))==0) )
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);
110 info=(SFSTree*)tmalloc(sizeof(SFSTree));
111 memset(info,0,sizeof(SFSTree));
113 info->datasize = datasize;
115 while(in && in->key) {
124 SFSInit_c(SFSTree *info, char **in) {
129 info=(SFSTree*)tmalloc(sizeof(SFSTree));
130 memset(info,0,sizeof(SFSTree));
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;
148 while( node && *ptr ) {
149 if ( node->isskip ) {
150 if ( STRNCMP(ptr, ((char*)node)+node->dataptr, 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);
162 StopLow = node->data;
163 StopHigh = StopLow + node->nchar;
164 while (StopLow < StopHigh) {
165 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
166 if ( StopMiddle->val == *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);
176 } else if ( StopMiddle->val < *ptr ) {
177 StopLow = StopMiddle + 1;
179 StopHigh = StopMiddle;
182 if ( StopLow >= StopHigh )
190 freeFSFNode(SFSTree *info, SFSNode *node, void (*freefunc)(void*)) {
193 if ( node->isskip ) {
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 ) );
199 SFSNodeData *nd = node->data;
200 char *data= ((char*)node) + node->dataptr;
202 for(i=0;i<node->nchar;i++) {
204 freeFSFNode(info, *(SFSNode**)( ((char*)nd) + nd->child ), freefunc);
205 if (freefunc && nd->isword && info->datasize) {
206 (*freefunc)( (void*)data );
207 data+=info->datasize;
217 SFSFree(SFSTree *info, void (*freefunc)(void*)) {
218 SFSNodeStack *s=info->stack;
220 if (info->node && !info->plainmemory) freeFSFNode(info, info->node, freefunc);
221 if (info->buf) tfree(info->buf);
234 makeSkipNode(SFSTree *info, SFSDataIO *io, int level) {
242 len = (io->keylen > 255) ? 255 : io->keylen;
243 size = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize) + len;
244 size = PTRALIGN(size);
246 res = (SFSNode*)tmalloc(size);
252 res->dataptr = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize);
253 memcpy(((char*)res) + res->dataptr, io->key, len);
255 if ( io->keylen > 255 ) {
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;
266 if (info->datasize) {
267 memcpy( res->data, io->data, info->datasize );
278 splitSkipNode(SFSTree *info, SFSNode* node, SFSDataIO *io, int level) {
284 tassert(node->isskip);
288 s1=((char*)node) + node->dataptr;
291 while( s1 - (((char*)node) + node->dataptr) < node->nchar && s2 - io->key < io->keylen && *s1==*s2) {
296 prefixlen = s2 - io->key;
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 )
305 ((char*)res) + res->dataptr + info->datasize * ndata->data,
306 ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0),
310 if ( node->haschild )
311 *(SFSNode**)( ((char*)ndata) + ndata->child ) = *(SFSNode**)( node->data );
312 info->totalen -= getNodeSize(info, node);
318 res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), EN_VAL|EN_CHLD, &ndata);
320 size = getNodeSize(info,node);
324 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + 1, node->nchar);
326 size = getNodeSize(info,node);
329 *(SFSNode**)( ((char*)ndata) + ndata->child ) = (SFSNode*)trealloc(node, size);
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) {
336 memcpy( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNodeData*) : 0),
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);
345 info->totalen += nsize - osize;
347 res=(SFSNode*)trealloc(node,nsize);
348 res->dataptr=SFSNHRDSZ + info->datasize + ((res->haschild) ? sizeof(SFSNodeData*) : 0);
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);
355 int size = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*) + prefixlen;
356 size = PTRALIGN(size);
360 res = (SFSNode*)tmalloc(size);
364 res->nchar = prefixlen;
365 res->dataptr = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*);
366 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
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);
374 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, size);
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);
382 res->dataptr+=sizeof(SFSNode*);
383 *(SFSNode**)(res->data) = makeSkipNode(info, io, prefixlen);
385 int size = SFSNHRDSZ + sizeof(SFSNodeData*) + prefixlen;
386 size = PTRALIGN(size);
389 res = (SFSNode*)tmalloc(size);
393 res->nchar = prefixlen;
394 res->dataptr = SFSNHRDSZ + sizeof(SFSNodeData*);
395 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
397 info->totalen-= getNodeSize(info,node);
398 node->nchar-=prefixlen;
400 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
402 size = getNodeSize(info,node);
403 info->totalen+= size;
405 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, size);
406 *(SFSNode**)(res->data) = splitSkipNode(info, *(SFSNode**)(res->data), io, prefixlen);
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;
429 for(i=0;i<nchar;i++) {
430 nfound += data->isword;
436 /*info->totalen -= PTRALIGN(SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize);*/
437 info->totalen -= getNodeSize(info, node);
439 if ( flag & EN_VAL ) nchar++;
440 if ( flag & EN_CHLD ) nchild++;
441 if ( flag & EN_DATA ) nfound++;
444 sizenode = SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
445 sizenode = PTRALIGN(sizenode);
447 info->totalen+=sizenode;
448 if ( !node ) info->nnodes++;
449 rs=(SFSNode*)tmalloc(sizenode);
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) );
460 SFSNode **ochld=(SFSNode**)( ((char*)node)+SFSNHRDSZ+node->nchar*sizeof(SFSNodeData) );
461 SFSNodeData *odata = node->data;
462 char *odataptr=((char*)node) + node->dataptr;
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 ) {
470 data->child = ((char*)chld) - ((char*)data);
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;
479 } else if ( val == odata->val ) {
480 tassert ( (flag&EN_VAL)==0 );
481 *(u_int32_t*)data = *(u_int32_t*)odata;
483 if ( odata->haschild || flag & EN_CHLD ) {
484 if (odata->haschild) *chld=*ochld;
485 data->child = ((char*)chld) - ((char*)data);
487 chld++; if (odata->haschild) ochld++;
490 if ( odata->isword || flag & EN_DATA ) {
492 if ( info->datasize && odata->isword ) {
493 memcpy(dataptr, odataptr, info->datasize);
494 odataptr += info->datasize;
496 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
497 dataptr += info->datasize;
504 tassert ( flag&EN_VAL );
506 if ( flag & EN_CHLD ) {
508 data->child = ((char*)chld) - ((char*)data);
512 if ( flag & EN_DATA ) {
514 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
515 dataptr += info->datasize;
523 *(u_int32_t*)data = *(u_int32_t*)odata;
524 if ( odata->haschild ) {
526 data->child = ((char*)chld) - ((char*)data);
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;
539 tassert ( flag&EN_VAL );
541 if ( flag & EN_CHLD ) {
543 data->child = ((char*)chld) - ((char*)data);
547 if ( flag & EN_DATA ) {
549 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
550 dataptr += info->datasize;
556 tassert ( flag & EN_VAL );
558 if ( flag & EN_CHLD ) {
560 data->child = ((char*)chld) - ((char*)data);
563 if ( flag & EN_DATA ) {
565 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
570 if (node) tfree(node);
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;
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);
585 node = splitSkipNode(info, node, in, level);
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 ) {
595 if ( info->datasize )
596 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
597 in->data, info->datasize );
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 );
605 StopMiddle->isword = 1;
607 } else if ( StopMiddle->haschild ) {
608 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
609 addRecord(info, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), in, level+1);
611 node = enlargeNode(info, node, *ptr, EN_CHLD, &StopMiddle);
612 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
613 makeSkipNode(info, in, level+1);
616 } else if ( StopMiddle->val < *ptr ) {
617 StopLow = StopMiddle + 1;
619 StopHigh = StopMiddle;
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 );
628 node = enlargeNode(info, node, *ptr, EN_VAL|EN_CHLD, &StopMiddle);
629 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
630 makeSkipNode(info, in, level+1);
634 node = makeSkipNode(info, in, level);
641 SFSAdd(SFSTree *info, SFSDataIO *in) {
644 in->keylen=strlen(in->key);
645 info->node = addRecord(info, info->node, in, 0);
649 pushStack(SFSNodeStack *top, SFSNode *node, int level ) {
650 SFSNodeStack *r=(SFSNodeStack*)tmalloc(sizeof(SFSNodeStack));
663 SFSIteratorStart(SFSTree *info) {
666 info->buf = (char*)tmalloc(info->tlen);
668 info->stack = pushStack(NULL, info->node, 0);
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);
679 if ( wlen+1>=info->tlen ) {
681 info->buf = (info->buf) ?
682 (char*)trealloc(info->buf,info->tlen)
684 (char*)tmalloc(info->tlen);
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);
696 } else if ( node->haschild ) {
698 node = getSkipChildPointer(info, node);
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 ) {
715 info->wdata = (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
717 if ( StopMiddle->haschild )
718 info->stack = pushStack(NULL, getChildPointer( info, StopMiddle ), len);
720 } else if ( StopMiddle->haschild ) {
721 node = getChildPointer( info, StopMiddle );
727 } else if ( StopMiddle->val < *ptr ) {
728 StopLow = StopMiddle + 1;
730 StopHigh = StopMiddle;
733 if ( StopLow >= StopHigh )
741 SFSIterate(SFSTree *info, SFSDataIO *out) {
742 SFSNodeStack *s=info->stack;
744 if ( info->hasword ) {
745 out->key = info->buf;
746 out->keylen = strlen(out->key);
747 out->data = info->wdata;
752 if ( s == NULL || s->node == NULL)
755 while ( s->level + s->node->nchar + 1 >= info->tlen ) {
757 info->buf = (char*)trealloc(info->buf, info->tlen);
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);
770 if ( s->node->haschild && !s->checkedchild) {
771 info->stack = pushStack(s, getSkipChildPointer(info, s->node), s->level+s->node->nchar);
773 if ( SFSIterate(info, out) )
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;
787 if ( s->checkedchild==0 && s->data->haschild ) {
788 info->stack = pushStack(s,
789 getChildPointer( info, s->data ), s->level+1);
791 if ( SFSIterate(info, out) )
794 s->checkedval = s->checkedchild = 0;
798 info->stack = s->next;
801 return SFSIterate(info, out);
805 SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l) {
806 SFSNodeStack *s=info->stack;
808 SFSPrefixIteratorStart(info, word);
811 if ( SFSIterate(info, f) ) {
812 SFSNodeStack *sptr = info->stack, *stmp;
813 while( sptr && sptr!=s ) {
820 memcpy(l,f,sizeof(SFSDataIO));
828 while( f->keylen + s->level + 2 >= info->tlen ) {
830 info->buf = (char*)trealloc(info->buf, info->tlen);
834 l->key = info->buf + f->keylen + 1;
835 memcpy(l->key, f->key, f->keylen + 1);
838 while( f->keylen + 1 + s->level + s->node->nchar + 1 >= info->tlen ) {
840 info->buf = (char*)trealloc(info->buf, info->tlen);
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;
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 );
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;
875 l->key = info->buf + f->keylen + 1;
881 typedef struct WorkPlain {
888 plainNode(WorkPlain *wp, SFSNode *node) {
889 int size = getNodeSize(wp->info, node);
890 off_t myoffset = wp->offset;
892 memcpy( wp->node + wp->offset, node, size );
895 tassert( wp->offset <= wp->info->totalen );
897 if ( node->isskip ) {
899 *(Opaque*)(wp->node + myoffset + SFSNHRDSZ) =
900 plainNode(wp, getSkipChildPointer(wp->info, node));
902 SFSNodeData *nd = node->data;
905 for(i=0;i<node->nchar;i++) {
907 *(Opaque*)(wp->node + myoffset + ( ((char*)nd) - ((char*)node) ) + nd->child) =
908 plainNode(wp, getChildPointer( wp->info, nd ) );
919 SFSMakePlain(SFSTree *info, void *pointer) {
922 if ( info->plainmemory )
928 wp.node = (char*)pointer;
930 wp.node = (char*)tmalloc(sizeof(char*) * info->totalen);
932 plainNode(&wp, info->node);
933 tassert( wp.offset == info->totalen );
935 info->node = (SFSNode*)wp.node;
936 info->plainmemory = 1;
940 revertNode(SFSTree *info, SFSNode* node) {
941 int size = getNodeSize(info, node);
944 newnode = (SFSNode*)tmalloc( size );
945 memcpy(newnode, node, size);
947 if ( node->isskip ) {
949 *(SFSNode**)( (char*)(newnode->data) ) =
950 revertNode(info, getSkipChildPointer(info, node));
952 SFSNodeData *nd = node->data;
953 SFSNodeData *nnd = newnode->data;
956 for(i=0;i<node->nchar;i++) {
958 *(SFSNode**) (((char*)nnd) + nnd->child ) =
959 revertNode(info, getChildPointer( info, nd ));
968 SFSRevertPlain(SFSTree *info) {
969 void *pointer = info->node;
971 if (! info->plainmemory )
974 info->node = revertNode(info, info->node);
975 info->plainmemory = 0;
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;
986 memcpy( wnode, node, size );
989 tassert( wp->offset <= wp->info->totalen );
991 if ( node->isskip ) {
993 *(Opaque*)( ((char*)wnode) + SFSNHRDSZ) =
994 writeNode(wp, fd, getSkipChildPointer(wp->info, node), extrasize);
996 SFSNodeData *nd = node->data;
999 for(i=0;i<node->nchar;i++) {
1001 *(Opaque*)(((char*)wnode) + ( ((char*)nd) - ((char*)node) ) + nd->child) =
1002 writeNode(wp, fd, getChildPointer( wp->info, nd ), extrasize );
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));
1018 SFSWriteDump(SFSTree *info, char *filename, void *extradata, u_int32_t extrasize) {
1020 off_t size = info->totalen + SFSTDHSZ;
1021 SFSTreeDumpHeader dh;
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", filename, strerror(errno));
1026 if ( flock(fd, LOCK_EX) < 0 )
1027 tlog(TL_CRIT|TL_EXIT, "flock failed: %s", strerror(errno));
1029 if ( extrasize == 0 )
1031 else if ( extradata == NULL )
1034 if ( lseek(fd, size + MAXALIGN(extrasize) , SEEK_SET) < 0 )
1035 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
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;
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));
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));
1058 extrasize = MAXALIGN(extrasize);
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));
1071 writeNode(&wp, fd, info->node, extrasize);
1079 readNode(SFSTree *info, int fd, char *buf, int bufsize, int extrasize) {
1083 size = read(fd, buf, bufsize );
1084 if ( size < SFSNHRDSZ + sizeof(void*) )
1085 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1087 size = getNodeSize(info, (SFSNode*)buf);
1088 tassert( size <= bufsize );
1089 node = (SFSNode*)tmalloc( size );
1090 memcpy(node, buf, size);
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);
1100 SFSNodeData *nd = node->data;
1103 for(i=0;i<node->nchar;i++) {
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);
1118 SFSReadDump(SFSTree *info, char *filename, void **extradata, u_int32_t *extrasize) {
1120 SFSTreeDumpHeader dh;
1129 memset(info,0,sizeof(SFSTree));
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));
1136 if ( read(fd, &dh, SFSTDHSZ) != SFSTDHSZ )
1137 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
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);
1146 info->totalen = dh.totalen;
1147 info->nnodes = dh.nnodes;
1148 info->datasize = dh.datasize;
1150 if ( dh.extrasize ) {
1151 void *pointer = tmalloc( MAXALIGN(dh.extrasize) );
1153 if ( read(fd, pointer, MAXALIGN(dh.extrasize)) != MAXALIGN(dh.extrasize) )
1154 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1157 *extradata = pointer;
1162 *extrasize = dh.extrasize;
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));
1176 SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size, void **extradata, u_int32_t *extrasize) {
1177 SFSTreeDumpHeader *dh;
1184 memset(info,0,sizeof(SFSTree));
1186 if ( size && size < SFSTDHSZ )
1187 tlog(TL_CRIT|TL_EXIT, "Memsize too small");
1189 dh = (SFSTreeDumpHeader*)pointer;
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);
1200 info->totalen = dh->totalen;
1201 info->nnodes = dh->nnodes;
1202 info->datasize = dh->datasize;
1203 info->plainmemory = 1;
1205 if ( dh->extrasize ) {
1207 *extradata = ((char*)pointer) + SFSTDHSZ;
1210 *extrasize = dh->extrasize;
1213 if ( info->totalen && info->nnodes )
1214 info->node = (SFSNode*)( ((char*)pointer) + SFSTDHSZ + MAXALIGN(dh->extrasize) );