Lista ligada
São realizadas várias versões do programa para exemplificar a utilização de diversos tipos de lista e técnicas de programação em linguagem C. Designadamente:
lista simplesmente ligada;
lista duplamente ligada;
lista não intrusiva;
lista genérica não intrusiva;
lista genérica intrusiva.
utilização da biblioteca Glib
Lista simplesmente ligada
A representação de um utente na lista é suportada por uma struct, que inclui os dados do utente e a indicação do próximo utente.
Os dados do utente são compostos pelo nome e pelo instante temporal em que chegou à fila.
O nome é armazenado num array de caracteres alocado dinamicamente,
por isso o campo name é um ponteiro para char.
O campo arrival guarda informação temporal que é representada pelo número de segundos,
desde o início de uma época (dia 1 de janeiro de 1970).
O campo next aponta para o próximo elemento da lista
por isso é do tipo ponteiro para struct user (struct user *).
struct user {
struct user *next; /* Próximo elemento na lista (fila) */
time_t arrival; /* Momento da chegada */
char *name; /* Nome do utente */
};
A tradução da disciplina primeiro a entrar – primeiro a sair da fila de espera para a lista ligada, corresponde a inserir num extremo da lista e a retirar no outro extremo.
Uma maneira de realizar esta operação com baixo custo de processamento é usar dois ponteiros, um para cada extremo da lista.
Os ponteiros head e tail que indicam respetivamente
o extremo de remoção e o extremo de inserçãoprimeiro e último elementos da lista.
Figura 7 Lista representando três utentes na fila
Inicialmente a lista está vazia por isso o ponteiro head é inicializado com NULL.
static struct user *head = NULL, *tail;
Listar utentes na fila
Esta operação consiste em percorrer a lista e para cada elemento
imprimir o nome do utente e o tempo que já esperou.
Percorrer a lista consiste em afetar o ponteiro user
com a referência para cada elemento da lista.
Começa com o apontado por head, que é o primeiro da lista,
e vai sendo atualizado, no final de cada iteração, com a referência para o próximo
(user = user->next).
Termina quando o valor retirado do campo next do elemento corrente for NULL.
Significa que o elemento corrente é o último da lista.
static void user_print()
{
if (NULL == head) {
printf("Fila vazia\n");
return;
}
int i = 1;
for (struct user *user = head; user != NULL; user = user->next)
printf("%d: %s, %ld\n", i++, user->name, time(NULL) - user->arrival);
}
Inserir novo utente na fila
- A inserção de novo utente na fila de espera é realizada em três passos:
alocar memória para uma nova
struct user– linhas 2 a 6;preencher a
struct usercom os dados do novo utente – linhas 7 a 14;inserir a
struct userna lista ligada – linhas 15 a 21.
O segundo passo engloba também a alocação do array de caracteres para alojar o nome do utente – linha 7.
1static void user_insert(char *name)
2{
3 struct user *user = malloc(sizeof *user);
4 if (NULL == user) {
5 fprintf(stderr, "Out of memory\n");
6 exit(EXIT_FAILURE);
7 }
8 user->name = malloc(strlen(name) + 1);
9 if (NULL == user->name) {
10 free(user);
11 fprintf(stderr, "Out of memory\n");
12 exit(EXIT_FAILURE);
13 }
14 strcpy(user->name, name);
15 time(&user->arrival);
16 user->next = NULL;
17 if (NULL == head)
18 head = tail = user;
19 else {
20 tail->next = user;
21 tail = user;
22 }
23}
Remover utente por atendimento normal
- A remoção por atendimento normal é realizada em três passos:
remover a
struct userque encabeça a lista – linhas 2 a 5 ;extrair a informação do utente – linha 7;
libertar a memória alocada para a
struct user– linha 8.
A memória alocada para alojar o nome não é libertada ainda porque o ponteiro para esse local vai ser retornado pela função.
1static char *user_answer()
2{
3 if (NULL == head)
4 return NULL;
5 struct user *user = head;
6 head = head->next;
7
8 char *name = user->name;
9 free(user);
10 return name;
11}
Remover utente por desistência
- A remoção por desistência é realizada em três passos:
localizar na lista a
struct userque representa o utente desistente – linha 4 a 6;remover essa
struct userda lista – linhas 7 a 14;por fim libertar a memória alocada – linhas 15 a 17.
A sequência das operações das linhas 15 e 16 terá que ser exatamente esta
– não poderia ser invertida.
Porque a partir do momento em que se liberta uma zona de memória com a operação free,
deixa de ser possível utilizar o conteúdo dessa zona de memória.
Se se executasse free(user) em primeiro lugar,
ao executar free(user->name) o conteúdo de user->name já seria inválido.
1static void user_remove(char *name)
2{
3 if (NULL == head)
4 return;
5 struct user *prev = NULL;
6 for (struct user *user = head; user != NULL; prev = user, user = user->next)
7 if (strcmp(name, user->name) == 0) {
8 if (NULL == prev) {
9 head = user->next;
10 }
11 else {
12 prev->next = user->next;
13 if (NULL == prev->next)
14 tail = prev;
15 }
16 free(user->name);
17 free(user);
18 return;
19 }
20}
Em listas de ligação simples, nas operações que impliquem
acrescentar ou remover elementos no interior da lista, é comum usarem-se duas
referências: uma para o elemento corrente e outra para o elemento anterior
– no exemplo, os ponteiros user e prev.
Estes ponteiros progridem em conjunto (prev = user, user = user->next),
estando o ponteiro prev sempre a referenciar o elemento anterior.
O ponteiro prev é inicializado com NULL para permitir detetar
se a operação incide sobre o primeiro elemento da lista.
Eliminar a fila de utentes
A lista ligada é destruida,
libertando a memória alocada em cada um dos seus elementos (linhas 4 e 5).
Note-se a utilização da variável next
para guardar temporariamente o ponteiro para o próximo elemento,
pois já não seria possível o acesso ao campo user->next,
depois de free(user).
1static void user_delete_queue()
2{
3 for (struct user *next, *user = head; user != NULL; user = next) {
4 next = user->next;
5 free(user->name);
6 free(user);
7 }
8}
Lista duplamente ligada
Numa lista duplamente ligada os elementos da lista têm duas referências de ligação, uma para o elemento seguinte e outra para o elemento anterior.
No exemplo que temos vindo a tratar é acresecentado o campo de ligação prev
à struct user para suportar a ligação em sentido inverso.
1struct user {
2 struct user *next, *prev;
3 time_t arrival;
4 char *name;
5};
A lista realizada caracteriza-se por ser duplamente ligada, com ligação circular e com presença de elemento sentinela.
A existência de dupla ligação conjugada com ligação circular (o primeiro e último elementos da lista referenciam-se mutuamente), permite suprimir o ponteiro para o último elemento.
A utilização de um elemento sentinela facilita a programação das operações de modificação da lista porque, ao garantir a existência de pelo menos um elemento na lista, evita lidar com o caso particular de lista vazia.
A sentinela é um elemento do mesmo tipo dos restantes elementos da lista, mas sem informação útil além das referências de ligação.
Figura 8 Lista duplamente ligada, circular, com sentinela, representando três utentes na fila
A lista vazia é caraterizada por ter os campos next e prev do elemento sentinela
a apontar para o próprio elemento sentinela.
static struct user queue = { .next = &queue, .prev = &queue };
Listar utentes na fila
void user_print()
{
if (queue.next == &queue) {
printf("Fila vazia\n");
return;
}
int i = 1;
for (struct user *user = queue.next; user != &queue; user = user->next)
printf("%d: %s, %ld\n", i++, user->name, time(NULL) - user->arrival);
}
Inserir novo utente na fila
Relativamente à versão de lista simplesmente ligada, a diferença está nas operações de manipulação da lista (linhas 17 a 20).
1static void user_insert(char *name)
2{
3 struct user *user = malloc(sizeof *user);
4 if (NULL == user) {
5 fprintf(stderr, "Out of memory\n");
6 exit(EXIT_FAILURE);
7 }
8 user->name = malloc(strlen(name) + 1);
9 if (NULL == user->name) {
10 free(user);
11 fprintf(stderr, "Out of memory\n");
12 exit(EXIT_FAILURE);
13 }
14 strcpy(user->name, name);
15 time(&user->arrival);
16
17 user->prev = queue.prev;
18 user->next = &queue;
19 queue.prev->next = user;
20 queue.prev = user;
21}
Remover utente por atendimento normal
Primeiro é necessário verificar se a lista está vazia.
O teste de lista vazia consiste em verificar se o campo next (ou prev)
do elemento sentinela aponta para o próprio elemento sentinela (linha 3).
O próximo utente a ser atendido corresponde ao primeiro elemento da lista (linha 5).
Nas linhas 7 e 8 o elemento é removido da lista.
1char *user_answer()
2{
3 if (queue.next == &queue)
4 return NULL;
5 struct user *user = queue.next;
6
7 user->next->prev = user->prev;
8 user->prev->next = user->next;
9
10 char *name = user->name;
11 free(user);
12 return name;
13}
Remover utente por desistência
Para encontrar o elemento a remover é necessário percorrer a lista (linhas 3 e 4).
Dado a lista possuir sentinela, a operação de remoção de um elemento, independentemente da sua posição, processa-se sempre da mesma maneira (linhas 6 e 7). Comparar com as linhas 7 e 8 da Listagem 79.
1static void user_remove(char *name)
2{
3 for (struct user *user = queue.next; user != &queue; user = user->next)
4 if (strcmp(name, user->name) == 0) {
5
6 user->prev->next = user->next;
7 user->next->prev = user->prev;
8
9 free(user->name);
10 free(user);
11 return;
12 }
13}
Eliminar a fila de utentes
1void user_delete_queue()
2{
3 for (struct user *next, *p = queue.next; p != &queue; p = next) {
4 next = p->next;
5 free(p->name);
6 free(p);
7 }
8}
Lista não intrusiva
Designa-se por lista intrusiva uma lista em que os elementos de formação da lista
(campos next e prev) fazem parte da mesma struct que os elementos de dados.
É o caso das listas anteriores.
Designa-se por lista não intrusiva uma lista cujos elementos de formação da lista são externos à struct que contém os dados de utilização.
Um objeto de dados pode estar inserido simultaneamente em várias listas não intrusivas.
Listas intrusivas só podem conter os objetos que contenham os elementos de ligação.
Para exemplificar a utilização de lista não intrusiva no programa de simulação de fila de espera, são criadas duas struct, uma para os elementos de formação da lista e outra para os elementos de dados.
A formação da lista é baseada na struct list_node
que contém os campos next e prev para referenciar os elementos adjacentes da lista
e um ponteiro para a struct de dados.
struct list_node {
struct list_node *next, *prev;
void *data;
};
A struct user que representa o utente contém apenas os campos estritamente necessários para guardar a informação do utente. Não contém campos de formção da lista.
struct user {
time_t arrival;
char *name;
};
Figura 9 Lista não intrusiva com três elementos
A lista é representada pela variável queue – elemento sentinela,
do tipo do elemento de formação da lista.
static struct list_node queue = { .next = &queue, .prev = &queue };
Listar utente na fila
1static void user_print()
2{
3 if (&queue == queue.next) {
4 printf("Fila vazia\n");
5 return;
6 }
7 for (struct list_node *node = queue.next; node != &queue; node = node->next) {
8 struct user *user = node->data;
9 printf("Nome: %s, %ld\n", user->name, time(NULL) - user->arrival);
10 }
11}
Inserir novo utente na fila
O código de inserção de utente na fila está separado em dois blocos. Das linhas 3 a 15 o código que trata dos dados do utente e nas linhas 27 a 30 o código de inserção na lista ligada.
1static void user_insert(char *name)
2{
3 struct user * user = malloc(sizeof *user);
4 if (NULL == user) {
5 fprintf(stderr, "Out of memory\n");
6 exit(EXIT_FAILURE);
7 }
8 user->name = malloc(strlen(name) + 1);
9 if (NULL == user->name) {
10 free(user);
11 fprintf(stderr, "Out of memory\n");
12 exit(EXIT_FAILURE);
13 }
14 strcpy(user->name, name);
15 time(&user->arrival);
16
17 struct list_node *node = malloc(sizeof *node);
18 if (NULL == node) {
19 free(user->name);
20 free(user);
21 fprintf(stderr, "Out of memory\n");
22 exit(EXIT_FAILURE);
23 }
24
25 node->data = user;
26
27 node->next = &queue;
28 node->prev = queue.prev;
29 queue.prev->next = node;
30 queue.prev = node;
31}
Remover utente por atendimento normal
O acesso aos dados de utilização faz-se através do campo data dos nós da lista.
As instruções das linhas 11 e 12 retiram o nó da lista
e a instrução free(node) liberta a memória alocada para o nó.
1static char *user_answer()
2{
3 if (&queue == queue.next)
4 return NULL;
5
6 struct list_node *node = queue.next;
7 struct user *user = node->data;
8 char *name = user->name;
9 free(user);
10
11 node->next->prev = node->prev;
12 node->prev->next = node->next;
13 free(node);
14
15 return name;
16}
Remover utente por desistência
1static void user_remove(char *name)
2{
3 for (struct list_node *node = queue.next; node != &queue; node = node->next) {
4 struct user *user = node->data;
5 if (strcmp(user->name, name) == 0) {
6 free(user->name);
7 free(user);
8
9 node->next->prev = node->prev;
10 node->prev->next = node->next;
11 free(node);
12
13 return;
14 }
15 }
16}
Eliminar fila de utentes
1static void user_delete_queue()
2{
3 for (struct list_node *next, *node = queue.next; node != &queue; node = next) {
4 next = node->next;
5 free(((struct user *)node->data)->name);
6 free(node->data);
7 free(node);
8 }
9}
Lista genérica não intrusiva
Esta implementação é equivalente à anterior, com a diferenças das operações de nanipulação da lista ligada serem integradas em funções. Essas funções por sua vez são agrupadas em ficheiro separado. O objetivo é viabilizar a reutilização do código específico da lista em outras aplicações. Os benefícios são dispensar o programador de lidar com detalhes de implementação e teste das operações sobre a lista. O código de utilização apenas tem que invocar as funções que realizam as operações desejadas.
Figura 10 Lista genérica não intrusiva
Por razões didáticas, as funções de manipulação da lista são apresentadas próximas dos contextos de utilização, à medida que vão sendo necessárias.
O utilizador terá também que lidar com a entidade opaca “nó da lista”, do tipo List_node.
A lista é representada por um ponteiro para List_node.
static List_node *queue;
A função list_create cria uma lista vazia e devolve o ponteiro para List_node
que representa a lista.
int main() {
...
queue = list_create();
...
A função list_create começa por alocar memória para o nó sentinela.
Aponta ambos os campos de ligação para si próprio, representando lista vazia,
e retorna o ponteiro para o nó sentinela.
1void list_init(struct list_node *node)
2{
3 node->next = node->prev = node;
4}
5
6struct list_node *list_create()
7{
8 struct list_node *node = malloc(sizeof *node);
Inserir novo utente na fila
1static void user_insert(char *name)
2{
3 struct user * user = malloc(sizeof *user);
4 if (NULL == user) {
5 fprintf(stderr, "Out of memory\n");
6 exit(EXIT_FAILURE);
7 }
8 user->name = malloc(strlen(name) + 1);
9 if (NULL == user->name) {
10 free(user);
11 fprintf(stderr, "Out of memory\n");
12 exit(EXIT_FAILURE);
13 }
14 strcpy(user->name, name);
15 time(&user->arrival);
16 list_insert_rear(queue, user);
17}
A função list_insert_rear começa por alocar memória para o novo nó,
em seguida anota a referência para os dados e por fim insere o nó na lista.
1 node->next->prev = new_node;
2 node->next = new_node;
3 return 1;
4}
5
6int list_insert_rear(struct list_node *node, void *data)
7{
8 struct list_node *new_node = malloc(sizeof *new_node);
9 if (NULL == new_node)
10 return 0;
11 new_node->data = data;
12
13 new_node->prev = node->prev;
Remover utente da fila por atendimento normal
A função list_get_front devolve o ponteiro para o primeiro nó da lista sem o remover.
A função list_get_data devolve o ponteiro para o elemento de dados referenciado pelo nó,
que neste contexto é o ponteiro para uma struct user.
A utilização de uma função em vez do acesso direto ao capo data,
torna o código de utilização da lista independente da sua implementação
– neste caso a constituição interna da struct list_node.
1char *user_answer()
2{
3 if (list_empty(queue))
4 return NULL;
5 struct list_node *node = list_get_front(queue);
6 struct user *user = list_get_data(node);
7 list_remove(node);
8
9 char *name = user->name;
10 free(user);
11 return name;
12}
A função list_remove, depois da desinserir o nó lista,
liberta a memória de suporte ao nó.
Note-se que a libertação dos elementos de dados de utilização,
por serem específicos, é realizada no contexto da função user_answer.
1 node->prev->next = new_node;
2 node->prev = new_node;
3 return 1;
4}
5
Remover utente da fila por desistência
A operação de procura do utente desistente é realizada pela função genérica list_search
que tem como argumentos:
a lista, o ponteiro para a função de comparação do nome e o nome a procurar.
Se existir na lista um elemento com nome igual ao nome procurado, é devolvido o ponteiro para o respetivo nó.
A remoção do nó da lista e a libertação da memória alocada para ele
é realizada pela função list_remove.
1static void user_remove(char *name)
2{
3 if (list_empty(queue))
4 return;
5 struct list_node *node = list_search(queue, name_compare, name);
6 if (node == NULL)
7 return;
8 struct user *user = list_get_data(node);
9 list_remove(node);
10 free(user->name);
11 free(user);
12}
A função list_search itera sobre a lista e, em cada iteração,
invoca a função de verificação predicate
passando o ponteiro para os dados desse elemento,
neste caso a struct user, e um elemento de contexto recebido da função invocante.
1 node != list && compare(node->data, data) < 0; node = node->next)
2 ;
3 return list_insert_rear(node, data);
4}
5
6struct list_node *list_search(struct list_node *list,
7 bool (*predicate)(const void *, const void *), const void *context)
8{
A função de verificação tem como primeiro parâmetro
o ponteiro para o elemento de dados – campo data de strct list_node –
e como segundo parâmetro, o terceiro parâmetro de struct list_search,
por onde o utilizador enviará um elemento de contexto à função de verificação
– neste caso o nome a procurar.
1static bool name_compare(const void *a, const void *b)
2{
3 const struct user *user = a;
4 const char *name = b;
5 return strcmp(user->name, name) == 0;
6}
A função de verificação é específica da utilização – neste caso a comparação de nomes.
A sua assinatura é genérica bool (*)(const void *, const void *),
a sua especificidade surge no interior.
A acesso aos argumentos é feito depois dos tipos genéricos dos parâmetros serem
covertidos para os tipos específicos.
No caso corrente, o primeiro argumento é um ponteiro para struct user
e o segundo argumento é um ponteiro para string, com o nome a comparar.
Listar utentes na fila
Tal como na procura de utente, a operação de listar consiste em percorrer a lista.
Esta operação é realizada através da operação genérica list_foreach,
que tem como parâmetro o ponteiro para uma função de callback a invocar em cada iteração.
Esta função recebe como parâmetro o ponteiro para o elemento de dados –
campo data de struct list_node
– e uma informação de contexto que neste caso não é utilizada.
1void user_print()
2{
3 if (list_empty(queue)) {
4 printf("Fila vazia\n");
5 return;
6 }
7 list_foreach(queue, print, NULL);
8}
1static void print(void *a, void *)
2{
3 struct user *user = a;
4 printf("Nome: %s, %ld\n", user->name, time(NULL) - user->arrival);
5}
6
1void list_remove_rear(struct list_node *node)
2{
3 list_remove(node->prev);
4}
5
6void list_foreach(struct list_node *node,
Eliminar fila de utentes
A eliminação da fila de espera é realizada em duas fases.
Em primeiro lugar, a libertação dos recursos associados aos dados dos utentes
e em segundo lugar a destruição da própria lista ligada.
A primeira operação é baseada na função list_foreach
que em cada iteração, ao invocar a função free_user elimina os recursos de um utente.
A segunda operação é realizada pela operação list_destroy.
1{
2 list_foreach(queue, free_user, NULL);
3 list_destroy(queue);
4}
5
1{
2 struct user *user = data;
3 free(user->name);
4 free(user);
5}
6
1 return NULL;
2 node->next = node->prev = node;
3 return node;
4}
5
6void list_destroy(struct list_node *list)
7{
8 for (struct list_node *next, *node = list->next; node != list; node = next) {
Implementação
Para se utilizar as operações sobre a lista, implementadas na forma de funções, em ficheiro separado, é preciso conhecer as suas assinaturas. O processo de organização do código utilizado em linguagem C consiste em criar dois ficheiros, um com a definição da interface de utilização, que contém a definição de tipos de dados e a assinatura das funções – declaração – e outro com a implementação das funções – definição.
1#ifndef LIST_H
2#define LIST_H
3
4struct list_node;
5
6/*
7 * Criar uma lista nova
8 */
9struct list_node *list_create();
10
11/*
12 * Eliminar uma lista
13 */
14void list_destroy(struct list_node *p);
15
16/*
17 * Remover elemento indicado
18 */
19void list_remove(struct list_node *node);
20
21/*
22 * Remover elemento atrás
23 */
24void list_remove_rear(struct list_node *p);
25
26/*
27 * Remover elemento à frente
28 */
29void list_remove_front(struct list_node *p);
30
31/*
32 * Inserir elemento atrás de
33 */
34int list_insert_rear(struct list_node *p, void *data);
35
36/*
37 * Inserir elemento em posição ordenada
38 */
Gerar programa executável, dmitindo que os três ficheiros wqueue4.c, list.h e list.c se encontram na diretoria corrente:
$ gcc wqueue4.c list.c -o wqueue4
Lista genérica intrusiva
Como característica de uma lista intrusiva, os elementos de formação da lista são integrados na própria struct de dados de utilização. As listas ligadas utilizadas nas duas primeiras versões da aplicação fila de espera são do tipo intrusivo. Esta versão que vamos agora começar vai utilizar uma lista duplamente ligada idêntica á utilizada na segunda versão, mas programada de uma forma genérica e implementada em ficheiro separado a fim de cumprir o objetivo da reutilização.
A inexistência de um nó de ligação em separado, resulta na supressão de um nível de indireção no acesso aos dados. Isso constitui uma vantagem que se manifesta em menos processamento e em melhor desempenho no acesso à memória (devido a melhor localidade espacial).
A desvantagem da lista intrusiva é a menor flexibilidade na utilização. O elemento de dados só pode ser inserido em listas para as quais possua elementos de ligação.
Figura 11 Lista duplamente ligada, genérica e intrusiva
O nó de ligação da lista (tipo ilist_node)
possui apenas os campos de referência para os nós adjacentes.
1struct ilist_node {
2 struct ilist_node *next, *prev;
3};
Na aplicação de fila de espera que temos vindo a tratar,
além dos habituais campos de dados de utilização – arrival e name –
é acrescentado o campo de formação da lista – node – do tipo struct ilist_node.
1struct user {
2 time_t arrival;
3 char *name;
4 struct ilist_node link;
5};
Figura 12 Fila de espera baseada em lista intrusiva
A lista é representada por um ponteiro para o elemento sentinela, do tipo Ilist_node.
struct ilist_node *queue;
Antes de começar a utilizar a lista é preciso iniciar o ponteiro queue
com o ponteiro para uma lista vazia.
int main() {
...
queue = ilist_create();
...
A principal diferença de utilização entre a lista intrusiva e não intrusiva,
está na forma de aceder aos dados de utilização.
Na primeira, o acesso faz-se através do campo data, existente no próprio nó da lista.
Implica uma operação de acesso à memória.
List_node *node;
...
User *user = node->data;
mov %rax, data(%rbx)
Na segunda, o acesso faz-se por ajuste do ponteiro para o nó que está integrado na struct de utilização.
É realizado por uma operação interna ao processador – neste caso uma subtração de constante.
O valor 16 é a distância, em posições de memória, entre o início da struct e o campo link.
A macro offsetof, definida em stddef.h,
devolve a distância do campo indicado até ao início da struct a que o campo pertence.
offsetof(User, link) devolve a distância do campo link ao início de struct user.
Este valor é determinado em compilação.
struct ilist_node *node;
...
User *user = (User*)((char*)node - offsetof(User, link));
lea -16(%rbx), %rax
Inserir um novo utente na fila
A referência para inserção de uma struct user na lista queue
é o ponteiro para o campo link dessa struct – linha 7.
1static void user_insert(char *name)
2{
3 struct user *user = malloc(sizeof *user);
4 if (NULL == user) {
5 fprintf(stderr, "Out of memory\n");
6 exit(EXIT_FAILURE);
7 }
8 user->name = malloc(strlen(name) + 1);
9 if (NULL == user->name) {
10 free(user);
11 fprintf(stderr, "Out of memory\n");
12 exit(EXIT_FAILURE);
13 }
14 strcpy(user->name, name);
15 time(&user->arrival);
16 ilist_insert_rear(queue, &user->link);
17}
Remover utente da fila por atendimento normal
O primeiro elemento da lista, do tipo struct user,
é obtido através da função ilist_remove_front – linha 4.
A referência recebida é um ponteiro para o campo link,
não o ponteiro para o início da struct user.
Como obter o ponteiro para struct user a partir do ponteiro para o campo link?
Subtraindo a este ponteiro, a distância do campo link até ao início da struct user – linha 5.
1 */
2char *user_answer()
3{
4 if (ilist_empty(queue))
5 return NULL;
6 struct ilist_node *node = ilist_remove_front(queue);
7 struct user *user = (struct user*)((char*)node - offsetof(struct user, link));
8
9 char *name = user->name;
10 free(user);
11 return name;
Remover utente da fila por desistência
1 */
2static int name_compare(struct ilist_node *node, const void *name)
3{
4 struct user *user = (struct user*)((char*)node - offsetof(struct user, link));
5 return strcmp(user->name, name);
6}
7
8static void user_remove(char *name)
9{
10 if (ilist_empty(queue))
11 return;
12 struct ilist_node * node = ilist_search(queue, name_compare, name);
13 if (node == NULL)
14 return;
15 struct user *user = (struct user*)((char*)node - offsetof(struct user, link));
16 ilist_remove(node);
17 free(user->name);
18 free(user);
Listar utentes na fila
1
2static void print(struct ilist_node *node, void *)
3{
4 struct user *user = (struct user*)((char*)node - offsetof(struct user, link));
5 printf("%s, %ld\n", user->name, time(NULL) - user->arrival);
6}
7
8void user_print()
9{
10 if (ilist_empty(queue)) {
11 printf("Fila vazia\n");
12 return;
13 }
14 ilist_foreach(queue, print, NULL);
Vazar fila de utentes
1void free_user(struct ilist_node *node, void *)
2{
3 struct user *user = (struct user*)((char*)node - offsetof(struct user, link));
4 free(user->name);
5 free(user);
6}
7
8void user_delete_queue()
9{
10 ilist_foreach(queue, free_user, NULL);
11 ilist_destroy(queue);
12}
struct GList – Biblioteca Glib
Nesta secção exemplifica-se a utilização de lista genérica pertencente à biblioteca GLib.
https://docs.gtk.org/glib/struct.List.html
Esta biblioteca dispõe de duas implementações de lista, uma simplesmente ligada e outra duplamente ligada, ambas não intrusivas e sem sentinela.
Vai ser utilizada a lista duplamente ligada.
O nó da lista é representado pela struct GList:
struct GList {
gpointer data;
GList *next;
GList *prev;
};
O campo data referencía os dados de utilização o que permite caraterizar a lista como não intrusiva.
Ao nível da aplicação, a lista é representada por um ponteiro para o primeiro nó da lista.
static struct GList *queue = NULL;
Não existe função de biblioteca específica para criar ou iniciar a lista.
A inicialização da lista como vazia consiste em atribuir o valor NULL ao ponteiro queue.
O código de aplicação é basicamente igual ao da Lista genérica não intrusiva com a substituição das funções de manipulação da lista pelas funções da biblioteca GLib.
Inserir um novo utente na fila
1static void user_insert(char *name)
2{
3 struct user *user = malloc(sizeof *user);
4 if (NULL == user) {
5 fprintf(stderr, "Out of memory\n");
6 exit(-1);
7 }
8 user->name = malloc(strlen(name) + 1);
9 if (NULL == user->name) {
10 free(user);
11 fprintf(stderr, "Out of memory\n");
12 exit(-1);
13 }
14 strcpy(user->name, name);
15 time(&user->arrival);
16 queue = g_list_insert_before(queue, NULL, user);
17}
Remover utente da fila por atendimento normal
1
2/*-----------------------------------------------------------------------------
3 Função para remover da fila o primeiro utente a ser atendido
4 */
5char *user_answer()
6{
7 if (ilist_empty(queue))
8 return NULL;
9 struct ilist_node *node = ilist_remove_front(queue);
10 struct user *user = (struct user*)((char*)node - offsetof(struct user, link));
11
Remover utente da fila por desistência
1static int name_compare(const void *a, const void *b)
2{
3 const struct user *user = a;
4 const char *name = b;
5 return strcmp(user->name, name);
6}
7
8static void user_remove(char *name)
9{
10 if (g_list_length(queue) == 0)
11 return;
12 GList *node = g_list_find_custom(queue, name, name_compare);
13 if (node == NULL)
14 return;
15 struct user *user = node->data;
16 queue = g_list_delete_link(queue, node);
17 free(user->name);
18 free(user);
19}
Listar utentes na fila
1static void print(void *data, void *not_used)
2{
3 struct user *user = data;
4 printf("Nome: %s, %ld\n", user->name, time(NULL) - user->arrival);
5}
6
7void user_print()
8{
9 if (g_list_length(queue) == 0) {
10 printf("Fila vazia\n");
11 return;
12 }
13 g_list_foreach(queue, print, NULL);
14}
Vazar fila de utentes
1void free_user(void *user)
2{
3 free(((struct user *)user)->name);
4 free(user);
5}
6
7void user_delete_queue()
8{
9 g_list_free_full(queue, free_user);
10}