/*
 * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *	notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *	notice, this list of conditions and the following disclaimer in the
 *	documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the author nor the names of any co-contributors
 *	may be used to endorse or promote products derived from this software
 *	without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <string.h>

#include "tlog.h"
#include "tmalloc.h"
#include "sfxstr.h"

#define EN_VAL	0x01
#define EN_CHLD	0x02
#define EN_DATA	0x04

static SFSNode* enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd);
static SFSNode* addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level);

#define STRNCMP(p1,p2,n) ( ((n)==1) ? ( *((char*)(p1))==*((char*)(p2)) ) : (strncmp((char*)(p1), (char*)(p2), (n))==0) )

SFSTree* 
SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in) {
	if ( datasize % sizeof(u_int32_t) )
		tlog(TL_ALARM|TL_EXIT,"SFSInit_dp: datasize(%d) should be divided by sizeof(u_int32_t)", datasize);
 
	if (!info) 
		info=(SFSTree*)tmalloc(sizeof(SFSTree));
	memset(info,0,sizeof(SFSTree));

	info->datasize = datasize;

	while(in && in->key) {
		SFSAdd(info, in);
		in++;
	}

	return info;	
}

SFSTree* 
SFSInit_c(SFSTree *info, char **in) {
	char **ptr=in;
	SFSDataIO  d;

	if (!info) 
		info=(SFSTree*)tmalloc(sizeof(SFSTree));
	memset(info,0,sizeof(SFSTree));

	while(ptr && *ptr) {
		d.key=*ptr;
		d.keylen=0;
		SFSAdd(info, &d);
		ptr++;
	}

	return info;
}

void*
SFSFindData(SFSTree *info, char *word) {
	SFSNode *node = info->node;
	SFSNodeData *StopLow, *StopHigh, *StopMiddle;
	u_int8_t *ptr =(u_int8_t*)word;

	while( node && *ptr ) {
		if ( node->isskip ) {
			if ( STRNCMP(ptr, ((char*)node)+node->dataptr, node->nchar) ) {
				ptr+=node->nchar;
				if ( *ptr=='\0' && node->isword) {
					return (void*) ( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0) );
				} else if ( node->haschild ) {
					node = *(SFSNode**)(node->data);
				} else {
					return NULL;
				}
			} else
				return NULL;
		} else {
			StopLow = node->data;
			StopHigh = StopLow + node->nchar;
			while (StopLow < StopHigh) {
			       StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
			       if ( StopMiddle->val == *ptr ) {
				       ptr++;
				       if ( *ptr=='\0' && StopMiddle->isword ) {
						return (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
					} else if ( StopMiddle->haschild ) {
						node=*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child );
					} else {
						return NULL;
					}
					break;
				} else if ( StopMiddle->val < *ptr ) {
					StopLow = StopMiddle + 1;
				} else {
					StopHigh = StopMiddle;
				}
			}
			if ( StopLow >= StopHigh )
				return NULL;
		}
	}
	return NULL;
}

static void
freeFSFNode(SFSTree *info, SFSNode *node, void (*freefunc)(void*)) {
	u_int32_t i;
 
	if ( node->isskip ) {
		if (node->haschild)
			freeFSFNode(info, *(SFSNode**)(node->data), freefunc);
		if (freefunc && node->isword && info->datasize)
			(*freefunc)( (void*)( ((char*)(node->data))+ (node->haschild) ? sizeof(SFSNode*) : 0 ) );
	} else {
		SFSNodeData *nd = node->data;
		char *data= ((char*)node) + node->dataptr;
	
		for(i=0;i<node->nchar;i++) {
			if (nd->haschild)
				freeFSFNode(info, *(SFSNode**)( ((char*)nd) + nd->child ), freefunc);
			if (freefunc && nd->isword && info->datasize) {
				(*freefunc)( (void*)data );
				data+=info->datasize;
			}
			nd++;
		}
	}

	tfree(node);
}

void 
SFSFree(SFSTree *info, void (*freefunc)(void*)) {
	SFSNodeStack *s=info->stack;

	if (info->node) freeFSFNode(info, info->node, freefunc);
	if (info->buf) tfree(info->buf);
	info->buf = NULL;
	info->tlen=0;
	info->node = NULL;

	while(s) {
		info->stack=s->next;
		tfree(s);
		s=info->stack;
	}
}

static SFSNode*
makeSkipNode(SFSTree *info, SFSDataIO *io, int level) {
	u_int32_t len;
	int size;
	SFSNode *res;

	io->key+=level;
	io->keylen-=level;

	len = (io->keylen > 255) ? 255 : io->keylen;
	size = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize) + len;

	res = (SFSNode*)tmalloc(size);

	info->nnodes++;
	info->totalen+=size;

	res->isskip=1;
	res->nchar=len;
	res->dataptr = SFSNHRDSZ + ((io->keylen > 255) ? sizeof(SFSNode*) : info->datasize);
	memcpy(((char*)res) + res->dataptr, io->key, len);

	if ( io->keylen > 255 ) {
		res->haschild=1;
		res->isword=0;
		io->key = io->key+len;
		io->keylen = io->keylen - len;
		*(SFSNode**)(res->data) = makeSkipNode(info, io, 0);
		io->key = io->key-len;
		io->keylen = io->keylen + len;
	} else {
		res->haschild=0;
		res->isword=1;
		if (info->datasize) {
			memcpy( res->data, io->data, info->datasize );
		}
	}

	io->key-=level;
	io->keylen+=level;

	return res;
}

static SFSNode*
splitSkipNode(SFSTree *info, SFSNode* node, SFSDataIO *io, int level) {
	SFSNode *res;
	int prefixlen=0;
	char *s1,*s2;
	SFSNodeData	*ndata;

	tassert(node->isskip);
	io->key+=level;
	io->keylen-=level;

	s1=((char*)node) + node->dataptr;
	s2=io->key;

	while( s1 - (((char*)node) + node->dataptr) < node->nchar && s2 - io->key < io->keylen && *s1==*s2) {
		s1++;
		s2++;
	}

	prefixlen = s2 - io->key;

	if ( prefixlen==0 ) {
		if ( node->nchar == 1 ) {
			int flag = EN_VAL | ((node->isword) ? EN_DATA : 0) | ((node->haschild) ? EN_CHLD : 0);
			res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), flag, &ndata);
			if ( node->isword ) {
				if ( info->datasize ) 
					memcpy(
						((char*)res) + res->dataptr + info->datasize * ndata->data,
						((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNode*) : 0),
						info->datasize
					);
			}
			if ( node->haschild ) 
				*(SFSNode**)( ((char*)ndata) + ndata->child ) = *(SFSNode**)( node->data );
			info->totalen -= SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
				((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar;
			info->nnodes--;
			tfree(node);
		} else {
			res = enlargeNode(info, NULL, *(u_int8_t*)(((char*)node) + node->dataptr), EN_VAL|EN_CHLD, &ndata);
			node->nchar--;
			memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + 1, node->nchar);
			info->totalen--;
			*(SFSNode**)( ((char*)ndata) + ndata->child ) = (SFSNode*)trealloc(node,
				SFSNHRDSZ + ((node->haschild) ? sizeof(SFSNode*) : 0) + 
				((node->isword) ? info->datasize : 0 )+ node->nchar);
		}
		res = addRecord(info, res, io, 0);
	} else if (prefixlen==io->keylen) {
		if (prefixlen==node->nchar) {
			if ( node->isword || info->datasize==0) {
				if (info->datasize)
					memcpy( ((char*)(node->data)) + ((node->haschild) ? sizeof(SFSNodeData*) : 0),
						io->data,
						info->datasize);
				node->isword=1;
				res=node;
			} else {
				int size = SFSNHRDSZ + info->datasize + ((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar;

				info->totalen+=info->datasize;
				res=(SFSNode*)trealloc(node,size);
				res->dataptr=SFSNHRDSZ + info->datasize + ((res->haschild) ? sizeof(SFSNodeData*) : 0);
				res->isword=1;
				memmove(((char*)res) + res->dataptr,
					((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), res->nchar);
				memcpy(((char*)(res->data))  + ((res->haschild) ? sizeof(SFSNodeData*) : 0), io->data, info->datasize);
			}
		} else {
			int size = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*) + prefixlen;
			info->totalen+=size;
			info->nnodes++;
			res = (SFSNode*)tmalloc(size);
			res->isskip=1;
			res->isword=1;
			res->haschild=1;
			res->nchar = prefixlen;
			res->dataptr = SFSNHRDSZ + info->datasize + sizeof(SFSNodeData*);
			memcpy(((char*)res)+res->dataptr, io->key, prefixlen);
			if (info->datasize)
				memcpy(((char*)(res->data)) + sizeof(SFSNodeData*), io->data, info->datasize);
			node->nchar-=prefixlen;
			memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
			info->totalen-=prefixlen;
			*(SFSNode**)(res->data) = (SFSNode*)trealloc(node, SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
				((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar);
		}
	} else if ( prefixlen==node->nchar ) {
		int size = SFSNHRDSZ + info->datasize +  sizeof(SFSNode*) + node->nchar;
		info->totalen+=sizeof(SFSNode*);
		res=(SFSNode*)trealloc(node,size);
		memmove( ((char*)(res->data)) + sizeof(SFSNode*), res->data, info->datasize + res->nchar);
		res->haschild=1;
		res->dataptr+=sizeof(SFSNode*);
		*(SFSNode**)(res->data) = makeSkipNode(info, io, prefixlen); 
	} else { 
		int size = SFSNHRDSZ + sizeof(SFSNodeData*) + prefixlen;
		info->totalen+=size;
		info->nnodes++;
		res = (SFSNode*)tmalloc(size);
		res->isskip=1;
		res->isword=0;
		res->haschild=1;
		res->nchar = prefixlen;
		res->dataptr = SFSNHRDSZ + sizeof(SFSNodeData*);
		memcpy(((char*)res)+res->dataptr, io->key, prefixlen);

		node->nchar-=prefixlen;
		memmove( ((char*)node) + node->dataptr, ((char*)node) + node->dataptr + prefixlen, node->nchar);
		info->totalen-=prefixlen;

		*(SFSNode**)(res->data) = (SFSNode*)trealloc(node, 
			SFSNHRDSZ + ((node->isword) ? info->datasize : 0) +
				((node->haschild) ? sizeof(SFSNodeData*) : 0) + node->nchar
		);
		*(SFSNode**)(res->data) = splitSkipNode(info, *(SFSNode**)(res->data), io, prefixlen); 

	}

	io->key-=level;
	io->keylen+=level;
	return res;
}


static SFSNode*
enlargeNode(SFSTree *info, SFSNode* node, u_int8_t val, int flag, SFSNodeData **nd) {
	u_int32_t nchild=0, nchar=0, nfound=0, i;
	SFSNode *rs,**chld;
	SFSNodeData *data;
	int sizenode;
	char *dataptr;


	if ( node ) {
		nchar=node->nchar;
		nchild=node->nchild;
		data=node->data;

		for(i=0;i<nchar;i++) {
			nfound += data->isword;
			data++;
		}
	}

	if ( node )
		info->totalen -= SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;

	if ( flag & EN_VAL )   nchar++;	
	if ( flag & EN_CHLD ) nchild++;	
	if ( flag & EN_DATA )  nfound++;	


	sizenode = SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*)+nfound*info->datasize;

	info->totalen+=sizenode;
 	if ( !node ) info->nnodes++;
	rs=(SFSNode*)tmalloc(sizenode);

	rs->isskip = 0;
	rs->nchar = nchar;
	rs->nchild = nchild;
	rs->dataptr=SFSNHRDSZ+nchar*sizeof(SFSNodeData)+nchild*sizeof(SFSNode*);
	dataptr=((char*)rs) + rs->dataptr;
	chld = (SFSNode**)( ((char*)rs)+SFSNHRDSZ+nchar*sizeof(SFSNodeData) );
	data=rs->data;

	if (node) {
		SFSNode **ochld=(SFSNode**)( ((char*)node)+SFSNHRDSZ+node->nchar*sizeof(SFSNodeData) );
		SFSNodeData *odata = node->data;
		char *odataptr=((char*)node) + node->dataptr;
		int wasins=0;

		for(i=0;i<node->nchar;i++) {
			if ( val > odata->val ) {
				*(u_int32_t*)data = *(u_int32_t*)odata;
				if ( odata->haschild ) {
					*chld=*ochld;
					data->child = ((char*)chld) - ((char*)data);
					chld++; ochld++;
				}
				if ( odata->isword && info->datasize ) {
					memcpy(dataptr, odataptr, info->datasize);
					data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
					dataptr += info->datasize; odataptr += info->datasize;
				}
				data++; odata++; 
			} else if ( val == odata->val ) {
				tassert ( (flag&EN_VAL)==0 );
				*(u_int32_t*)data = *(u_int32_t*)odata;
				wasins=1;
				if ( odata->haschild || flag & EN_CHLD ) {
					if (odata->haschild) *chld=*ochld;
					data->child = ((char*)chld) - ((char*)data);
					data->haschild=1;
					chld++; if (odata->haschild) ochld++;
				} else
					data->haschild=0;
				if ( odata->isword || flag & EN_DATA ) {
					data->isword=1;
					if ( info->datasize && odata->isword ) {
						memcpy(dataptr, odataptr, info->datasize);
						odataptr += info->datasize;
					}
					data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
					dataptr += info->datasize;
				} else
					data->isword=0;
				*nd = data;
				data++; odata++; 
			} else {
				if ( wasins==0 ) {
					tassert ( flag&EN_VAL );
					data->val = val;
					if ( flag & EN_CHLD ) {
						data->haschild=1;
						data->child = ((char*)chld) - ((char*)data);
						chld++;
					} else
						data->haschild=0;
					if ( flag & EN_DATA ) {
       				 		data->isword=1;
						data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
						dataptr += info->datasize;
					} else
						data->isword=0;
					*nd = data;
					data++;
					wasins=1;
					i--;
				} else {
					*(u_int32_t*)data = *(u_int32_t*)odata;
					if ( odata->haschild ) {
						*chld=*ochld;
						data->child = ((char*)chld) - ((char*)data);
						chld++; ochld++;
					}
					if ( odata->isword && info->datasize ) {
						memcpy(dataptr, odataptr, info->datasize);
						data->data = ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize;
						dataptr += info->datasize; odataptr += info->datasize;
					}
					data++; odata++; 
				}
			} 
		}
		if ( wasins==0 ) {
			tassert ( flag&EN_VAL );
			data->val = val;
			if ( flag & EN_CHLD ) {
				data->haschild=1;
				data->child = ((char*)chld) - ((char*)data);
				chld++;
			} else
				data->haschild=0;
			if ( flag & EN_DATA ) {
       		 		data->isword=1;
				data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
				dataptr += info->datasize;
			} else 
				data->isword=0;
			*nd = data;
		}
	} else {
		tassert ( flag & EN_VAL );
		data->val = val;
		if ( flag & EN_CHLD ) {
			data->haschild=1;
			data->child = ((char*)chld) - ((char*)data);
		} else
			data->haschild=0;
		if ( flag & EN_DATA ) {
			data->isword=1;
			data->data = ( info->datasize ) ? ((dataptr - ((char*)rs)) - rs->dataptr)/info->datasize : 0;
		} else
			data->isword=0;
		*nd = data;
	}
	if (node) tfree(node);
	return rs;
}

static SFSNode*
addRecord(SFSTree *info, SFSNode* node, SFSDataIO *in, int level) {
	SFSNodeData *StopLow, *StopHigh, *StopMiddle;
	u_int8_t *ptr = ((u_int8_t*)in->key) + level;


	if ( node ) {
		if ( node->isskip ) {
			if ( node->haschild && in->keylen-level > node->nchar && 
					strncmp(in->key+level, ((char*)node)+node->dataptr, node->nchar)==0 ) 
				*(SFSNode**)( node->data ) = addRecord(info, *(SFSNode**)( node->data ), in, level+node->nchar); 
			else 
				node = splitSkipNode(info, node, in, level); 
		} else {
	       		StopLow = node->data;   
			StopHigh = StopLow + node->nchar;
			while (StopLow < StopHigh) {
				StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
		       	 	if ( StopMiddle->val == *ptr ) {
					if ( *(ptr+1)=='\0' ) {
						if ( StopMiddle->isword ) {
							/* already exists */
							if ( info->datasize ) 
								memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
									in->data, info->datasize );
						} else {
							/* not exist word */
							if (info->datasize) {
								node = enlargeNode(info, node, *ptr, EN_DATA, &StopMiddle);
								memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
									in->data, info->datasize );
							}
							StopMiddle->isword = 1;
						}
					} else if ( StopMiddle->haschild ) {
						*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) = 
							addRecord(info, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), in, level+1);
					} else {
						node = enlargeNode(info, node, *ptr, EN_CHLD, &StopMiddle);
						*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) =
							makeSkipNode(info, in, level+1);
					}
					return node;
				} else if ( StopMiddle->val < *ptr ) {
					StopLow = StopMiddle + 1;
				} else {
					StopHigh = StopMiddle;
				}
			}
			if ( *(ptr+1)=='\0' ) {
				node = enlargeNode(info, node, *ptr, EN_VAL|EN_DATA, &StopMiddle);
				if ( info->datasize )
					memcpy(((char*)node) + node->dataptr + info->datasize * StopMiddle->data,
					in->data, info->datasize );
			} else {
				node = enlargeNode(info, node, *ptr, EN_VAL|EN_CHLD, &StopMiddle);
				*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ) = 
					makeSkipNode(info, in, level+1);
			}
		}
	} else 
		node = makeSkipNode(info, in, level); 


	return node;

}

void
SFSAdd(SFSTree *info, SFSDataIO *in) {
	if (in->keylen<=0)
		in->keylen=strlen(in->key);
	info->node = addRecord(info, info->node, in, 0);
}

static SFSNodeStack*
pushStack(SFSNodeStack *top, SFSNode *node, int level ) {
	SFSNodeStack *r=(SFSNodeStack*)tmalloc(sizeof(SFSNodeStack));

	r->next = top;
	r->node=node;
	r->data=node->data;
	r->level=level;
	r->checkedchild = 0;
	r->checkedval = 0;

	return r;
}

void 
SFSIteratorStart(SFSTree *info) {
	if ( !info->buf ) {
		info->tlen = 32;
		info->buf = (char*)tmalloc(info->tlen);
	} 
	info->stack = pushStack(NULL, info->node, 0);
	info->hasword=0; 
}

void
SFSPrefixIteratorStart(SFSTree *info, char *word) {
	SFSNode *node = info->node;
	SFSNodeData *StopLow, *StopHigh, *StopMiddle;
	u_int8_t *ptr =(u_int8_t*)word;
	int len,wlen=strlen(word);

	if ( wlen+1>=info->tlen ) {
		info->tlen = 2*wlen;
		info->buf = (info->buf) ?
				(char*)trealloc(info->buf,info->tlen)
			:
				(char*)tmalloc(info->tlen);
	}

	info->hasword=0;
	while( node && *ptr) {
		len = wlen - (((char*)ptr)-word);
		if ( node->isskip ) {
			if ( STRNCMP(ptr, ((char*)node)+node->dataptr, (len<node->nchar) ? len : node->nchar) ) {
				if ( len<=node->nchar ) {
					strcpy(info->buf,word);
					info->stack = pushStack(NULL, node, ((char*)ptr) - word);
					return;
				} else if ( node->haschild ) {
					ptr+=node->nchar;
					node = *(SFSNode**)(node->data);
				} else {
					return;
				}
			} else
				return;
		} else {
			StopLow = node->data;
			StopHigh = StopLow + node->nchar;
			while (StopLow < StopHigh) {
				StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
				if ( StopMiddle->val == *ptr ) {
					if ( *(ptr+1)=='\0' ) {
						len =((char*)ptr)-word+1;
						strcpy(info->buf,word);
						if ( StopMiddle->isword ) {
							info->hasword=1;
							info->wdata = (void*)( ((char*)node) + node->dataptr + info->datasize * StopMiddle->data );
						}
						if ( StopMiddle->haschild )
							info->stack = pushStack(NULL, *(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child ), len);
						return;
					} else if ( StopMiddle->haschild ) {
						node=*(SFSNode**)( ((char*)StopMiddle) + StopMiddle->child );
					} else {
						return;
					}
					ptr++;
					break;
				} else if ( StopMiddle->val < *ptr ) {
					StopLow = StopMiddle + 1;
				} else {
					StopHigh = StopMiddle;
				}
			}
			if ( StopLow >= StopHigh )
				break;
		}
	}
	return;
}

int
SFSIterate(SFSTree *info, SFSDataIO *out) {
	SFSNodeStack *s=info->stack;

	if ( info->hasword ) {
		out->key = info->buf;
		out->keylen = strlen(out->key);
		out->data = info->wdata;
		info->hasword = 0;
		return 1;
	}

	if ( s == NULL || s->node == NULL)
		return 0;
							 
	while ( s->level + s->node->nchar + 1 >= info->tlen ) {
		info->tlen *= 2;
		info->buf = (char*)trealloc(info->buf, info->tlen);
	}

	if ( s->node->isskip ) {
		memcpy( info->buf + s->level, ((char*)s->node) + s->node->dataptr, s->node->nchar );
		if ( s->node->isword && !s->checkedval) {
			info->buf[ s->level+s->node->nchar ] = '\0';
			out->key = info->buf;
			out->keylen = s->level+s->node->nchar;
			out->data =((char*)(s->node->data)) + ((s->node->haschild) ? sizeof(SFSNode*) : 0);
			s->checkedval=1;
			return 1;
		}
		if ( s->node->haschild && !s->checkedchild) {
			info->stack = pushStack(s, *(SFSNode**)( (char*)(s->node->data) ), s->level+s->node->nchar);
			s->checkedchild=1;
			if ( SFSIterate(info, out) )
				return 1;
		}
	} else {
		while( s->data - s->node->data < s->node->nchar ) {
			info->buf[ s->level ] = (char)s->data->val;
			if ( s->checkedval==0 && s->data->isword ) {
				info->buf[ s->level+1 ] = '\0';  
				out->key = info->buf;
				out->keylen = s->level+1;
				out->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
				s->checkedval = 1;
				return 1;
			}
			if ( s->checkedchild==0 && s->data->haschild ) {
				info->stack = pushStack(s, *(SFSNode**)( ((char*)s->data) + s->data->child ), s->level+1);
				s->checkedchild=1;
				if ( SFSIterate(info, out) )
					return 1;
			}
			s->checkedval = s->checkedchild = 0;
			s->data++;
		}
	}
	info->stack = s->next;
	tfree(s);

	return SFSIterate(info, out);
}

int
SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l) {
	SFSNodeStack *s=info->stack;

	SFSPrefixIteratorStart(info, word);
	s=info->stack;

	if ( SFSIterate(info, f) ) {
		SFSNodeStack *sptr = info->stack, *stmp;
		while( sptr && sptr!=s ) {
			stmp=sptr->next;
			tfree(sptr);
			sptr=stmp;
		}
	 
		if ( s == NULL ) {
			memcpy(l,f,sizeof(SFSDataIO));
			return 1;
		}
	} else
		return 0;
							 
	info->stack=NULL;

	while( f->keylen +  s->level + 2 >= info->tlen ) {
		info->tlen *= 2;
		info->buf = (char*)trealloc(info->buf, info->tlen);
	}

	f->key = info->buf;
	l->key = info->buf + f->keylen + 1;
	memcpy(l->key, f->key, f->keylen + 1);
			
	while(s->node) {
		while( f->keylen + 1 + s->level + s->node->nchar + 1 >= info->tlen ) {
			info->tlen *= 2;
			info->buf = (char*)trealloc(info->buf, info->tlen);
		}
		if ( s->node->isskip ) {
			memcpy(info->buf + f->keylen + 1 + s->level,
				((char*)(s->node))+s->node->dataptr, s->node->nchar);
			s->level+=s->node->nchar;
			if (s->node->haschild) {
				s->node=*(SFSNode**)( s->node->data );  
			} else { /* if (s->node->isword) */
				info->buf[ f->keylen + 1 + s->level + 1 ] = '\0';
				l->data = (void*)(s->node->data);
				l->keylen = s->level+1;
				break;
			}
		} else {
			s->data = s->node->data + s->node->nchar - 1;
			while( s->data - s->node->data >= 0 ) {
				info->buf[ f->keylen + 1 + s->level ] = (char)s->data->val;
				if ( s->data->haschild ) {
					s->node = *(SFSNode**)( ((char*)s->data) + s->data->child );
					s->level++;
					break;
				}
				if ( s->data->isword ) {
					info->buf[ f->keylen + 1 + s->level+1 ] = '\0';
					l->keylen = s->level+1;
					l->data =((char*)s->node) + s->node->dataptr + info->datasize * s->data->data;
					s->node=NULL;
					break;
				}
				s->data--;
			}
		}
	}		
	f->key = info->buf;
	l->key = info->buf + f->keylen + 1;
	tfree(s); 

	return 1;
}