199 lines
6.7 KiB
C
199 lines
6.7 KiB
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 queues. */
|
|
/* Include guards + includes. */
|
|
#ifndef QUEUE_C
|
|
#define QUEUE_C
|
|
#include "queue.h"
|
|
#endif /* QUEUE_C */
|
|
/* Include dependencies from linked list. */
|
|
#ifndef SINGLE_LINKED_LIST_H
|
|
#include "single_linked_list.h"
|
|
#endif
|
|
|
|
/* Function implementations. */
|
|
|
|
/* This function initializes a new empty queue. */
|
|
/* Will return a pointer to the queue on success, otherwise will return NULL. */
|
|
static inline queue_t *initialize_queue() {
|
|
/* Variables. */
|
|
queue_t *result;
|
|
|
|
/* Attempt to allocate. */
|
|
result = (queue_t*) malloc(sizeof(queue_t));
|
|
|
|
/* Check if the allocation failed. */
|
|
if (!result)
|
|
return NULL;
|
|
|
|
/* Allocate the internal list struct. */
|
|
result->list = (linked_list_t*) malloc(sizeof(linked_list_t));
|
|
|
|
/* Check if the allocation failed. */
|
|
if (!(result->list)) {
|
|
free(result);
|
|
return NULL;
|
|
}
|
|
|
|
/* Initialize the internal fields. */
|
|
result->tail = NULL;
|
|
result->list->head = NULL;
|
|
result->list->length = 0;
|
|
|
|
/* Return the result. */
|
|
return result;
|
|
}
|
|
|
|
/* This function enqueues a node. */
|
|
/* This function attempts to enqueue a given node into the given queue. */
|
|
static inline void enqueue(queue_t *queue, node_t *node) {
|
|
/* Input sanity check. */
|
|
assert(queue && (queue->list) && node && (((queue->list->head) && (queue->tail)) || (!(queue->list->head) && !(queue->tail))));
|
|
|
|
/* Delegate. */
|
|
prepend_node_single_linked_list(queue->list, node);
|
|
/* Check if to update the tail. */
|
|
if (!(queue->tail) || queue->list->length == 1)
|
|
queue->tail = node;
|
|
}
|
|
|
|
/* This function allocates and enqueues a node. */
|
|
/* This function attempts to create a node then enqueue it into the given queue, on success will return SUCCESS_CODE_QUEUE_C, otherwise will return FAILURE_CODE_QUEUE_C. */
|
|
static inline int enqueue_data(queue_t *queue, void *data) {
|
|
/* Variables. */
|
|
node_t *node;
|
|
|
|
/* Input sanity check. */
|
|
assert(queue && (queue->list) && (((queue->list->head) && (queue->tail)) || (!(queue->list->head) && !(queue->tail))));
|
|
|
|
/* Attempt to allocate the node. */
|
|
node = (node_t*) malloc(sizeof(node));
|
|
if (!node)
|
|
return FAILURE_CODE_QUEUE_C;
|
|
|
|
/* Add the data to the node. */
|
|
node->data = data;
|
|
|
|
/* Attempt to enqueue the node. */
|
|
enqueue(queue, node);
|
|
return SUCCESS_CODE_QUEUE_C;
|
|
}
|
|
|
|
/* This function dequeues a node. */
|
|
/* This function attempts to dequeue a node from the given queue, on success will return a pointer to the dequeued node - otherwise returns NULL. */
|
|
static inline node_t *dequeue(queue_t *queue) {
|
|
/* Variables. */
|
|
node_t *result, *replacement, *tmp;
|
|
int i;
|
|
|
|
/* Input sanity check. */
|
|
assert(queue && (queue->list) && (((queue->list->head) && (queue->tail)) || (!(queue->list->head) && !(queue->tail))));
|
|
|
|
/* Attempt to dequeue the node. */
|
|
/* Check if the length is zero. */
|
|
if (!(queue->list->length) || !(queue->tail))
|
|
return NULL;
|
|
if (queue->list->length == 1) {
|
|
/* A queue that is of length 1. */
|
|
result = queue->list->head;
|
|
queue->list->head = NULL;
|
|
queue->tail = NULL;
|
|
} else {
|
|
/* This is the general case, move the tail and unlink. */
|
|
/* Set the result to be the tail. */
|
|
result = queue->tail;
|
|
/* Attempt to find the new tail. */
|
|
tmp = queue->list->head;
|
|
while (tmp->next != result)
|
|
tmp = tmp->next;
|
|
/* Unlink and set the new tail. */
|
|
tmp->next = NULL;
|
|
queue->tail = tmp;
|
|
}
|
|
/* Decrease the length. */
|
|
(queue->list->length)--;
|
|
|
|
/* Return the node. */
|
|
return result;
|
|
}
|
|
|
|
/* This function frees all the nodes of the given queue and the queue itself (setting it to NULL). */
|
|
/* Note that it doesn't touch the data stored within the queue's nodes, might exhibit undefined behavior when the internal state of the queue isn't coherent. */
|
|
static inline void clear_queue(queue_t **queue) {
|
|
/* Sanity check. */
|
|
assert(queue && (*queue) && ((*queue)->list));
|
|
|
|
/* Delegate to implementation (linked list). */
|
|
clear_list_single_linked_list(&((*queue)->list));
|
|
|
|
/* Successfully cleared the internal structure, just free the queue struct and set the pointer to NULL. */
|
|
free(*queue);
|
|
*queue = NULL;
|
|
}
|
|
|
|
/* This function frees all the nodes of the given queue and the queue itself (setting it to NULL).*/
|
|
/* Might exhibit undefined behavior on inconsistent internal state of the queue. */
|
|
/* If free_function is NULL, then it the standard library's free() call is used. */
|
|
static inline void clear_queue_data(queue_t **queue, void (*free_func)(const void*)) {
|
|
/* Sanity check. */
|
|
assert(queue && (*queue));
|
|
|
|
/* Delegate to implementation (linked list). */
|
|
clear_list_data_single_linked_list(&((*queue)->list), free_func);
|
|
|
|
/* Successfully cleared the internal structure, just free the queue struct and set the pointer to NULL. */
|
|
free(*queue);
|
|
*queue = NULL;
|
|
}
|
|
|
|
/* This function deletes all the nodes of the given queue, but doesn't touch the queue struct itself or the stored data. */
|
|
static inline void clear_queue_nodes(queue_t *queue) {
|
|
/* Sanity check. */
|
|
assert(queue && (queue->list));
|
|
|
|
/* Check if there is anything to remove. */
|
|
if (!(queue->list->length) || !(queue->list->head))
|
|
return;
|
|
|
|
/* Delegate to implementation in linked list. */
|
|
clear_list_nodes_single_linked_list(queue->list);
|
|
queue->tail = NULL;
|
|
}
|
|
|
|
/* This function deletes all the nodes of the given queue, but doesn't touch the queue struct itself or the stored data. */
|
|
static inline void clear_queue_nodes_data(queue_t *queue, void (*free_function)(const void*)) {
|
|
/* Sanity check. */
|
|
assert(queue && (queue->list));
|
|
|
|
/* Check if there is anything to remove. */
|
|
if (!(queue->list->length) || !(queue->list->head))
|
|
return;
|
|
|
|
/* Delegate to implementation in linked list. */
|
|
clear_list_nodes_data_single_linked_list(queue->list, free_function);
|
|
queue->tail = NULL;
|
|
}
|
|
|
|
/* This function serializes the queue. */
|
|
/* Note that it'll return NULL on allocation failure or invalid input. */
|
|
/* 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. */
|
|
void *serialize_queue(queue_t *queue, void (*array_setting_function)(void*, size_t, void*), void *array) {
|
|
/* Delegate. */
|
|
return (!queue) ? NULL : serialize_linked_list(queue->list, array_setting_function, array);
|
|
}
|