Travessia de uma árvore de diretórios usando recursividade

Introdução

O diretório é um elemento familiar nos sistemas de ficheiros, sendo empregue para organizar o armazenamento de dados em suporte persistente como, por exemplo, discos rígidos. Uma operação relativamente comum num sistema de ficheiros é a travessia da árvore de diretórios, através da qual são visitados todos os subdiretórios e ficheiros. Este artigo foca o uso de recursividade e das funções stat e readdir para a travessia de uma árvore de diretório recorrendo à metodologia denominada de busca em profundidade (depth-first search na designação anglo-saxónica) (Knuth, 1968) (Wikipedia, 2015). Embora o artigo assente no ambiente Linux e na linguagem C, a metodologia utilizada pode ser empregue, com algumas adaptações, noutras plataformas e com outras linguagens de programação.

Diretórios, caminhos absolutos e caminhos relativos

Um diretório pode conter ficheiros, outros diretórios e assim sucessivamente, resultando numa estrutura em árvore. O ponto de entrada da árvore é designado por diretório raiz, sendo representado pela barra / (slash bar na designação anglo-saxónica) em sistemas operativos UNIX e derivados. A barra / é ainda empregue como separador na representação de caminhos dos sistemas de ficheiros que identifiquem um determinado recurso, seja um diretório ou um ficheiro. No que respeita a caminhos, esses podem ser representados de forma absoluta ou relativa. A representação absoluta requer que o caminho do recurso que se pretende identificar seja especificado desde a raiz, iniciando-se pela barra /. Por exemplo, o caminho absoluto /bin/ls identifica a localização tradicional do comando ls num sistema UNIX. Por sua vez, e como o nome sugere, um caminho relativo é especificado em relação ao diretório corrente, não se iniciando, portanto, com a barra /. Por exemplo, o caminho programar/artigo.doc refere-se ao ficheiro artigo.doc que se encontra no diretório programar que existe no diretório corrente. A Listagem 1 mostra o primeiro nível da árvore de diretórios definida pelo sistema de ficheiros de um sistema Linux.

├── bin
├── boot
├── dev
├── etc
├── home
├── lib
├── lost+found
├── media
├── mnt
├── opt
├── proc
├── root
├── run
├── sbin
├── srv
├── sys
├── tmp
├── usr
└── var
Listagem 1: árvore de diretórios de um sistema Linux a partir do diretório / (saída do tree: tree -L 1 -d /)

As funções da família stat

As funções da família statstat, fstat e lstat – permitem o acesso aos metadados de uma entrada do sistema de ficheiros, seja um diretório, um ficheiro, uma ligação simbólica ou um outro recurso. A designação metadados abrange os elementos caracterizadores da entrada, tal como a data de criação, as permissões, a identificação do dono e grupo do recurso, entre outros elementos. Para o efeito, as funções da família stat recorrem à estrutura struct stat para representação dos metadados. A struct stat tem 13 campos, apresentados na Listagem 2 que foi diretamente extraída da saída do comando man 2 stat. Note-se que algumas versões de UNIX podem ter campos adicionais na struct stat, sendo que o uso desses campos extra num programa limita necessariamente a portabilidade do código.

struct stat {
   dev_t     st_dev;     /* ID of device containing file */
   ino_t     st_ino;     /* inode number */
   mode_t    st_mode;    /* protection */
   nlink_t   st_nlink;   /* number of hard links */
   uid_t     st_uid;     /* user ID of owner */
   gid_t     st_gid;     /* group ID of owner */
   dev_t     st_rdev;    /* device ID (if special file) */
   off_t     st_size;    /* total size, in bytes */
   blksize_t st_blksize; /* blocksize for filesystem I/O */
   blkcnt_t  st_blocks;  /* num of 512B blocks allocated */
   time_t    st_atime;   /* time of last access */
   time_t    st_mtime;   /* time of last modification */
   time_t    st_ctime;   /* time of last status change */
};
Listagem 2: estrutura struct stat (fonte: man 2 stat)

A Listagem 3 apresenta o código da aplicação metadados_dir_corrente que exemplifica o uso da função stat, mostrando na saída padrão o valor dos 13 campos de metadados da struct stat para a entrada . (ponto). A entrada . é uma entrada especial que representa o diretório corrente. Outra entrada especial é o .. (ponto ponto) que representa o diretório pai ou diretório ascendente. Tanto o diretório . e o diretório pai .. existem em todos os diretórios, pelo que as entradas . e .. são sempre válidas (no caso do diretório raiz /, a entrada .. aponta para o próprio diretório raiz). A Listagem 4 mostra a saída resultante da execução da aplicação metadados_dir_corrente. Obviamente, a saída varia consoante o diretório corrente onde é executada a aplicação.

Em termos de código, para além da chamada à função stat, a aplicação metadados_dir_corrente implementa a função tipo_file_str que recebendo o campo st_mode da struct stat devolve uma cadeia de caracteres indicando se a entrada corresponde a um ficheiro regular, diretório, atalho (symbolic link) ou “outro”. Para determinar o tipo de entrada, a função tipo_file_str() faz uso das macros do sistema S_IS_REG(), S_IS_DIR() e S_IS_LNK() indicando como parâmetro o campo st_mode da entrada em análise. Importa notar que para além do tipo de entrada, o campo st_mode contém, a informação referente às permissões de acesso do recurso – leitura, escrita, execução – para o dono, o grupo e o outros. Finalmente, os campos do tipo time_t, isto é, st_atime, st_ctime e st_mtime são convertidos para uma representação dia/hora através da função ctime_r que corresponde à versão reentrante da função ctime. Mais detalhes podem ser encontrados na respetiva página do manual (man ctime).

Conforme referido anteriormente, a família de funções stat tem, para além da função stat propriamente dita, as funções fstat e lstat. Na função fstat, o ficheiro do qual se pretende os respetivos metadados é indicado por um descritor de ficheiro, descritor esse previamente obtido através da função open. Por sua vez, a função lstat comporta-se de forma similar à função stat, com uma exceção: quando é indicada uma ligação simbólica, o lstat devolve os metadados da ligação simbólica e não os metadados para a qual aponta a ligação simbólica. Mais adiante neste artigo, far-se-á uso da função lstat na implementação recursiva da travessia de uma árvore de diretórios.

#include <...>
char *tipo_file_str(mode_t st_mode){
         if( S_ISREG(st_mode) ){
                  return "ficheiro normal";
         }else if( S_ISDIR(st_mode) ){
                  return "Diretório";
         }else if( S_ISLNK(st_mode) ){
                  return "Atalho";
         }
         /* ainda aqui? */
         return "outro";
}

void mostra_struct_stat(const struct stat *buf_ptr){
         char dia_hora_str[128];
         printf("st_dev = %u.%u\n",
                  major(buf_ptr->st_dev),
                  minor(buf_ptr->st_dev));
         printf("st_ino = %ld\n", buf_ptr->st_ino);
         printf("st_mode = %x (%s)\n", buf_ptr->st_mode,
                  tipo_file_str(buf_ptr->st_mode) );
         printf("st_nlink = %d\n", buf_ptr->st_nlink);
         printf("st_uid = %d\n", buf_ptr->st_uid);
         printf("st_gid = %d\n", buf_ptr->st_gid);
         printf("st_rdev= %d\n", (int)buf_ptr->st_rdev);
         printf("st_size= %lu\n", buf_ptr->st_size);
         printf("st_blksize= %ld\n",
                           buf_ptr->st_blksize);
         printf("st_blocks=%ld (blocos de 512B)\n",
                           buf_ptr->st_blocks);
         /* ctime devolve string com '\n' no final */
         printf("st_atime (ultimo acesso)=%s",
           ctime_r(&(buf_ptr->st_atime),dia_hora_str));
         printf("st_mtime (ultima modificação)=%s",
           ctime_r(&(buf_ptr->st_mtime),dia_hora_str));
         printf("st_ctime (ultima alter. estado)=%s",
           ctime_r(&(buf_ptr->st_ctime),dia_hora_str));
}
 
int main(void){
         char *nome = "."; /* diretório corrente */
         int ret_stat;
         struct stat stat_buf;
         ret_stat = stat(nome, &stat_buf);
         if( ret_stat == -1 ){
                  fprintf(stderr,"Erro: chamada stat"
                  " para recurso '%s' - %s\n",
                  nome, strerror(errno));
                  exit(1);
         }
         mostra_struct_stat(&stat_buf);
         return 0;
}
Listagem 3: aplicação mostra_metadados_dir_corrente
st_dev = 8.17
st_ino = 3662149
st_mode = 41fd (Diretório)
st_nlink = 2
st_uid = 1000
st_gid = 1000
st_rdev= 0
st_size= 4096
st_blksize= 4096
st_blocks=8 (blocos de 512B)
st_atime (ultimo acesso)=Sat Oct 31 01:04:05 2015
st_mtime (ultima modificação)=Sat Oct 31 01:10:16 2015
st_ctime (ultima alter. estado)=Sat Oct 31 01:10:16 2015
Listagem 4: saída produzida pela execução de metadados_dir_corrente

Acesso ao conteúdo de um diretório

Em termos de programação, o acesso ao conteúdo de um diretório – ficheiros, diretórios, atalhos, etc. – apresenta algumas semelhanças com a leitura de um ficheiro, sendo necessário efetuar a abertura do diretório antes que se possa aceder ao conteúdo e fechar o diretório quando se terminou o respetivo uso. Para o efeito existem as funções opendir (abertura) e closedir (fecho). O acesso ao conteúdo é feito através de chamadas sucessivas à função readdir que devolve uma entrada por chamada. Os protótipos das funções necessárias para iterar o conteúdo de um diretório estão indicados na Listagem 5.

No acesso ao conteúdo de um dado diretório, a primeira operação consiste na abertura do diretório através da função opendir que, caso seja bem sucedida, devolve o endereço de memória de um descritor de diretório do tipo de dados DIR.

#include <sys/types.h>
#include <dirent.h>

DIR *opendir(const char *name);
 
struct dirent *readdir(DIR *dirp);
int readdir_r(DIR *dirp, struct dirent *entry,
                           struct dirent **result);

int closedir(DIR *dirp);
Listagem 5: protótipos das funções opendir, readdir e closedir (fonte: man opendir e man readdir)

O descritor devolvido pela função opendir é empregue para iterar o conteúdo do diretório através da função readdir. Esta função deve ser chamada em ciclo, devolvendo para cada chamada uma entrada do diretório. A função readdir assinala o término da iteração através da devolução do valor NULL, indicando que já foram iteradas todas as entradas do diretório. O passo final corresponde ao encerrar do diretório, efetuando-se através da chamada à função closedir. De seguida, analisam-se separadamente cada uma das etapas para acesso aos conteúdos de um diretório: abertura, leitura e encerramento do diretório.

Publicado na edição 51 (PDF) da Revista PROGRAMAR.