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

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пытается исправить каждую его составную часть, в которой несовпавшая буква была опущена, оказалась лишней, просто неверна или поменялась местами с другой буквой. Это удобное средство рассчитано на того, кто печатает не очень внимательно.

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

$ 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. Полный набор "системных" типов находится в , который должен быть включен до .

Действия 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

#include

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 = '\0';

if (*old == '\0') /* exact or corrected */

return strcmp(oldname, newname) != 0;

p = guess; /* copy next component into guess */

for (; *old != '/' && *old != '\0'; old++)

if (p < guess+DIRSIZ)

*p++ = *old;

*p = '\0';

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] = '\0'; /* +1 for terminal '\0' */

if (dir[0] == '\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++ == '\0')

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

#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— диалоговая программа, но подходят и для недиалоговых программ.