C_lib/linked_lists/double_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 a double-linked-list. */
#ifndef DOUBLE_LINKED_LIST_C
#define DOUBLE_LINKED_LIST_C
#include "double_linked_list.h"
#endif /* DOUBLE_LINKED_LIST_C */

/* Function implementations. */

/* This function initializes a new double-linked list, returns NULL on failure. */
static inline double_linked_list_t* initialize_double_linked_list() {
	/* Local variables. */
	double_linked_list_t* list;

	/* Attempt to allocate. */
	list = (double_linked_list_t*) malloc(sizeof(double_linked_list_t));

	/* Check if the allocation failed. */
	if (!list)
		return NULL;

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

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

/* This function appends a node to the given linked list. */
static inline void append_node_double_linked_list(double_linked_list_t *list, double_node_t *node){
	/* Sanity check - make sure input is not NULL and list state is defined! */
	assert(list && node && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Set the next node to NULL. */
	node->next = NULL;

	/* The data is in a defined state, append. */
	/* Split cases according to if this is the first node or not. */
	if (!(list->head)) {
		/* Set the previous node to NULL. */
		node->previous = NULL;
		/* Attach. */
		list->head = node;
		list->tail = node;
		list->length = 1;
		return;
	}

	/* Connect the nodes and update the tail. */
	list->tail->next = node;
	node->previous = list->tail;
	list->tail = node;
	(list->length)++;
}

/* This function prepends a node the the given linked list. */
static inline void prepend_node_double_linked_list(double_linked_list_t *list, double_node_t *node){
	/* Sanity check - make sure input is not NULL and list state is defined! */
	assert(list && node && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Set the previous node to NULL. */
	node->previous = NULL;

	/* The data is in a defined state, prepend. */
	/* Split cases according to if this is the first node or not. */
	if (!(list->head)) {
		/* Set the next node to NULL. */
		node->next = NULL;
		/* Attach. */
		list->head = node;
		list->tail = node;
		list->length = 1;
		return;
	}

	/* Connect the nodes and update the head. */
	list->head->previous = node;
	node->next = list->head;
	list->tail = node;
	(list->length)++;
}

/* This function creates and appends a node to the given linked list. */
/* Returns SUCCESS_CODE_DOUBLE_LINKED_LIST_C on success, and FAILURE_CODE_DOUBLE_LINKED_LIST_C on failure. */
static inline int append_node_data_double_linked_list(double_linked_list_t *list, void *data){
	/* Sanity check - make sure input is not NULL and list state is defined! */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Local variables. */
	double_node_t* node;

	/* Attempt to allocate the node. */
	node = (double_node_t*) malloc(sizeof(double_node_t));
	/* Check for allocation failure. */
	if (!node)
		return FAILURE_CODE_DOUBLE_LINKED_LIST_C;
	/* Store the value. */
	node->data = data;

	/* Delegate. */
	append_node_double_linked_list(list, node);
	return SUCCESS_CODE_DOUBLE_LINKED_LIST_C;
}

/* This function creates and prepends a node to the given linked list. */
/* Returns SUCCESS_CODE_DOUBLE_LINKED_LIST_C on success, and FAILURE_CODE_DOUBLE_LINKED_LIST_C on failure. */
static inline int prepend_node_data_double_linked_list(double_linked_list_t *list, void *data){
	/* Sanity check - make sure input is not NULL and list state is defined! */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Local variables. */
	double_node_t* node;

	/* Attempt to allocate the node. */
	node = (double_node_t*) malloc(sizeof(double_node_t));
	/* Check for allocation failure. */
	if (!node)
		return FAILURE_CODE_DOUBLE_LINKED_LIST_C;
	/* Store the value. */
	node->data = data;

	/* Delegate. */
	prepend_node_double_linked_list(list, node);
	return SUCCESS_CODE_DOUBLE_LINKED_LIST_C;
}

/* This function inserts a node at the ith place. */
static inline void add_node_i_double_linked_list(double_linked_list_t *list, double_node_t *node, size_t i) {
	/* Sanity check - make sure input is not NULL, list state is defined and index is valid. */
	assert(list && node && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && i < list->length);

	/* Deal with special "easy" cases. */
	if (!i) {
		prepend_node_double_linked_list(list, node);
		return;
	}
	if (i == list->length) {
		append_node_double_linked_list(list, node);
		return;
	}

	/* Local variables. */
	size_t index;
	double_node_t* current;

	/* Loop until we get to the desired node. */
	current = list->head;
	for (index = 0L; index < i; index++)
		current = current->next;
	/* Insert before current. */
	node->previous = current->previous;
	node->next = current;
	current->previous->next = node;
	current->previous = node;

	/* Increase the length. */
	(list->length)++;
}

/* This function creates and inserts a node at the ith place. */
/* Returns SUCCESS_CODE_DOUBLE_LINKED_LIST_C on success, and FAILURE_CODE_DOUBLE_LINKED_LIST_C on failure. */
static inline int add_node_data_i_double_linked_list(double_linked_list_t *list, void *data, size_t i) {
	/* Sanity check - make sure list state is defined and index is valid. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && i < list->length);

	/* Local variables. */
	double_node_t* node;

	/* Attempt to allocate the node. */
	node = (double_node_t*) malloc(sizeof(double_node_t));
	/* Check for allocation failure. */
	if (!node)
		return FAILURE_CODE_DOUBLE_LINKED_LIST_C;
	/* Store the data. */
	node->data = data;

	/* Delegate. */
	add_node_i_double_linked_list(list, node, i);
	return SUCCESS_CODE_DOUBLE_LINKED_LIST_C;
}

/* This function reads the data at the ith node. */
/* Returns NULL on failure! (Even if NULL can be a legitimate value). */
static inline void* read_node_i_double_linked_list(double_linked_list_t *list, size_t i) {
	/* Sanity check - make sure list state is defined and index is valid. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && i < list->length);

	/* Local variables. */
	size_t index;
	double_node_t* current;

	/* Loop until we get to the desired node. */
	current = list->head;
	for (index = 0L; index < i; index++)
		current = current->next;

	/* Return the data. */
	return current->data;
}

/* This function retrieves a pointer to the ith node. */
/* Returns NULL on failure! */
static inline double_node_t* get_node_i_double_linked_list(double_linked_list_t *list, size_t i) {
	/* Sanity check - make sure list state is defined and index is valid. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && i < list->length);

	/* Local variables. */
	size_t index;
	double_node_t* current;

	/* Loop till we get to the desired node. */
	current = list->head;
	for (index = 0L; index < i; index++)
		current = current->next;

	/* Return the node pointer. */
	return current;
}

/* This function attempts to find the index of a given node, by pointer. */
/* Returns INDEX_NOT_FOUND_CODE_DOUBLE_LINKED_LIST_C on failure. */
static inline size_t get_node_index_pointer_double_linked_list(double_linked_list_t *list, double_node_t *node) {
	/* Sanity check. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && node);

	/* Local variables. */
	size_t index = 0L;
	double_node_t* current = list->head;

	/* Loop and look for it. */
	while (current != node && current != NULL) {
		current = current->next;
		index++;
	}

	/* Return according to if found or not. */
	return (current != NULL) ? index : INDEX_NOT_FOUND_CODE_DOUBLE_LINKED_LIST_C;
}

/* This function deletes the ith node, leaves the data AS IS! */
static inline void remove_node_i_double_linked_list(double_linked_list_t *list, size_t i) {
	/* Sanity check - make sure list state is defined and index is valid. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && i < list->length);

	/* Local variables. */
	double_node_t* current;
	size_t index;

	/* Special case of an empty list. */
	if (!(list->length)) {
		/* Do nothing. */
		return;
	}

	/* Special case of a list with a single node. */
	if (list->length == 1L) {
		/* Clear the node. */
		free(list->head);
		/* "Relink" */
		list->head = NULL;
		list->tail = NULL;
		list->length = 0L;
		/* Done. */
		return;
	}

	/* Loop till we get to the desired node. */
	while (index < i) {
		/* Increment. */
		index++;
		current = current->next;
	}

	/* Try to remove the node. */
	/* Check if head or tail. */
	if (!(current->previous)) {
		/* Update head. */
		list->head = current->next;
		list->head->previous = NULL;
		/* Free node struct. */
		free(current);
		current = NULL;
		/* Update length. */
		(list->length)--;
		/* Done. */
		return;
	}
	if (!(current->next)) {
		/* Update tail. */
		list->tail = current->previous;
		current->previous->next = NULL;
		/* Free node struct. */
		free(current);
		current = NULL;
		/* Update length. */
		(list->length)--;
		/* Done. */
		return;
	}

	/* General (middle) case. */
	/* Update preceding and following nodes. */
	current->previous->next = current->next;
	current->next->previous = current->previous;
	/* Free node struct. */
	free(current);
	current = NULL;
	/* Update length. */
	(list->length)--;
}

/* This function deletes the ith node and the data stored within. */
/* If free_function is NULL, will use the stdlib's free(). */
static inline void remove_node_i_data_double_linked_list(double_linked_list_t *list, size_t i, void (*free_function)(const void*)) {
	/* Sanity check - make sure list state is defined and index is valid. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))) && i < list->length);

	/* Local variables. */
	double_node_t* current;
	size_t index;

	/* Special case of an empty list. */
	if (!(list->length)) {
		/* Done nothing. */
		return;
	}

	/* Special case of a list with a single node. */
	if (list->length == 1L) {
		/* Free the data within the node. */
		if (!free_function)
			free(list->head->data);
		else
			free_function(list->head->data);
		/* Clear the node. */
		free(list->head);
		/* "Relink" */
		list->head = NULL;
		list->tail = NULL;
		list->length = 0L;
		/* Done. */
		return;
	}

	/* Loop till we get to the desired node. */
	for (index = 0L; index < i; index++)
		current = current->next;

	/* Try to remove the node. */
	/* Check if head or tail. */
	if (!(current->previous)) {
		/* Update head. */
		list->head = current->next;
		current->next->previous = NULL;
		/* Free node struct and the data within it. */
		if (!free_function)
			free(current->data);
		else
			free_function(current->data);
		free(current);
		current = NULL;
		/* Update length. */
		(list->length)--;
		/* Done. */
		return;
	}
	if (!(current->next)) {
		/* Update tail. */
		list->tail = current->previous;
		current->previous->next = NULL;
		/* Free node struct and the data within it. */
		if (!free_function)
			free_function(current->data);
		else
			free(current->data);
		free(current);
		current = NULL;
		/* Update length. */
		(list->length)--;
		/* Done. */
		return;
	}

	/* General (middle) case. */
	/* Update preceding and following nodes. */
	current->previous->next = current->next;
	current->next->previous = current->previous;
	/* Free node struct and the data within it. */
	if (!free_function)
		free_function(current->data);
	else
		free(current->data);
	free(current);
	current = NULL;
	/* Update length. */
	(list->length)--;
}

/* This function reads the data at the first node. */
/* Returns NULL on error or empty list. */
static inline void* read_node_head_double_linked_list(double_linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Return the data. */
	return (list->head) ? list->head->data : NULL;
}

/* This function retrieves the first node. */
/* Returns NULL on error or empty list. */
static inline double_node_t* get_node_head_double_linked_list(double_linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Return the data. */
	return list->head;
}

/* This function deletes the first node. */
static inline void remove_node_head_double_linked_list(double_linked_list_t *list) {
	/* Sanity check. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Check if we have to do anything at all. */
	if (!(list->head))
		return;

	/* Split into cases. */
	if (list->length == 1L) {
		/* Clear the only node. */
		free(list->head);
		/* Set the list to be empty again. */
		list->head = NULL;
		list->tail = NULL;
		list->length = 0L;
		/* Done. */
		return;
	}

	/* Length over one. */
	/* Local variables. */
	double_node_t* tmp = list->head;

	/* Reconnect. */
	list->head = list->head->next;
	list->head->previous = NULL;

	/* Free the node. */
	free(tmp);

	/* Change the length. */
	(list->length)--;
}

/* This function deletes the first node and the data thereof. */
/* If free_function is NULL, will use the stdlib's free(). */
static inline void remove_node_head_data_double_linked_list(double_linked_list_t *list, void (*free_function)(const void*)) {
	/* Sanity check. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Check if we have to do anything at all. */
	if (!(list->head))
		return;

	/* Split into cases. */
	if (list->length == 1L) {
		/* Clear the only node and the data therof. */
		if (!free_function)
			free(list->head->data);
		else
			free_function(list->head->data);
		free(list->head);
		/* Set the list to be empty again. */
		list->head = NULL;
		list->tail = NULL;
		list->length = 0L;
		/* Done. */
		return;
	}

	/* Length over one. */
	/* Local variables. */
	double_node_t* tmp = list->head;

	/* Reconnect. */
	list->head = list->head->next;
	list->head->previous = NULL;

	/* Free the node and data thereof. */
	if (!free_function)
		free(list->head->data);
	else
		free_function(list->head->data);
	free(tmp);

	/* Change the length. */
	(list->length)--;
}

/* This function reads the data at the last node. */
/* Returns NULL on error or empty list. */
static inline void* read_node_tail_double_linked_list(double_linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Return the data. */
	return (list->tail) ? list->tail->data : NULL;
}

/* This function retrieves the last node. */
static inline double_node_t* get_node_tail_double_linked_list(double_linked_list_t *list) {
	/* Sanity check. */
	assert(list);

	/* Return the data. */
	return list->tail;
}

/* This function deletes the last node. */
/* Failure is also when the list state isn't properly defined! */
static inline void remove_node_tail_double_linked_list(double_linked_list_t *list) {
	/* Sanity check. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Local variables. */
	double_node_t *current;

	/* Split cases. */
	/* Empty list. */
	if (!(list->length))
		return;
	/* Single node case. */
	if (list->length == 1L) {
		free(list->tail);
		list->head = NULL;
		list->tail = NULL;
		list->length = 0L;
		return;
	}

	/* General case. */
	/* Save the pointer to the node to be deleted. */
	current = list->tail;
	/* Relink the tail. */
	list->tail = current->previous;
	free(current);
	(list->length)--;
}

/* This function deletes the last node and the data thereof. */
/* If free_function is NULL, will use the stdlib's free(). */
static inline void remove_node_tail_data_double_linked_list(double_linked_list_t *list, void (*free_function)(const void*)) {
	/* Sanity check. */
	assert(list && ((list->head && list->tail) || (!(list->head) && !(list->tail))));

	/* Local variables. */
	double_node_t *current;

	/* Split cases. */
	/* Empty list. */
	if (!(list->length))
		return;
	/* Single node case. */
	if (list->length == 1L) {
		/* Free the data. */
		if (!free_function)
			free(list->tail->data);
		else
			free_function(list->tail->data);
		/* Free the node and clean up. */
		free(list->tail);
		list->head = NULL;
		list->tail = NULL;
		list->length = 0L;
		return;
	}

	/* General case. */
	/* Save the pointer to the node to be deleted. */
	current = list->tail;
	/* Free the data. */
	if (!free_function)
		free(list->tail->data);
	else
		free_function(list->tail->data);
	/* Free the node and clean up. */
	/* Relink the tail. */
	list->tail = current->previous;
	free(current);
	(list->length)--;
}

/* This function deletes all the nodes of the given list and the list itself. */
static inline void clear_list_double_linked_list(double_linked_list_t **list) {
	/* Sanity check. */
	if (!list || !(*list))
		return;

	/* Invalid state. */
	assert((((*list)->head) && ((*list)->tail)) || (!((*list)->head) && !((*list)->tail)));

	/* Variables. */
	double_node_t *current, *next;

	/* Special case. */
	if (!((*list)->length)) {
		/* Free the list, and set the pointer. */
		free(*list);
		*list = NULL;
		return;
	}

	/* General case, free all nodes then the list. */
	current = (*list)->head;
	while (current) {
		/* Save the next pointer. */
		next = current->next;
		/* Free the current node. */
		free(current);
		/* Advance by one node. */
		current = next;
	}
	/* Free the list, and set the pointer. */
	free(*list);
	*list = NULL;
}


/* This function deletes all the nodes and data stored within of the given list and the list itself. */
/* If free_function is NULL, will use the stdlib's free(). */
static inline void clear_list_data_double_linked_list(double_linked_list_t **list, void (*free_function)(const void*)) {
	/* Sanity check. */
	if (!list || !(*list))
		return;

	/* Invalid state. */
	assert((((*list)->head) && ((*list)->tail)) || (!((*list)->head) && !((*list)->tail)));

	/* Variables. */
	double_node_t *current, *next;

	/* Special case. */
	if (!((*list)->length)) {
		/* Free the list, and set the pointer. */
		free(*list);
		*list = NULL;
		return;
	}

	/* General case, free all nodes then the list. */
	current = (*list)->head;
	while (current) {
		/* Save the next pointer. */
		next = current->next;
		/* Free the current node's data. */
		if (!free_function)
			free(current->data);
		else
			free_function(current->data);
		/* Free the current node. */
		free(current);
		/* Advance by one node. */
		current = next;
	}
	/* Free the list, and set the pointer. */
	free(*list);
	*list = NULL;
}

/* This function attempts to serialize a doubly-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_double_linked_list(double_linked_list_t *list, void (*array_setting_function)(void*, size_t, void*), void *array) {
	/* Local variables. */
	double_node_t *current;
	size_t i = 0L;

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

	/* Loop and add the elements. */
	for (current = list->head; current; i++, current = current->next)
		array_setting_function(array, i, current->data);

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