temelia/src/linked_list.c

/*!
 Temelia - Linked list implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu, Macovei Alexandru

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/linked_list.h"
#include "include/common.h"
#include "include/list_common.h"
#include <stdlib.h>

struct _linked_list_t
{
	/*! reference to the first node in the list */
	struct _linked_list_iterator_t *begin;

	/*! reference to the last node in the list */
	struct _linked_list_iterator_t *end;

	/*! list's size */
	int size;
};

/* Auxiliary recursive function used by the linked_list_print function if value == -1 . */
static void _linked_list_iterate_aux(linked_list_iterator_t it,
		void key_handler(void *, void *context), void *context);
static void _linked_list_reverse_aux(linked_list_iterator_t it);

linked_list_t linked_list_new(void)
{
	linked_list_t list;

	LIST_NEW(linked_list_t, list);

	return list;
}

void linked_list_delete(linked_list_t list)
{
	linked_list_iterator_t crt, prc;

	LIST_DELETE(list, crt, prc, linked_list_iterator);
}

linked_list_t linked_list_clone(linked_list_t list, void *(*clone)(void *key,
		void *context), void *context)
{
	linked_list_t clone_list;
	linked_list_iterator_t it;

	LIST_CLONE(linked_list, list, it, clone_list, clone, context);

	return clone_list;
}

int linked_list_is_empty(linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, -1);

	return list->size == 0;
}

void *linked_list_get_front(linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(list->size, ==, 0, INVALID_INPUT, NULL);

	return linked_list_iterator_get_key(list->begin);
}

void *linked_list_get_back(linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(list->size, ==, 0, INVALID_INPUT, NULL);

	return linked_list_iterator_get_key(list->end);
}

linked_list_iterator_t linked_list_get_begin(linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);

	return list->begin;
}

void linked_list_set_begin(linked_list_t list, linked_list_iterator_t begin)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	list->begin = begin;
}

linked_list_iterator_t linked_list_get_end(linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);

	return list->end;
}

void linked_list_set_end(linked_list_t list, linked_list_iterator_t end)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	list->end = end;
}

int linked_list_get_size(linked_list_t list)
{
	_ASSERT(list, ==, NULL, NULL_POINTER, -1);

	return list->size;
}

void linked_list_set_size(linked_list_t list, int size)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	list->size = size;
}

int linked_list_check(linked_list_t list, linked_list_iterator_t p)
{
	linked_list_iterator_t it;

	for (it = list->begin; it != NULL; it = linked_list_iterator_get_next(it))
		if (it == p)
			return 1;

	return 0;
}

linked_list_iterator_t linked_list_iterator_get_prev(linked_list_t list,
		linked_list_iterator_t p)
{
	linked_list_iterator_t it;

	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);

	if (p == list->begin)
		return NULL;
	for (it = list->begin;; it = linked_list_iterator_get_next(it))
		if (linked_list_iterator_get_next(it) == p)
			return it;
	return NULL;
}

linked_list_iterator_t linked_list_get_iterator_at(linked_list_t list,
		int position)
{
	linked_list_iterator_t it;
	int i;

	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(position, <, 0, INVALID_INPUT, NULL);
	_ASSERT(position, >=, list->size, INVALID_INPUT, NULL);

	for (i = 0, it = list->begin; i < position && it != NULL; i++, it
			= linked_list_iterator_get_next(it))
		;
	return it;
}

void *linked_list_get_key_at(linked_list_t list, int position)
{
	linked_list_iterator_t it = linked_list_get_iterator_at(list, position);

	if (it)
		return linked_list_iterator_get_key(it);
	return NULL;
}

void linked_list_set_key_at(linked_list_t list, int position, void *new_key)
{
	linked_list_iterator_t it = linked_list_get_iterator_at(list, position);

	if (it)
		linked_list_iterator_set_key(it, new_key);
}

linked_list_iterator_t linked_list_search_key(linked_list_t list, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	linked_list_iterator_t it;

	_ASSERT(list, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	for (it = list->begin; it != NULL; it = linked_list_iterator_get_next(it))
		if (!compare(linked_list_iterator_get_key(it), key, context))
			return it;
	return NULL;
}

int linked_list_search_iterator(linked_list_t list, linked_list_iterator_t it)
{
	int i;
	linked_list_iterator_t it_search;

	_ASSERT(list, ==, NULL, NULL_POINTER, -1);

	for (it_search = list->begin, i = 0; it_search; it_search
			= linked_list_iterator_get_next(it_search), i++)
		if (it_search == it)
			return i;

	return -1;
}

void linked_list_remove_iterator(linked_list_t list, linked_list_iterator_t it,
		int free)
{
	linked_list_iterator_t aux;

	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(it, ==, NULL, NULL_POINTER,);
	_ASSERT(list->size, ==, 0, EMPTY,);

	if (list->size == 1)
	{
		if (list->begin == it && list->end == it)
			list->begin = list->end = NULL;
		else
			_ASSERT(1, ==, 1, INVALID_INPUT,);
	}
	else
	{
		if (it == list->begin)
			list->begin = linked_list_iterator_get_next(list->begin);
		else if (it == list->end)
		{
			for (aux = list->begin; linked_list_iterator_get_next(aux) != it; aux
					= linked_list_iterator_get_next(aux))
				;
			linked_list_iterator_set_next(aux, NULL);
			list->end = aux;
		}
		else
		{
			for (aux = list->begin; linked_list_iterator_get_next(aux) != it; aux
					= linked_list_iterator_get_next(aux))
				;
			if (aux)
				linked_list_iterator_set_next(aux,
						linked_list_iterator_get_next(
								linked_list_iterator_get_next(aux)));
			else
				_ASSERT(1, ==, 1, INVALID_INPUT,);
		}
	}
	list->size--;

	if (free)
		_delete(it);
}

linked_list_iterator_t linked_list_remove_key(linked_list_t list, void *key,
		int compare(void *x, void *y, void *context), void *context, int free)
{
	linked_list_iterator_t it = linked_list_search_key(list, key, compare,
			context);

	if (it)
	{
		linked_list_remove_iterator(list, it, free);

		if (free)
			return NULL;
		return it;
	}
	return NULL;
}

void linked_list_insert_after(linked_list_t list, linked_list_iterator_t it,
		void *key)
{
	_ASSERT(list, ==, NULL, NULL_POINTER,);

	/*
	 * Inserting after NULL iterator is equivalent
	 * with inserting before list's begin iterator.
	 */
	if (it == NULL)
		linked_list_insert_before(list, list->begin, key);
	else
	{
		linked_list_iterator_join(it, linked_list_iterator_new(key, NULL),
				linked_list_iterator_get_next(it));

		if (it == list->end)
			list->end = linked_list_iterator_get_next(list->end);
		list->size++;
	}
}

void linked_list_insert_before(linked_list_t list, linked_list_iterator_t it,
		void *key)
{
	linked_list_iterator_t new_node;

	_ASSERT(list, ==, NULL, NULL_POINTER,);

	new_node = linked_list_iterator_new(key, NULL);

	if (list->size == 0)
	{
		if (it == NULL)
			list->begin = list->end = new_node;
		else
		{
			linked_list_iterator_delete(new_node);
			_ASSERT(NULL, ==, NULL, INVALID_INPUT,);
		}
	}
	else if (it == list->begin)
	{
		linked_list_iterator_set_next(new_node, it);
		list->begin = new_node;
	}
	else if (it == NULL)
	{
		linked_list_iterator_set_next(list->end, new_node);
		list->end = new_node;
	}
	else
	{
		linked_list_iterator_join(linked_list_iterator_get_prev(list, it),
				new_node, it);

		if (list->size == 1)
			list->begin = new_node;
	}

	list->size++;
}

void linked_list_push_front(linked_list_t list, void *key)
{
	linked_list_iterator_t new_node;

	_ASSERT(list, ==, NULL, NULL_POINTER,);

	new_node = linked_list_iterator_new(key, list->begin);

	if (list->size == 0)
		list->end = list->begin = new_node;
	else
		list->begin = new_node;
	list->size++;
}

void linked_list_push_back(linked_list_t list, void *key)
{
	linked_list_iterator_t new_node;

	_ASSERT(list, ==, NULL, NULL_POINTER,);

	new_node = linked_list_iterator_new(key, NULL);

	if (list->size == 0)
		list->end = list->begin = new_node;
	else
	{
		linked_list_iterator_set_next(list->end, new_node);
		list->end = new_node;
	}
	list->size++;
}

void linked_list_pop_front(linked_list_t list)
{
	linked_list_iterator_t aux;

	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(list->size, <=, 0, INVALID_INPUT,);

	aux = list->begin;
	list->begin = linked_list_iterator_get_next(list->begin);
	list->size--;

	if (list->size == 0)
		list->end = NULL;
	_delete(aux);
}

void linked_list_pop_back(linked_list_t list)
{
	linked_list_iterator_t it, aux;
	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(list->size, <=, 0, INVALID_INPUT,);

	aux = list->end;
	if (list->size == 1)
		list->begin = list->end = NULL;
	else
	{
		for (it = list->begin; linked_list_iterator_get_next(it) != list->end; it
				= linked_list_iterator_get_next(it))
			;
		list->end = it;
	}
	_delete(aux);
	list->size--;
}

void linked_list_iterate(linked_list_t list, void key_handler(void *x,
		void *context), void *context, int order)
{
	linked_list_iterator_t p;

	_ASSERT(list, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	if (order == 1)
		for (p = list->begin; p != NULL; p = linked_list_iterator_get_next(p))
			key_handler(linked_list_iterator_get_key(p), context);
	else if (order == -1)
		_linked_list_iterate_aux(list->begin, key_handler, context);
	else
		temelia_errno = INVALID_INPUT;
}

void linked_list_sort(linked_list_t list, int compare(void *x, void *y,
		void *context), void *context)
{
	void *aux;
	linked_list_iterator_t it;

	LIST_SORT(list, it, aux, compare, context, linked_list_iterator);
}

linked_list_t linked_list_merge(linked_list_t L1, linked_list_t L2,
		int compare(void *x, void *y, void *context), void *context)
{
	linked_list_t L3;
	linked_list_iterator_t it1, it2;
	void *key1, *key2;

	_ASSERT(L1, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(L2, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	L3 = linked_list_new();

	it1 = L1->begin;
	it2 = L2->begin;

	LIST_MERGE(L3, it1, it2, key1, key2, linked_list, compare, context);

	return L3;
}

void linked_list_reverse(linked_list_t list)
{
	void *aux;

	_ASSERT(list, ==, NULL, NULL_POINTER,);

	_linked_list_reverse_aux(list->begin);

	/*
	 * Swaps "begin" with "end" for a consistent reverse;
	 * also sets "end's" next iterator pointer to NULL
	 */
	aux = list->begin;
	list->begin = list->end;
	list->end = aux;
	linked_list_iterator_set_next(list->end, NULL);
}

void linked_list_spice(linked_list_t list1, linked_list_t list2,
		linked_list_iterator_t it)
{
	linked_list_iterator_t next_node;

	_ASSERT(list1, ==, NULL, NULL_POINTER,);
	_ASSERT(list2, ==, NULL, NULL_POINTER,);

	if (it == NULL)
	{
		/*
		 * => list2 -> list1
		 */
		if (list1->end == NULL || list1->begin == list1->end)
			list1->end = list2->end;
		linked_list_iterator_set_next(list2->end, list1->begin);
		list1->begin = list2->begin;
	}
	else if (list1->size > 0)
	{
		if (it == list1->end)
		{
			linked_list_iterator_set_next(list1->end, list2->begin);
			list1->end = list2->end;
		}
		else
		{
			// Finally, we can use the given iterator :-)
			next_node = linked_list_iterator_get_next(it);

			_ASSERT(next_node, ==, NULL, NULL_POINTER,);

			linked_list_iterator_set_next(it, list2->begin);
			linked_list_iterator_set_next(list2->end, next_node);
		}
	}
	else if (list1->size == 0)
	{
		// Simply copies the two pointers
		list1->begin = list2->begin;
		list1->end = list2->end;
	}

	list1->size += list2->size;
	_delete(list2);
}

static void _linked_list_iterate_aux(linked_list_iterator_t it,
		void key_handler(void *key, void *context), void *context)
{
	_ASSERT(it, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);
	_linked_list_iterate_aux(linked_list_iterator_get_next(it), key_handler,
			context);
	key_handler(linked_list_iterator_get_key(it), context);
}

static void _linked_list_reverse_aux(linked_list_iterator_t it)
{
	if (it == NULL)
		return;

	_linked_list_reverse_aux(linked_list_iterator_get_next(it));
	linked_list_iterator_set_next(linked_list_iterator_get_next(it), it);
}