ni-linkedlist/nilinkedlist.h

#include "../ni-arena/niarena.h"

typedef struct _NILinkedListNode {
	void *content;
	struct _NILinkedListNode *next;
} NILinkedListNode;

typedef struct _NILinkedList {
	size_t count;
	struct _NILinkedListNode *first;
} NILinkedList;

typedef void(NILinkedListVisitorFunctor)(const void *);
typedef void *(NILinkedListMapFunctor)(const void *, NIArena **arena);
typedef void(NILinkedListReduceFunctor)(void **accumulator, const void *current);

NILinkedList *nilinkedlist_new(NIArena **arena);
bool nilinkedlist_empty(NILinkedList **self);
void nilinkedlist_push(NILinkedList **self, NIArena **arena, void *content);
const void *nilinkedlist_pop(NILinkedList **self);
void nilinkedlist_emplace(NILinkedList **self, NIArena **arena, void *content, const size_t idx);
const void *nilinkedlist_peek(NILinkedList *self, const size_t idx);
void nilinkedlist_enqueue(NILinkedList **self, NIArena **arena, void *content);
const void *nilinkedlist_dequeue(NILinkedList **self);
void nilinkedlist_traverse(NILinkedList *list, NILinkedListVisitorFunctor f);
void nilinkedlist_map(NILinkedList *list, NIArena **arena, NILinkedListMapFunctor f, NILinkedList **out);
void nilinkedlist_reduce(NILinkedList *list, NILinkedListReduceFunctor f, void **out);

#ifdef NILINKEDLIST_IMPLEMENTATION

NILinkedList *
nilinkedlist_new(NIArena **arena)
{
	NILinkedList *list =
		(NILinkedList *)niarena_alloc(arena, sizeof(NILinkedList));
	list->count = 0;
	list->first = NULL;
	return list;
}

NILinkedListNode *
nilinkedlist_node_new(NIArena **arena)
{
	NILinkedListNode *node =
		(NILinkedListNode *)niarena_alloc(arena, sizeof(NILinkedListNode));
	node->next = NULL;
	node->content = NULL;
	return node;
}

bool
nilinkedlist_empty(NILinkedList **self)
{
	return (*self)->count == 0;
}

void
nilinkedlist_push(NILinkedList **self, NIArena **arena, void *content)
{
	NILinkedList *list = *self;
	NILinkedListNode *node = nilinkedlist_node_new(arena);
	node->content = content;
	if(list->first == NULL) {
		list->first = node;
	} else {
		NILinkedListNode *current_node = list->first;
		while(current_node->next != NULL) {
			current_node = current_node->next;
		}
		current_node->next = node;
	}
	list->count++;
}

const void *
nilinkedlist_pop(NILinkedList **self)
{
	NILinkedList *list = *self;
	if(list->count == 0) {
		return NULL;
	}
	NILinkedListNode *current_node = list->first;
	NILinkedListNode *previous_node = NULL;
	while(current_node->next != NULL) {
		previous_node = current_node;
		current_node = current_node->next;
	}
	if(previous_node == NULL) {
		list->first = NULL;
	} else {
		previous_node->next = NULL;
	}
	list->count--;
	return current_node->content;
}

void
nilinkedlist_emplace(NILinkedList **self, NIArena **arena, void *content, const size_t idx)
{
	NILinkedList *list = *self;
	NILinkedListNode *node = nilinkedlist_node_new(arena);
	node->content = content;
	if(list->count == 0 || idx == 0) {
		node->next = list->first;
		list->first = node;
	} else {
		NILinkedListNode *aux = list->first;
		const size_t real_idx = list->count < idx ? list->count : idx;
		for(size_t i = 1; i < real_idx; i++) {
			aux = aux->next;
		}
		node->next = aux->next;
		aux->next = node;
	}
	list->count++;
}

const void *
nilinkedlist_peek(NILinkedList *self, const size_t idx)
{
	if(self->count == 0 || idx >= self->count) {
		return NULL;
	}
	size_t real_idx = idx + 1; // 1 indexed
	NILinkedListNode *node = self->first;
	for(size_t i = 1; i < real_idx; i++) {
		node = node->next;
	}
	return node->content;
}

void
nilinkedlist_enqueue(NILinkedList **self, NIArena **arena, void *content)
{
	nilinkedlist_emplace(self, arena, content, 0);
}

const void *
nilinkedlist_dequeue(NILinkedList **self)
{
	return nilinkedlist_pop(self);
}

void
nilinkedlist_traverse(NILinkedList *list, NILinkedListVisitorFunctor f)
{
	if(list->count == 0) {
		return;
	}
	NILinkedListNode *node = list->first;
	while(node->next != NULL) {
		f(node->content);
		node = node->next;
	}
}

void
nilinkedlist_map(NILinkedList *list, NIArena **arena, NILinkedListMapFunctor f, NILinkedList **out)
{
	if(list->count > 0) {
		void *content;
		NILinkedListNode *node = list->first;
		while(node->next != NULL) {
			content = f(node->content, arena);
			nilinkedlist_push(out, arena, content);
			node = node->next;
		}
		content = f(node->content, arena);
		nilinkedlist_push(out, arena, content);
	}
}

void
nilinkedlist_reduce(NILinkedList *list, NILinkedListReduceFunctor f, void **out)
{
	if(list->count > 0) {
		NILinkedListNode *node = list->first;
		while(node->next != NULL) {
			f(out, node->content);
			node = node->next;
		}
		f(out, node->content);
	}
}

#endif