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;
}

//NOTE: Можем ли мы расчитывать на то, что node->next валидно после вызова list_free_cb???
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 != NULL) {
			cb(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;
	} else {
		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->tail == NULL) {
		l->head = item;
		l->tail = item;
	} else {
		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 count = 0;
	list_node *current = l->head;
	while (current != NULL) {
		count++;
		current = current->next;
	}
	return count;
}

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

void
list_insert(list *l, list_node *item, int idx)
{
	assert(l && item);
	
	if (idx <= 0) {
		list_push_front(l, item);
		return;
	}
	
	list_node *current = list_get(l, idx);
	if (current == NULL) {
		list_push_back(l, item);
	} else {
		list_node_orphan(item);
		item->prev = current->prev;
		item->next = current;
		current->prev->next = item;
		current->prev = 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) return NULL;
	
	if (idx == 0) {
		return list_pop_front(l);
	}
	
	list_node *node = list_get(l, idx);
	if (node == NULL) return NULL;
	
	if (node->next != NULL) {
		node->next->prev = node->prev;
	}
	if (node->prev != NULL) {
		node->prev->next = node->next;
	}
	
	if (node == l->tail) {
		l->tail = node->prev;
	}
	
	return list_node_orphan(node);
}

void
list_reverse(list *l)
{
	assert(l);
	list_node *current = l->head;
	list_node *temp = NULL;
	
	while (current != NULL) {
		temp = current->prev;
		current->prev = current->next;
		current->next = temp;
		current = current->prev;
	}
	
	if (temp != NULL) {
		l->tail = l->head;
		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);
	}
}