queue/queue.c

   1 // PingPongOS - PingPong Operating System
   2 // Prof. Carlos A. Maziero, DINF UFPR
   3 // Versão 2.0 -- Junho de 2025
   4
   5 // Implementação do TAD fila genérica
   6
   7 /* PEDRO HENRIQUE FRIEDRICH RAMOS : GRR20243133  */
   8
   9 #include "queue.h"
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12
  13 /* -------------------------------------------------------------------------  */
  14 /* Data types  -------------------------------------------------------------  */
  15
  16 /* Queue element.  */
  17 struct node_t
  18 {
  19   void *item; /* User provided opaque pointer.  */
  20   struct node_t *next; /* Pointer to the next node in the queue.  */
  21 };
  22
  23 /* -------------------------------------------------------------------------  */
  24
  25 /* Queue.  */
  26 struct queue_t
  27 {
  28   struct node_t *head; /* Pointer to the first node in the queue.  */
  29   struct node_t *tail; /* Pointer to the last node in the queue.  */
  30   struct node_t *iterator; /* Pointer to the current node.  */
  31   int size; /* Number of nodes in the queue.  */
  32 };
  33
  34 /* -------------------------------------------------------------------------  */
  35 /* Internal functions  -----------------------------------------------------  */
  36
  37 static inline struct node_t *
  38 node_create (void)
  39 {
  40   return calloc (1, sizeof (struct node_t));
  41 }
  42
  43 /* -------------------------------------------------------------------------  */
  44
  45 static inline void
  46 node_destroy (struct node_t *node)
  47 {
  48   free (node);
  49 }
  50
  51 /* -------------------------------------------------------------------------  */
  52 /* Exported functions  -----------------------------------------------------  */
  53
  54 struct queue_t *
  55 queue_create (void)
  56 {
  57   return calloc (1, sizeof (struct queue_t));
  58 }
  59
  60 /* -------------------------------------------------------------------------  */
  61
  62 int
  63 queue_destroy (struct queue_t *queue)
  64 {
  65   struct node_t *n, *next;
  66
  67   if (!queue)
  68     return ERROR;
  69
  70   n = queue->head;
  71
  72   while (n)
  73     {
  74       /* Save the next node pointer before destroying the current node.  */
  75       next = n->next;
  76       node_destroy (n);
  77       n = next;
  78     }
  79
  80   free (queue);
  81   return NOERROR;
  82 }
  83
  84 /* -------------------------------------------------------------------------  */
  85
  86 int
  87 queue_add (struct queue_t *queue, void *item)
  88 {
  89   struct node_t *n;
  90
  91   if (!queue || !item)
  92     return ERROR;
  93
  94   if (!(n = node_create ()))
  95     return ERROR;
  96
  97   n->item = item;
  98   ++queue->size;
  99
 100   /* Empty queue, this is the first element.  */
 101   if (!queue->head)
 102     {
 103       queue->head = queue->tail = queue->iterator = n;
 104       return NOERROR;
 105     }
 106
 107   /* Append to queue.  */
 108   queue->tail = queue->tail->next = n;
 109   return NOERROR;
 110 }
 111
 112 /* -------------------------------------------------------------------------  */
 113
 114 int
 115 queue_del (struct queue_t *queue, void *item)
 116 {
 117   struct node_t *n, *prev;
 118
 119   if (!queue || !item)
 120     return ERROR;
 121
 122   if (!(n = queue->head)) /* Queue is empty.  */
 123     return ERROR;
 124
 125   prev = NULL;
 126
 127   while (n && n->item != item)
 128     {
 129       prev = n;
 130       n = n->next;
 131     }
 132
 133   if (!n) /* Not found.  */
 134     return ERROR;
 135
 136   if (prev)
 137     prev->next = n->next;
 138
 139   /* Update boundaries accordingly.  */
 140   if (queue->head == n)
 141     queue->head = n->next;
 142
 143   if (queue->tail == n)
 144     queue->tail = prev;
 145
 146   /* Advance the iterator if it points to the removed node.  */
 147   if (queue->iterator == n)
 148     queue->iterator = n->next;
 149
 150   --queue->size;
 151   node_destroy (n);
 152   return NOERROR;
 153 }
 154
 155 /* -------------------------------------------------------------------------  */
 156
 157 bool
 158 queue_has (struct queue_t *queue, void *item)
 159 {
 160   struct node_t *n;
 161
 162   if (!queue || !item)
 163     return false;
 164
 165   if (!(n = queue->head))
 166     return false;
 167
 168   /* Traverse until the item is found or the end is reached.  */
 169   while (n->item != item && (n = n->next))
 170     ;
 171
 172   return n != NULL;
 173 }
 174
 175 /* -------------------------------------------------------------------------  */
 176
 177 int
 178 queue_size (struct queue_t *queue)
 179 {
 180   if (!queue)
 181     return ERROR;
 182
 183   return queue->size;
 184 }
 185
 186 /* -------------------------------------------------------------------------  */
 187
 188 void *
 189 queue_head (struct queue_t *queue)
 190 {
 191   if (!queue || !queue->head)
 192     return NULL;
 193
 194   queue->iterator = queue->head;
 195
 196   return queue->head->item;
 197 }
 198
 199 /* -------------------------------------------------------------------------  */
 200
 201 void *
 202 queue_next (struct queue_t *queue)
 203 {
 204   if (!queue || !queue->iterator)
 205     return NULL;
 206
 207   queue->iterator = queue->iterator->next;
 208
 209   if (!queue->iterator)
 210     return NULL;
 211
 212   return queue->iterator->item;
 213 }
 214
 215 /* -------------------------------------------------------------------------  */
 216
 217 void *
 218 queue_item (struct queue_t *queue)
 219 {
 220   if (!queue || !queue->iterator)
 221     return NULL;
 222
 223   return queue->iterator->item;
 224 }
 225
 226 /* -------------------------------------------------------------------------  */
 227
 228 void
 229 queue_print (char *name, struct queue_t *queue, void (func) (void *))
 230 {
 231   struct node_t *n;
 232
 233   if (!name)
 234     return;
 235
 236   printf ("%s: ", name);
 237
 238   if (!queue)
 239     {
 240       puts ("undef");
 241       return;
 242     }
 243
 244   fputs ("[ ", stdout);
 245
 246   for (n = queue->head; n; n = n->next)
 247     {
 248       if (func)
 249         func (n->item);
 250
 251       else
 252         fputs ("undef", stdout);
 253
 254       putchar (' ');
 255     }
 256
 257   printf ("] (%d items)\n", queue->size);
 258 }
 259
 260 /* -------------------------------------------------------------------------  */