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.
33 #include <sys/types.h>
48 #define SFSTREE_VERSION 0x0100
50 typedef uintptr_t Opaque; /* XXX sizeof(Opaque) == sizeof(void *) */
52 #define CHECK_MEMORY(tree) ( ( (tree)->plainmemory ) ? \
53 tlog(TL_CRIT|TL_EXIT, "Tree in plain memory - read only access") : (void)0 )
56 getNodeSize(SFSTree *info, SFSNode *node) {
61 size += info->datasize;
63 size += sizeof(SFSNode*);
68 SFSNodeData *data = node->data;
70 size += sizeof(SFSNodeData) * node->nchar;
71 size += sizeof(SFSNode*) * node->nchild;
73 for(i=0;i<node->nchar;i++)
74 nfound += data[i].isword;
76 size += nfound*info->datasize;
79 return PTRALIGN(size);
82 static __inline__ SFSNode*
83 getChildPointer(SFSTree *info, SFSNodeData *nodedata) {
84 char *p = ((char*)nodedata) + nodedata->child;
86 if ( info->plainmemory )
87 return (SFSNode*) ( ((char*)(info->node)) + *(Opaque*)p );
92 static __inline__ SFSNode*
93 getSkipChildPointer(SFSTree *info, SFSNode *node) {
94 if ( info->plainmemory )
95 return (SFSNode*) ( ((char*)(info->node)) + *(Opaque*)node->data );
97 return *(SFSNode**)( (char*)(node->data) );
100 static SFSNode* enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd);
101 static SFSNode* addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level);
103 #define STRNCMP(p1,p2,n) ( ((n)==1) ? ( *((char*)(p1))==*((char*)(p2)) ) : (strncmp((char*)(p1), (char*)(p2), (n))==0) )
106 SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in) {
107 if ( datasize % sizeof(u_int32_t) )
108 tlog(TL_ALARM|TL_EXIT,"SFSInit_dp: datasize(%d) should be divided by sizeof(u_int32_t)", datasize);
111 info=(SFSTree*)tmalloc(sizeof(SFSTree));
112 memset(info,0,sizeof(SFSTree));
114 info->datasize = datasize;
116 while(in && in->key) {
125 SFSInit_c(SFSTree *info, char **in) {
130 info=(SFSTree*)tmalloc(sizeof(SFSTree));
131 memset(info,0,sizeof(SFSTree));
143 #define ISEND(p,w,l) ( (l>0) ? ( ((char*)(p))-(w) >= (l) ) : ( *(p) == '\0' ) )
146 SFSFindData(SFSTree *info, char *word, int len) {
152 return SFSFindDataFromSavedOrSave(info, &in, NULL);
156 SFSFindDataOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position) {
158 memset(position, 0, sizeof(SFSTreePosition));
160 return SFSFindDataFromSavedOrSave(info, in, position);
164 SFSFindDataFromSavedOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position) {
165 SFSNode *node = info->node;
166 SFSNode **pnode = &(info->node);
167 SFSNodeData *StopLow, *StopHigh, *StopMiddle;
168 u_int8_t *ptr =(u_int8_t*)in->key;
170 if ( position && position->nodeptr && position->node && in->keylen > position->level ) {
171 node = position->node;
172 pnode = position->nodeptr;
173 ptr += position->level;
176 while( node && !ISEND(ptr, in->key, in->keylen) ) {
178 position->nodeptr = pnode;
179 position->node = node;
180 position->level = ((char*)ptr) - in->key;
183 if ( node->isskip ) {
184 if ( in->keylen>0 && in->keylen - (((char*)ptr) - in->key) < node->nchar )
186 else if ( STRNCMP(ptr, ((char*)node)+node->dataptr, node->nchar) ) {
188 if ( ISEND(ptr, in->key, in->keylen) ) {
190 return (void*) ( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0) );
192 } else if ( node->haschild ) {
193 pnode = (SFSNode**)( (char*)(node->data) );
194 node = getSkipChildPointer(info, node);
201 StopLow = node->data;
202 StopHigh = StopLow + node->nchar;
203 while (StopLow < StopHigh) {
204 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
205 if ( StopMiddle->val == *ptr ) {
207 if ( ISEND(ptr, in->key, in->keylen) ) {
208 if ( StopMiddle->isword )
209 return (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
211 } else if ( StopMiddle->haschild ) {
212 pnode = (SFSNode**)(((char*)StopMiddle) + StopMiddle->child);
213 node = getChildPointer(info, StopMiddle);
218 } else if ( StopMiddle->val < *ptr ) {
219 StopLow = StopMiddle + 1;
221 StopHigh = StopMiddle;
224 if ( StopLow >= StopHigh )
232 SFSAddSaved(SFSTree *info, SFSDataIO *in, SFSTreePosition *position) {
235 if ( !(position && position->nodeptr && position->node) ) {
240 position->node = *(position->nodeptr) = addRecord(info, position->node, in, position->level);
244 freeFSFNode(SFSTree *info, SFSNode *node, void (*freefunc)(void*)) {
247 if ( node->isskip ) {
249 freeFSFNode(info, *(SFSNode**)(node->data), freefunc);
250 if (freefunc && node->isword && info->datasize)
251 (*freefunc)( (void*)( ((char*)(node->data))+ (node->haschild) ? sizeof(SFSNode*) : 0 ) );
253 SFSNodeData *nd = node->data;
254 char *data= ((char*)node) + node->dataptr;
256 for(i=0;i<node->nchar;i++) {
258 freeFSFNode(info, *(SFSNode**)( ((char*)nd) + nd->child ), freefunc);
259 if (freefunc && nd->isword && info->datasize) {
260 (*freefunc)( (void*)data );
261 data+=info->datasize;
271 SFSFree(SFSTree *info, void (*freefunc)(void*)) {
272 SFSNodeStack *s=info->stack;
274 if (info->node && !info->plainmemory) freeFSFNode(info, info->node, freefunc);
275 if (info->buf) tfree(info->buf);
288 makeSkipNode(SFSTree *info, SFSDataIO *io, int level) {
296 len = (io->keylen > 255) ? 255 : io->keylen;
297 size = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize) + len;
298 size = PTRALIGN(size);
300 res = (SFSNode*)tmalloc(size);
306 res->dataptr = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize);
307 memcpy(((char*)res) + res->dataptr, io->key, len);
309 if ( io->keylen > 255 ) {
312 io->key = io->key+len;
313 io->keylen = io->keylen - len;
314 *(SFSNode**)(res->data) = makeSkipNode(info, io, 0);
315 io->key = io->key-len;
316 io->keylen = io->keylen + len;
320 if (info->datasize) {
321 memcpy( res->data, io->data, info->datasize );
332 splitSkipNode(SFSTree *info, SFSNode* node, SFSDataIO *io, int level) {
338 tassert(node->isskip);
342 s1=((char*)node) + node->dataptr;
345 while( s1 - (((char*)node) + node->dataptr) < node->nchar && s2 - io->key < io->keylen && *s1==*s2) {
350 prefixlen = s2 - io->key;
352 if ( prefixlen==0 ) {
353 if ( node->nchar == 1 ) {
354 int flag = EN_VAL | ((node->isword) ? EN_DATA : 0) | ((node->haschild) ? EN_CHLD : 0);
355 res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), flag, &ndata);
356 if ( node->isword ) {
357 if ( info->datasize )
359 ((char*)res) + res->dataptr + info->datasize * ndata->data,
360 ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0),
364 if ( node->haschild )
365 *(SFSNode**)( ((char*)ndata) + ndata->child ) = *(SFSNode**)( node->data );
366 info->totalen -= getNodeSize(info, node);
372 res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), EN_VAL|EN_CHLD, &ndata);
374 size = getNodeSize(info,node);
378 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + 1, node->nchar);
380 size = getNodeSize(info,node);
383 *(SFSNode**)( ((char*)ndata) + ndata->child ) = (SFSNode*)trealloc(node, size);
385 res = addRecord(info, res, io, 0);
386 } else if (prefixlen==io->keylen) {
387 if (prefixlen==node->nchar) {
388 if ( node->isword || info->datasize==0) {
390 memcpy( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNodeData*) : 0),
396 int osize = PTRALIGN(SFSNHRDSZ + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
397 int nsize = PTRALIGN(SFSNHRDSZ + info->datasize + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
399 info->totalen += nsize - osize;
401 res=(SFSNode*)trealloc(node,nsize);
402 res->dataptr=SFSNHRDSZ + info->datasize + ((res->haschild) ? sizeof(SFSNodeData*) : 0);
404 memmove(((char*)res) + res->dataptr,
405 ((char*)(res->data)) + ((res->haschild) ? sizeof(SFSNodeData*) : 0), res->nchar);
406 memcpy(((char*)(res->data)) + ((res->haschild) ? sizeof(SFSNodeData*) : 0), io->data, info->datasize);
409 int size = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*) + prefixlen;
410 size = PTRALIGN(size);
414 res = (SFSNode*)tmalloc(size);
418 res->nchar = prefixlen;
419 res->dataptr = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*);
420 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
422 memcpy(((char*)(res->data)) + sizeof(SFSNodeData*), io->data, info->datasize);
423 info->totalen-=getNodeSize(info,node);
424 node->nchar-=prefixlen;
425 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
426 size = getNodeSize(info,node);
428 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, size);
430 } else if ( prefixlen==node->nchar ) {
431 int size = SFSNHRDSZ + info->datasize + sizeof(SFSNode*) + node->nchar;
432 info->totalen+=sizeof(SFSNode*);
433 res=(SFSNode*)trealloc(node,size);
434 memmove( ((char*)(res->data)) + sizeof(SFSNode*), res->data, info->datasize + res->nchar);
436 res->dataptr+=sizeof(SFSNode*);
437 *(SFSNode**)(res->data) = makeSkipNode(info, io, prefixlen);
439 int size = SFSNHRDSZ + sizeof(SFSNodeData*) + prefixlen;
440 size = PTRALIGN(size);
443 res = (SFSNode*)tmalloc(size);
447 res->nchar = prefixlen;
448 res->dataptr = SFSNHRDSZ + sizeof(SFSNodeData*);
449 memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
451 info->totalen-= getNodeSize(info,node);
452 node->nchar-=prefixlen;
454 memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
456 size = getNodeSize(info,node);
457 info->totalen+= size;
459 *(SFSNode**)(res->data) = (SFSNode*)trealloc(node, size);
460 *(SFSNode**)(res->data) = splitSkipNode(info, *(SFSNode**)(res->data), io, prefixlen);
470 enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd) {
471 u_int32_t nchild=0, nchar=0, nfound=0, i;
483 for(i=0;i<nchar;i++) {
484 nfound += data->isword;
490 /*info->totalen -= PTRALIGN(SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize);*/
491 info->totalen -= getNodeSize(info, node);
493 if ( flag & EN_VAL ) nchar++;
494 if ( flag & EN_CHLD ) nchild++;
495 if ( flag & EN_DATA ) nfound++;
498 sizenode = SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;
499 sizenode = PTRALIGN(sizenode);
501 info->totalen+=sizenode;
502 if ( !node ) info->nnodes++;
503 rs=(SFSNode*)tmalloc(sizenode);
508 rs->dataptr=SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*);
509 dataptr=((char*)rs) + rs->dataptr;
510 chld = (SFSNode**)( ((char*)rs)+SFSNHRDSZ+nchar*sizeof(SFSNodeData) );
514 SFSNode **ochld=(SFSNode**)( ((char*)node)+SFSNHRDSZ+node->nchar*sizeof(SFSNodeData) );
515 SFSNodeData *odata = node->data;
516 char *odataptr=((char*)node) + node->dataptr;
519 for(i=0;i<node->nchar;i++) {
520 if ( val > odata->val ) {
521 *(u_int32_t*)data = *(u_int32_t*)odata;
522 if ( odata->haschild ) {
524 data->child = ((char*)chld) - ((char*)data);
527 if ( odata->isword && info->datasize ) {
528 memcpy(dataptr, odataptr, info->datasize);
529 data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
530 dataptr += info->datasize; odataptr += info->datasize;
533 } else if ( val == odata->val ) {
534 tassert ( (flag&EN_VAL)==0 );
535 *(u_int32_t*)data = *(u_int32_t*)odata;
537 if ( odata->haschild || flag & EN_CHLD ) {
538 if (odata->haschild) *chld=*ochld;
539 data->child = ((char*)chld) - ((char*)data);
541 chld++; if (odata->haschild) ochld++;
544 if ( odata->isword || flag & EN_DATA ) {
546 if ( info->datasize && odata->isword ) {
547 memcpy(dataptr, odataptr, info->datasize);
548 odataptr += info->datasize;
550 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
551 dataptr += info->datasize;
558 tassert ( flag&EN_VAL );
560 if ( flag & EN_CHLD ) {
562 data->child = ((char*)chld) - ((char*)data);
566 if ( flag & EN_DATA ) {
568 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
569 dataptr += info->datasize;
577 *(u_int32_t*)data = *(u_int32_t*)odata;
578 if ( odata->haschild ) {
580 data->child = ((char*)chld) - ((char*)data);
583 if ( odata->isword && info->datasize ) {
584 memcpy(dataptr, odataptr, info->datasize);
585 data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
586 dataptr += info->datasize; odataptr += info->datasize;
593 tassert ( flag&EN_VAL );
595 if ( flag & EN_CHLD ) {
597 data->child = ((char*)chld) - ((char*)data);
601 if ( flag & EN_DATA ) {
603 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
604 dataptr += info->datasize;
610 tassert ( flag & EN_VAL );
612 if ( flag & EN_CHLD ) {
614 data->child = ((char*)chld) - ((char*)data);
617 if ( flag & EN_DATA ) {
619 data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
624 if (node) tfree(node);
629 addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level) {
630 SFSNodeData *StopLow, *StopHigh, *StopMiddle;
631 u_int8_t *ptr = ((u_int8_t*)in->key) + level;
634 if ( node->isskip ) {
635 if ( node->haschild && in->keylen-level > node->nchar &&
636 strncmp(in->key+level, ((char*)node)+node->dataptr, node->nchar)==0 )
637 *(SFSNode**)( node->data ) = addRecord(info, *(SFSNode**)( node->data ), in, level+node->nchar);
639 node = splitSkipNode(info, node, in, level);
641 StopLow = node->data;
642 StopHigh = StopLow + node->nchar;
643 while (StopLow < StopHigh) {
644 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
645 if ( StopMiddle->val == *ptr ) {
646 if ( *(ptr+1)=='\0' ) {
647 if ( StopMiddle->isword ) {
649 if ( info->datasize )
650 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
651 in->data, info->datasize );
654 if (info->datasize) {
655 node = enlargeNode(info, node, *ptr, EN_DATA, &StopMiddle);
656 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
657 in->data, info->datasize );
659 StopMiddle->isword = 1;
661 } else if ( StopMiddle->haschild ) {
662 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
663 addRecord(info, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), in, level+1);
665 node = enlargeNode(info, node, *ptr, EN_CHLD, &StopMiddle);
666 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
667 makeSkipNode(info, in, level+1);
670 } else if ( StopMiddle->val < *ptr ) {
671 StopLow = StopMiddle + 1;
673 StopHigh = StopMiddle;
676 if ( *(ptr+1)=='\0' ) {
677 node = enlargeNode(info, node, *ptr, EN_VAL|EN_DATA, &StopMiddle);
678 if ( info->datasize )
679 memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
680 in->data, info->datasize );
682 node = enlargeNode(info, node, *ptr, EN_VAL|EN_CHLD, &StopMiddle);
683 *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
684 makeSkipNode(info, in, level+1);
688 node = makeSkipNode(info, in, level);
695 SFSAdd(SFSTree *info, SFSDataIO *in) {
698 in->keylen=strlen(in->key);
699 info->node = addRecord(info, info->node, in, 0);
703 pushStack(SFSNodeStack *top, SFSNode *node, int level ) {
704 SFSNodeStack *r=(SFSNodeStack*)tmalloc(sizeof(SFSNodeStack));
717 SFSIteratorStart(SFSTree *info) {
720 info->buf = (char*)tmalloc(info->tlen);
722 info->stack = pushStack(NULL, info->node, 0);
727 SFSPrefixIteratorStart(SFSTree *info, char *word) {
728 SFSNode *node = info->node;
729 SFSNodeData *StopLow, *StopHigh, *StopMiddle;
730 u_int8_t *ptr =(u_int8_t*)word;
731 int len,wlen=strlen(word);
733 if ( wlen+1>=info->tlen ) {
735 info->buf = (info->buf) ?
736 (char*)trealloc(info->buf,info->tlen)
738 (char*)tmalloc(info->tlen);
742 while( node && *ptr) {
743 len = wlen - (((char*)ptr)-word);
744 if ( node->isskip ) {
745 if ( STRNCMP(ptr, ((char*)node)+node->dataptr, (len<node->nchar) ? len : node->nchar) ) {
746 if ( len<=node->nchar ) {
747 strcpy(info->buf,word);
748 info->stack = pushStack(NULL, node, ((char*)ptr) - word);
750 } else if ( node->haschild ) {
752 node = getSkipChildPointer(info, node);
759 StopLow = node->data;
760 StopHigh = StopLow + node->nchar;
761 while (StopLow < StopHigh) {
762 StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
763 if ( StopMiddle->val == *ptr ) {
764 if ( *(ptr+1)=='\0' ) {
765 len =((char*)ptr)-word+1;
766 strcpy(info->buf,word);
767 if ( StopMiddle->isword ) {
769 info->wdata = (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
771 if ( StopMiddle->haschild )
772 info->stack = pushStack(NULL, getChildPointer( info, StopMiddle ), len);
774 } else if ( StopMiddle->haschild ) {
775 node = getChildPointer( info, StopMiddle );
781 } else if ( StopMiddle->val < *ptr ) {
782 StopLow = StopMiddle + 1;
784 StopHigh = StopMiddle;
787 if ( StopLow >= StopHigh )
795 SFSIterate(SFSTree *info, SFSDataIO *out) {
796 SFSNodeStack *s=info->stack;
798 if ( info->hasword ) {
799 out->key = info->buf;
800 out->keylen = strlen(out->key);
801 out->data = info->wdata;
808 if ( s->node == NULL ) {
809 info->stack = s->next;
811 return SFSIterate(info, out);
814 while ( s->level + s->node->nchar + 1 >= info->tlen ) {
816 info->buf = (char*)trealloc(info->buf, info->tlen);
819 if ( s->node->isskip ) {
820 memcpy( info->buf + s->level, ((char*)s->node) + s->node->dataptr, s->node->nchar );
821 if ( s->node->isword && !s->checkedval) {
822 info->buf[ s->level+s->node->nchar ] = '\0';
823 out->key = info->buf;
824 out->keylen = s->level+s->node->nchar;
825 out->data =((char*)(s->node->data)) + ((s->node->haschild) ? sizeof(SFSNode*) : 0);
829 if ( s->node->haschild && !s->checkedchild) {
830 info->stack = pushStack(s, getSkipChildPointer(info, s->node), s->level+s->node->nchar);
832 if ( SFSIterate(info, out) )
836 while( s->data - s->node->data < s->node->nchar ) {
837 info->buf[ s->level ] = (char)s->data->val;
838 if ( s->checkedval==0 && s->data->isword ) {
839 info->buf[ s->level+1 ] = '\0';
840 out->key = info->buf;
841 out->keylen = s->level+1;
842 out->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
846 if ( s->checkedchild==0 && s->data->haschild ) {
847 info->stack = pushStack(s,
848 getChildPointer( info, s->data ), s->level+1);
850 if ( SFSIterate(info, out) )
853 s->checkedval = s->checkedchild = 0;
857 info->stack = s->next;
860 return SFSIterate(info, out);
864 SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l) {
865 SFSNodeStack *s=info->stack;
867 SFSPrefixIteratorStart(info, word);
870 if ( SFSIterate(info, f) ) {
871 SFSNodeStack *sptr = info->stack, *stmp;
872 while( sptr && sptr!=s ) {
879 memcpy(l,f,sizeof(SFSDataIO));
887 while( f->keylen + s->level + 2 >= info->tlen ) {
889 info->buf = (char*)trealloc(info->buf, info->tlen);
893 l->key = info->buf + f->keylen + 1;
894 memcpy(l->key, f->key, f->keylen + 1);
897 while( f->keylen + 1 + s->level + s->node->nchar + 1 >= info->tlen ) {
899 info->buf = (char*)trealloc(info->buf, info->tlen);
901 if ( s->node->isskip ) {
902 memcpy(info->buf + f->keylen + 1 + s->level,
903 ((char*)(s->node))+s->node->dataptr, s->node->nchar);
904 s->level+=s->node->nchar;
905 if (s->node->haschild) {
906 s->node=getSkipChildPointer(info, s->node);
907 } else { /* if (s->node->isword) */
908 info->buf[ f->keylen + 1 + s->level ] = '\0';
909 l->data = (void*)(s->node->data);
910 l->keylen = s->level+1;
914 s->data = s->node->data + s->node->nchar - 1;
915 while( s->data - s->node->data >= 0 ) {
916 info->buf[ f->keylen + 1 + s->level ] = (char)s->data->val;
917 if ( s->data->haschild ) {
918 s->node = getChildPointer( info, s->data );
922 if ( s->data->isword ) {
923 info->buf[ f->keylen + 1 + s->level ] = '\0';
924 l->keylen = s->level+1;
925 l->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
934 l->key = info->buf + f->keylen + 1;
940 typedef struct WorkPlain {
947 plainNode(WorkPlain *wp, SFSNode *node) {
948 int size = getNodeSize(wp->info, node);
949 off_t myoffset = wp->offset;
951 memcpy( wp->node + wp->offset, node, size );
954 tassert( wp->offset <= wp->info->totalen );
956 if ( node->isskip ) {
958 *(Opaque*)(wp->node + myoffset + SFSNHRDSZ) =
959 plainNode(wp, getSkipChildPointer(wp->info, node));
961 SFSNodeData *nd = node->data;
964 for(i=0;i<node->nchar;i++) {
966 *(Opaque*)(wp->node + myoffset + ( ((char*)nd) - ((char*)node) ) + nd->child) =
967 plainNode(wp, getChildPointer( wp->info, nd ) );
978 SFSMakePlain(SFSTree *info, void *pointer) {
981 if ( info->plainmemory )
987 wp.node = (char*)pointer;
989 wp.node = (char*)tmalloc(sizeof(char*) * info->totalen);
991 plainNode(&wp, info->node);
992 tassert( wp.offset == info->totalen );
994 info->node = (SFSNode*)wp.node;
995 info->plainmemory = 1;
999 revertNode(SFSTree *info, SFSNode* node) {
1000 int size = getNodeSize(info, node);
1003 newnode = (SFSNode*)tmalloc( size );
1004 memcpy(newnode, node, size);
1006 if ( node->isskip ) {
1008 *(SFSNode**)( (char*)(newnode->data) ) =
1009 revertNode(info, getSkipChildPointer(info, node));
1011 SFSNodeData *nd = node->data;
1012 SFSNodeData *nnd = newnode->data;
1015 for(i=0;i<node->nchar;i++) {
1017 *(SFSNode**) (((char*)nnd) + nnd->child ) =
1018 revertNode(info, getChildPointer( info, nd ));
1027 SFSRevertPlain(SFSTree *info) {
1028 void *pointer = info->node;
1030 if (! info->plainmemory )
1033 info->node = revertNode(info, info->node);
1034 info->plainmemory = 0;
1040 writeNode(WorkPlain *wp, int fd, SFSNode *node, u_int32_t extrasize) {
1041 int size = getNodeSize(wp->info, node);
1042 SFSNode *wnode = (SFSNode*)tmalloc(size);
1043 off_t myoffset = wp->offset;
1045 memcpy( wnode, node, size );
1048 tassert( wp->offset <= wp->info->totalen );
1050 if ( node->isskip ) {
1052 *(Opaque*)( ((char*)wnode) + SFSNHRDSZ) =
1053 writeNode(wp, fd, getSkipChildPointer(wp->info, node), extrasize);
1055 SFSNodeData *nd = node->data;
1058 for(i=0;i<node->nchar;i++) {
1060 *(Opaque*)(((char*)wnode) + ( ((char*)nd) - ((char*)node) ) + nd->child) =
1061 writeNode(wp, fd, getChildPointer( wp->info, nd ), extrasize );
1066 if ( lseek(fd, myoffset + SFSTDHSZ + extrasize, SEEK_SET) < 0 )
1067 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1068 if ( write(fd, wnode, size) != size )
1069 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1077 SFSWriteDump(SFSTree *info, char *filename, void *extradata, u_int32_t extrasize) {
1079 off_t size = info->totalen + SFSTDHSZ;
1080 SFSTreeDumpHeader dh;
1082 if ( (fd = open(filename, O_RDWR|O_CREAT|O_TRUNC, 0666)) < 0 )
1083 tlog(TL_CRIT|TL_EXIT, "Can not open file '%s': %s", filename, strerror(errno));
1085 if ( flock(fd, LOCK_EX) < 0 )
1086 tlog(TL_CRIT|TL_EXIT, "flock failed: %s", strerror(errno));
1088 if ( extrasize == 0 )
1090 else if ( extradata == NULL )
1093 if ( lseek(fd, size + MAXALIGN(extrasize) , SEEK_SET) < 0 )
1094 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1096 dh.version = SFSTREE_VERSION;
1097 dh.opaquesize = sizeof(Opaque);
1098 dh.headersize = SFSTDHSZ;
1099 dh.datasize = info->datasize;
1100 dh.totalen = info->totalen;
1101 dh.nnodes = info->nnodes;
1102 dh.extrasize = extrasize;
1104 if ( lseek(fd, 0, SEEK_SET) < 0 )
1105 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1106 if ( write(fd, &dh, SFSTDHSZ) != SFSTDHSZ )
1107 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1110 if ( write(fd, extradata, extrasize) != extrasize )
1111 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1112 if ( extrasize != MAXALIGN(extrasize) ) {
1113 char dummy[8] = {0,0,0,0,0,0,0,0};
1114 if ( write(fd, dummy, MAXALIGN(extrasize) - extrasize ) != MAXALIGN(extrasize) - extrasize )
1115 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1117 extrasize = MAXALIGN(extrasize);
1121 if ( info->plainmemory ) {
1122 if ( write(fd, info->node, info->totalen) != info->totalen )
1123 tlog(TL_CRIT|TL_EXIT, "write failed: %s", strerror(errno));
1131 writeNode(&wp, fd, info->node, extrasize);
1139 readNode(SFSTree *info, int fd, char *buf, int bufsize, int extrasize) {
1143 size = read(fd, buf, bufsize );
1144 if ( size < SFSNHRDSZ + sizeof(void*) )
1145 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1147 size = getNodeSize(info, (SFSNode*)buf);
1148 tassert( size <= bufsize );
1149 node = (SFSNode*)tmalloc( size );
1150 memcpy(node, buf, size);
1152 if ( node->isskip ) {
1153 if (node->haschild) {
1154 if ( lseek(fd, *(Opaque*)node->data + SFSTDHSZ + extrasize, SEEK_SET) < 0 )
1155 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1156 *(SFSNode**)( (char*)(node->data) ) =
1157 readNode(info, fd, buf, bufsize, extrasize);
1160 SFSNodeData *nd = node->data;
1163 for(i=0;i<node->nchar;i++) {
1165 if ( lseek(fd, *(Opaque*)(((char*)nd) + nd->child ) + SFSTDHSZ + extrasize, SEEK_SET) < 0 )
1166 tlog(TL_CRIT|TL_EXIT, "lseek failed: %s", strerror(errno));
1167 *(SFSNode**) (((char*)nd) + nd->child ) =
1168 readNode(info, fd, buf, bufsize, extrasize);
1178 SFSReadDump(SFSTree *info, char *filename, void **extradata, u_int32_t *extrasize) {
1180 SFSTreeDumpHeader dh;
1189 memset(info,0,sizeof(SFSTree));
1191 if ( (fd = open(filename, O_RDONLY)) < 0 )
1192 tlog(TL_CRIT|TL_EXIT, "Can not open file '%s': %s", strerror(errno));
1193 if ( flock(fd, LOCK_SH) < 0 )
1194 tlog(TL_CRIT|TL_EXIT, "flock failed: %s", strerror(errno));
1196 if ( read(fd, &dh, SFSTDHSZ) != SFSTDHSZ )
1197 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1199 if ( dh.version != SFSTREE_VERSION )
1200 tlog(TL_CRIT|TL_EXIT, "Tree version mismatch (should be 0x%04x but 0x%04x)", SFSTREE_VERSION, dh.version);
1201 if ( dh.opaquesize != sizeof(Opaque) )
1202 tlog(TL_CRIT|TL_EXIT, "sizeof(Opaque) mismatch");
1203 if ( dh.headersize != SFSTDHSZ )
1204 tlog(TL_CRIT|TL_EXIT, "Tree's header size mismatch (should be %d but %d bytes)", SFSTDHSZ, dh.headersize);
1206 info->totalen = dh.totalen;
1207 info->nnodes = dh.nnodes;
1208 info->datasize = dh.datasize;
1210 if ( dh.extrasize ) {
1211 void *pointer = tmalloc( MAXALIGN(dh.extrasize) );
1213 if ( read(fd, pointer, MAXALIGN(dh.extrasize)) != MAXALIGN(dh.extrasize) )
1214 tlog(TL_CRIT|TL_EXIT, "read failed: %s", strerror(errno));
1217 *extradata = pointer;
1222 *extrasize = dh.extrasize;
1225 /* allocate buffer with max allowed size */
1226 bufsize = SFSNHRDSZ + 256*(sizeof(SFSNodeData) + sizeof(void*) + info->datasize);
1227 buf = tmalloc( bufsize );
1228 info->node = readNode(info, fd, buf, bufsize, MAXALIGN(dh.extrasize));
1236 SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size, void **extradata, u_int32_t *extrasize) {
1237 SFSTreeDumpHeader *dh;
1244 memset(info,0,sizeof(SFSTree));
1246 if ( size && size < SFSTDHSZ )
1247 tlog(TL_CRIT|TL_EXIT, "Memsize too small");
1249 dh = (SFSTreeDumpHeader*)pointer;
1251 if ( dh->version != SFSTREE_VERSION )
1252 tlog(TL_CRIT|TL_EXIT, "Tree version mismatch (should be 0x%04x but 0x%04x)", SFSTREE_VERSION, dh->version);
1253 if ( dh->opaquesize != sizeof(Opaque) )
1254 tlog(TL_CRIT|TL_EXIT, "sizeof(Opaque) mismatch");
1255 if ( dh->headersize != SFSTDHSZ )
1256 tlog(TL_CRIT|TL_EXIT, "Tree's header size mismatch (should be %d but %d bytes)", SFSTDHSZ, dh->headersize);
1257 if ( size && size != dh->totalen + SFSTDHSZ + MAXALIGN(dh->extrasize) )
1258 tlog(TL_CRIT|TL_EXIT, "Memory size mismatch (should be %d but %d bytes)", dh->totalen + SFSTDHSZ + dh->extrasize , size);
1260 info->totalen = dh->totalen;
1261 info->nnodes = dh->nnodes;
1262 info->datasize = dh->datasize;
1263 info->plainmemory = 1;
1265 if ( dh->extrasize ) {
1267 *extradata = ((char*)pointer) + SFSTDHSZ;
1270 *extrasize = dh->extrasize;
1273 if ( info->totalen && info->nnodes )
1274 info->node = (SFSNode*)( ((char*)pointer) + SFSTDHSZ + MAXALIGN(dh->extrasize) );