lab6_list/list.c

#include <assert.h>
#include <string.h>

#include "util.h"
#include "list.h"


void
list_init(list *l)
{
	assert(l);
	memset(l, 0, sizeof(*l));
}

static inline list_node *
list_node_orphan(list_node *li)
{
	li->next = NULL;
	li->prev = NULL;
	return li;
}

void
list_clear(list *l, list_free_cb cb)
{
	assert(l);
	list_node *current = l->head;
	while (current != NULL) {
		list_node *next = current->next;
		if (cb) {
			cb(current);
		} else {
			free(current);
		}
		current = next;
	}
	l->head = NULL;
	l->tail = NULL;
}

void
list_push_front(list *l, list_node *item)
{
	assert(l && item);
	list_node_orphan(item);
	
	if (l->head == NULL) {
		l->head = item;
		l->tail = item;
		return;
	}
	
	item->next = l->head;
	l->head->prev = item;
	l->head = item;
}

void
list_push_back(list *l, list_node *item)
{
	assert(l && item);
	list_node_orphan(item);
	
	if (l->head == NULL) {
		l->head = item;
		l->tail = item;
		return;
	}
	
	item->prev = l->tail;
	l->tail->next = item;
	l->tail = item;
}

list_node *
list_first(list *l)
{
	assert(l);
	return l->head;
}

list_node *
list_last(list *l)
{
	assert(l);
	return l->tail;
}

size_t
list_len(list *l)
{
	assert(l);
	size_t len = 0;
	list_node *current = l->head;
	while (current != NULL) {
		len++;
		current = current->next;
	}
	return len;
}

list_node *
list_get(list *l, int idx)
{
	assert(l);
	if (idx < 0) return NULL;
	
	list_node *current = l->head;
	for (int i = 0; current != NULL && i < idx; i++) {
		current = current->next;
	}
	return current;
}

void
list_insert(list *l, list_node *item, int idx)
{
	assert(l && item);
	
	if (idx < 0) {
		list_push_back(l, item);
		return;
	}
	
	size_t length = list_len(l);
	if (idx > length) {
		xerror(1, "Index out of bounds in list_insert");
		return;
	}
	
	if (idx == 0) {
		list_push_front(l, item);
		return;
	}
	
	if (idx == length) {
		list_push_back(l, item);
		return;
	}
	
	list_node *prev_node = list_get(l, idx - 1);
	list_node_orphan(item);
	
	item->next = prev_node->next;
	item->prev = prev_node;
	prev_node->next->prev = item;
	prev_node->next = item;
}

list_node *
list_pop_front(list *l)
{
	assert(l);
	if (l->head == NULL) return NULL;
	list_node *node = l->head;
	l->head = node->next;

	if (l->head != NULL) {
		l->head->prev = NULL;
	} else {
		l->tail = NULL;
	}

	return list_node_orphan(node);
}

list_node *
list_pop_back(list *l)
{
	assert(l);
	if (l->tail == NULL) return NULL;

	list_node *node = l->tail;
	l->tail = node->prev;

	if (l->tail != NULL) {
		l->tail->next = NULL;
	} else {
		l->head = NULL;
	}

	return list_node_orphan(node);
}

int
list_index(list *l, list_node *n)
{
	assert(l && n);
	list_node *tmp;
	int i = 0;
	for (tmp = l->head; tmp != NULL; tmp = tmp->next) {
		if (tmp == n)
			return i;
		i++;
	}
	return -1;
}

list_node *
list_remove(list *l, int idx)
{
	assert(l);
	if (idx < 0 || l->head == NULL) return NULL;
	
	if (idx == 0) return list_pop_front(l);
	
	list_node *node = list_get(l, idx);
	if (node == NULL) return NULL;
	
	if (node->prev != NULL) {
		node->prev->next = node->next;
	}
	
	if (node->next != NULL) {
		node->next->prev = node->prev;
	} else {
		l->tail = node->prev;
	}
	
	return list_node_orphan(node);
}

void
list_reverse(list *l)
{
	assert(l);
	if (l->head == NULL) return;
	
	list_node *current = l->head;
	list_node *temp = NULL;
	l->tail = l->head;
	
	while (current != NULL) {
		temp = current->prev;
		current->prev = current->next;
		current->next = temp;
		current = current->prev;
	}
	
	if (temp != NULL) {
		l->head = temp->prev;
	}
}

void
list_pass(list *l, list_pass_cb cb, void *opaq)
{
	struct list_node *iter;
	list_for_each(iter, l) {
		cb(iter, opaq);
	}
}