Текст книги "Linux программирование в примерах"
Автор книги: Арнольд Роббинс
Жанры:
Программирование
,сообщить о нарушении
Текущая страница: 17 (всего у книги 55 страниц)
В разделе 5.3 «Чтение каталогов» мы продемонстрировали, как элементы каталогов возвращаются в физическом порядке каталога. В большинстве случаев гораздо полезнее иметь содержимое каталога отсортированным каким-нибудь образом, например, по имени или по времени изменения. Хотя и не стандартизованные POSIX, несколько процедур упрощают это, используя qsort() в качестве лежащего в основе сортирующего агента:
#include
int scandir(const char *dir, struct dirent ***namelist,
int (*select)(const struct dirent*),
int (*compare)(const struct dirent **, const struct dirent **));
int alphasort(const void *a, const void *b);
int versionsort(const void *a, const void *b); /* GLIBC */
Функции scandir() и alphasort() были сделаны доступными в 4.2 BSD и широко поддерживаются[68]68
Заметным исключением является лишь Sun Solaris, где эти две функции существуют лишь в трудной для использования библиотеке совместимости с BSD – Примеч. автора.
[Закрыть], versionsort() является расширением GNU.
scandir() читает каталог, имя которого дано в dir, создает с использованием malloc() массив указателей struct dirent и устанавливает *namelist, чтобы он указывал на начало этого массива. Как массив указателей, так и указываемые структуры struct dirent выделяются с помощью malloc(); вызывающий код должен использовать free(), чтобы избежать утечек памяти.
Для выбора нужных элементов используйте указатель функции select. Когда это значение равно NULL, все действительные элементы каталога включаются в конечный массив. В противном случае (*select)() вызывается для каждого элемента, и те элементы, для которых она возвращает ненулевое (истинное) значение, включаются в массив.
Указатель функции compare сравнивает два элемента каталога. Он передается функции qsort() для использования при сортировке.
alphasort() лексикографически сравнивает имена файлов. Она использует для сравнения функцию strcoll(). strcoll() похожа на strcmp(), но учитывает связанные с местной спецификой правила сортировки (см. раздел 13.4 «Не могли бы вы написать это для меня по буквам?»).
versionsort() является расширением GNU, которое использует для сравнения имен файлов функцию GNU strverscmp() (см. strverscmp(3).) Короче говоря, эта функция понимает обычные соглашения по версиям имен файлов и сравнивает их соответствующим образом.
В ch06-sortdir.c приведена программа, похожая на ch04-catdir.c. Однако, она использует для работы scandir() и alphasort().
1 /* ch06-sortdir.c – Демонстрирует scandir(), alphasort(). */
2
3 #include
4 #include
5 #include
6 #include
7
8 char *myname;
9 int process(const char *dir);
10
11 /* main – перечислить аргументы каталога */
12
13 int main(int argc, char **argv)
14 {
15 int i;
16 int errs = 0;
17
18 myname = argv[0];
19
20 if (argc == 1)
21 errs = process("."); /* по умолчанию текущий каталог */
22 else
23 for (i = 1; i < argc; i++)
24 errs += process(argv[i]);
25
26 return (errs != 0);
27 }
28
29 /* nodots – игнорирует файлы с точкой, для scandir() */
30
31 int
32 nodots(const struct dirent *dp)
33 {
34 return (dp->d_name[0] != '.');
35 }
36
37 /*
38 * process – сделать что-то с каталогом, в данном случае,
39 * вывести в стандартный вывод пары индекс/имя.
40 * Вернуть 0, если все нормально, в противном случае 1.
41 */
42
43 int
44 process(const char *dir)
45 {
46 DIR *dp;
47 struct dirent **entries;
48 int nents, i;
49
50 nents = scandir(dir, &entries, nodots, alphasort);
51 if (nents < 0) {
52 fprintf(stderr, "%s: scandir failed: %sn", myname,
53 strerror(errno));
54 return 1;
55 }
56
57 for (i = 0; i < nents; i++) {
58 printf("%81d %sn", entries[i]->d_ino, entries[i]->d_name);
59 free(entries[i]);
60 }
61
62 free(entries);
63
64 return 0;
65 }
Функция main() программы (строки 1–27) следует стандартному шаблону, который мы использовали до этого. Функция nodots() (строки 31–35) действует как параметр select, выбирая лишь имена файлов, которые не начинаются с точки.
Функция process() (строки 43–65) довольно проста, причем scandir() делает большую часть работы. Обратите внимание, как каждый элемент отдельно освобождается с помощью free() (строка 59) и как освобождается также весь массив (строка 62).
При запуске содержимое каталога в самом деле выводится в отсортированном порядке, без '.' и '..'.
$ ch06-sortdir /* Действия по умолчанию отображают текущий каталог */
2097176 00-preface.texi
2097187 01-intro.texi
2097330 02-cmdline.texi
2097339 03-memory.texi
2097183 03-memory.texi.save
2097335 04-fileio.texi
2097334 05-fileinfo.texi
2097332 06-generall.texi
...
bsearch()Линейный поиск в значительной степени похож на свое название: вы начинаете в начале и проходите искомый массив, пока не встретите то, что нужно. Для чего-нибудь простого, типа поиска целых, это обычно принимает форму цикла for. Рассмотрите эту функцию:
/* ifind – линейный поиск, возвращает найденный индекс или -1 */
int ifind(int x, const int array[], size_t nelems) {
size_t i;
for (i = 0; i < nelems; i++)
if (array(i) == x) /* найдено */
return i;
return -1;
}
Преимуществом линейного поиска является его простота; легко с самого начала написать правильный код. Более того, он работает всегда. Даже если в конец массива добавляются элементы или они удаляются из него, нет необходимости сортировать массив.
Недостатком линейного поиска является то, что он медленный. В среднем для массива, содержащего nelems элементов, при линейном поиске случайного элемента требуется 'nelems/2' сравнений, прежде чем найдется нужный элемент. Это становится чрезмерно дорогим даже на современных высокопроизводительных системах, когда nelems принимает большие значения. Поэтому линейный поиск следует использовать лишь с небольшими массивами.
В отличие от линейного, бинарный поиск требует, чтобы входной массив был уже отсортирован. Недостатком здесь является то, что если добавляются элементы, массив перед новым поиском нужно повторно отсортировать. (Когда элементы удаляются, остальное содержимое массива все равно должно быть перетасовано. Это не так дорого, как повторная сортировка, но все равно может потребовать большого перемещения данных.)
Преимуществом бинарного поиска, и значительным, является то, что бинарный поиск умопомрачительно быстр, требуя самое большее log2(N) сравнений, где N является числом элементов в массиве. Функция bsearch() объявлена следующим образом:
#include
void *bsearch(const void *key, const void *base, size_t nmemb,
size_t size, int (*compare)(const void*, const void*));
Параметры и их назначение сходны с таковыми для qsort():
const void *key
Объект, который ищется в массиве.
const void *base
Начало массива.
size_t nmemb
Число элементов в массиве.
size_t size
Размер каждого элемента, полученный с помощью sizeof.
int (*compare)(const void*, const void*)
Функция сравнения. Она должна работать таким же образом, как функция сравнения для qsort(), возвращая отрицательные/нулевые/положительные значения в соответствии с тем, меньше/равен/больше первый параметр по сравнению со вторым.
Если объект не найден, bsearch() возвращает NULL. В противном случае она возвращает указатель на найденный объект. Если key соответствует более одного объекта, какой из них будет возвращен, не определено. Поэтому, как и в случае с qsort(), убедитесь, что функция сравнения принимает во внимание все существенные части искомой структуры данных.
ch06-searchemp.c показывает bsearch() на практике, расширяя использованный ранее пример struct employee:
1 /* ch06-searchemp.с – Демонстрация bsearch(). */
2
3 #include
4 #include
5 #include
6
7 struct employee {
8 char lastname[30];
9 char firstname[30];
10 long emp_id;
11 time_t start_date;
12 };
13
14 /* emp_id_compare – сравнение по ID */
15
16 int emp_id_compare(const void *e1p, const void *e2p)
17 {
18 const struct employee *e1, *e2;
19
20 e1 = (const struct employee*)e1p;
21 e2 = (const struct employee*)e2p;
22
23 if (e1->emp_id < e2->emp_id)
24 return -1;
25 else if (e1->emp_id == e2->emp_id)
26 return 0;
27 else
28 return 1;
29 }
30
31 /* print_employee – напечатать структуру сотрудника */
32
33 void print_employee(const struct employee *emp)
34 {
35 printf("%s %st%dt%s", emp->lastname, emp->firstname,
36 emp->emp_id, ctime(&emp->start_date));
37 }
Строки 7–12 определяют struct employee; она та же, что и раньше. Строки 16–29 служат в качестве функции сравнения как для qsort(), так и для bsearch(). Они сравнивают лишь ID сотрудников. Строки 33–37 определяют print_employee(), которая является удобной функцией для печати структуры, поскольку это делается из разных мест.
39 /* main – демонстрация сортировки */
40
41 int main(int argc, char **argv)
42 {
43 #define NPRES 10
44 struct employee presidents[NPRES];
45 int i, npres;
46 char buf[BUFSIZ];
47 struct employee *the_pres;
48 struct employee key;
49 int id;
50 FILE *fp;
51
52 if (argc != 2) {
53 fprintf(stderr, "usage: %s datafilen", argv[0]);
54 exit(1);
55 }
56
57 if ((fp = fopen(argv[1], "r")) == NULL) {
58 fprintf(stderr, "%s: %s: could not open: %sn", argv[0],
59 argv[1], strerror(errno));
60 exit(1);
61 }
62
63 /* Очень простой код для чтения данных: */
64 for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, fp) != NULL;
65 npres++) {
66 sscanf(buf, "%s %s %ld %ld",
67 presidents[npres].lastname,
68 presidents[npres].firstname,
69 &presidents[npres].emp_id,
70 &presidents[npres].start_date);
71 }
72 fclose(fp);
73
74 /* В npres теперь число действительно прочитанных строк. */
75
76 /* Сначала отсортировать по id */
77 qsort(presidents, npres, sizeof(struct employee), emp_id_compare);
78
79 /* Напечатать результат */
80 printf("Sorted by ID:n");
81 for (i = 0; i < npres; i++) {
82 putchar('t');
83 print_employee(&presidents[i]);
84 }
85
86 for (;;) {
87 printf("Enter ID number: ");
88 if (fgets(buf, BUFSIZ, stdin) == NULL)
89 break;
90
91 sscanf(buf, "%dn", &id);
92 key.emp_id = id;
93 the_pres = (struct employee*)bsearch(&key, presidents,
94 npres, sizeof(struct employee), emp_id_compare);
95
96 if (the_pres != NULL) {
97 printf("Found: ");
98 print_employee(the_pres);
99 } else
100 printf("Employee with ID %d not found'n", id);
101 }
102
103 putchar('n'); /* Напечатать в конце символ новой строки. */
104
105 exit(0);
106 }
Функция main() начинается с проверки аргументов (строки 52–55). Затем она читает данные из указанного файла (строки 57–72). Стандартный ввод для данных сотрудников использоваться не может, поскольку он зарезервирован для запроса у пользователя ID искомого сотрудника.
Строки 77–84 сортируют, а затем печатают данные. Затем программа входит в цикл, начинающийся со строки 86. Она запрашивает идентификационный номер сотрудника, выходя из цикла по достижению конца файла. Для поиска в массиве мы используем struct employee с именем key. Достаточно лишь установить в его поле emp_id введенный номер ID; другие поля при сравнении не используются (строка 92).
Если найден элемент с подходящим ключом, bsearch() возвращает указатель на него. В противном случае она возвращает NULL. Возвращенное значение проверяется в строке 96, и осуществляется нужное действие. Наконец, строка 102 выводит символ конца строки, чтобы системное приглашение появилось с новой строки. Вот что появляется после компилирования и запуска программы:
$ ch06-searchemp presdata.txt /* Запуск программы */
Sorted by ID:
Carter James 39 Thu Jan 20 13:00:00 1977
Reagan Ronald 40 Tue Jan 20 13:00:00 1981
Bush George 41 Fri Jan 20 13:00:00 1989
Clinton William 42 Wed Jan 20 13:00:00 1993
Bush George 43 Sat Jan 20 13:00:00 2001
Enter ID number: 42 /* Ввод действительного номера */
Found: Clinton William 42 Wed Jan 20 13:00:00 1993 /* Найдено */
Enter ID number: 29 /* Ввод неверного номера */
Employee with ID 29 not found! /* He найдено */
Enter ID number: 40 /* Попытка другого верного номера */
Found: Reagan Ronald 40 Tue Jan 20 13:00:00 1981 /* Этот тоже найден */
Enter ID number: ^D /* CTRL-D в качестве конца файла */
$ /* Готов к приему следующей команды */
Дополнительный, более продвинутый API для поиска коллекций данных описан в разделе 14.4 «Расширенный поиск с использованием двоичных деревьев».
6.3. Имена пользователей и группХотя операционная система для сохранения владельцев файлов и проверки прав доступа работает с идентификационными номерами пользователей и групп, люди предпочитают работать с именами пользователей и групп.
Ранние системы Unix хранили информацию, сопоставляющую имена с номерами ID, в простых текстовых файлах /etc/passwd и /etc/group. На современных системах эти файлы до сих пор существуют, а их формат не изменился после V7 Unix. Однако, они больше не определяют данные полностью. Большие установленные системы с множеством сетевых хостов хранят сведения в сетевых базах данных, которые представляют собой способ хранения информации на небольшом числе серверов, доступ к которым осуществляется через сеть[69]69
Типичные сетевые базы данных включают Network Information Service (NIS) и NIS+ от Sun Microsystems, Kerberos (Hesiod), MacOS X NetInfo (версии вплоть до и включая 10.2) и LDAP, Lightweight Directory Access Protocol. Системы BSD хранят сведения в базах данных на диске и автоматически создают файлы /etc/passwd и /etc/group – Примеч. автора.
[Закрыть]. Однако, такое использование прозрачно для большинства приложений, поскольку доступ к информации осуществляется через тот самый API, который использовался для получения сведений из текстовых файлов. Именно по этой причине POSIX стандартизует лишь API; в совместимой с POSIX системе файлы /etc/passwd и /etc/group не обязательно должны существовать.
API для этих двух баз данных похожи; большая часть обсуждения фокусируется на базе данных пользователей.
Традиционный формат /etc/passwd поддерживает по одной строке на пользователя. В каждой строке есть несколько полей, каждое из которых отделено от следующего символом двоеточия:
$ grep arnold /etc/passwd
arnold:x:2076:10:Arnold D. Robbins:/home/arnold:/bin/bash
По порядку эти поля следующие:
Имя пользователя
Это то, что пользователь набирает при регистрации, что отображается с помощью 'ls -l', а также используется в любом другом контексте при отображении пользователей.
Поле пароля
На старых системах здесь хранился зашифрованный пароль пользователя. На новых системах в этом поле скорее всего стоит x (как в данном случае), это означает, что сведения о пароле находятся в другом файле. Это разделение является средством обеспечения безопасности; если непривилегированному пользователю недоступен зашифрованный пароль, его значительно сложнее «взломать».
ID пользователя
Должен быть уникальным; один номер на пользователя.
ID группы
Это номер ID начальной группы пользователя. Как обсуждается далее, на современных системах с процессами связаны несколько групп.
Настоящее имя пользователя
Это по крайней мере имя и фамилия пользователя. Некоторые системы допускают разделяемые запятыми поля для местоположения офиса, номера телефона и т.д., но это не стандартизовано.
Входной каталог
Этот каталог становится домашним каталогом для пользователей, когда они зарегистрируются в системе ($HOME – по умолчанию для команды cd).
Входная программа
Программа, которая запускается при регистрации пользователя. Обычно это оболочка, но не обязательно. Если это поле оставлено пустым, по умолчанию используется /bin/sh.
Доступ к базе данных пользователей осуществляется через процедуры, объявленные в
#include
#include
struct passwd *getpwent(void);
void setpwent(void);
void endpwent(void);
struct passwd *getpwnam(const char *name);
struct passwd *getpwuid(uid_t uid);
Поля в struct passwd, использующиеся различными процедурами API, напрямую соответствуют полям файла паролей.
struct passwd {
char *pw_name; /* имя пользователя */
char *pw_passwd; /* пароль пользователя */
uid_t pw_uid; /* id пользователя */
gid_t pw_gid; /* id группы */
char *pw_gecos; /* настоящее имя */
char *pw_dir; /* домашний каталог */
char *pw_shell; /* программа оболочки */
};
(Имя pw_gecos историческое; когда разрабатывались ранние системы Unix, это поле содержало соответствующие сведения для учетной записи пользователя на системах Bell Labs Honeywell с операционной системой GECOS.)
Назначение каждой процедуры описано в следующем списке.
struct passwd *getpwent(void)
Возвращает указатель на внутреннюю структуру static struct passwd, содержащую сведения о «текущем» пользователе. Эта процедура читает всю базу данных паролей, по одной записи за раз, возвращая указатель на структуру для каждого пользователя. Каждый раз возвращается тот же самый указатель; т.е. для каждой записи пользователя внутренняя struct passwd переписывается заново. Когда getpwent() достигает конца базы данных паролей, она возвращает NULL. Таким образом, она позволяет пройти через всю базу данных по одному пользователю за раз. Порядок, в котором возвращаются записи, не определен.
void setpwent(void)
Сбрасывает внутреннее состояние, так что следующий вызов getpwent() возвращает первую запись в базе данных паролей.
void endpwent(void)
«Закрывает базу данных», так сказать, будь то простой файл, сетевое соединение или что-нибудь еще.
struct passwd *getpwnam(const char *name)
Ищет пользователя с членом pw_name, соответствующим name, возвращая указатель на static struct passwd, описывающий пользователя, или NULL, если пользователь не найден.
struct passwd *getpwuid(uid_t uid)
Сходным образом ищет пользователя с номером ID, приведенным в uid, возвращая указатель на static struct passwd, описывающий пользователя, или NULL, если пользователь не найден.
getpwuid() – вот что нужно, когда есть номер ID пользователя (такой, как в struct stat) и вам нужно вывести имя соответствующего пользователя. getpwnam() преобразует имя в номер ID пользователя, например, если вы хотите использовать с файлом chown() или fchown(). Теоретически обе эти процедуры осуществляют линейный поиск по базе данных паролей для обнаружения нужных сведений. На практике это верно, когда используется файл паролей, однако, кулуарные базы данных (сетевые или другие, как на системах BSD) склоняются к использованию более эффективных методов хранения, так что эти вызовы, возможно, в таком случае не такие дорогие[70]70
К сожалению, если производительность является проблемой, нет стандартных способов узнать, как ваша библиотека осуществляет работу, а на самом деле способ ее работы может варьировать во время исполнения! (См. справочную страницу nsswitchconf(5) в системе GNU/Linux.) С другой стороны, назначением API помимо всего прочего является сокрытие деталей – Примеч. автора.
[Закрыть].
getpwent() полезна, когда нужно пройти через всю базу данных паролей. Например, может быть необходимо прочесть ее всю в память, отсортировать, а затем осуществить быстрый поиск с помощью bsearch(). Это очень полезно для избежания множества линейных поисков, свойственных поиску по одному элементу за раз с помощью getpwuid() или getpwnam().
ЗАМЕЧАНИЕ. Указатели, возвращаемые
getpwent(),getpwnam()иgetpwuid(), все указывают на внутренниеstaticданные. Поэтому следует сделать копию их содержимого, если нужно сохранить сведения.Хорошенько рассмотрите определение
struct passwd. Члены, представляющие символьные строки, являются указателями, они также указывают на внутренниеstaticданные, и если вы собираетесь скопировать структуру, не забудьте также скопировать и данные, на которые указывает каждый член структуры.
Формат базы данных групп /etc/group подобен формату /etc/passwd, но с меньшим числом полей.
$ grep arnold /etc/group
mail:x:12:mail,postfix,arnold
uucp:x:14:uucp,arnold
floppy:x:19:arnold
devel:x:42:miriam,arnold
arnold:x:2076:arnold
Опять-таки на одну группу отводится одна строка, с полями, разделенными двоеточием. Поля следующие.
Имя группы
Это имя группы, как оно отображается в 'ls -l' или в любом другом контексте, когда требуется имя группы.
Пароль группы
Историческое поле. Оно больше не используется.
ID группы
Как и для ID пользователя, должен быть уникальным для каждой группы.
Список пользователей
Разделенный запятыми список пользователей, являющихся членами группы.
В предыдущем примере мы видели, что пользователь arnold является членом нескольких групп. Это членство на практике отражается в том, что называют набором групп (group set). Помимо главных номеров ID пользователя и ID группы, которые есть у процессов, набор групп является набором номеров ID дополнительных групп, который имеет при себе каждый процесс. Система проверяет на соответствие с этими ID групп, ID группы файла при осуществлении проверки прав доступа. Эта тема более подробно обсуждается в разделе 11 «Разрешения и ID пользователя и группы».
API базы данных групп сходна с API для базы данных пользователей. Следующие функции определены в
#include
#include
struct group *getgrent(void);
void setgrent(void);
void endgrent(void);
struct group *getgrnam(const char *name);
struct group *getgrgid(gid_t gid);
struct group соответствует записям в /etc/group:
struct group {
char *gr_name; /* имя группы */
char *gr_passwd; /* пароль группы */
gid_t gr_gid; /* id группы */
char **gr_mem; /* члены группы */
};
Поле gr_mem требует некоторого объяснения. Хотя оно объявлено в виде указателя на указатель (char**), лучше представить его как массив строк (наподобие argv). Последний элемент в массиве устанавливается в NULL. Когда в списке нет членов, первый элемент массива равен NULL.
ch06-groupinfo.с демонстрирует, как использовать struct group и поле gr_mem. Программа принимает в командной строке имя единственного пользователя и печатает все записи групп, в которых появляется этот пользователь:
1 /* ch06-groupinfo.с – Демонстрация getgrent() и struct group */
2
3 #include
4 #include
5 #include
6
7 extern void print_group(const struct group *gr);
8
9 /* main – вывести строки групп для пользователя в argv[1] */
10
11 int
12 main(int argc, char **argv)
13 {
14 struct group *gr;
15 int i;
16
17 if (argc != 2) { /* Проверка аргументов */
18 fprintf(stderr, "usage: %s usern", argv[0]);
19 exit(1);
20 }
21
22 while ((gr = getgrent()) != NULL) /* Получить запись каждой группы: */
23 for (i = 0; gr->gr_mem[i] != NULL; i++) /* Рассмотреть каждый член */
24 if (strcmp(gr->gr_mem[i], argv[i]) == 0) /* Если пользователь найден... */
25 print_group(gr); /* Вывести запись */
26
27 endgrent();
28
29 exit(0);
30 }
Функция main() сначала проверяет ошибки (строки 17–20). Основным компонентом программы является вложенный цикл. Внешний цикл (строка 22) перечисляет все записи базы данных группы. Внутренний цикл (строка 23) перечисляет всех членов массива gr_mem. Если один из членов соответствует имени из командной строки (строка 24), для печати записи вызывается print_group() (строка 25):
32 /* print_group – печать записи группы */
33
34 void
35 print_group(const struct group *gr)
36 {
37 int i;
38
39 printf("%s:%s:%ld:gr->gr_name, gr->gr_passwd, (long)gr->gr_gid);
40
41 for (i = 0; gr->gr_mem[i] != NULL; i++) {
42 printf("%s", gr->gr_mem[i]);
43 if (gr->gr_mem[i+1) != NULL)
44 putchar(',');
45 }
46
47 putchar('n');
48 }
Функция print_group() (строки 34–48) проста, ее логика подобна логике main() для печати списка членов. Члены списка группы разделены запятыми; поэтому тело цикла до вывода запятой должно проверить, что следующий элемент в массиве не является NULL. Этот код работает правильно, даже если в группе нет членов. Однако мы знаем, что для этой программы есть члены, иначе print_group() не была бы вызвана! Вот что происходит при запуске программы:
$ ch06-groupinfo arnold
mail:x:12:mail,postfix,arnold
uucp:x:14:uucp,arnold
floppy:x:19:arnold
devel:x:42:miriam,arnold
arnold:x:2076:arnold
