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