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

$ 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[];