/** @file critbit.c
 * Crit-bit tree example.
 * PUBLIC DOMAIN - Jon Mayo - July 7, 2009
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef EXPORT
/**
 * you could define this for tagging functions that are exported. by default export nothing.
 */
#define EXPORT static
#endif

#define CRITBIT_IS_EXTERNAL(n)

/** gives the key for a leaf pointer. */
#define CRITBIT_LEAF_KEY(p) ((char*)(p))

typedef char *critbit_data_t;
typedef unsigned char critbit_flag_t;

/**
 * TBD.
 */
struct critbit_node {
	void *child[2]; /**< either a leaf node or an inner node. */
	size_t ofs; /**< byte offset */
	critbit_flag_t external_fl[2]; /**< flag to indicate if node is internal or external. */
	unsigned char critbitmask; /**< mask, normal bits are 1, critbit is 0. */
};

/**
 * TBD.
 */
struct critbit_tree {
	void *root;
	critbit_flag_t external_fl; /**< flag to indicate if node is internal or external. */
};

/**
 * TBD.
 */
EXPORT struct critbit_node *critbit_allocate(void) {
	struct critbit_node *ret;
	ret=calloc(1, sizeof *ret);
	if(!ret) {
		perror(__func__);
		return NULL;
	}
	return ret;
}

/**
 * TBD.
 */
EXPORT void critbit_free(struct critbit_node *n) {
	if(n) {
		memset(n, 0, sizeof *n);
		free(n);
	}
}

/**
 * get differing byte.
 * if they are the same then returns the length/location of null terminator.
 */
static size_t critbit_diff_byte(size_t a_len, critbit_data_t a, size_t b_len, critbit_data_t b, unsigned char *mask) {
	size_t i;

	/*** this function is shit */

	for(i=0;i<b_len;i++) {
		if(a[i]!=b[i]) {
			*mask=a[i]^b[i];
			return i;
		}
	}
	if(a[i]) {
		*mask=a[i];
		return i;
	}

	return 0;
}


/**
 * find the best matching node.
 * @param p the starting node.
 */
static const void *critbit_best_match(const void *p, size_t u_len, const critbit_data_t u, unsigned *external_fl) {

	/* walk tree to find best member. */
	while(!*external_fl) {
		unsigned dir;
		const struct critbit_node *curr=p;

		assert(curr != NULL);

		/* calculate direction. treat out of bounds as 0. */
		dir=(curr->ofs<u_len) ? u[curr->ofs] : 0;
		dir=((curr->critbitmask|dir)+1)>>8; /* get 0 or 1 from the critbitmask. */

		*external_fl=curr->external_fl[dir];
		p=curr->child[dir];

		assert(p != NULL); /* because of the construction of the tree this cannot happen. */
	}
	return p;
}

/**
 * returns a matching entry.
 */
EXPORT critbit_data_t critbit_find(const struct critbit_tree *t, const critbit_data_t u) {
	const void *p;
	unsigned external_fl; /* is curr an external pointer or internal one. */
	size_t u_len=strlen(CRITBIT_LEAF_KEY(u));

	assert(t != NULL);

	/* collect important values from root. */
	p=t->root;
	external_fl=t->external_fl;

	if(!p) return 0; /* empty tree. */

	p=critbit_best_match(p, u_len, u, &external_fl);

	/** check for successful membership. */
	assert(external_fl != 0); /* curr no longer points to a struct critbit_node. */
	return strcmp(u, CRITBIT_LEAF_KEY(p)) ? NULL : (critbit_data_t)p;
}

static void **find_wherep(struct critbit_tree *t, critbit_flag_t **wherep_ex_fl, size_t ofs, unsigned char mask, size_t u_len, const char *u) {
	void **wherep;
	critbit_flag_t *external_fl;

	wherep=&t->root;
	external_fl=&t->external_fl;

	while(1) {
		struct critbit_node *p;
		unsigned dir;
		unsigned char c;


		/* stop at external nodes. */
		if(*external_fl) break;

		p=*wherep;

		if(p->ofs>ofs) break;
		if(p->ofs==ofs && p->critbitmask>mask) break;

		c=(p->ofs<u_len)?u[p->ofs]:0;

		dir=((p->critbitmask|c)+1)>>8; /* get 0 or 1 from the mask. */

		/* next node. */
		external_fl=&p->external_fl[dir];
		wherep=&p->child[dir];
	}

	*wherep_ex_fl=external_fl;
	return wherep;
}

/**
 * inserts preallocated data.
 */
EXPORT int critbit_insert(struct critbit_tree *t, critbit_data_t u) {
	size_t i, u_len=strlen(CRITBIT_LEAF_KEY(u));
	void **wherep;
	const void *p;
	unsigned external_fl;
	unsigned char mask;
	critbit_flag_t *wherep_ex_fl;
	unsigned dir;
	struct critbit_node *n;

	/* collect important values from root. */
	p=t->root;
	external_fl=t->external_fl;

	if(!p) { /* insert into empty tree. */
		t->external_fl=1;
		t->root=u;
		return 1;
	}

	p=critbit_best_match(p, u_len, u, &external_fl);

	assert(p != NULL);

	/** @todo find critical bit */

	i=critbit_diff_byte(strlen(CRITBIT_LEAF_KEY(p)), CRITBIT_LEAF_KEY(p), u_len, u, &mask);

	while(mask&(mask-1)) {
		mask&=mask-1;
	}
	mask^=255;

	/* printf("mask=%#x\n", mask); */

	/** @note assumes p[i] is 0 when end of the array */
	dir=((mask|CRITBIT_LEAF_KEY(p)[i])+1)>>8; /* get 0 or 1 from the mask. */

	/** @todo insert new string */

	n=critbit_allocate();
	if(!n) {
		return 0;
	}

	n->ofs=i;
	n->critbitmask=mask;
	n->child[1^dir]=u;
	n->external_fl[1^dir]=1;

	wherep=find_wherep(t, &wherep_ex_fl, i, mask, u_len, u);

	n->child[dir]=*wherep;
	n->external_fl[dir]=*wherep_ex_fl;
	*wherep=n;
	*wherep_ex_fl=0;

	return 0;
}

/**
 * delete an entry.
 *
 * @return the entry we have removed, or NULL on failure.
 */
EXPORT critbit_data_t critbit_delete(struct critbit_tree *t, const char *key) {
	critbit_flag_t external_fl, *q_external_fl, *p_external_fl;
	void **whereq, **wherep, *ret;
	unsigned dir;
	struct critbit_node *p, *q;
	size_t key_len=strlen(key);

	/* if the tree is empty then we're done. */
	if(!t->root) return 0; /* tree is empty. */

	whereq=NULL;
	p=*(wherep=&t->root);
	external_fl=*(p_external_fl=&t->external_fl);

	/* walk tree for best match to delete. */
	while(!external_fl) {
		unsigned char c;

		assert(wherep != NULL);

		p=*wherep;
		whereq=wherep;
		q_external_fl=p_external_fl;

		c=(p->ofs<key_len)?key[p->ofs]:0;
		dir=((p->critbitmask|c)+1)>>8; /* get 0 or 1 from the mask. */
		external_fl=p->external_fl[dir];
		wherep=&p->child[dir];
		p_external_fl=&p->external_fl[dir];
	}

	/* check that we have the right element. */
	if(strcmp(key, (const char*)*wherep)) return 0; /* no match. */

	/* past this point we have the right element. */

	/* node doesn't have a grandparent. */
	if(!whereq) {
		void *tmp=*wherep;
		t->root=NULL;
		t->external_fl=0;
		return tmp; /* removed successfully. */
	}

	assert(q_external_fl != NULL);
	assert(*q_external_fl == 0); /* live grandparents are always internal nodes. */

	q=*whereq; /* save q to be free()'d later. */
	ret=*wherep; /* ret=p */

	/* replace q with p. */
	*q_external_fl=p->external_fl[dir^1];
	*whereq=p->child[dir^1];

	critbit_free(q);

	return ret;
}

/**
 * TBD.
 */
static void critbit_print(void *p, int external_fl, FILE *out) {
	if(!p) return;
	if(!external_fl) {
		struct critbit_node *q=p;
		unsigned i;

		for(i=0;i<2;i++) {
			fprintf(out, "\"node_%p\" [shape=record,label=\"{%p|{<0>0|<1>1}}\"];\n", p, p);

			if(q->external_fl[i]) {
				fprintf(out, "\"node_%p\":%u -> \"%s\";\n", p, i, CRITBIT_LEAF_KEY(q->child[i]));
			} else {
				fprintf(out, "\"node_%p\":%u -> \"node_%p\":n;\n", p, i, q->child[i]);
			}
			critbit_print(q->child[i], q->external_fl[i], out);
		}
	} else {
		fprintf(out, "\"%s\" [shape=ellipse, style=filled];\n", CRITBIT_LEAF_KEY(p));
	}
}

/**
 * output a graphviz .dot file.
 * @param t tree.
 * @param filename if NULL output to stdout.
 */
EXPORT void critbit_dump(struct critbit_tree *t, const char *filename) {
	FILE *out;

	out=filename?fopen(filename, "w"):NULL;

	fprintf(out?out:stdout, "digraph critbit {\n");
	critbit_print(t->root, t->external_fl, out?out:stdout);
	fprintf(out?out:stdout, "}\n");

	if(out) fclose(out);
}

/**
 * TBD.
 */
static void critbit_test(void) {
	struct critbit_tree t={NULL, 0}; /* initialize with an empty tree. */
	char *testdata[] = {
		"commercially",
		"honked",
		"calibrators",
		"prejudices",
		"scow",
		"irretrievably",
		"lovesick",
		"mimosas",
		"deviates",
		"drolleries",
		"spiel",
		"chignon",
		"journeyman",
		"marabous",
		"hung",
		"hyphenations",
		"bribes",
		"timescale",
		"magazines",
		"flattening",
		"attacker",
		"hobbyists",
		"rapids",
		"peyote",
		"bamboozles",
		"diluting",
		"slathering",
		"dehumidifiers",
		"gravest",
		"hothoused",
		"arid",
		"chlorinates",
		"condense",
		"hewed",
		"beefy",
		"disdains",
		"reefed",
		"indistinctly",
		"bogs",
		"hired",
	};
	unsigned i, j;

	/* insert all the test data. */
	for(i=0;i<sizeof testdata/sizeof *testdata;i++) {
		critbit_insert(&t, testdata[i]);

		/* each time we insert check that all the data is still there. */
		for(j=0;j<i;j++) {
			critbit_data_t data;
			data=critbit_find(&t, testdata[i]);
			if(!data || strcmp(data, testdata[i])) {
				printf("%s():%u:error res=\'%s\'. should be '%s'. i=%u\n", __func__, __LINE__, data, testdata[i], i);
			}
		}
	}

	critbit_dump(&t, "critbit.dot");

	/* delete half of the entries. */
	for(i=0;i<(sizeof testdata/sizeof *testdata)/2;i++) {
		char *str;
		str=critbit_delete(&t, testdata[i]);
		if(!str || strcmp(str, testdata[i])) {
			fprintf(stderr, "Failed deletion. Tried to delete [%u] \"%s\" but got \"%s\".\n", i, testdata[i], str);
		}
	}

	fprintf(stderr, "*** Halfway done ***\n");
	critbit_dump(&t, "critbit-half.dot");

	/* delete the remaining. */
	for(;i<sizeof testdata/sizeof *testdata;i++) {
		char *str;
		str=critbit_delete(&t, testdata[i]);
		if(!str || strcmp(str, testdata[i])) {
			fprintf(stderr, "Failed deletion. Tried to delete [%u] \"%s\" but got \"%s\".\n", i, testdata[i], str);
		}
	}

	critbit_dump(&t, "critbit-empty.dot");
}

int main() {
	critbit_test();
	return 0;
}