#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include "ft.h"

static void
ft_datadel(p)
	FTENT *p;
{
	if (p->ft_data) 
		free(p->ft_data);
	p->ft_data=NULL;
	p->ft_size=0;
}

static FTENT *
ft_datacpy(p, data, size)
	FTENT *p;
	void *data;
	size_t size;
{
	p->ft_size=size;
	p->ft_data=malloc(size);
	if (!p->ft_data)
		return (NULL);
	(void)memcpy(p->ft_data, data, size);
	
	return (p);
}

static FTENT *
ft_ssort(childs, chsize)
	FTENT *childs;
	int chsize;
{
	FTENT *last, tmp;
	int i, j;

	if (chsize == 1)
		return (&childs[0]);
		
	last=&childs[chsize-1];
	for (i=0; i<chsize; ++i) {
		if (strncmp(childs[i].ft_name, last->ft_name, PATH_MAX) > 0)
			break;
	}
	if (i==chsize)
		return (last);
		
	(void)memcpy(&tmp, last, sizeof(FTENT));	
	(void)memmove(&childs[i+1], &childs[i],
	    sizeof(FTENT)*(chsize-i-1));
	(void)memcpy(&childs[i], &tmp, sizeof(FTENT));
		
	last=&childs[i];		
	for ( ; i<chsize; ++i)
		childs[i].ft_index=i;

	return (last);
}

static int
ft_getlevel(p)
	const char *p;
{
	int level;

	if (strncmp(p, "/", 2) == 0)
		return (0);

	for (level=0; *p; ++p) {
		if (*p == '/')
			level++;
	}

	return (level);
}

static char *
ft_lpath(srcpath, level, newpath)
	const char *srcpath;
	int level;
	char *newpath;
{
	int i, len;

	if (level<=0) {
		(void)strncpy(newpath, "/", 2);
		return (newpath);
	}

	for (i=0, len=strlen(srcpath); 0<=level && i<=len; ++i) {
		if ((newpath[i]=srcpath[i])=='/')
			level--;
	}
	newpath[i-1]=(char)0x0;

	return (newpath);
}

static void
ft_lname(path, level, beg_r, len_r)
	const char *path;
	int level, *beg_r, *len_r;
{
	int i=0;
	while (0<level) {
		if (path[i++]=='/')
			level--;
	}
	*beg_r=i;
	
	while (path[i]!=0x0 && path[i]!='/')
		i++;
	*len_r=i-*beg_r;
}

static void
ft_setparent(childs, chsize)
	FTENT *childs;
	int chsize;
{
	FTENT *ent;
	int i, j;
	for (i=0; i<chsize; ++i) {
		ent=&childs[i];
		for (j=0; j<ent->ft_chsize; ++j)
			ent->ft_childs[j].ft_parent=ent;
	}
}

static void
ft_cutslash(path)
	char *path;
{
	int i=strlen(path)-1;
    
	while (0<i && path[i]=='/')
		path[i--]=0x0;
}

static FTENT *
ft_malloc_ent(ft, ent, parent, path, data, size)
	FT *ft;
	FTENT *ent, *parent;
	const char *path;
	void *data;
	size_t size;
{
	if (!(ent->ft_path=(char *)strdup(path)))
		return (NULL);
	ent->ft_pathlen=strlen(ent->ft_path);
	ent->ft_level=ft_getlevel(ent->ft_path);	

	ent->ft_name=strrchr(ent->ft_path, '/')+1;
	ent->ft_namelen=strlen(ent->ft_name);

	ent->ft_parent=parent;
	ent->ft_childs=NULL;
	ent->ft_chsize=0;
	
	ent->ft_index=(parent ? parent->ft_chsize : 0);
	ent->ft_opt=0;

	ent->ft_size=0;
	ent->ft_data=NULL;
	if (data) {
		if (!ft->ft_datacpy(ent, data, size))
			goto mem1;
	}
	
	return (ent);

mem1:	free(ent->ft_path);
	return (NULL);
}

static FTENT *
ft_malloc(ft, parent, path, data, size)
	FT *ft;
	FTENT *parent;
	const char *path;
	void *data;
	size_t size;
{
	FTENT *newchs, *newent;

	newchs=(FTENT *)realloc(parent->ft_childs,
	    sizeof(FTENT)*(parent->ft_chsize+1));
	if (!newchs)
		return (NULL);

	newent=&newchs[parent->ft_chsize];
	if (!ft_malloc_ent(ft, newent, parent, path, data, size)) {
		if (parent->ft_childs!=newchs)
			ft_setparent(parent->ft_childs, parent->ft_chsize);		
		parent->ft_childs=(FTENT *)realloc(newchs,
		    sizeof(FTENT)*parent->ft_chsize);
		return (NULL);
	}
	parent->ft_chsize++;	

	if (newchs!=parent->ft_childs)
		parent->ft_childs=newchs;

	newent=ft_ssort(parent->ft_childs, parent->ft_chsize);
	ft_setparent(parent->ft_childs, parent->ft_chsize);

	return (newent);
}

static void
ft_freeent(ft, ent)
	FT *ft;
	FTENT *ent;
{
	free(ent->ft_path);
	if (ent->ft_data)
		ft->ft_datadel(ent);
}

FTENT *
ft_find(ft, path, parent_r)
	FT *ft;
	const char *path;	
	FTENT **parent_r;
{
	FTENT *cent, *cparent;
	int clevel, chi, level, lname_beg, lname_len;
	char pathbuff[PATH_MAX+1];

	(void)strncpy(pathbuff, path, PATH_MAX);
	pathbuff[PATH_MAX-1]=(char)0x0;
	ft_cutslash(pathbuff);

	if (strncmp(pathbuff, "/", 2)==0)
		return (ft->ft_root);

	level=ft_getlevel(pathbuff);
	if (parent_r)
		*parent_r=ft->ft_root;
	cparent=ft->ft_root;
	for (clevel=1; clevel<=level; ++clevel) {
		(void)ft_lname(pathbuff, clevel, &lname_beg, &lname_len);
		for (chi=0; chi<cparent->ft_chsize; ++chi) {
			cent=&cparent->ft_childs[chi];
			if (cent->ft_namelen==lname_len && memcmp(cent->ft_name,
			    &pathbuff[lname_beg], lname_len)==0)
				break;
		}
		if (chi==cparent->ft_chsize)
			return (NULL);
		if (parent_r)
			*parent_r=cent;
		cparent=cent;	
	}
	return (cent);
}

FTENT *
ft_add(ft, path, data, size)
	FT *ft;
	const char *path;
	void *data;
	size_t size;
{
	FTENT *newent, *ment, *parent;
	char fullpath[PATH_MAX+1], pathbuff[PATH_MAX+1];
	int level, i;

	(void)strncpy(fullpath, path, PATH_MAX);
	ft_cutslash(fullpath);

	level=ft_getlevel(fullpath);
	newent=ft_find(ft, fullpath, &parent);
	if (newent) {
		if (newent->ft_data)
			ft->ft_datadel(newent);

		newent->ft_size=0;
		newent->ft_data=NULL;
		if (data)
			ft->ft_datacpy(newent, data, size);
	} else {
		for (i=parent->ft_level; i<level-1; ++i) {
			(void)ft_lpath(fullpath, i+1, pathbuff);
			ment=ft_malloc(ft, parent, pathbuff, NULL, 0);
			if (!ment)
				return (NULL);
			parent=ment;
		}
		newent=ft_malloc(ft, parent, fullpath, data, size);
		if (!newent)
			return (NULL);
	}
	return (newent);
}

void
ft_delete(ft, ent)
	FT *ft;
	FTENT *ent;
{
	FTENT *parent, *cent;

	if (ent->ft_chsize > 0) {
		cent=ent;
		do {
			if (cent->ft_chsize > 0) {
				cent->ft_chsize--;
				cent=&cent->ft_childs[cent->ft_chsize];
			} else {
				ft_freeent(ft, cent);
				if (cent->ft_index > 0) {
					cent--;
				} else {
					cent=cent->ft_parent;
					free(cent->ft_childs);
					cent->ft_childs=NULL;
					cent->ft_chsize=0;
				}
			}
		} while (cent != ent);
	}

	if (ent != ft->ft_root) {
		ft_freeent(ent);
		parent=ent->ft_parent;
		parent->ft_chsize--;
		if (parent->ft_chsize > 0) {
			if (ent->ft_index<parent->ft_chsize)
				(void)memmove(ent, ent+1, sizeof(FTENT) *
				    (parent->ft_chsize-ent->ft_index));
			(void)realloc(parent->ft_childs,
			    sizeof(FTENT)*parent->ft_chsize);
		} else {
			free(parent->ft_childs);
			parent->ft_childs=NULL;
		}
	}
}

FT *
ft_init(datadel, datacpy)
	void (*datadel)(FTENT *);
	FTENT * (*datacpy)(FTENT *, void *, size_t);
{
	FT *p;

	p=(FT *)malloc(sizeof(FT));
	if (!p)
		return (NULL);

	p->ft_datadel=(datadel ? datadel : &ft_datadel);
	p->ft_datacpy=(datacpy ? datacpy : &ft_datacpy);
	p->ft_root=(FTENT *)malloc(sizeof(FTENT));	
	if (!p->ft_root)
		goto mem1;
	if (!ft_malloc_ent(p, p->ft_root, NULL, "/", NULL, 0))
		goto mem2;

	return (p);

mem2:	free(p->ft_root);
mem1:	free(p);	
	return(NULL);
}

void
ft_close(p)
	FT *p;
{
	ft_delete(p, p->ft_root);
	ft_freeent(p, p->ft_root);
	free(p->ft_root);
	free(p);
}

static int
ft_traverse_do(ftent, func, sp)
	FTENT *ftent;
	int (*func)(FTENT *, void *);
	void *sp;
{
	int ret, i;
	if ((ret=func(ftent, sp))!=0)
		return (ret);
	for (i=0; i<ftent->ft_chsize; ++i) {
		if ((ret=ft_traverse_do(&ftent->ft_childs[i], func, sp))!=0)
			return (ret);
	}
	return (0);
}

int
ft_traverse(ft, func, sp)
	FT *ft;
	int (*func)(FTENT *, void *);
	void *sp;
{
	return (ft_traverse_do(ft->ft_root, func, sp));
}