add queue/

diff --git a/queue/makefile b/queue/makefile
new file mode 100644 (file)
index 0000000..409a826
--- /dev/null
+++ b/queue/makefile
@@ -0,0 +1,40 @@
+# 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.
+
+# flags de compilação e ligação
+CC       = gcc
+CFLAGS   = -std=c99 -Wall -Wextra -O0 -g -Wno-unused-function -Wno-unused-parameter
+LDFLAGS  = -z noexecstack
+BIN      = testa-fila
+OUT      = saida.txt
+
+# estes alvos não são arquivos
+.PHONY: test clean purge
+
+# compila e liga o projeto
+testa-fila:   testa-fila.o queue.o
+queue.o:      queue.c queue.h
+testa-fila.o: testa-fila.c queue.h
+
+# teste: compara saída gerada com saída esperada
+test: $(BIN)
+       @echo "Gerando saída em $(OUT)"
+       ./$(BIN) > $(OUT)
+       @echo "Comparando saídas esperada e gerada (formato diff)"
+       @if diff testa-fila.txt $(OUT) ; then \
+       echo "CORRETO: saidas identicas" ; \
+       else \
+       echo "ERRADO: saidas diferentes" ; \
+       fi
+
+# limpa arquivos temporários
+clean:
+       -rm -f *.o *~ $(OUT)
+
+# limpa tudo, deixa só o o código-fonte
+purge: clean
+       -rm -f $(BIN)

diff --git a/queue/queue.c b/queue/queue.c
new file mode 100644 (file)
index 0000000..949e461
--- /dev/null
+++ b/queue/queue.c
@@ -0,0 +1,5 @@
+// PingPongOS - PingPong Operating System
+// Prof. Carlos A. Maziero, DINF UFPR
+// Versão 2.0 -- Junho de 2025
+
+// Implementação do TAD fila genérica

diff --git a/queue/queue.h b/queue/queue.h
new file mode 100644 (file)
index 0000000..6cb94b6
--- /dev/null
+++ b/queue/queue.h
@@ -0,0 +1,94 @@
+// 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

diff --git a/queue/testa-fila.c b/queue/testa-fila.c
new file mode 100644 (file)
index 0000000..cde9806
--- /dev/null
+++ b/queue/testa-fila.c
@@ -0,0 +1,230 @@
+// 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);
+}

diff --git a/queue/testa-fila.txt b/queue/testa-fila.txt
new file mode 100644 (file)
index 0000000..013fbd3
--- /dev/null
+++ b/queue/testa-fila.txt
@@ -0,0 +1,88 @@
+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!