Subversion Repositories igor

/*
 * Copyright (c) 2007 The Akuma Project
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 * $Id: linkedlist.c 108 2007-05-13 18:47:48Z eirik $
 */
 
#include <stdio.h>
#include <stdlib.h>
 
#include "linkedlist.h"
 
llist_t
llist_make(void)
{
	llist_t llist;
 
	llist = malloc(sizeof *llist);
	if (llist == NULL)
		return NULL;
	llist->head = NULL;
	llist->tail = NULL;
 
	return llist;
}
 
void
llist_destroy(llist_t head)
{
	llist_node_t node, next;
 
	for (node = head->head; node; node = next) {
		next = node->next;
		free(node);
	}
 
	free(head);
}
 
enum llist_add_type {
	HEAD,
	TAIL
};
 
static int
llist_add(llist_t head, void *obj, enum llist_add_type type)
{
	llist_node_t node;
 
	node = malloc(sizeof *node);
	if (node == NULL)
		return 0;
 
	node->next = NULL;
	node->obj = obj;
 
	/* First object added */
	if (head->head == NULL) {
		head->head = node;
		head->tail = node;
	} else if (type == TAIL) {
		head->tail->next = node;
		head->tail = node;
	} else if (type == HEAD) {
		node->next = head->head;
		head->head = node;
	}
 
	return 1;
}
 
int
llist_add_pos(llist_t head, void *obj, int pos)
{
	llist_node_t node, prev, newnode;
	int n;
 
	if (head->head == NULL) {
		return llist_add_head(head, obj);
	}
	newnode = malloc(sizeof *newnode);
	if (newnode == NULL)
		return 0;
	newnode->obj = obj;
	newnode->next = NULL;
 
	node = head->head;
	prev = NULL;
	for(node = head->head, n = 0; n < pos; node = node->next, n++) {
		if (node == NULL) {
			prev->next = newnode;
			head->tail = newnode;
			return 1;
		}
		prev = node;
	}
	if (prev == NULL) {
		head->head = newnode;
		newnode->next = node;
	} else {
		newnode->next = prev->next;
		prev->next = newnode;
	}
 
	return 1;
}
 
int
llist_add_tail(llist_t head, void *obj)
{
	return llist_add(head, obj, TAIL);
}
 
int
llist_add_head(llist_t head, void *obj)
{
	return llist_add(head, obj, HEAD);
}
 
void *
llist_pop(llist_t head)
{
	llist_node_t node;
	void *obj;
 
	if (head->head == NULL)
		return NULL;
	node = head->head;
	if (node->next == NULL) {
		head->head = NULL;
		head->tail = NULL;
	}
	else {
		head->head = node->next;
	}
 
	obj = llist_getobj(node);
	free(node);
	return obj;
}
 
/* zero indexed */
void *
llist_getelem(llist_t head, int num)
{
	int i;
	llist_node_t node;
 
	i = 0;
	LLIST_FOREACH(head, node) {
		if (i == num)
			return llist_getobj(node);
		i++;
	}
	return NULL;
}
 
void *
llist_getobj(llist_node_t node)
{
	return node->obj;
}
 
int
llist_empty(llist_t head)
{
	return (head->head == NULL);
}
 
llist_t
llist_copy(llist_t old)
{
	llist_t new;
	llist_node_t node;
 
	new = llist_make();
	if (new == NULL)
		return NULL;
	LLIST_FOREACH(old, node) {
		if (!llist_add_tail(new, llist_getobj(node))) {
			llist_destroy(new);
			return NULL;
		}
	}
 
	return new;
}
 
int
llist_insert_list_head(llist_t head, llist_t add)
{
	llist_t copy = llist_copy(add);
	llist_node_t node;
 
	if (copy == NULL)
		return 0;
	if (head->head == NULL) {
		head->head = copy->head;
		head->tail = copy->tail;
	} else {
		node = head->head;
		head->head = copy->head; 
		copy->tail->next = node;
	}
	free(copy);
 
	return 1;
}
 
int
llist_size(llist_t head)
{
	int n;
	llist_node_t node;
 
	n = 0;
	LLIST_FOREACH(head, node)
		n++;
 
	return n;
}
 
void
llist_remove_elem(llist_t list, int n)
{
	llist_node_t cur, prev;
	int i;
 
	if (list->head == NULL)
		return;
 
	prev = NULL;
	for(cur = list->head, i = 0; cur; cur = cur->next, i++) {
		if (i == n) {
			if (cur == list->head) {
				list->head = cur->next;
			}
			if (cur == list->tail) {
				list->tail = prev;
			}
			prev->next = cur->next;
			free(cur);
			return;
		}
		i++;
		prev = cur;
	}
}
 
int
llist_insert_list(llist_t list, llist_t newlist, int pos)
{
	llist_node_t node;
	int n;
 
	n = pos;
	LLIST_FOREACH(newlist, node) {
		if (!llist_add_pos(list, llist_getobj(node), n++))
			return 0;
	}
 
	return 1;
}
 
#ifdef TEST_LINKEDLIST
 
int
main(void)
{
	llist_t head;
	llist_node_t node;
 
	if ((head = llist_make()) == NULL) {
		fprintf(stderr, "Unable to make linked list\n");
		exit(1);
	}
 
	printf("Add1: %d\n", llist_add_tail(head, "eirik"));
	printf("Add2: %d\n", llist_add_tail(head, "akuma"));
	printf("Add3: %d\n", llist_add_head(head, "jeroen"));
 
	LLIST_FOREACH(head, node) {
		printf("Got: %s\n", llist_getobj(node));
	}
 
	llist_destroy(head);
 
	return 0;
}
 
#endif /* TEST_LINKEDLIST */