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

{

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

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

Имя tx совпадает с каким-либо именем tc, которое оказывается последним в каталоге для любого одиночного символа с. Можете ли вы придумать лучшую меру расстояния? Реализуйте ее и посмотрите, насколько хорошо эта конструкция работает с реальными пользователями.

Работает ли p ощутимо быстрее, если чтение каталога выполняется большими порциями?

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

Какую пользу могли бы извлечь другие программы из spname? Сконструируйте отдельную программу, которая корректировала бы другие аргументы прежде, чем передать их другой программе, как в

$ fix prog filenames...

Можете написать версию cd, которая использует spname? Как бы вы ее встроили?

7.3 Файловая система: индексные дескрипторы

Теперь мы обсудим системные вызовы применительно к файловой системе, в частности к такой информации о файлах, как размеры, даты изменений, права доступа и т.д. Эти системные вызовы позволяют получить полностью всю информацию, о которой упоминалось во второй главе.

Для начала разберемся в самом индексном дескрипторе. Часть индексного дескриптора описывается структурой stat, определенной в <sys/stat.h>:

struct stat /* структура, возвращаемая stat */

{

 dev_t st_dev;    /* устройство, содержащее файл */

 ino_t st_ino;    /* индекс */

 short st_mod;    /* биты режима */

 short st_nlink;  /* число связей файла */

 short st_uid;    /* пользовательский идентификатор

                     владельца */

 short st_gid;    /* идентификатор группы владельцев */

 dev_t st_rdev;   /* для специальных файлов */

 off_t st_size;   /* размер файла в символах */

 time_t st_atime; /* время последнего чтения файла */

 time_t st_mtime; /* время последней записи

                     или создания файла */

 time_t st_ctime; /* время последнего изменения

                     индексного дескриптора или файла */

}

Большинство полей поясняются примечаниями. Типы вроде dev_t и ino_t определены в <sys/types.h>, как отмечено выше. Поле st_mode содержит множество флагов, описывающих файл; для удобства определения флагов также являются частью файла <sys/stat.h>:

#define S_IFMT   0170000  /* тип файла */

#define  S_IFDIR 0040000  /* каталог */

#define  S_IFCHR 0020000  /* байт-ориентированный */

#define  S_IFBLK 0060000  /* блок-ориентированный */

#define  S_IFREG 0100000  /* регулярный */

#define S_SUID   0004000  /* установка идентификатора пользователя при

                             выполнении */

#define S_ISGID  0002000  /* установка идентификатора группы

                             при выполнении */

#define S_ISVTX  0001000  /* сохранить выгруженный текст даже после

                             использования */

#define S_IREAD  0000400  /* разрешение читать, владелец */

#define S_IWRITE 0000200  /* разрешение писать, владелец */

#define S_IEXEC  0000100  /* разрешение на выполнение/поиск, владелец */

Индексный дескриптор для файла доступен двум системным вызовам stat и fstat. При вызове stat параметром является имя файла, а результатом — информация из индексного дескриптора для этого файла (или — 1 при наличии ошибки). Fstat выполняет те же функции в отношении дескриптора открытого файла (не в отношении указателя на FILE). Иными словами,

char *name;

int fd;

struct stat stbuf;

stat(name, &stbuf);

fstat(fd, &stbuf);

заполняет структуру stbuf информацией из индексного дескриптора для имени файла или дескриптора файла fd.

Зная все это, мы можем приступить к написанию некоторой полезной программы. Начнем с версии checkmail — программы на Си, которая следит за содержимым вашего почтового ящика. Если файл увеличивается, checkmail выдает сообщение: "У вас есть корреспонденция" и включает звонок. (При уменьшении файла, видимо, из-за того, что вы успели прочитать и сбросить некоторую почтовую корреспонденцию, сообщение не требуется.) Для первого шага вы сделали вполне достаточно, а когда ваша программа заработает, вы станете знатоком.