/* $Id$
 *
 * Tiny implementation of a single linked set.
 *
 * Copyright (C) 2008-2009 FAUmachine Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */

#include "slset.h"
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>

#if 0
#define DEBUG_MEM_FUNC
#endif

#ifdef DEBUG_MEM_FUNC
extern char etext;
extern char _init;

/* check if a function pointer is inside the text segment. */
#define CHECK_FUNC_ADDR(fun_ptr) { \
	if (fun_ptr != NULL) { \
		assert((void *)fun_ptr < (void *)&etext); \
		assert((void *)&_init < (void *)fun_ptr); \
	} \
}

#else /* ! DEBUG_MEM_FUNC */
#define CHECK_FUNC_ADDR(fun_ptr)	/* nothing */
#endif /* DEBUG_MEM_FUNC */

static int
__attribute__((__const__))
slset_compare_builtin(const void *o1, const void *o2)
{
	if (o1 < o2) {
		return -1;
	}

	if (o1 == o2) {
		return 0;
	}

	return 1;
}

static void
slset_destroy_set(struct slset *s, bool d_data, void (*deallocator)(void *))
{
	struct slset_entry *tmp;
	struct slset_entry *i = s->first;

	while (i != NULL) {
		tmp = i;
		i = i->next;
		if (d_data) {
			deallocator(tmp->data);
		}
		deallocator(tmp);
	}
}


struct slset *
slset_create(
	int (*compare)(const void *o1, const void *o2), 
	void *(*allocator)(size_t)
)
{
	struct slset *ret;
	CHECK_FUNC_ADDR(compare);

	ret = allocator(sizeof(struct slset));
	assert(ret != NULL);

	ret->compare = compare;
	if (ret->compare == NULL) {
		ret->compare = &slset_compare_builtin;
	}
	ret->first = NULL;
	return ret;
}

void
slset_destroy(struct slset *s, void (*deallocator)(void *))
{
	slset_destroy_set(s, false, deallocator);
	deallocator(s);
}

void
slset_destroy_data(struct slset *s, void (*deallocator)(void *))
{
	slset_destroy_set(s, true, deallocator);
	deallocator(s);
}


void
slset_add(
	struct slset *s, 
	void *data,
	void *(*allocator)(size_t)
)
{
	struct slset_entry *entry;
	struct slset_entry *i;
	struct slset_entry *last;
	bool past_entry = false;

	CHECK_FUNC_ADDR(s->compare);

	entry = allocator(sizeof(struct slset_entry));
	assert(entry != NULL);

	entry->data = data;

	if (s->first == NULL) {
		entry->next = NULL;
		s->first = entry;
		return;
	}

	/* entries already present. */
	last = NULL;
	for (i = s->first; i != NULL; i = i->next) {
		int cmp = s->compare(i->data, data);

		if (cmp > 0) {
			past_entry = true;
			break;
		}

		if (cmp == 0) {
			/* entry already present. do nothing. */
			return;
		}

		last = i;
	}

	if (past_entry) {
		int cmp;

		if (last == NULL) {
			entry->next = s->first;
			s->first = entry;
			return;
		}

		cmp = s->compare(last->data, data);
		assert(cmp == -1);

		entry->next = last->next;
		last->next = entry;

		return;
	}

	/* gone all through the list, but not past the entry where to 
	   insert -> insert after tail. */
	entry->next = NULL;
	last->next = entry;
	/* s->first doesn't change */
}

void
slset_move_all(
	struct slset *src, 
	struct slset *dst,
	void *(*allocator)(size_t),
	void (*deallocator)(void *)
)
{
	struct slset_entry *i;

	assert(src != NULL);
	assert(dst != NULL);
	assert(src->compare == dst->compare);

	/* FIXME use a faster implementation */
	for (i = src->first; i != NULL; i = i->next) {
		slset_add(dst, i->data, allocator);
	}

	slset_destroy_set(src, false, deallocator);
	src->first = NULL;
}

bool
slset_empty(const struct slset *s)
{
	return s->first == NULL;
}

bool
slset_contains(const struct slset *haystack, const void *needle)
{
	struct slset_entry *i;

	CHECK_FUNC_ADDR(haystack->compare);

	for (i = haystack->first; i != NULL; i = i->next) {
		int cmp = haystack->compare(i->data, needle);

		if (cmp == 0) {
			return true;
		}

		if (cmp > 0) {
			/* already past element */
			break;
		}

	}

	return false;
}

void
slset_remove(struct slset *s, const void *data, void (*deallocator)(void *))
{
	struct slset_entry *i;
	struct slset_entry *prev;

	CHECK_FUNC_ADDR(s->compare);

	prev = s->first;
	for (i = s->first; i != NULL; i = i->next) {
		int cmp = s->compare(i->data, data);

		if (cmp == 0) {
			/* found */
			if (prev == i) {
				/* first element */
				s->first = prev->next;
				deallocator(i);
				return;
			}

			prev->next = i->next;
			deallocator(i);
			return;
		}
		
		if (cmp > 0) {
			/* past element */
			return;
		}
		prev = i;
	}
}

void
slset_clear(struct slset *s, void (*deallocator)(void *))
{
	struct slset_entry *i;
	struct slset_entry *n;

	for (i = s->first; i != NULL; /* nothing */) {
		n = i;
		i = i->next;
		deallocator(n);
	}

	s->first = NULL;
}

void
slset_truncate_at(
	struct slset *s,
	const void *data,
	bool del_data,
	void (*deallocator)(void *)
)
{	
	struct slset_entry *i;
	struct slset_entry *prev = NULL;

	CHECK_FUNC_ADDR(s->compare);

	for (i = s->first; i != NULL; i = i->next) {
		int cmp = s->compare(i->data, data);
		if (cmp != -1) {
			break;
		}

		prev = i;
	}

	/* nothing to delete? */
	if (i == NULL) {
		return;
	}

	/* first entry? */
	if (prev == NULL) {
		s->first = NULL;
	} else {
		prev->next = NULL;
	}

	while (i != NULL) {
		prev = i;
		i = i->next;

		if (del_data) {
			deallocator(prev->data);
		}

		deallocator(prev);
	}
}

void
slset_debug_print(
	const struct slset *s, 
	const char *(*print_data)(const void *))
{
	const struct slset_entry *i;

	fprintf(stderr, "fauhdli slset: printing set instance %p\n", s);

	for (i = s->first; i != NULL; i = i->next) {
		fprintf(stderr, "fauhdli slset: "
			"tstruct %p, data %s\n", i, print_data(i->data));
	}
}