Книга: UNIX — универсальная среда программирования

7.2 Файловая система: каталоги

7.2 Файловая система: каталоги

Наша следующая тема — как ориентироваться в иерархии каталогов. При этом мы будем использовать не новые системные вызовы, а лишь несколько старых в новом контексте. В качестве примера приведем функцию spname, которая пытается справиться с неверно написанными именами файлов. Функция

n = spname(name, newname);

ищет файл с именем, "достаточно близким" к name. Если такое имя найдено, оно копируется в newname. Значение n, возвращаемое spname, равно -1, если ничего достаточно близкого не найдено, 0 — при точном совпадении и 1, если была сделана коррекция.

Spname является удобным дополнением к команде p: если вы пытаетесь печатать файл, но неверно написали имя, p спросит вас, не имели ли вы в виду что-либо другое:

$ p /urs/srx/ccmd/p/spnam.с  Очень плохое имя

"/usr/src/cmd/p/spname.с"? y Предложенная коррекция принята

/* spname: возвращает верно написанное имя файла */
...

Пока мы пишем имя файла, spname пытается исправить каждую его составную часть, в которой несовпавшая буква была опущена, оказалась лишней, просто неверна или поменялась местами с другой буквой. Это удобное средство рассчитано на того, кто печатает не очень внимательно.

Прежде чем писать программу, уместно сделать короткий обзор структуры файловой системы. Каталог представляет собой файл, содержащий список имен файлов и указание, где они размещены. Место размещения определяется индексом в так называемой индексной таблице файлов. В записи индексной таблицы содержится вся информация о файле, кроме его имени. Строка каталога, таким образом, состоит из двух элементов — индекса файла и его имени. Точное описание можно найти в файле <sys/dir.h>:

$ cat /usr/include/sys/dir.h
#define DIRSIZ 14 /* максимальная длина имени файла */
struct direct /* структура строки каталога */
{
 ino_t d_ino; /* номер индексного дескриптора */
 char d_name[DIRSIZ]; /* имя файла */
};
$

"Тип" ino_t это typedef, описывающий индекс в индексной таблице. Он является коротким целым без знака (unsigned short) в версиях системы для PDP-11 и VAX и не должен включаться в программу, так как может быть иным на другой машине. Поэтому мы воспользуемся определением типа typedef. Полный набор "системных" типов находится в <sys/types.h>, который должен быть включен до <sys/dir.h>.

Действия spname достаточно прямолинейны, хотя и требуют выполнения нескольких граничных условий. Предположим, что имя файла /d1/d2/f. Основная идея состоит в следующем: отделить первую компоненту (/), найти в каталоге имя, близкое к следующей компоненте (d1), затем найти имя, близкое к d2, и т.д. до тех пор, пока не будет достигнуто полное совпадение для каждой составной части. Если на какой-то стадии в каталоге не окажется подходящего кандидата, поиск прекратится.

Мы разбили процесс на три функции. Сама spname выделяет компоненты пути и составляет из них имя файла, наилучшим образом совпадающее с исходным. Функция mindist ищет в данном каталоге файл с именем, ближайшим к составленному функцией spname. Функция spdist вычисляет "расстояние" между двумя именами.

/* spname: return correctly spelled filename */
/*
 * spname(oldname, newname) char *oldname, *newname;
 * returns -1 if no reasonable match to oldname,
 * 0 if exact match,
 *1 if corrected.
 * stores corrected name in newname.
 */
#include <sys/types.h>
#include <sys/dir.h>
spname(oldname, newname)
 char *oldname, *newname;
{
 char *p, guess[DIRSIZ+1], best[DIRSIZ+1];
 char *new = newname, *old = oldname;
 for (;;) {
  while (*old == '/') /* skip slashes */
   *new++ = *old++;
  *new = '';
  if (*old == '') /* exact or corrected */
   return strcmp(oldname, newname) != 0;
  p = guess; /* copy next component into guess */
  for (; *old != '/' && *old != ''; old++)
   if (p < guess+DIRSIZ)
    *p++ = *old;
   *p = '';
   if (mindist(newname, guess, best) >= 3)
    return -1; /* hopeless */
   for (p = best; *new = *p++; ) /* add to end */
    new++; /* of newname */
 }
}
mindist(dir, guess, best) /* search dir for guess */
 char *dir, *guess, *best;
{
 /* set best, return distance 0..3 */
 int d, nd, fd;
 struct {
  ino_t ino;
  char name[DIRSIZ+1]; /* 1 more than in dir.h */
 } nbuf;
 nbuf.name[DIRSIZ] = ''; /* +1 for terminal '' */
 if (dir[0] == '') /* current directory */
  dir = ".";
 d = 3; /* minimum distance */
 if ((fd = open(dir, 0)) == -1)
  return d;
 while (read(fd,(char *)&nbuf, sizeof(struct direct)) > 0)
  if (nbuf.ino) {
   nd = spdist(nbuf.name, guess);
   if (nd <= d && nd != 3) {
    strcpy(best, nbuf.name);
    d = nd;
    if (d == 0) /* exact match */
     break;
   }
  }
 close(fd);
 return d;

Если имя каталога, данное mindist, пустое, отыскивается '.'. Функция mindist читает одну строку каталога за один раз. Отметим, что буфер для read представляет собой структуру, а не массив символов. Мы используем sizeof, чтобы вычислить число байтов и привести адрес к символьному указателю.

Если строка каталога в данный момент не используется (поскольку файл удален), то поле индекса в ней равно нулю и она пропускается. Проверка расстояния осуществляется как

if (nd <= d...)

а не как

if (nd < d...)

поэтому любой одиночный символ дает лучшее совпадение, чем имя '.', которое всегда является первой строкой в каталоге.

/* spdist: return distance between two names */ /*
 * very rough spelling metric:
 * 0 if the strings are identical
 * 1 if two chars are transposed
 * 2 if one char wrong, added or deleted
 * 3 otherwise
 */
#define EQ(s,t) (strcmp(s,t) == 0)
spdist(s, t)
 char *s, *t;
{
 while (*s++ == *t)
  if (*t++ == '')
   return 0; /* exact match */
 if (*--s) {
  if (*t) {
   if (s[1] && t[1] && *s == t[1] && *t == s[1] && EQ(s+2, t+2))
    return 1; /* transposition */
   if (EQ(s+1, t+1))
    return 2; /* 1 char mismatch */
  }
  if (EQ(s+1, t))
   return 2; /* extra character */
 }
 if (*t && EQ(s, t+1))
  return 2; /* missing character */
 return 3;
}

Поскольку у нас есть spname, несложно вставить функции по коррекции написания в p:

/* p: print input in chunks (version 4) */
#include <stdio.h>
#define PAGESIZE 22
char *progname; /* program name for error message */
main(argc, argv)
 int argc;
 char *argv[];
{
 FILE *fp, *efopen();
 int i, pagesize = PAGESIZE;
 char *p, *getenv(), buf[BUFSIZ];
 progname = argv[0];
 if ((p=getenv("PAGESIZE")) != NULL)
  pagesize = atoi(p);
 if (argc > 1 && argv[1][0] == '-') {
  pagesize = atoi(&argv[1][1]);
  argc--;
  argv++;
 }
 if (argc == 1)
  print(stdin, pagesize);
 else
  for (i = 1; i < argc; i++)
   switch (spname(argv[i], buf)) {
   case -1: /* no match possible */
    fp = efopen(argv[i], "r");
    break;
   case 1: /* corrected */
    fprintf(stderr, ""%s"? ", buf);
    if (ttyin() == 'n')
     break;
    argv[i] = buf; /* fall through... */
   case 0: /* exact match */
    fp = efopen(argv[i], "r");
    print(fp, pagesize);
    fclose(fp);
   }
 exit(0);
}

Функции по коррекции написания не следует слепо применять к каждой программе, которая использует имена файлов. Они хорошо сочетаются с p, так как p — диалоговая программа, но подходят и для недиалоговых программ.

Оглавление книги