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. Полный набор "системных" типов находится в <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 = '\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 */