--- /dev/null
+// PingPongOS - PingPong Operating System
+// Prof. Carlos A. Maziero, DINF UFPR
+// Versão 2.0 -- Junho de 2025
+
+// ATENÇÃO: ESTE ARQUIVO NÃO DEVE SER ALTERADO;
+// ALTERAÇÕES SERÃO DESCARTADAS NA CORREÇÃO.
+
+/*
+TAD fila genérica de ponteiros, que armazena itens de tipo "void *".
+A fila mantém um iterador que aponta para um item da fila (ou para NULL).
+O iterador pode ser ajustado usando as funções queue_head() e queue_next()
+e ter seu item consultado com a função queue_item(). Inicialmente o iterador
+aponta para o começo da fila.
+*/
+
+#ifndef __QUEUE__
+#define __QUEUE__
+
+#include <stdbool.h>
+
+// códigos de retorno das funções
+#ifndef ERROR
+#define ERROR -1
+#define NOERROR 0
+#endif
+
+// ponteiro nulo
+#ifndef NULL
+#define NULL ((void *)0)
+#endif
+
+// struct que representa uma fila; este é um struct "opaco",
+// que deve ser redefinido completamente em queue.c
+struct queue_t;
+
+// Cria uma fila inicialmente vazia.
+// Retorno: ponteiro p/ a nova fila
+// NULL se houver erro
+struct queue_t *queue_create();
+
+// Destroi uma fila, liberando a memória alocada por ela.
+// IMPORTANTE: os itens apontados pela fila NÃO devem ser liberados,
+// pois a aplicação que os criou e pôs na fila é responsável por eles.
+// Retorno: NOERROR ou ERROR (se a fila não existir)
+int queue_destroy(struct queue_t *queue);
+
+// Adiciona um item no fim da fila; ajusta o iterador para ele
+// se for o primeiro item (ou seja, se a fila estiver vazia).
+// Retorno: NOERROR ou ERROR (se fila ou item não existir)
+int queue_add(struct queue_t *queue, void *item);
+
+// Retira da fila o item com o valor indicado; se o item estiver
+// em mais de uma posição da fila, retira apenas da primeira posição
+// encontrada; se o item estiver apontado pelo iterador, este avança
+// para o próximo item da fila (ou para NULL, se for o último).
+// Retorno: NOERROR ou ERROR (não encontrou ou outro erro).
+int queue_del(struct queue_t *queue, void *item);
+
+// Informa se o item indicado está na fila.
+// Retorno: true/false (error: false).
+bool queue_has(struct queue_t *queue, void *item);
+
+// Informa o número de itens na fila.
+// Retorno: número de itens na fila (>= 0)
+// ERROR se a fila não existir
+int queue_size(struct queue_t *queue);
+
+// Põe o iterador no início da fila.
+// Retorno: ptr para o item apontado pelo iterador
+// NULL se a fila estiver vazia ou não existir
+void *queue_head(struct queue_t *queue);
+
+// Avança o iterador ao próximo item na fila.
+// Retorno: ptr para o item apontado pelo iterador após avançar
+// NULL se o iterador passou do último item da fila
+// NULL se a fila estiver vazia ou não existir
+void *queue_next(struct queue_t *queue);
+
+// Informa o item atualmente sob o iterador na fila.
+// Retorno: ptr para o item apontado pelo iterador
+// NULL se a fila estiver vazia ou não existir
+// NULL se o iterador passou do fim da fila
+void *queue_item(struct queue_t *queue);
+
+// Imprime os elementos de uma fila; a função externa "func"
+// deve ser chamada para imprimir cada item.
+// Exemplos de saída, com name == "Frutas":
+// Frutas: [ banana pera ameixa uva ] (4 itens)
+// Frutas: [ ] (0 itens)
+// Frutas: undef se queue == NULL
+// Frutas: [ undef undef undef ] (3 itens) se func == NULL
+void queue_print(char *name, struct queue_t *queue, void(func)(void *));
+
+#endif
--- /dev/null
+// TAD filas genéricas
+// Prof. Carlos A. Maziero, DINF UFPR
+// Versão 1.0 - 09/2025
+
+// ATENÇÃO: ESTE ARQUIVO NÃO DEVE SER ALTERADO;
+// ALTERAÇÕES SERÃO DESCARTADAS NA CORREÇÃO.
+
+// Teste do TAD fila genérica (fila de itens void *)
+// usando uma fila de strings com nomes de frutas.
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include "queue.h"
+
+// verifica o sistema operacional
+#ifndef __linux__
+#error "Este código foi planejado para ambientes Linux."
+#endif
+
+// imprime na tela um elemento da fila (chamada pela função queue_print)
+void print_item(void *ptr)
+{
+ printf("%s", (char *)ptr);
+}
+
+int main()
+{
+ char *fruta[] = {"ameixa", "banana", "goiaba",
+ "laranja", "morango", "uva"};
+ int num_frutas = 6;
+ struct queue_t *q;
+ char *item;
+ int pos, status;
+
+ // Testes com fila inexistente
+ printf("1 Testes com uma fila inexistente\n");
+ q = NULL;
+
+ // tamanho deve ser ERROR
+ printf(" teste queue_size\n");
+ assert(queue_size(q) == ERROR);
+
+ // destruir deve retornar ERROR
+ printf(" teste queue_destroy\n");
+ status = queue_destroy(q);
+ assert(status == ERROR);
+
+ // operações com iterador devem retornar NULL
+ printf(" teste queue_head\n");
+ assert(queue_head(q) == NULL);
+ printf(" teste queue_next\n");
+ assert(queue_next(q) == NULL);
+ printf(" teste queue_item\n");
+ assert(queue_item(q) == NULL);
+
+ // inserção e remoção devem deve retornar ERROR
+ printf(" teste queue_add\n");
+ assert(queue_add(q, "teste") == ERROR);
+ printf(" teste queue_del\n");
+ assert(queue_del(q, "teste") == ERROR);
+
+ queue_print(" fila", q, print_item);
+
+ // Testes com fila existente, mas vazia
+ printf("2 Testes com uma fila existente mas vazia\n");
+
+ // cria a fila
+ printf(" teste queue_create\n");
+ q = queue_create();
+ assert(q);
+
+ // tamanho deve ser 0
+ printf(" teste queue_size\n");
+ assert(queue_size(q) == 0);
+
+ // operações com iterador devem retornar NULL
+ printf(" teste queue_head\n");
+ assert(queue_head(q) == NULL);
+ printf(" teste queue_next\n");
+ assert(queue_next(q) == NULL);
+ printf(" teste queue_item\n");
+ assert(queue_item(q) == NULL);
+
+ // remoção deve deve retornar NULL
+ printf(" teste queue_del\n");
+ assert(queue_del(q, "teste") == ERROR);
+
+ queue_print(" fila", q, print_item);
+
+ // Testes de inserção
+ printf("3 Testes de inserção\n");
+
+ for (int i = 0; i < num_frutas; i++)
+ {
+ item = fruta[i];
+ printf(" colocando %s\n", item);
+ assert(queue_add(q, item) == NOERROR);
+ assert(queue_size(q) == (i + 1));
+ queue_print(" fila", q, print_item);
+ }
+
+ printf("4 Testes do queue_print:\n");
+
+ queue_print(" fila", NULL, print_item);
+ queue_print(" fila", q, NULL);
+
+ printf("5 Testes do iterador:\n");
+
+ // iterador deve apontar para a primeira posição
+ item = queue_item(q);
+ pos = 0;
+
+ // testa se iterador aponta e se desloca corretamente
+ while (item)
+ {
+ printf(" iterador em %s (posição %d)\n", item, pos);
+ assert(item == fruta[pos]);
+ item = queue_next(q);
+ pos++;
+ }
+ printf(" iterador em %s\n", (char *)queue_item(q));
+
+ // testando queue_head
+ assert(queue_head(q) == fruta[0]);
+ assert(queue_item(q) == fruta[0]);
+
+ printf("6 Testes de remoção\n");
+
+ // testando queue_del com fila NULL
+ printf(" retirando de fila NULL\n");
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_del(NULL, fruta[0]) == ERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[0]);
+
+ // testando queue_del com item NULL
+ printf(" retirando item NULL\n");
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_del(q, NULL) == ERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[0]);
+
+ // testando queue_del com item que não está na fila
+ printf(" retirando acerola (que não está na fila)\n");
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_del(q, "acerola") == ERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[0]);
+
+ // testando queue_del com item no meio da fila
+ pos = num_frutas / 2;
+ printf(" retirando %s (no meio da fila)\n", fruta[pos]);
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_del(q, fruta[pos]) == NOERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[0]);
+
+ // testando queue_del com item no inicio da fila
+ pos = 0;
+ printf(" retirando %s (no início da fila)\n", fruta[pos]);
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_del(q, fruta[pos]) == NOERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[1]);
+
+ // testando queue_del com item no fim da fila
+ pos = num_frutas - 1;
+ printf(" retirando %s (no fim da fila)\n", fruta[pos]);
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_del(q, fruta[pos]) == NOERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[1]);
+
+ // testando queue_del com item apontado pelo iterador, no meio
+ queue_next(q);
+ pos = 2;
+ printf(" retirando sob o iterador\n");
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[pos]);
+ assert(queue_del(q, fruta[pos]) == NOERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[4]);
+
+ // testando queue_del com item apontado pelo iterador, no fim
+ pos = 4;
+ printf(" retirando sob o iterador\n");
+ queue_print(" fila antes ", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == fruta[pos]);
+ assert(queue_del(q, fruta[pos]) == NOERROR);
+ queue_print(" fila depois", q, print_item);
+ printf(" iterador em %s\n", (char *)queue_item(q));
+ assert(queue_item(q) == NULL);
+
+ // esvaziando a fila
+ printf("7 Esvaziando a fila\n");
+ queue_print(" fila", q, print_item);
+ item = queue_head(q);
+ while (item)
+ {
+ assert(queue_del(q, item) == NOERROR);
+ printf(" retirei %s\n", item);
+ queue_print(" fila", q, print_item);
+ item = queue_item(q);
+ }
+ assert(queue_size(q) == 0);
+
+ // testando queue_destroy
+ printf("8 Teste queue_destroy\n");
+ status = queue_destroy(q);
+ assert(status == NOERROR);
+
+ printf("Testes concluídos com sucesso!\n");
+ exit(0);
+}
--- /dev/null
+1 Testes com uma fila inexistente
+ teste queue_size
+ teste queue_destroy
+ teste queue_head
+ teste queue_next
+ teste queue_item
+ teste queue_add
+ teste queue_del
+ fila: undef
+2 Testes com uma fila existente mas vazia
+ teste queue_create
+ teste queue_size
+ teste queue_head
+ teste queue_next
+ teste queue_item
+ teste queue_del
+ fila: [ ] (0 items)
+3 Testes de inserção
+ colocando ameixa
+ fila: [ ameixa ] (1 items)
+ colocando banana
+ fila: [ ameixa banana ] (2 items)
+ colocando goiaba
+ fila: [ ameixa banana goiaba ] (3 items)
+ colocando laranja
+ fila: [ ameixa banana goiaba laranja ] (4 items)
+ colocando morango
+ fila: [ ameixa banana goiaba laranja morango ] (5 items)
+ colocando uva
+ fila: [ ameixa banana goiaba laranja morango uva ] (6 items)
+4 Testes do queue_print:
+ fila: undef
+ fila: [ undef undef undef undef undef undef ] (6 items)
+5 Testes do iterador:
+ iterador em ameixa (posição 0)
+ iterador em banana (posição 1)
+ iterador em goiaba (posição 2)
+ iterador em laranja (posição 3)
+ iterador em morango (posição 4)
+ iterador em uva (posição 5)
+ iterador em (null)
+6 Testes de remoção
+ retirando de fila NULL
+ fila antes : [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ fila depois: [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ retirando item NULL
+ fila antes : [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ fila depois: [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ retirando acerola (que não está na fila)
+ fila antes : [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ fila depois: [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ retirando laranja (no meio da fila)
+ fila antes : [ ameixa banana goiaba laranja morango uva ] (6 items)
+ iterador em ameixa
+ fila depois: [ ameixa banana goiaba morango uva ] (5 items)
+ iterador em ameixa
+ retirando ameixa (no início da fila)
+ fila antes : [ ameixa banana goiaba morango uva ] (5 items)
+ iterador em ameixa
+ fila depois: [ banana goiaba morango uva ] (4 items)
+ iterador em banana
+ retirando uva (no fim da fila)
+ fila antes : [ banana goiaba morango uva ] (4 items)
+ iterador em banana
+ fila depois: [ banana goiaba morango ] (3 items)
+ iterador em banana
+ retirando sob o iterador
+ fila antes : [ banana goiaba morango ] (3 items)
+ iterador em goiaba
+ fila depois: [ banana morango ] (2 items)
+ iterador em morango
+ retirando sob o iterador
+ fila antes : [ banana morango ] (2 items)
+ iterador em morango
+ fila depois: [ banana ] (1 items)
+ iterador em (null)
+7 Esvaziando a fila
+ fila: [ banana ] (1 items)
+ retirei banana
+ fila: [ ] (0 items)
+8 Teste queue_destroy
+Testes concluídos com sucesso!
projects / ppos.git / commitdiff