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   return n != NULL;
 168 }
 169
 170 int
 171 queue_size (struct queue_t *queue)
 172 {
 173   if (!queue)
 174     {
 175       return ERROR;
 176     }
 177
 178   return queue->size;
 179 }
 180
 181 void *
 182 queue_head (struct queue_t *queue)
 183 {
 184   if (!queue || !queue->head)
 185     {
 186       return NULL;
 187     }
 188
 189   queue->iterator = queue->head;
 190
 191   return queue->head->item;
 192 }
 193
 194 void *
 195 queue_next (struct queue_t *queue)
 196 {
 197   if (!queue || !queue->iterator)
 198     {
 199       return NULL;
 200     }
 201
 202   queue->iterator = queue->iterator->next;
 203
 204   if (!queue->iterator)
 205     {
 206       return NULL;
 207     }
 208
 209   return queue->iterator->item;
 210 }
 211
 212 void *
 213 queue_item (struct queue_t *queue)
 214 {
 215   if (!queue || !queue->iterator)
 216     {
 217       return NULL;
 218     }
 219
 220   return queue->iterator->item;
 221 }
 222
 223 void
 224 queue_print (char *name, struct queue_t *queue, void (func) (void *))
 225 {
 226   struct node_t *n;
 227
 228   if (!name)
 229     {
 230       return;
 231     }
 232
 233   printf ("%s: ", name);
 234
 235   if (!queue)
 236     {
 237       puts ("undef");
 238       return;
 239     }
 240
 241   fputs ("[ ", stdout);
 242
 243   for (n = queue->head; n; n = n->next)
 244     {
 245       if (func)
 246         {
 247           func (n->item);
 248         }
 249
 250       else
 251         {
 252           fputs ("undef", stdout);
 253         }
 254
 255       putchar (' ');
 256     }
 257
 258   printf ("] (%d items)\n", queue->size);
 259 }