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 struct node_t
  14 {
  15   void *item;
  16   struct node_t *next;
  17 };
  18
  19 struct queue_t
  20 {
  21   struct node_t *head;
  22   struct node_t *tail;
  23   struct node_t *iterator;
  24   int size;
  25 };
  26
  27 static inline struct node_t *
  28 node_create (void)
  29 {
  30   return calloc (1, sizeof (struct node_t));
  31 }
  32
  33 static inline void
  34 node_destroy (struct node_t *node)
  35 {
  36   free (node);
  37 }
  38
  39 struct queue_t *
  40 queue_create (void)
  41 {
  42   return calloc (1, sizeof (struct queue_t));
  43 }
  44
  45 int
  46 queue_destroy (struct queue_t *queue)
  47 {
  48   struct node_t *n, *next;
  49
  50   if (!queue)
  51     {
  52       return ERROR;
  53     }
  54
  55   n = queue->head;
  56
  57   while (n)
  58     {
  59       next = n->next;
  60       node_destroy (n);
  61       n = next;
  62     }
  63
  64   free (queue);
  65   return NOERROR;
  66 }
  67
  68 int
  69 queue_add (struct queue_t *queue, void *item)
  70 {
  71   struct node_t *n;
  72
  73   if (!queue || !item)
  74     {
  75       return ERROR;
  76     }
  77
  78   if (!(n = node_create ()))
  79     {
  80       return ERROR;
  81     }
  82
  83   n->item = item;
  84   ++queue->size;
  85
  86   if (!queue->head)
  87     {
  88       queue->head = queue->tail = queue->iterator = n;
  89       return NOERROR;
  90     }
  91
  92   queue->tail = queue->tail->next = n;
  93   return NOERROR;
  94 }
  95
  96 int
  97 queue_del (struct queue_t *queue, void *item)
  98 {
  99   struct node_t *n, *prev;
 100
 101   if (!queue || !item)
 102     {
 103       return ERROR;
 104     }
 105
 106   if (!(n = queue->head))
 107     {
 108       return ERROR;
 109     }
 110
 111   prev = NULL;
 112
 113   while (n && n->item != item)
 114     {
 115       prev = n;
 116       n = n->next;
 117     }
 118
 119   if (!n) /* not found */
 120     {
 121       return ERROR;
 122     }
 123
 124   if (prev)
 125     {
 126       prev->next = n->next;
 127     }
 128
 129   if (queue->head == n)
 130     {
 131       queue->head = n->next;
 132     }
 133
 134   if (queue->tail == n)
 135     {
 136       queue->tail = prev;
 137     }
 138
 139   if (queue->iterator == n)
 140     {
 141       queue->iterator = n->next;
 142     }
 143
 144   --queue->size;
 145   node_destroy (n);
 146   return NOERROR;
 147 }
 148
 149 bool
 150 queue_has (struct queue_t *queue, void *item)
 151 {
 152   struct node_t *n;
 153
 154   if (!queue || !item)
 155     {
 156       return false;
 157     }
 158
 159   if (!(n = queue->head))
 160     {
 161       return false;
 162     }
 163
 164   while (n->item != item && (n = n->next))
 165     ;
 166
 167   if (!n)
 168     {
 169       return false;
 170     }
 171
 172   return true;
 173 }
 174
 175 int
 176 queue_size (struct queue_t *queue)
 177 {
 178   if (!queue)
 179     {
 180       return ERROR;
 181     }
 182
 183   return queue->size;
 184 }
 185
 186 void *
 187 queue_head (struct queue_t *queue)
 188 {
 189   if (!queue || !queue->head)
 190     {
 191       return NULL;
 192     }
 193
 194   queue->iterator = queue->head;
 195
 196   return queue->head->item;
 197 }
 198
 199 void *
 200 queue_next (struct queue_t *queue)
 201 {
 202   if (!queue || !queue->iterator)
 203     {
 204       return NULL;
 205     }
 206
 207   queue->iterator = queue->iterator->next;
 208
 209   if (!queue->iterator)
 210     {
 211       return NULL;
 212     }
 213
 214   return queue->iterator->item;
 215 }
 216
 217 void *
 218 queue_item (struct queue_t *queue)
 219 {
 220   if (!queue || !queue->iterator)
 221     {
 222       return NULL;
 223     }
 224
 225   return queue->iterator->item;
 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     {
 235       return;
 236     }
 237
 238   printf ("%s: ", name);
 239
 240   if (!queue)
 241     {
 242       puts ("undef");
 243       return;
 244     }
 245
 246   fputs ("[ ", stdout);
 247
 248   for (n = queue->head; n; n = n->next)
 249     {
 250       if (func)
 251         {
 252           func (n->item);
 253         }
 254
 255       else
 256         {
 257           fputs ("undef", stdout);
 258         }
 259
 260       putchar (' ');
 261     }
 262
 263   printf ("] (%d items)\n", queue->size);
 264 }