X-Git-Url: https://git.wirehaze.ovh/ppos.git/blobdiff_plain/cbd9f5a4f12510a0cb1c36ad38c6c8057853a888..f0f504ecf7d69d520311484390142913b4b8bdf0:/queue/queue.c

diff --git a/queue/queue.c b/queue/queue.c
index 4afa4a5..6a08e90 100644
--- a/queue/queue.c
+++ b/queue/queue.c
@@ -4,18 +4,257 @@
 
 // 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;
-  struct node_t *next;
+  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;
-  struct node_t *tail;
-  struct node_t *iterator;
-  int size;
+  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);
+}
+
+/* -------------------------------------------------------------------------  */