C_lib/linked_lists/single_linked_list.c

/*
* C_lib Copyright (C) 2021 Wael Karram.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3 of the License.
*
* 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, see <https://www.gnu.org/licenses/>.
*/

/* This file contains the function implementations for single linked lists. */
/* Include guard + includes. */
#ifndef SINGLE_LINKED_LIST_C
#define SINGLE_LINKED_LIST_C
#include "single_linked_list.h"
#endif /* SINGLE_LINKED_LIST_C */

/* This function initializes a new linked list, returns NULL on failure. */
static inline linked_list_t* initialize_single_linked_list() {
	/* Variables. */
	linked_list_t *result;

	/* Attempt to allocate. */
	result = (linked_list_t*) malloc(sizeof(linked_list_t));

	/* Check if the allocation worked. */
	if (!result)
		return NULL;

	/* Initialize the internal fields. */
	result->length = 0L;
	result->head = NULL;

	/* Return the result. */
	return result;
}

/* This function appends a node to the given linked list. */
static inline void append_node_single_linked_list(linked_list_t *list, node_t *node) {
	/* Input sanity check. */
	assert(list && node);

	/* Set the next to NULL. */
	node->next = NULL;
	/* Check if we can append at the start. */
	if (!(list->head)) {
		list->head = node;
		(list->length)++;
		return;
	}
	/* Loop till we get to the end. */
	node_t *current = list->head;
	while (current->next) {
		current = current->next;
	}
	/* Got to the end, append and add. */
	current->next = node;
	(list->length)++;
}

/* This function prepends a node to the given linked list. */
static inline void prepend_node_single_linked_list(linked_list_t *list, node_t *node) {
	/* Input sanity check. */
	assert(list && node);

	/* Check if we can prepend at the start. */
	if (!(list->head)) {
		list->head = node;
		(list->length)++;
		return;
	}
	/* Set the node's next to the current head, and swap. */
	node->next = list->head;
	list->head = node;
	(list->length)++;
}

/* This function creates and appends a node to the given linked list, returns 1 on success and 0 on failure. */
static inline int append_node_data_single_linked_list(linked_list_t *list, void *data) {
	/* Input sanity check. */
	assert(list && data);

	/* Attempt to create a node. */
	node_t *node = (node_t*) malloc(sizeof(node_t));
	if (!node)
		return FAILURE_CODE_SINGLE_LINKED_LIST_C;
	/* Insert the data. */
	node->data = data;
	/* Delegate the work. */
	append_node_single_linked_list(list, node);
	return SUCCESS_CODE_SINGLE_LINKED_LIST_C;
}

/* This function creates and prepends a node to the given linked list, returns 1 on success and 0 on failure. */
static inline int prepend_node_data_single_linked_list(linked_list_t *list, void *data) {
	/* Input sanity check. */
	assert(list && data);

	/* Attempt to create a node. */
	node_t *node = (node_t*) malloc(sizeof(node_t));
	if (!node)
		return FAILURE_CODE_SINGLE_LINKED_LIST_C;
	/* Insert the data. */
	node->data = data;
	/* Delegate the work. */
	prepend_node_single_linked_list(list, node);
	return SUCCESS_CODE_SINGLE_LINKED_LIST_C;
}

/* This function inserts a node at the ith place. */
static inline void add_node_i_single_linked_list(linked_list_t *list, node_t *node, size_t i) {
	/* Input sanity check. */
	assert(list && node && list->length > i);

	/* Set the next to NULL. */
	node->next = NULL;
	/* Deal with special case of head. */
	if (!i) {
		node->next = list->head;
		list->head = node;
		(list->length)++;
		return;
	}
	/* Loop till we get to the right place. */
	node_t *current = list->head;
	for (; i > 0; i--)
		current = current->next;
	/* Insert the node. */
	node->next = current->next;
	current->next = node;
	(list->length)++;
}

/* This function creates and inserts a node at the ith place, returns 1 in success and 0 on failure. */
static inline int add_node_data_i_single_linked_list(linked_list_t *list, void *data, size_t i) {
	/* Input sanity check. */
	assert(list && list->length >= i);

	/* Attempt to create a node. */
	node_t *node = (node_t*) malloc(sizeof(node_t));
	if (!node)
		return FAILURE_CODE_SINGLE_LINKED_LIST_C;
	/* Insert the data. */
	node->data = data;
	/* Delegate. */
	add_node_i_single_linked_list(list, node, i);
	return SUCCESS_CODE_SINGLE_LINKED_LIST_C;
}

/* This function reads the data at the ith node, returns NULL on failure or NULL data! */
static inline void* read_node_i_single_linked_list(linked_list_t *list, size_t i) {
	/* Input sanity check. */
	assert(list && list->length > i);

	/* Check if dealing with the head. */
	if (!i)
		return (list->head) ? list->head->data : NULL;

	/* Loop and read. */
	node_t *current = list->head;
	for (; i > 0; i--)
		current = current->next;

	/* Got to the requested node, return the stored data. */
	return (current) ? current->data : NULL;
}

/* This function retrieves a pointer to the ith node, returns NULL on failure. */
static inline node_t* get_node_i_single_linked_list(linked_list_t *list, size_t i) {
	/* Input sanity check */
	assert(list && list->length > i);

	/* Check if dealing with the head. */
	if (!i)
		return list->head;

	/* Loop. */
	node_t *current = list->head;
	for (; i > 0; i--)
		current = current->next;

	/* Got to the requested node, return the pointer. */
	return current;
}

/* This function attempts to find the index of a given node, by pointer. */
/* Returns -1 when not found. */
static inline size_t get_node_index_pointer_single_linked_list(linked_list_t *list, node_t *node){
	/* Sanity check. */
	assert(list && node);

	/* Local variables. */
	node_t *current;
	size_t i = 0L;

	/* Attempt to search. */
	if (!(list->head))
		return INDEX_NOT_FOUND_CODE_SINGLE_LINKED_LIST_C;
	current = list->head;
	while (current && current != node) {
		current = current->next;
		i++;
	}

	/* Check if found or not. */
	return (i >= list->length) ? INDEX_NOT_FOUND_CODE_SINGLE_LINKED_LIST_C : i;
}

/* This function attempts to find the index of a given node, by data. */
/* Returns -1 when not found. */
static inline size_t get_node_index_data_single_linked_list(linked_list_t *list, void *data, int (*comparison_function)(const void*, const void*)) {
	/* Sanity check. */
	assert(list && comparison_function);

	/* Local variables. */
	node_t *current;
	size_t i = 0L;

	/* Check if there is anything to search in the first place. */
	if (!(list->head))
		return INDEX_NOT_FOUND_CODE_SINGLE_LINKED_LIST_C;
	/* Set the start. */
	current = list->head;
	/* Attempt to search. */
	while (current && !comparison_function(data, current->data)) {
		current = current->next;
		i++;
	}
	/* Check if we found it or not. */
	return (i >= list->length) ? INDEX_NOT_FOUND_CODE_SINGLE_LINKED_LIST_C : i;
}

/* This function deletes the ith node. */
static inline void remove_node_i_single_linked_list(linked_list_t *list, size_t i) {
	/* Input sanity check */
	assert(list && list->length > i);

	/* Deal with the special case of the head node. */
	if (!i) {
		if (!(list->head))
			return;
		node_t *tmp = list->head;
		list->head = tmp->next;
		tmp->next = NULL;
		free(tmp);
		(list->length)--;
		return;
	}
	/* Loop. */
	node_t *current = list->head;
	for (; i > 0; i--)
		current = current->next;
	/* Got to the requested node, delete it. */
	node_t *tmp = current->next;
	current->next = tmp->next;
	tmp->next = NULL;
	free(tmp);
	(list->length)--;
}

/* This function deletes the ith node with the data stored within it. */
static inline void remove_node_i_data_single_linked_list(linked_list_t *list, size_t i, void (*free_function)(const void*)) {
	/* Input sanity check */
	assert(list && list->length > i);

	/* Deal with the special case of the head node. */
	if (!i) {
		if (!(list->head))
			return;
		node_t *tmp = list->head;
		list->head = tmp->next;
		tmp->next = NULL;
		if (!free_function)
			free(tmp->data);
		else
			free_function(tmp->data);
		free(tmp);
		(list->length)--;
		return;
	}

	/* Loop to the correct location. */
	node_t *current = list->head;
	for (; i > 0; i--)
		current = current->next;
	/* Got to the requested node, delete it. */
	node_t *tmp = current->next;
	current->next = tmp->next;
	tmp->next = NULL;
	if (!free_function)
		free(tmp->data);
	else
		free_function(tmp->data);
	free(tmp);
	(list->length)--;
}

/* This function reads the data at the first node, note that it will return NULL on invalid input or first node being NULL. */
static inline void* read_node_head_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Delegate. */
	return read_node_i_single_linked_list(list, INDEX_HEAD_SINGLE_LINKED_LIST_C);
}

/* This function retrieves the first node, note that it will return NULL on invalid input or first node being NULL. */
static inline node_t* get_node_head_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Delegate. */
	return get_node_i_single_linked_list(list, INDEX_HEAD_SINGLE_LINKED_LIST_C);
}

/* This function deletes the first node, returns 1 on success and 0 on failure. */
static inline void remove_node_head_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Delegate. */
	return remove_node_i_single_linked_list(list, INDEX_HEAD_SINGLE_LINKED_LIST_C);
}

/* This function deletes the first node and the contents thereof. */
static inline void remove_node_head_data_single_linked_list(linked_list_t *list, void (*free_function)(const void*)) {
	/* Sanity check. */
	assert(list && free_function);

	/* Delegate. */
	return remove_node_i_data_single_linked_list(list, INDEX_HEAD_SINGLE_LINKED_LIST_C, free_function);
}

/* This function reads the data at the last node, will return NULL on invalid input or first node being NULL. */
static inline void* read_node_tail_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Delegate. */
	return read_node_i_single_linked_list(list, list->length - 1);
}

/* This function retrieves the last node, will return NULL on invalid input or the first node being NULL. */
/* Sets the error code in error (instead of returning it). */
static inline node_t* get_node_tail_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Delegate. */
	return get_node_i_single_linked_list(list, list->length - 1);
}

/* This function deletes the last node. */
static inline void remove_node_tail_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list && (list->head));

	/* Delegate. */
	return remove_node_i_single_linked_list(list, list->length - 1);
}

/* This function deletes the last node and the data thereof. */
static inline void remove_node_tail_data_single_linked_list(linked_list_t *list, void (*free_function)(const void*)) {
	/* Sanity check. */
	assert(list && (list->head));

	/* Delegate. */
	return remove_node_i_data_single_linked_list(list, list->length - 1, free_function);
}

/* This function deletes all the nodes of the given list and the list itself. */
/* Note that it doesn't touch the data, returns 1 on success and 0 on failure - failure is potentially undefined behavior! */
/* Will return -1 when the list was freed successfully but it was initially malformed. */
static inline int clear_list_single_linked_list(linked_list_t **list) {
	/* Sanity check. */
	assert(list && *list);

	/* Local variables. */
	node_t *current = (*list)->head, *tmp;
	size_t length, count = 0;
	/* Loop and free. */
	while(current) {
		count++;
		tmp = current->next;
		free(current);
		current = tmp;
	}
	/* Save the list's length. */
	length = (*list)->length;

	/* Should all be freed by now, free the list and return. */
	free(*list);
	*list = NULL;
	return (count == length) ? SUCCESS_CODE_SINGLE_LINKED_LIST_C : CODE_FREE_SUCCESS_MALFORMED_SINGLE_LINKED_LIST_C;
}

/* This function deletes all the nodes and data stored within of the given list and the list itself. */
/* Returns 1 on success and 0 on failure, undefined behavior in the latter. Will return -1 when the list was freed successfully but was initially malformed. */
/* If free_function is NULL will use STDLIB free instead. */
static inline int clear_list_data_single_linked_list(linked_list_t **list, void (*free_function)(const void*)) {
	/* Sanity check. */
	assert(list && *list);

	/* Local variables. */
	node_t *current = (*list)->head, *tmp;
	size_t length, count = 0;

	/* Loop and free. */
	while(current) {
		count++;
		tmp = current->next;
		if (free_function)
			free_function(current->data);
		else
			free(current->data);
		free(current);
		current = tmp;
	}
	/* Save the list's length. */
	length = (*list)->length;

	/* Should all be freed by now, free the list and return. */
	free(*list);
	*list = NULL;
	return (count == length) ? SUCCESS_CODE_SINGLE_LINKED_LIST_C : CODE_FREE_SUCCESS_MALFORMED_SINGLE_LINKED_LIST_C;
}

/* This function deletes all the nodes of a linked list. */
static inline void clear_list_nodes_single_linked_list(linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Local variables. */
	node_t *current = list->head, *tmp;
	size_t length, count = 0L;

	/* Special case. */
	if (!(list->length) || !(list->head))
		return;

	/* Loop and free. */
	while (current) {
		count++;
		tmp = current->next;
		free(current);
		current = tmp;
	}
	/* Reset the length. */
	list->length = 0L;
}

/* This function deletes all the nodes and the data stored within of a linked list. */
/* If free_function is NULL will use STDLIB free instead. */
static inline void clear_list_nodes_data_single_linked_list(linked_list_t *list, void (*free_function)(const void*)) {
	/* Sanity check. */
	assert(list);

	/* Local variables. */
	node_t *current = list->head, *tmp;
	size_t length, count = 0L;

	/* Special case. */
	if (!(list->length) || !(list->head))
		return;

	/* Loop and free. */
	while (current) {
		count++;
		tmp = current->next;
		if (free_function)
			free_function(current->data);
		else
			free(current->data);
		free(current);
		current = tmp;
	}
	/* Reset the length. */
	list->length = 0L;
}

/* This function attetmps to serialize a linked list into an array. */
/* Note that the array has to be allocated by the caller. */
/* The array setting function is used to set the values at an index, takes the pointer to the array, index, and value to put. */
static inline void *serialize_linked_list(linked_list_t *list, void (*array_setting_function)(void*, size_t, void*), void *array) {
	/* Local variables. */
	node_t *current;
	size_t i = 0L;

	/* Sanity check. */
	assert(list && (list->head) && list->length >= 0 && array && array_setting_function);

	/* Fill the array. */
	for (current = list->head; current; i++) {
		/* Set the ith value. */
		array_setting_function(array, i, current->data);
		/* Advance the pointer. */
		current = current->next;
	}

	/* Return the result. */
	return array;
}