// Versão 2.0 -- Junho de 2025
// Implementação do TAD fila genérica
+
+/* PEDRO HENRIQUE FRIEDRICH RAMOS : GRR20243133 */
+
+#include "queue.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+/* ------------------------------------------------------------------------- */
+/* Data types ------------------------------------------------------------- */
+
+/* Queue element. */
+struct node_t
+{
+ void *item; /* User provided opaque pointer. */
+ struct node_t *next; /* Pointer to the next node in the queue. */
+};
+
+/* ------------------------------------------------------------------------- */
+
+/* Queue. */
+struct queue_t
+{
+ struct node_t *head; /* Pointer to the first node in the queue. */
+ struct node_t *tail; /* Pointer to the last node in the queue. */
+ struct node_t *iterator; /* Pointer to the current node. */
+ int size; /* Number of nodes in the queue. */
+};
+
+/* ------------------------------------------------------------------------- */
+/* Internal functions ----------------------------------------------------- */
+
+static inline struct node_t *
+node_create (void)
+{
+ return calloc (1, sizeof (struct node_t));
+}
+
+/* ------------------------------------------------------------------------- */
+
+static inline void
+node_destroy (struct node_t *node)
+{
+ free (node);
+}
+
+/* ------------------------------------------------------------------------- */
+/* Exported functions ----------------------------------------------------- */
+
+struct queue_t *
+queue_create (void)
+{
+ return calloc (1, sizeof (struct queue_t));
+}
+
+/* ------------------------------------------------------------------------- */
+
+int
+queue_destroy (struct queue_t *queue)
+{
+ struct node_t *n, *next;
+
+ if (!queue)
+ return ERROR;
+
+ n = queue->head;
+
+ while (n)
+ {
+ /* Save the next node pointer before destroying the current node. */
+ next = n->next;
+ node_destroy (n);
+ n = next;
+ }
+
+ free (queue);
+ return NOERROR;
+}
+
+/* ------------------------------------------------------------------------- */
+
+int
+queue_add (struct queue_t *queue, void *item)
+{
+ struct node_t *n;
+
+ if (!queue || !item)
+ return ERROR;
+
+ if (!(n = node_create ()))
+ return ERROR;
+
+ n->item = item;
+ ++queue->size;
+
+ /* Empty queue, this is the first element. */
+ if (!queue->head)
+ {
+ queue->head = queue->tail = queue->iterator = n;
+ return NOERROR;
+ }
+
+ /* Append to queue. */
+ queue->tail = queue->tail->next = n;
+ return NOERROR;
+}
+
+/* ------------------------------------------------------------------------- */
+
+int
+queue_del (struct queue_t *queue, void *item)
+{
+ struct node_t *n, *prev;
+
+ if (!queue || !item)
+ return ERROR;
+
+ if (!(n = queue->head)) /* Queue is empty. */
+ return ERROR;
+
+ prev = NULL;
+
+ while (n && n->item != item)
+ {
+ prev = n;
+ n = n->next;
+ }
+
+ if (!n) /* Not found. */
+ return ERROR;
+
+ if (prev)
+ prev->next = n->next;
+
+ /* Update boundaries accordingly. */
+ if (queue->head == n)
+ queue->head = n->next;
+
+ if (queue->tail == n)
+ queue->tail = prev;
+
+ /* Advance the iterator if it points to the removed node. */
+ if (queue->iterator == n)
+ queue->iterator = n->next;
+
+ --queue->size;
+ node_destroy (n);
+ return NOERROR;
+}
+
+/* ------------------------------------------------------------------------- */
+
+bool
+queue_has (struct queue_t *queue, void *item)
+{
+ struct node_t *n;
+
+ if (!queue || !item)
+ return false;
+
+ if (!(n = queue->head))
+ return false;
+
+ /* Traverse until the item is found or the end is reached. */
+ while (n->item != item && (n = n->next))
+ ;
+
+ return n != NULL;
+}
+
+/* ------------------------------------------------------------------------- */
+
+int
+queue_size (struct queue_t *queue)
+{
+ if (!queue)
+ return ERROR;
+
+ return queue->size;
+}
+
+/* ------------------------------------------------------------------------- */
+
+void *
+queue_head (struct queue_t *queue)
+{
+ if (!queue || !queue->head)
+ return NULL;
+
+ queue->iterator = queue->head;
+
+ return queue->head->item;
+}
+
+/* ------------------------------------------------------------------------- */
+
+void *
+queue_next (struct queue_t *queue)
+{
+ if (!queue || !queue->iterator)
+ return NULL;
+
+ queue->iterator = queue->iterator->next;
+
+ if (!queue->iterator)
+ return NULL;
+
+ return queue->iterator->item;
+}
+
+/* ------------------------------------------------------------------------- */
+
+void *
+queue_item (struct queue_t *queue)
+{
+ if (!queue || !queue->iterator)
+ return NULL;
+
+ return queue->iterator->item;
+}
+
+/* ------------------------------------------------------------------------- */
+
+void
+queue_print (char *name, struct queue_t *queue, void (func) (void *))
+{
+ struct node_t *n;
+
+ if (!name)
+ return;
+
+ printf ("%s: ", name);
+
+ if (!queue)
+ {
+ puts ("undef");
+ return;
+ }
+
+ fputs ("[ ", stdout);
+
+ for (n = queue->head; n; n = n->next)
+ {
+ if (func)
+ func (n->item);
+
+ else
+ fputs ("undef", stdout);
+
+ putchar (' ');
+ }
+
+ printf ("] (%d items)\n", queue->size);
+}
+
+/* ------------------------------------------------------------------------- */
projects / ppos.git / blobdiff