From 283ca9f199199a81c65cb243b63ba9f433d14ad3 Mon Sep 17 00:00:00 2001 From: Alexandre P Francisco Date: Tue, 13 May 2014 22:47:45 +0100 Subject: [PATCH] Adding proj2 solution --- 1314s2p2/Makefile | 15 +++++ 1314s2p2/list.c | 121 ++++++++++++++++++++++++++++++++++++++ 1314s2p2/list.h | 25 ++++++++ 1314s2p2/main.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 308 insertions(+) create mode 100644 1314s2p2/Makefile create mode 100644 1314s2p2/list.c create mode 100644 1314s2p2/list.h create mode 100644 1314s2p2/main.c diff --git a/1314s2p2/Makefile b/1314s2p2/Makefile new file mode 100644 index 0000000..250f4c6 --- /dev/null +++ b/1314s2p2/Makefile @@ -0,0 +1,15 @@ +CC=gcc +CFLAGS=-O -Wall -ansi -pedantic + +EXECS=proj + +OBJS=main.o list.o +HDRS=list.h + +all: ${EXECS} + +proj: ${OBJS} ${HDRS} + ${CC} ${CFLAGS} -o $@ ${OBJS} + +clean: + rm -f *.o ${EXECS} diff --git a/1314s2p2/list.c b/1314s2p2/list.c new file mode 100644 index 0000000..fb9347e --- /dev/null +++ b/1314s2p2/list.c @@ -0,0 +1,121 @@ +/** + * @file list.c + * @brief Implementacao basica de uma lista circular. + */ +#include + +#include "list.h" + +/** + * @brief Funcao para insercao. + * + * @param 'head' identifica a cabeca da lista onde inserir. + * @param 'value' identifica o valor a inserir. + */ +void +list_insert(link head, void * value) +{ + link node = (link) malloc(sizeof(struct node)); + node->value = value; + node->next = head; + node->prev = head->prev; + + head->prev->next = node; + head->prev = node; + head->value = (void *) (((size_t) head->value) + 1); +} + +/** + * @brief Funcao para remover um no' da lista. + * + * Neste caso nao e' necessaria a cabeca da lista uma vez que estamos + * a utilizar listas duplamente ligadas. + * + * @param 'node' identifica o no' a remover. + */ +void +list_delete(link head, link node) +{ + if (!node) return; + node->prev->next = node->next; + node->next->prev = node->prev; + free(node); + head->value = (void *) (((size_t) head->value) - 1); +} + +/** + * @brief Funcao que indica se a lista está vazia + * + * @param 'head' identifica a cabeca da lista. + */ +int +list_is_empty(link head) +{ + return head == head->next; +} + +/** + * @brief Funcao para libertar a memoria associada a uma lista. + * + * @param 'head' identifica a cabeca da lista a libertar. + * @param 'freevalue' identifica a funcao que liberta a memoria + * associada aos valores (pode ser NULL). + */ +void +list_free(link head, void (*freevalue)(void *)) +{ + link l = head->next, aux; + + while (l != head) { + if (freevalue) + (*freevalue)(l->value); + aux = l; + l = l->next; + free(aux); + } + + head->next = head; + head->prev = head; + head->value = 0; +} + +/** + * @brief Funcao que permite efectuar uma visita a todos os elementos + * + * @param 'head' identifica a cabeca da lista a libertar. + * @param 'visit' identifica a funcao de visita. + * + */ +void +list_visit(link head, void (*visit)(void *)) +{ + link l = head->next; + + while (l != head) { + if (visit) + (*visit)(l->value); + l = l->next; + } +} + +/** + * @brief Funcao que retorna os elementos da lista num vector + * + * @param 'head' identifica a cabeca da lista a libertar. + * @param 'size' ref onde guardar os numero de elementos. + */ +void ** +list_to_array(link head) +{ + link l = head->next; + size_t i = 0; + void ** vec; + + vec = malloc(sizeof(void *)*((size_t) head->value)); + + for (l = head->next; l != head; l = l->next) + vec[i++] = l->value; + + return vec; +} + diff --git a/1314s2p2/list.h b/1314s2p2/list.h new file mode 100644 index 0000000..eac337f --- /dev/null +++ b/1314s2p2/list.h @@ -0,0 +1,25 @@ +/** + * @file list.h + * @brief Implementacao basica de uma lista circular. + */ +#ifndef LIST_H +#define LIST_H + +typedef struct node *link; + +struct node { + void * value; + struct node *next, *prev; +}; + +#define list_size(A) ((size_t) (A)->value) + +void list_insert(link head, void * value); +void list_delete(link head, link node); +int list_is_empty(link head); +void list_free(link head, void (*freevalue)(void *)); + +void ** list_to_array(link head); +void list_visit(link head, void (*visit)(void *)); + +#endif diff --git a/1314s2p2/main.c b/1314s2p2/main.c new file mode 100644 index 0000000..4f51713 --- /dev/null +++ b/1314s2p2/main.c @@ -0,0 +1,147 @@ +/** + * @file proj2.c + * @brief Implementacao do segundo projecto de IAED 2013/14 S2. + */ +#include +#include +#include + +#include "list.h" + +#define MSG_MAX_LEN 502 + +#define SEND "send" +#define PROC "process" +#define LIST "list" +#define SORT "listsorted" +#define KILL "kill" +#define QUIT "quit" + +/** + * @brief Tipo de dados que representa uma mensagem enviada pelo + * utilizador 'u' para o utilizador 'v', com o texto 'text'. + */ +typedef struct { + int u, v; + char * text; +} message; + +void freemsg(void *m) { + free(((message *) m)->text); + free(m); +} + +void visitmsg(void *m) { + message * msg = (message *) m; + printf("%d %d %s\n", msg->v, msg->u, msg->text); +} + +int msgcmp(const void *m1, const void *m2) { + message *msg1 = *((message **) m1); + message *msg2 = *((message **) m2); + int cmp = strcmp(msg1->text, msg2->text); + + if (cmp) return cmp; + return msg1->u - msg2->u; +} + +/** + * @brief Vector de filas para guardar mensagens de cada utilizador. + */ +static link queue; + +/** + * @brief Numero de utilizadores máximo (igual ao número de filas). + */ +static int n; + +/** + * @brief Funcao main. + * + * @return Codigo de estado de saida do programa. + */ +int main() +{ + char buffer[MSG_MAX_LEN]; + message *msg, **vmsg; + int i, msglen, v; + + scanf("%d", &n); + + /* Inicializar filas circulares. */ + queue = malloc(sizeof(struct node)*n); + memset(queue, 0x0, sizeof(struct node)*n); + for (i = 0; i < n; i++) + queue[i].next = queue[i].prev = queue + i; + + /* Processar comandos. */ + scanf("%s", buffer); + + while (strcmp(QUIT, buffer)) { + + /* send u v msg*/ + if (!strcmp(SEND, buffer)) { + msg = malloc(sizeof(message)); + scanf("%d%d", &msg->u, &msg->v); + getchar(); /* remove space */ + fgets(buffer, MSG_MAX_LEN, stdin); + msglen = strlen(buffer); + msg->text = malloc(sizeof(char)*(msglen + 1)); + buffer[--msglen] = '\0'; /* Remover '\n' */ + strcpy(msg->text, buffer); + list_insert(queue + msg->v, msg); + } + + /* process v */ + if (!strcmp(PROC, buffer)) { + scanf("%d", &v); + if (!list_is_empty(queue + v)) { + visitmsg(queue[v].next->value); + msg = (message *) queue[v].next->value; + free(msg->text); + free(msg); + list_delete(queue + v, queue[v].next); + } else + printf("NULL\n"); + } + + /* list v */ + if (!strcmp(LIST, buffer)) { + scanf("%d", &v); + if (!list_is_empty(queue + v)) + list_visit(queue + v, visitmsg); + else + printf("NULL\n"); + } + + /* listsorted v*/ + if (!strcmp(SORT, buffer)) { + scanf("%d", &v); + if (!list_is_empty(queue + v)) { + vmsg = (message **) list_to_array(queue + v); + qsort(vmsg, list_size(queue + v), sizeof(message *), msgcmp); + for (i = 0; i < list_size(queue + v); i++) + visitmsg(vmsg[i]); + + free(vmsg); + } else + printf("NULL\n"); + } + + /* kill v */ + if (!strcmp(KILL, buffer)) { + scanf("%d", &v); + list_free(queue + v, freemsg); + } + + scanf("%s", buffer); + } + + for (i = 0; i < n; i++) + list_free(queue + i, freemsg); + free(queue); + + /* Terminar o programa com sucesso. */ + return EXIT_SUCCESS; +} + -- 2.30.2