/* @configure_input@ */

/*
**  Copyright 1998-2002 University of Illinois Board of Trustees
**  Copyright 1998-2002 Mark D. Roth
**  All rights reserved.
**
**  @LISTHASH_PREFIX@_list.c - linked list routines
**
**  Mark D. Roth <roth@uiuc.edu>
**  Campus Information Technologies and Educational Services
**  University of Illinois at Urbana-Champaign
*/

#include <config.h>
#include <compat.h>

#include <@LISTHASH_PREFIX@_listhash.h>

#include <stdio.h>
#include <errno.h>
#include <sys/param.h>

#ifdef STDC_HEADERS
# include <string.h>
# include <stdlib.h>
#endif


/*
** @LISTHASH_PREFIX@_listptr_reset() - reset a list pointer
*/
void
@LISTHASH_PREFIX@_listptr_reset(@LISTHASH_PREFIX@_listptr_t *lp)
{
	*lp = NULL;
}


/*
** @LISTHASH_PREFIX@_listptr_data() - retrieve the data pointed to by lp
*/
void *
@LISTHASH_PREFIX@_listptr_data(@LISTHASH_PREFIX@_listptr_t *lp)
{
	return (*lp)->data;
}


/*
** @LISTHASH_PREFIX@_list_new() - create a new, empty list
*/
@LISTHASH_PREFIX@_list_t *
@LISTHASH_PREFIX@_list_new(int flags, @LISTHASH_PREFIX@_cmpfunc_t cmpfunc)
{
	@LISTHASH_PREFIX@_list_t *newlist;

#ifdef DS_DEBUG
	printf("in @LISTHASH_PREFIX@_list_new(%d, 0x%lx)\n", flags, cmpfunc);
#endif

	if (flags != LIST_USERFUNC
	    && flags != LIST_STACK
	    && flags != LIST_QUEUE)
	{
		errno = EINVAL;
		return NULL;
	}

	newlist = (@LISTHASH_PREFIX@_list_t *)calloc(1, sizeof(@LISTHASH_PREFIX@_list_t));
	if (cmpfunc != NULL)
		newlist->cmpfunc = cmpfunc;
	else
		newlist->cmpfunc = (@LISTHASH_PREFIX@_cmpfunc_t)strcmp;
	newlist->flags = flags;

	return newlist;
}


/*
** @LISTHASH_PREFIX@_list_iterate() - call a function for every element
**				      in a list
*/
int
@LISTHASH_PREFIX@_list_iterate(@LISTHASH_PREFIX@_list_t *l,
			       @LISTHASH_PREFIX@_iterate_func_t plugin,
			       void *state)
{
	@LISTHASH_PREFIX@_listptr_t n;

	if (l == NULL)
		return -1;

	for (n = l->first; n != NULL; n = n->next)
	{
		if ((*plugin)(n->data, state) == -1)
			return -1;
	}

	return 0;
}


/*
** @LISTHASH_PREFIX@_list_empty() - empty the list
*/
void
@LISTHASH_PREFIX@_list_empty(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_freefunc_t freefunc)
{
	@LISTHASH_PREFIX@_listptr_t n;

	for (n = l->first; n != NULL; n = l->first)
	{
		l->first = n->next;
		if (freefunc != NULL)
			(*freefunc)(n->data);
		free(n);
	}

	l->nents = 0;
}


/*
** @LISTHASH_PREFIX@_list_free() - remove and free() the whole list
*/
void
@LISTHASH_PREFIX@_list_free(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_freefunc_t freefunc)
{
	@LISTHASH_PREFIX@_list_empty(l, freefunc);
	free(l);
}


/*
** @LISTHASH_PREFIX@_list_nents() - return number of elements in the list
*/
unsigned int
@LISTHASH_PREFIX@_list_nents(@LISTHASH_PREFIX@_list_t *l)
{
	return l->nents;
}


/*
** @LISTHASH_PREFIX@_list_add() - adds an element to the list
** returns:
**	0			success
**	-1 (and sets errno)	failure
*/
int
@LISTHASH_PREFIX@_list_add(@LISTHASH_PREFIX@_list_t *l, void *data)
{
	@LISTHASH_PREFIX@_listptr_t n, m;

#ifdef DS_DEBUG
	printf("==> @LISTHASH_PREFIX@_list_add(\"%s\")\n", (char *)data);
#endif

	n = (@LISTHASH_PREFIX@_listptr_t)malloc(sizeof(struct @LISTHASH_PREFIX@_node));
	if (n == NULL)
		return -1;
	n->data = data;
	l->nents++;

#ifdef DS_DEBUG
	printf("    @LISTHASH_PREFIX@_list_add(): allocated data\n");
#endif

	/* if the list is empty */
	if (l->first == NULL)
	{
		l->last = l->first = n;
		n->next = n->prev = NULL;
#ifdef DS_DEBUG
		printf("<== @LISTHASH_PREFIX@_list_add(): list was empty; "
		       "added first element and returning 0\n");
#endif
		return 0;
	}

#ifdef DS_DEBUG
	printf("    @LISTHASH_PREFIX@_list_add(): list not empty\n");
#endif

	if (l->flags == LIST_STACK)
	{
		n->prev = NULL;
		n->next = l->first;
		if (l->first != NULL)
			l->first->prev = n;
		l->first = n;
#ifdef DS_DEBUG
		printf("<== @LISTHASH_PREFIX@_list_add(): LIST_STACK set; "
		       "added in front\n");
#endif
		return 0;
	}

	if (l->flags == LIST_QUEUE)
	{
		n->prev = l->last;
		n->next = NULL;
		if (l->last != NULL)
			l->last->next = n;
		l->last = n;
#ifdef DS_DEBUG
		printf("<== @LISTHASH_PREFIX@_list_add(): LIST_QUEUE set; "
		       "added at end\n");
#endif
		return 0;
	}

	for (m = l->first; m != NULL; m = m->next)
		if ((*(l->cmpfunc))(data, m->data) < 0)
		{
			/*
			** if we find one that's bigger,
			** insert data before it
			*/
#ifdef DS_DEBUG
			printf("    @LISTHASH_PREFIX@_list_add(): gotcha..."
			       "inserting data\n");
#endif
			if (m == l->first)
			{
				l->first = n;
				n->prev = NULL;
				m->prev = n;
				n->next = m;
#ifdef DS_DEBUG
				printf("<== @LISTHASH_PREFIX@_list_add(): "
				       "added first, returning 0\n");
#endif
				return 0;
			}
			m->prev->next = n;
			n->prev = m->prev;
			m->prev = n;
			n->next = m;
#ifdef DS_DEBUG
			printf("<== @LISTHASH_PREFIX@_list_add(): added middle,"
			       " returning 0\n");
#endif
			return 0;
		}

#ifdef DS_DEBUG
	printf("    @LISTHASH_PREFIX@_list_add(): new data larger than current "
	       "list elements\n");
#endif

	/* if we get here, data is bigger than everything in the list */
	l->last->next = n;
	n->prev = l->last;
	l->last = n;
	n->next = NULL;
#ifdef DS_DEBUG
	printf("<== @LISTHASH_PREFIX@_list_add(): added end, returning 0\n");
#endif
	return 0;
}


/*
** @LISTHASH_PREFIX@_list_del() - remove the element pointed to by n
**				  from the list l
*/
void
@LISTHASH_PREFIX@_list_del(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_listptr_t *n)
{
	@LISTHASH_PREFIX@_listptr_t m;

#ifdef DS_DEBUG
	printf("==> @LISTHASH_PREFIX@_list_del()\n");
#endif

	l->nents--;

	m = (*n)->next;

	if ((*n)->prev)
		(*n)->prev->next = (*n)->next;
	else
		l->first = (*n)->next;
	if ((*n)->next)
		(*n)->next->prev = (*n)->prev;
	else
		l->last = (*n)->prev;

	free(*n);
	*n = m;
}


/*
** @LISTHASH_PREFIX@_list_next() - get the next element in the list
** returns:
**	1			success
**	0			end of list
*/
int
@LISTHASH_PREFIX@_list_next(@LISTHASH_PREFIX@_list_t *l,
			    @LISTHASH_PREFIX@_listptr_t *n)
{
	if (*n == NULL)
		*n = l->first;
	else
		*n = (*n)->next;

	return (*n != NULL ? 1 : 0);
}


/*
** @LISTHASH_PREFIX@_list_prev() - get the previous element in the list
** returns:
**	1			success
**	0			end of list
*/
int
@LISTHASH_PREFIX@_list_prev(@LISTHASH_PREFIX@_list_t *l,
			    @LISTHASH_PREFIX@_listptr_t *n)
{
	if (*n == NULL)
		*n = l->last;
	else
		*n = (*n)->prev;

	return (*n != NULL ? 1 : 0);
}


/*
** @LISTHASH_PREFIX@_str_match() - string matching function
** returns:
**	1			match
**	0			no match
*/
int
@LISTHASH_PREFIX@_str_match(char *check, char *data)
{
	return !strcmp(check, data);
}


/*
** @LISTHASH_PREFIX@_list_add_str() - splits string str into delim-delimited
**				      elements and adds them to list l
** returns:
**	0			success
**	-1 (and sets errno)	failure
*/
int
@LISTHASH_PREFIX@_list_add_str(@LISTHASH_PREFIX@_list_t *l,
			       char *str, char *delim)
{
	char tmp[10240];
	char *tokp, *nextp = tmp;

	strlcpy(tmp, str, sizeof(tmp));
	while ((tokp = strsep(&nextp, delim)) != NULL)
	{
		if (*tokp == '\0')
			continue;
		if (@LISTHASH_PREFIX@_list_add(l, strdup(tokp)))
			return -1;
	}

	return 0;
}


/*
** @LISTHASH_PREFIX@_list_search() - find an entry in a list
** returns:
**	1			match found
**	0			no match
*/
int
@LISTHASH_PREFIX@_list_search(@LISTHASH_PREFIX@_list_t *l,
			      @LISTHASH_PREFIX@_listptr_t *n, void *data,
			      @LISTHASH_PREFIX@_matchfunc_t matchfunc)
{
#ifdef DS_DEBUG
	printf("==> @LISTHASH_PREFIX@_list_search(l=0x%lx, n=0x%lx, \"%s\")\n",
	       l, n, (char *)data);
#endif

	if (matchfunc == NULL)
		matchfunc = (@LISTHASH_PREFIX@_matchfunc_t)@LISTHASH_PREFIX@_str_match;

	if (*n == NULL)
		*n = l->first;
	else
		*n = (*n)->next;

	for (; *n != NULL; *n = (*n)->next)
	{
#ifdef DS_DEBUG
		printf("checking against \"%s\"\n", (char *)(*n)->data);
#endif
		if ((*(matchfunc))(data, (*n)->data) != 0)
			return 1;
	}

#ifdef DS_DEBUG
	printf("no matches found\n");
#endif
	return 0;
}


/*
** @LISTHASH_PREFIX@_list_dup() - copy an existing list
*/
@LISTHASH_PREFIX@_list_t *
@LISTHASH_PREFIX@_list_dup(@LISTHASH_PREFIX@_list_t *l)
{
	@LISTHASH_PREFIX@_list_t *newlist;
	@LISTHASH_PREFIX@_listptr_t n;

	newlist = @LISTHASH_PREFIX@_list_new(l->flags, l->cmpfunc);
	for (n = l->first; n != NULL; n = n->next)
		@LISTHASH_PREFIX@_list_add(newlist, n->data);

#ifdef DS_DEBUG
	printf("returning from @LISTHASH_PREFIX@_list_dup()\n");
#endif
	return newlist;
}


/*
** @LISTHASH_PREFIX@_list_merge() - merge two lists into a new list
*/
@LISTHASH_PREFIX@_list_t *
@LISTHASH_PREFIX@_list_merge(@LISTHASH_PREFIX@_cmpfunc_t cmpfunc, int flags,
			     @LISTHASH_PREFIX@_list_t *list1,
			     @LISTHASH_PREFIX@_list_t *list2)
{
	@LISTHASH_PREFIX@_list_t *newlist;
	@LISTHASH_PREFIX@_listptr_t n;

	newlist = @LISTHASH_PREFIX@_list_new(flags, cmpfunc);

	n = NULL;
	while (@LISTHASH_PREFIX@_list_next(list1, &n) != 0)
		@LISTHASH_PREFIX@_list_add(newlist, n->data);
	n = NULL;
	while (@LISTHASH_PREFIX@_list_next(list2, &n) != 0)
		@LISTHASH_PREFIX@_list_add(newlist, n->data);

	return newlist;
}