// PingPongOS - PingPong Operating System // Prof. Carlos A. Maziero, DINF UFPR // Versão 1.4 -- Janeiro de 2022 // Teste da implementação de fila genérica queue.c/queue.h. // ESTE ARQUIVO NÃO DEVE SER MODIFICADO - ELE SERÁ SOBRESCRITO NOS TESTES // operating system check #if defined(_WIN32) || (!defined(__unix__) && !defined(__unix) && (!defined(__APPLE__) || !defined(__MACH__))) #warning Este código foi planejado para ambientes UNIX (LInux, *BSD, MacOS). A compilação e execução em outros ambientes é responsabilidade do usuário. #endif #include #include #include #include "queue.h" #define N 100 // A estrutura "filaint_t" será usada com as funções de queue.c usando um // casting para o tipo "queue_t". Isso funciona bem, se os campos iniciais // de ambas as estruturas forem os mesmos. De acordo com a seção 6.7.2.1 do // padrão C99: "Within a structure object, the non-bit-field members and the // units in which bit-fields reside have addresses that increase in the order // in which they are declared.". typedef struct filaint_t { struct filaint_t *prev ; // ptr para usar cast com queue_t struct filaint_t *next ; // ptr para usar cast com queue_t int id ; // outros campos podem ser acrescidos aqui } filaint_t ; filaint_t item[N]; filaint_t *fila0, *fila1, *aux, *final ; int ret ; //------------------------------------------------------------------------------ // imprime na tela um elemento da fila (chamada pela função queue_print) void print_elem (void *ptr) { filaint_t *elem = ptr ; if (!elem) return ; elem->prev ? printf ("%d", elem->prev->id) : printf ("*") ; printf ("<%d>", elem->id) ; elem->next ? printf ("%d", elem->next->id) : printf ("*") ; } //------------------------------------------------------------------------------ // retorna 1 se a estrutura da fila está correta, 0 senão int fila_correta (filaint_t *fila) { filaint_t *aux ; // uma fila vazia sempre está correta if (!fila) return 1 ; // fila com um só elemento e correta if ((fila->next == fila) && (fila->prev == fila)) return 1 ; // fila com um só elemento, mas incorreta if ((fila->next == fila) || (fila->prev == fila)) { printf ("ERRO: ponteiros errados na fila com um elemento\n") ; return 0 ; } // fila com mais elementos, percorrer e testar todos os ponteiros aux = fila ; do { // testa ponteiro next (avaliação em curto-circuito) if (aux->next && (aux->next->prev == aux)) ; // ponteiro ok else { printf ("ERRO: ponteiros errados ->next ou ->next->prev\n") ; return 0 ; } // testa ponteiro prev (avaliação em curto-circuito) if (aux->prev && (aux->prev->next == aux)) ; // ponteiro ok else { printf ("ERRO: ponteiros errados ->prev ou ->prev->next\n") ; return 0 ; } aux = aux->next ; } while (aux != fila) ; // passou por tudo, estrutura da fila parece estar ok return 1 ; } //------------------------------------------------------------------------------ int main (int argc, char **argv, char **envp) { int i ; // inicializa os N elementos for (i=0; iid) ; // testa posição do elemento i i++ ; aux = aux->next ; } while (aux != fila0) ; assert (i == N) ; assert (queue_size ((queue_t*) fila0) == N) ; printf ("Testes de insercao funcionaram!\n") ; // PARTE 2: queue_remove ==================================================== // esvazia fila0, retirando sempre o primeiro elemento printf ("Remocao %d vezes o primeiro elemento...\n", N) ; i=0 ; while (iid == i) ; // testa ordem do elemento removido assert (aux->prev == NULL) ; // testa elemento removido assert (aux->next == NULL) ; // testa elemento removido i++ ; } assert (fila0 == NULL) ; // fila deve estar vazia printf ("Ok, apos %d remocoes a fila ficou vazia\n", N) ; // reconstroi fila de teste fila0 = NULL ; for (i=0; inext ; queue_remove ((queue_t**) &fila0, (queue_t*) aux) ; assert (fila_correta (fila0)) ; // estrutura continua correta assert (aux->id == ((i+1)%N)) ; // testa ordem do elemento removido assert (aux->prev == NULL) ; // testa elemento removido assert (aux->next == NULL) ; // testa elemento removido i++ ; } assert (fila0 == NULL) ; // fila deve estar vazia printf ("Ok, apos %d remocoes a fila ficou vazia\n", N) ; // reconstroi fila de teste fila0 = NULL ; for (i=0; iprev ; queue_remove ((queue_t**) &fila0, (queue_t*) aux) ; assert (fila_correta (fila0)) ; // estrutura continua correta assert (aux->id+i == N-1) ; // testa ordem do elemento removido assert (aux->prev == NULL) ; // testa elemento removido assert (aux->next == NULL) ; // testa elemento removido i++ ; } assert (fila0 == NULL) ; // fila deve estar vazia printf ("Ok, apos %d remocoes a fila ficou vazia\n", N) ; // reconstroi fila de teste fila0 = NULL ; for (i=0; inext ; } queue_remove ((queue_t**) &fila0, (queue_t*) aux) ; } assert (fila0 == NULL) ; // fila deve estar vazia printf ("Ok, apos %d remocoes aleatorias a fila ficou vazia\n", N) ; printf ("Testes de remocao funcionaram!\n") ; // PARTE 3: operações inválidas ============================================= // inicializa os N elementos for (i=0; iid = i ; aux->prev = aux->next = NULL ; queue_append ((queue_t**) &fila0, (queue_t*) aux) ; assert (fila_correta (fila0)) ; } printf ("Ok, criei uma fila com %d elementos ordenados\n", N*N) ; // retirar e destruir cada elemento da fila, em sequencia for (i=0; i< N*N; i++) { aux = fila0 ; queue_remove ((queue_t**) &fila0, (queue_t*) fila0) ; assert (fila_correta (fila0)) ; assert (aux->id == i) ; free (aux) ; } printf ("Ok, retirei e destrui em ordem %d elementos da fila\n", N*N) ; printf ("Testes de operações inválidas funcionaram!\n") ; // PARTE 4: queue_print ===================================================== printf ("Teste do queue_print...\n"); // inicializa os N elementos for (i=0; i1 0<1>2 1<2>3 2<3>4 3<4>5 4<5>6 5<6>7 6<7>8 7<8>9 8<9>0]\n") ; queue_print ("Saida gerada ", (queue_t*) fila0, print_elem) ; printf ("Testes concluidos!!!\n") ; exit(0) ; }