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