Listas circulares, do jeito Knuth (e do Linux)…

Já falei sobre listas encadeadas ao estilo Sedgewick aqui, mas eis uma maneira de implementar listas que fica ainda mais simples… O header abaixo mostra a implementação atual do MyToyOS, devidamente copiado do estilo Knuth e Linus de listas circulares:

#ifndef __LIST_INCLUDED__
#define __LIST_INCLUDED__

// Essa é a estrutura de um nó de uma lista, 
// mas também do nó "batente" ou "cabeça" da
// lista. E, uma vez que mantemos o nó "cabeça",
// a lista é "circular", para facilitar a 
// manipulação (sempre haverá um nó cabeça!).
// A lista "vazia" tem apenas a cabeça, apontando
// para si própria.
//
// Note que a lista é double linked e circular.
//
// COMO USAR:
//
// Suponha que você queira manter uma "lista de
// retângulos", onde um retângulo tenha a estrutura:
//
//   struct rect {
//     int left, top, right, bottom;
//   };
//
// A lista pode ser definida como:
//
//  struct _list_head rect_list_head;
//  INIT_LIST_HEAD(&rect_list_head);
//
// É claro, podemos inicializar a lista diretamente:
//
//  struct _list_head rect_list_head = 
//             EMPTY_LIST(rect_list_head);
//
// A última forma é útil para inicialização de listas
// locais estáticas e globais.
//
// No exemplo dos retângulos, os nós da lista, DEVEM
// ser definidos como:
//
//   struct rect_node {
//     struct _list_head next_rect;  // Isso tem que estar
//                                   // no início!
//     struct rect rc;
//   };
//
// Para adicionar um retângulo no fim da lista:
//
//   _list_add_tail(&rect_list_head, 
//                  (struct _list_head *)&rc_node);
//
// Para adicionar um retângulo no início da lista:
//
//   _list_add_after(&rect_list_head, 
//                   (struct _list_head *)&rc_node);
//
// Para retirar um retângulo da lista:
//
//   _list_unlink((struct _list_head *)&rc_node);
//
// Para percorrer a lista, do início ao fim:
//
//   struct _list_head *p;
//   _list_foreach(p, &rect_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Para percorrer a lista do fim para o início:
//
//   struct _list_head *p;
//   _list_foreach_reverse(p, &rc_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Infelizmente AINDA não criei a rotina para 
// percorrer toda a lista à partir de um nó 
// específico. Mas, você pode fazer isso guardando
// o nó en questão, percorrendo a lista em uma
// direção até o nó head (_list_foreach*) e 
// depois percorrer do head para o nó guardado. 
// Por exemplo, para frente:
//
//  struct _list_head *p = (struct _list_head *)&rc_node;
//  struct _list_head *q = p->prev;
//  struct _list_head *r = p;
//  _list_foreach(r, q)
//  { ... }
//  _list_forearch(r, &rc_list_head)
//  {
//    if (r == q) break;
//  }
//
// Repare também que, embora tenhamos um "batente", o 
// macro aceita qualquer nó da lista como "alvo". Mas 
// é necessário cuidado porque o "batente" real não tem
// dados.
//

// Estrutura da "cabeça" da lista.
struct _list_head { 
  struct _list_head *next;
  struct _list_head *prev; // Funciona como 'tail' para a 
                           // cabeça da lista.
};

// Os macros citados acima...
#define INIT_LIST_HEAD(name) \
  { (name)->next = (name)->prev = (name); }
#define EMPTY_LIST(name) \
  { .next = .prev = &(name); }

// Essencialmente a mesma coisa que acima, mas lida com o
// ponteiro para a "cabeça" da lista.
static inline void _list_init(struct _list_head *head)
{
  head->next = head->prev = head;
}

// A lista está vazia? Se next aponta para a cabeça, está!
static inline _Bool _list_empty(struct _list_head *head)
{ return head == head->next; }

// Insere o novo item depois do item "prev".
static inline void _list_add_after(struct _list_head *prev, 
                                   struct _list_head *_new)
{
  struct _list_head *next;
  struct _list_head *prev;

  next = head->next;
  prev = head->prev;

  if (_list_empty(head)) // Caso especial!
    head->prev = _new;
  _new->next = next;
  _new->prev = prev;
  head->next = _new;
}

// Addiciona um item no fim da lista.
static inline void _list_add_tail(struct _list_head *head, 
                                  struct _list_head *_new)
{
  _list_add_after(head->prev, _new);
}

// Apaga um nó da lista.
// OBS: Cuidado ao usar free(). o nó pode ser a cabeça!
static inline void _list_unlink(struct _list_head *node)
{
  // Note que se a lista estiver vazia, nada acontece.
  struct _list_head *next;
  struct _list_head *prev;

  next = node->next;
  prev = node->prev;
  prev->next = node->next;
  next->prev = node->prev;
}

// Percorrer uma lista pode ser feito com:
//
// struct _list_head *p = &mylist;
//
// for (p = mylist->next; p != &mylist; p = p->next)
// { ... }
//
// Dai o macro abaixo (tanto p quanto head são ponteiros:
//
// OBS: É bom lembrar que a cada iteração do loop o 
//      ponteiro de controle apontará para o próximo
//      item da lista (ou para o anterior se o sentido
//      for reverso) até que ele retorne para a "cabeça".
//      Assim, usá-lo para deletar itens na lista deve
//      ser feito com cuidado.
#define _list_foreach(p,head) \
  for (p=head->next; p != head; p=p->next)

#define _list_foreach_reverse(p,head) \
  for (p=head->prev; p != head; p=p->prev)

#endif

Por que as funções estão definidas no header e não num módulo C separado? Ora, as rotinas são tão simples que posso fazê-las inline. Rotinas em módulos separados, necessariamente, não são “inlineáveis”. Os macros _list_foreach e _list_foreach_reverse não podem ser funções porque são atalhos para a construção do loop que percorrerá toda a lista… Aliás, um conselho: Cuidado com o código abaixo

struct _list_head *p;
_list_foreach(p, &list_of_rects)
{
  _list_unlink(p);
}

Dependendo do que você fizer com os ponteiros do nó apontado por p, o loop não fará o que você quer (mas, do jeito que está, deve funcionar, porque o componente next de p continua apontando para o próximo item, embora o nó não faça mais parte da lista… No fim das contas apenas o a cabeça da lista sobrará (não será “desligada” da lista)…

Note também que nenhuma das rotinas é responsável por alocar ou dealocar a estrutura de um nó. Tudo o que elas fazem são as ligações corretas para manter a lista. É sua responsabilidade alocar ou liberar nós, incluindo a “cabeça”, é sempre deixada na lista no caso do desligamento de todos os nós…

A característica circular da lista torna fácil algumas operações (principalmente _list_foreach e sua contraparte).