From: phfr24 Date: Sat, 28 Feb 2026 18:49:51 +0000 (-0300) Subject: add queue/ X-Git-Tag: queue~8 X-Git-Url: https://git.wirehaze.ovh/ppos.git/commitdiff_plain/4d086dac0486989c861ae172d0fc28c4d6bb3d9c?ds=sidebyside add queue/ --- 4d086dac0486989c861ae172d0fc28c4d6bb3d9c diff --git a/queue/makefile b/queue/makefile new file mode 100644 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 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 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 + +// 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 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 +#include +#include +#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 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!