Формирование и выполнение командных строк

Служебная программа xargs позволяет формировать и выполнять командные строки, объединяя зафиксированный набор начальных аргументов с аргументами, прочитанными со стандартного ввода:

xargs [-E логич_конец_файла] [-I заменяемая_цепочка] [-L число] [-n число] [-p] [-s размер] [-t] [-x] [утилита [начальный_аргумент ...]]

Программа xargs объединяет зафиксированный набор заданных начальных_аргументов с аргументами, прочитанными со стандартного ввода, и выполняет указанную утилиту (по умолчанию – echo) в рамках сформированной командной строки, ожидая завершения выполнения. Данный процесс повторяется до достижения физического или логического конца файла стандартного ввода или до возвращения выполненной командной строкой кода завершения 255.

Аргументы, прочитанные со стандартного ввода, – это непрерывные цепочки символов, разделенные одним или несколькими пробелами или переводами строки; пустые строки игнорируются.

Опциям служебной программы xargs приписан следующий смысл.

-E логич_конец_файла

Цепочка символов логич_конец_файла считается признаком логического конца файла стандартного ввода.

-I заменяемая_цепочка

Режим вставки: утилита выполняется для каждой строки стандартного ввода, причем вся строка рассматривается как один аргумент и подставляется в начальные аргументы вместо каждого вхождения заменяемой цепочки. Допускается не более пяти начальных аргументов, содержащих одно или несколько подобных вхождений. Пробелы в начале вводимых строк отбрасываются. Сформированные аргументы не могут быть длиннее 255 символов. Опция -I включает опцию -x.

-L число

Выполнять утилиту для каждой группы из заданного числа непустых строк аргументов, прочитанных со стандартного ввода. Последний вызов утилиты может быть с меньшим числом строк аргументов. Считается, что строка заканчивается символом перевода строки, если только перед ним не стоит пробел; пробел в конце сигнализируют о том, что следующая непустая строка является продолжением данной.

-n число

Выполнить утилиту, используя максимально возможное количество аргументов, прочитанных со стандартного ввода, но не более заданного числа.
Будет использовано меньше аргументов, если их общая длина превышает размер, специфицированный опцией -s, или если для последнего вызова их осталось меньше, чем заданное число.

-p

Режим с приглашением: xargs перед каждым вызовом утилиты запрашивает подтверждение. Включается режим трассировки (-t), за счет чего в стандартный протокол выводится командная строка, которая должна быть выполнена, а за ней – приглашение "?...". Положительный ответ, прочитанный с устройства /dev/tty, приводит к выполнению утилиты; в противном случае данный вызов утилиты игнорируется.

-s размер

Максимальный общий размер (в символах) каждого списка аргументов установить равным заданной величине; в рамках этого ограничения со стандартного ввода берется максимально возможное число аргументов. Будет использовано меньше аргументов, если более сильными окажутся ограничения, наложенные опциями -n или -L, или если встретится конец файла.

-t

Режим трассировки: каждая сформированная командная строка перед выполнением выдается в стандартный протокол.

-x

Завершить работу служебной программы xargs, если очередная сформированная командная строка, потребившая заданное опцией -n число аргументов или заданное опцией -L число строк, оказалась длиннее, чем специфицированный опцией -s размер.

Приведем несколько примеров применения служебной программы xargs. На всякий случай подчеркнем, что никто не утверждал, что Linux или какая-либо иная операционная система соответствует стандарту POSIX-2001. Весьма вероятно, что перед исполнением примеров их придется немного подправить.

Следующая однострочная shell-процедура пересылает все файлы из каталога $1 в каталог $2 и сообщает о каждой пересылке, перед тем как ее выполнить:

ls $1 | xargs -I {} -t mv $1/{} $2/{}

Еще одна однострочная shell-процедура применяет служебную программу diff к последовательным парам своих аргументов.

echo $* | xargs -n 2 diff

Пользователя спрашивают, какие объектные файлы из текущего каталога должны быть занесены в библиотеку mylib.a.При выполнении первого конвейера (см. ниже) файлы заносятся по одному; при выполнении второго заносится сразу много файлов.

ls *.o | xargs -p -L 1 ar -r mylib.a ls *.o | xargs -p -L 1 | xargs ar -r mylib.a

Отметим, что во втором звене второго конвейера в качестве подразумеваемой утилиты будет использована служебная программа echo.

Функции для работы с базой данных учетной информации о пользователях

Мы продолжаем рассматривать функции, находящиеся на стыке пользовательских и административных средств.

Стандартом POSIX-2001 предусмотрен набор функций для работы с базой данных учетной информации о пользователях. Эти функции реализуют последовательный просмотр учетных записей (getutxent()), поиск в базе (getutxid(), getutxline()), модификацию или добавление записей (pututxline()), возврат к началу (setutxent()) и завершение работы с базой (endutxent()) (см. листинг 9.7).

#include <utmpx.h>

struct utmpx *getutxent (void);

struct utmpx *getutxid ( const struct utmpx *id);

struct utmpx *getutxline ( const struct utmpx *line);

struct utmpx *pututxline ( const struct utmpx *utmpx);

void setutxent (void);

void endutxent (void);

Листинг 9.7. Описание функций для работы с базой данных учетной информации о пользователях. (html, txt)

Центральную роль для описываемого набора функций играет структура типа utmpx, которая, согласно стандарту, должна содержать по крайней мере следующие поля.

char ut_user []; /* Входное имя пользователя */ char ut_id []; /* Неспецифицированный */ /* инициализационный идентификатор */ /* процесса (например, первое поле */ /* в строке файла inittab) */ char ut_line []; /* Имя устройства */ pid_t ut_pid; /* Идентификатор процесса */ short ut_type; /* Тип записи */ struct timeval ut_tv; /* Время создания записи */

Мы продолжаем рассматривать функции, находящиеся на стыке пользовательских и административных средств.

#include <utmpx.h>

struct utmpx *getutxent (void);

struct utmpx *getutxid ( const struct utmpx *id);

struct utmpx *getutxline ( const struct utmpx *line);

struct utmpx *pututxline ( const struct utmpx *utmpx);

void setutxent (void);

void endutxent (void);

Листинг 9.7. Описание функций для работы с базой данных учетной информации о пользователях.

В зависимости от типа записи (элемент ut_type) определяется подмножество полей, содержащих осмысленные значения. Для пустых записей (тип EMPTY) таких полей нет вообще. Для типов BOOT_TIME (идентифицирует время загрузки системы), OLD_TIME (время изменения показаний системных часов), NEW_TIME (показания системных часов после изменения) имеет смысл только время создания записи (элемент ut_tv). Записи типа USER_PROCESS идентифицируют пользовательские процессы и содержат полезную информацию в элементах ut_user (входное имя пользователя), ut_id, ut_line, ut_pid и ut_tv. Почти такое же подмножество полей имеет смысл для типа LOGIN_PROCESS (по стандарту он идентифицирует лидера сеанса вошедшего в систему пользователя): ut_user (зависящее от реализации имя входного процесса), ut_id, ut_pid, ut_tv.

Наконец, для типов INIT_PROCESS ( идентифицирует процесс, порожденный системным процессом init) и DEAD_PROCESS (по стандарту он идентифицирует лидера сеанса, завершившего выполнение) имеют смысл лишь элементы ut_id, ut_pid и ut_tv.

Разумеется, реальные размеры массивов, являющихся элементами структуры, можно узнать, применяя к ним на целевой платформе функцию sizeof().

Функция getutxent() читает очередную запись из базы данных учетной информации о пользователях. Если база данных еще не открыта, она открывается. При достижении конца базы данных выполнение функции завершается неудачей и возвращается пустой указатель. Нормальным результатом является указатель на копию прочитанной записи, размещенную в структуре типа utmpx.

Функция getutxid(), начиная с текущей позиции, разыскивает запись базы данных, в которой поле ut_type соответствует значению id->ut_type. Если элемент id->ut_type равен BOOT_TIME, OLD_TIME, или NEW_TIME, то требуется точное равенство типов. Если же id->ut_type равняется INIT_PROCESS, LOGIN_PROCESS, USER_PROCESS или DEAD_PROCESS, то функция getutxid() вернет указатель на копию первой записи, тип которой равен одному из четырех перечисленных, и поле ut_id соответствует значению id->ut_id.

Функция getutxline() аналогичным образом разыскивает запись, тип которой равен LOGIN_PROCESS или USER_PROCESS, а поле ut_line соответствует значению line->ut_line.

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

Функция pututxline() записывает указанную utmpx-структуру в базу данных (если вызывающий процесс обладает соответствующими привилегиями). При этом для поиска нужного места используется функция getutxid(), если обнаруживается, что текущая позиция не является подходящей. В случае неудачи поиска запись добавляется в конец базы данных.

Отметим, что запись базы данных, к которой было последнее обращение, может сохраняться реализацией в статической структуре (и указатель на нее возвращаться в качестве результата функций), поэтому доступ к нескольким записям требует копирования структур.

Далее, при обращении к getutxid() или getutxline() реализация имеет право сначала проанализировать упомянутую статическую структуру и, если та окажется подходящей, не производить поиск, а вернуть ее же. Следовательно, если приложению требуется найти несколько подходящих записей, то после очередного успешного поиска и копирования структуры ее необходимо очистить.

В свою очередь, согласно стандарту, приложение имеет право передать функции pututxline() указатель на статическую структуру, заполненную в результате обращения к getutxent(), getutxid() или getutxline(), предварительно изменив ее требуемым образом. Неявное чтение, осуществляемое функцией pututxline() для определения замещаемой записи, эту структуру не испортит.

Функция setutxent() устанавливает указатель текущей позиции на начало базы данных. Ее следует вызывать перед поиском каждой новой записи, если предполагается, что поиск должен проводиться во всей базе.

Функция endutxent() закрывает базу данных учетной информации о пользователях.

Приведем пример использования описанных функций (см. листинг 9.8). Прочитаем и выведем все записи базы данных учетной информации о пользователях.

Листинг 9.8. Пример применения функций для работы с базой данных учетной информации о пользователях. (html, txt)

Фрагмент возможных результатов выполнения приведенной программы на платформе ОС Linux показан на листинге 9.9. Его изучение позволяет лучше уяснить смысл элементов структуры utmpx для разных типов записей и, попутно, увидеть некоторые нестандартности в поведении ОС Linux.

Листинг 9.9. Фрагмент возможных результатов выполнения программы, применяющей функции для работы с базой данных учетной информации о пользователях. (html, txt)

Отметим, что нестандартный тип записи 1 соответствует смене уровня выполнения.

Обратим также внимание на то, что в шаблоне поиска, производимого с помощью функции getutxid(), значение поля ut_type задано как INIT_PROCESS, а в результате поиска оно оказалось равным USER_PROCESS (в полном соответствии со стандартом).

Наконец, для типов INIT_PROCESS ( идентифицирует процесс, порожденный системным процессом init) и DEAD_PROCESS (по стандарту он идентифицирует лидера сеанса, завершившего выполнение) имеют смысл лишь элементы ut_id, ut_pid и ut_tv.

Разумеется, реальные размеры массивов, являющихся элементами структуры, можно узнать, применяя к ним на целевой платформе функцию sizeof().

Функция getutxent() читает очередную запись из базы данных учетной информации о пользователях. Если база данных еще не открыта, она открывается. При достижении конца базы данных выполнение функции завершается неудачей и возвращается пустой указатель. Нормальным результатом является указатель на копию прочитанной записи, размещенную в структуре типа utmpx.

Функция getutxid(), начиная с текущей позиции, разыскивает запись базы данных, в которой поле ut_type соответствует значению id->ut_type. Если элемент id->ut_type равен BOOT_TIME, OLD_TIME, или NEW_TIME, то требуется точное равенство типов. Если же id->ut_type равняется INIT_PROCESS, LOGIN_PROCESS, USER_PROCESS или DEAD_PROCESS, то функция getutxid() вернет указатель на копию первой записи, тип которой равен одному из четырех перечисленных, и поле ut_id соответствует значению id->ut_id.

Функция getutxline() аналогичным образом разыскивает запись, тип которой равен LOGIN_PROCESS или USER_PROCESS, а поле ut_line соответствует значению line->ut_line.

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

Функция pututxline() записывает указанную utmpx-структуру в базу данных (если вызывающий процесс обладает соответствующими привилегиями). При этом для поиска нужного места используется функция getutxid(), если обнаруживается, что текущая позиция не является подходящей. В случае неудачи поиска запись добавляется в конец базы данных.

Отметим, что запись базы данных, к которой было последнее обращение, может сохраняться реализацией в статической структуре (и указатель на нее возвращаться в качестве результата функций), поэтому доступ к нескольким записям требует копирования структур.

Далее, при обращении к getutxid() или getutxline() реализация имеет право сначала проанализировать упомянутую статическую структуру и, если та окажется подходящей, не производить поиск, а вернуть ее же. Следовательно, если приложению требуется найти несколько подходящих записей, то после очередного успешного поиска и копирования структуры ее необходимо очистить.

В свою очередь, согласно стандарту, приложение имеет право передать функции pututxline() указатель на статическую структуру, заполненную в результате обращения к getutxent(), getutxid() или getutxline(), предварительно изменив ее требуемым образом. Неявное чтение, осуществляемое функцией pututxline() для определения замещаемой записи, эту структуру не испортит.

Функция setutxent() устанавливает указатель текущей позиции на начало базы данных. Ее следует вызывать перед поиском каждой новой записи, если предполагается, что поиск должен проводиться во всей базе.

Функция endutxent() закрывает базу данных учетной информации о пользователях.

Приведем пример использования описанных функций (см. листинг 9.8). Прочитаем и выведем все записи базы данных учетной информации о пользователях.

/* * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Пример использования функций для работы */ /* с базой данных учетной информации о пользователях */ /* * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h> #include <limits.h> #include <time.h> #include <utmpx.h> #include <string.h>

int main (void) { struct utmpx *utmpx_ptr; /* Указатель на текущую запись */ char dtbuf [LINE_MAX]; /* Буфер для данных о времени */ struct utmpx spat; /* Шаблон для поиска в базе */

/* Прочитаем и распечатаем все записи в базе */ printf ("Содержимое базы данных учетной информации " "о пользователях\n"); while ((utmpx_ptr = getutxent ()) != NULL) { (void) strftime (dtbuf, sizeof (dtbuf), "%c", localtime (&(utmpx_ptr->ut_tv.tv_sec))); switch (utmpx_ptr->ut_type) { case EMPTY: printf ("Пустая запись\n"); break; case BOOT_TIME: printf ("Время загрузки системы: %s\n", dtbuf); break; case OLD_TIME: printf ("Время изменения показаний системных " "часов: %s\n", dtbuf); break; case NEW_TIME: printf ("Показания системных часов после " "изменения: %s\n", dtbuf); break; case USER_PROCESS: printf ("Процесс пользователя: %s, идентификатор: " "%d,\n", utmpx_ptr->ut_user, utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Имя устройства: %s,\n", utmpx_ptr->ut_line); printf ("Время создания записи: %s\n", dtbuf); break; case LOGIN_PROCESS: printf ("Входной процесс: %s, идентификатор: %d,\n", utmpx_ptr->ut_user, utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Время создания записи: %s\n", dtbuf); break; case INIT_PROCESS: printf ("Процесс, порожденный системным процессом " "init:\n"); printf ("Идентификатор: %d,\n", utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Время создания записи: %s\n", dtbuf); break; case DEAD_PROCESS: printf ("Лидер сеанса, завершивший выполнение:\n"); printf ("Идентификатор: %d,\n", utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Время создания записи: %s\n", dtbuf); break; default: printf ("Нестандартный тип записи: %x\n", utmpx_ptr->ut_type); break; } }

/* Найдем и распечатаем записи, */ /* инициализационный идентификатор которых */ /* равняется S4 */ spat.ut_type = INIT_PROCESS; (void) strncpy (spat.ut_id, "S4", sizeof (spat.ut_id));

/* Позиционируемся на начало базы */ setutxent ();

printf ("Записи, инициализационный идентификатор " "которых равняется S4:\n"); while ((utmpx_ptr = getutxid (&spat)) != NULL) { switch (utmpx_ptr->ut_type) { case USER_PROCESS: printf ("Процесс пользователя: %s, " "идентификатор: %d\n", utmpx_ptr->ut_user, utmpx_ptr->ut_pid); break; case LOGIN_PROCESS: printf ("Входной процесс: %s, идентификатор: " "%d\n",utmpx_ptr->ut_user, utmpx_ptr->ut_pid); break; case INIT_PROCESS: printf ("Процесс, порожденный системным процессом " "init:\n"); printf ("Идентификатор: %d\n", utmpx_ptr->ut_pid); break; case DEAD_PROCESS: printf ("Лидер сеанса, завершивший " "выполнение:\n"); printf ("Идентификатор: %d\n", utmpx_ptr->ut_pid); break; default: printf ("Нестандартный тип результата поиска: " "%x\n", utmpx_ptr->ut_type); break; }

/* Обеспечим сдвиг поиска с текущей записи */ utmpx_ptr->ut_id [0] = 0; }

endutxent ();

return 0; }

Листинг 9.8. Пример применения функций для работы с базой данных учетной информации о пользователях.

Фрагмент возможных результатов выполнения приведенной программы на платформе ОС Linux показан на листинге 9.9. Его изучение позволяет лучше уяснить смысл элементов структуры utmpx для разных типов записей и, попутно, увидеть некоторые нестандартности в поведении ОС Linux.

Содержимое базы данных учетной информации о пользователях Лидер сеанса, завершивший выполнение: Идентификатор: 17, Инициализационный идентификатор процесса: si, Время создания записи: Tue Apr 27 10:08:42 2004 Время загрузки системы: Tue Apr 27 10:08:42 2004 Нестандартный тип записи: 1 Лидер сеанса, завершивший выполнение: Идентификатор: 284, Инициализационный идентификатор процесса: l5, Время создания записи: Tue Apr 27 10:09:15 2004 Лидер сеанса, завершивший выполнение: Идентификатор: 1115, Инициализационный идентификатор процесса: ud, Время создания записи: Tue Apr 27 10:09:15 2004 . . .

Входной процесс: LOGIN, идентификатор: 1123, Инициализационный идентификатор процесса: S3, Время создания записи: Tue Apr 27 10:09:15 2004 Процесс пользователя: galat, идентификатор: 1124, Инициализационный идентификатор процесса: S4, Имя устройства: ttyS4, Время создания записи: Tue Apr 27 12:52:51 2004 Процесс пользователя: sambor, идентификатор: 1125, Инициализационный идентификатор процесса: S5, Имя устройства: ttyS5, Время создания записи: Tue Apr 27 13:57:31 2004 Процесс пользователя: kost, идентификатор: 1126, Инициализационный идентификатор процесса: S6, Имя устройства: ttyS6, Время создания записи: Tue Apr 27 10:09:30 2004 . . . Процесс, порожденный системным процессом init: Идентификатор: 1128, Инициализационный идентификатор процесса: x, Время создания записи: Tue Apr 27 10:09:15 2004 . . . Лидер сеанса, завершивший выполнение: Идентификатор: 11708, Инициализационный идентификатор процесса: /1, Время создания записи: Tue Apr 27 11:19:33 2004 . . . Записи, инициализационный идентификатор которых равняется S4: Процесс пользователя: galat, идентификатор: 1124

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

Отметим, что нестандартный тип записи 1 соответствует смене уровня выполнения.

Обратим также внимание на то, что в шаблоне поиска, производимого с помощью функции getutxid(), значение поля ut_type задано как INIT_PROCESS, а в результате поиска оно оказалось равным USER_PROCESS (в полном соответствии со стандартом).

Функции для работы с простыми базами данных

Описываемые ниже функции полезны для реализации "игрушечных" баз данных при изготовлении прототипов приложений. Нет и речи о поддержке многопользовательского режима. Ключ в записи может быть только один. Суммарная длина ключа и данных (точнее, всех ключей, имеющих один хэш-код, и ассоциированных с ними данных) не должна превышать 1023 байта и т.д. и т.п.

Набор стандартизованных функций "традиционно минимален" (см. листинг 9.10). Базу данных можно открыть (dbm_open()) и закрыть (dbm_close()), выбрать (dbm_fetch()), сохранить (dbm_store()) и удалить (dbm_delete()) запись по ключу, перебрать имеющиеся в базе ключи (dbm_firstkey(), dbm_nextkey()), опросить статус ошибки (dbm_error()) и очистить его (dbm_clearerr()).

#include <ndbm.h>

DBM *dbm_open (const char *file, int open_flags, mode_t file_mode);

void dbm_close (DBM *db);

datum dbm_fetch (DBM *db, datum key);

int dbm_store (DBM *db, datum key, datum content, int store_mode);

int dbm_delete (DBM *db, datum key);

datum dbm_firstkey (DBM *db);

datum dbm_nextkey (DBM *db);

int dbm_error (DBM *db);

int dbm_clearerr (DBM *db);

Листинг 9.10. Описание функций для работы с простыми базами данных. (html, txt)

Функцию dbm_open() можно считать аналогом open(), только в роли возвращаемого в качестве результата дескриптора базы данных выступает указатель на объект типа DBM (структура последнего скрыта от приложения), база хранится в двух файлах – file.dir и file.pag, ее нельзя открыть только на запись, а применение флага O_APPEND ведет к неспецифицированным последствиям. В случае ошибки результат вызова dbm_open() равняется (DBM *) NULL.

При работе с ключами и данными центральную роль играет структура типа datum, которая по стандарту должна содержать по крайней мере два поля.

void *dptr; /* Указатель на прикладные данные */ size_t dsize; /* Размер прикладных данных */

Функция dbm_fetch() служит для выборки записи по ключу key. Если таковая отсутствует или обнаруживается ошибка, то в возвращаемом объекте типа datum элемент dptr равняется пустому указателю.

Функция dbm_store() позволяет поместить данные, заданные аргументом content, в базу. Аргумент store_mode определяет способ сохранения новых данных. Если в базе уже есть запись с заданным ключом key, то в режиме DBM_REPLACE новая запись замещает старую, а в режиме DBM_INSERT она (новая запись) игнорируется (и результат вызова равняется единице). Если записи с ключом key в базе нет, новая запись добавляется к базе.

Функция dbm_delete() предназначена для удаления данных и ключа key.

Нормальным результатом функций dbm_store() и dbm_delete() является нуль; в случае ошибки возвращается отрицательное значение.

Функция dbm_nextkey() является итератором по ключам, хранящимся в базе, а dbm_firstkey() инициализирует этот итератор, возвращая первый ключ. При завершении перебора и при наличии ошибок возвращается объект типа datum с пустым указателем в качестве значения элемента dptr. Если по ходу итераций содержимое базы менялось (вызывались функции dbm_store() и/или dbm_delete()), перебор ключей нужно начинать заново.

Функция dbm_error() возвращает ненулевое значение при установленном статусе ошибки, функция dbm_clearerr() делает статус "безошибочным". Таким образом, вся диагностика по сути сводится к одному биту, интерпретировать который должно приложение.

Несмотря на "игрушечность" описанного интерфейса, он находит определенное применение на Unix-системах. В качестве примера рассмотрим программу, которая распечатывает содержимое базы данных aliases, расположенной в каталоге /etc/mail на SPARC-станции (см. листинг 9.11).

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа перебирает все ключи в базе данных */ /* и выдает ассоциированную с ними информацию. */ /* Предполагается, что ключи и данные – текстовые*/ /* * * * * * * * * * * * * * * * * * * * * * * * */

#include <ndbm.h> #include <stdio.h> #include <fcntl.h>

int main (int argc, char *argv []) { DBM *dbdes; /* Дескриптор открытой базы */ datum ckey; /* Текущий ключ */ datum cdat; /* Текущие данные */ int nkeys = 0; /* Число ключей */

if (argc != 2) { fprintf (stderr, "Использование: %s имя_базы\n", argv [0]); return (1); }

if ((dbdes = dbm_open (argv [1], O_RDONLY, 0777)) == (DBM *) NULL) { fprintf (stderr, " Не удалось открыть базу данных %s\n", argv [1]); return (2); }

for (ckey = dbm_firstkey (dbdes); ckey.dptr != NULL; ckey = dbm_nextkey (dbdes)) { nkeys++; printf ("Длина ключа номер %d: %d\n", nkeys, ckey.dsize); printf ("Ключ номер %d: %s\n", nkeys, ckey.dptr);

if (cdat = dbm_fetch (dbdes, ckey), cdat.dptr != NULL) { printf ("Длина данных для ключа номер %d: %d\n", nkeys, cdat.dsize); printf ("Данные для ключа номер %d: %s\n", nkeys, cdat.dptr); } else { fprintf (stderr, "Отсутствуют данные для " "ключа номер %d\n", nkeys); } }

printf ("Число ключей в базе: %d\n", nkeys);

dbm_close (dbdes);

return 0; }

Листинг 9.11. Пример применения функций для работы с простыми базами данных.

Результаты работы этой программы могут выглядеть так, как показано на листинге 9.12.

Длина ключа номер 1: 16 Ключ номер 1: YP_LAST_MODIFIED Длина данных для ключа номер 1: 10 Данные для ключа номер 1: 0898782331 Длина ключа номер 2: 14 Ключ номер 2: mailer-daemon Длина данных для ключа номер 2: 11 Данные для ключа номер 2: postmaster Длина ключа номер 3: 14 Ключ номер 3: YP_MASTER_NAME Длина данных для ключа номер 3: 3 Данные для ключа номер 3: t41 Длина ключа номер 4: 11 Ключ номер 4: postmaster Длина данных для ключа номер 4: 5 Данные для ключа номер 4: root Длина ключа номер 5: 7 Ключ номер 5: nobody Длина данных для ключа номер 5: 10 Данные для ключа номер 5: /dev/null Длина ключа номер 6: 2 Ключ номер 6: @ Длина данных для ключа номер 6: 2 Данные для ключа номер 6: @ Число ключей в базе: 6

Листинг 9.12. Возможные результаты выполнения программы, применяющей функции для работы с простыми базами данных.

Функции для работы с псевдотерминалами

В курсе [1] мы уже останавливались на понятии псевдотерминала. Опишем теперь соответствующие функции.

Первым действием при работе с псевдотерминалами является открытие главного устройства, осуществляемое функцией posix_openpt() (см. листинг 9.49).

#include <stdlib.h> #include <fcntl.h> int posix_openpt (int oflag);

Листинг 9.49. Описание функции открытия главного устройства псевдотерминала. (html, txt)

В значении аргумента oflag есть смысл устанавливать флаги O_RDWR и O_NOCTTY (последний означает, что терминал не будет управляющим для процесса).

Разумеется, нормальным результатом функции posix_openpt()> служит файловый дескриптор; в случае ошибки возвращается -1.

Считается, что после открытия главного устройства подчиненное устройство псевдотерминала блокируется, и эту блокировку необходимо явным образом снять, вызвав функцию unlockpt() (см. листинг 9.50).

#include <stdlib.h> int unlockpt (int masterfd);

Листинг 9.50. Описание функции разблокирования подчиненного устройства псевдотерминала. (html, txt)

Здесь masterfd – файловый дескриптор главного устройства псевдотерминала, полученный в результате вызова функции posix_openpt().

Нормальным для unlockpt() является нулевой результат.

Функция grantpt() (см. листинг 9.51) позволяет сформировать нужные права доступа к подчиненному устройству псевдотерминала. Владелец устройства устанавливается в соответствии с реальным идентификатором пользователя вызывающего процесса; ему (владельцу) предоставляются права на чтение и запись.

#include <stdlib.h> int grantpt (int masterfd);

Листинг 9.51. Описание функции формирования прав доступа к подчиненному устройству псевдотерминала. (html, txt)

Применительно к функции grantpt() в стандарте POSIX-2001 оговаривается одна тонкость: вызывающий процесс не должен обрабатывать сигнал SIGCHLD. Это можно понять (и оправдать), поскольку grantpt() выполняет суперпользовательское действие, реализация которого в некоторых ОС может быть сопряжена с порождением процессов.

Чтобы узнать имя подчиненного устройства псевдотерминала, следует обратиться к функции ptsname() (см. листинг 9.52).

#include <stdlib.h> char *ptsname (int masterfd);

Листинг 9.52. Описание функции получения имени подчиненного устройства псевдотерминала. (html, txt)

Разумеется, результирующий указатель может ссылаться на статическую область, перезаписываемую при каждом вызове ptsname(), поэтому рекомендуется полученное имя скопировать или поскорее использовать. Использование очевидно – посредством обычной функции open() открыть подчиненное устройство псевдотерминала и получить его файловый дескриптор.

Таким образом, в стандарте POSIX-2001 выстроена пятиэтапная модель получения доступа к псевдотерминалу:

открытие главного устройства псевдотерминала, получение его файлового дескриптора (осуществляется функцией posix_openpt());разблокирование подчиненного устройства псевдотерминала (функция unlockpt());формирование прав доступа к подчиненному устройству псевдотерминала (grantpt());получение имени подчиненного устройства псевдотерминала (ptsname());открытие подчиненного устройства псевдотерминала, получение его файлового дескриптора (open()).

Применение описанных функций иллюстрируется переработанным вариантом программы из курса [1], запускающей командный интерпретатор на псевдотерминале (см. листинг 9.53).

Листинг 9.53. Пример программы, использующей псевдотерминалы. (html, txt)

Здесь все пять упоминавшихся подготовительных этапов вошли в состав одного условного оператора. Обратим внимание на применение флага O_NOCTTY при вызове posix_openpt(), а также на то, что обращение к grantpt() выполнено до установки функции обработки сигнала SIGCHLD.

Функции и утилиты для работы с системным журналом

Под системным журналом в стандарте POSIX-2001 понимается некое средство хранения и/или отображения данных, предназначенных для изучения системным администратором. Средство это, разумеется, зависит от реализации. Это может быть обычный локальный файл (например, /var/log/messages), список рассылки, удаленный сетевой ресурс и т.д.

Для работы с системным журналом стандарт предлагает функции записи сообщений (syslog()), установки фильтра (маски журналируемых сообщений, setlogmask()) и других параметров журналирования (openlog()) и, наконец, завершения работы с системным журналом (closelog()) (см. листинг 9.1). Средства чтения системного журнала, как и все, что связано с администрированием, в стандарт POSIX-2001 не входят.

#include <syslog.h>

void syslog (int priority, const char *message, ... /* аргументы */);

int setlogmask (int maskpri); void openlog (const char *ident, int logopt, int facility);

void closelog (void);

Листинг 9.1. Описание функций для работы с системным журналом. (html, txt)

Сообщение, которое помещает в системный журнал функция syslog(), включает заголовок и тело.

В заголовок входит по крайней мере временной штамп и идентифицирующая цепочка символов.

Тело сообщения формируется из аргумента message, играющего роль формата, и следующих за ним необязательных аргументов аналогично тому, как если бы использовалась функция printf(), только допускается один дополнительный спецификатор преобразования – %m, не требующий аргумента и осуществляющий вывод текущего значения переменной errno.

Значение аргумента priority формируется как побитное ИЛИ флагов двух видов, задающих, соответственно, уровень серьезности и источник сообщения.

Уровень серьезности может принимать следующие значения.

LOG_EMERG

Катастрофическая ситуация.

LOG_ALERT

Ситуация, требующая немедленного вмешательства (например, повреждение системной базы данных).

LOG_CRIT

Опасная ситуация (например, ошибки в работе аппаратуры).

LOG_ERR

Сообщение об ошибке.

LOG_WARNING

Предупреждающее сообщение.

#include <syslog.h>

void syslog (int priority, const char *message, ... /* аргументы */);

int setlogmask (int maskpri); void openlog (const char *ident, int logopt, int facility);

void closelog (void);

Листинг 9.1. Описание функций для работы с системным журналом.

Сообщение, которое помещает в системный журнал функция syslog(), включает заголовок и тело.

В заголовок входит по крайней мере временной штамп и идентифицирующая цепочка символов.

Уровень серьезности может принимать следующие значения.

LOG_EMERG

Катастрофическая ситуация.

LOG_ALERT

Ситуация, требующая немедленного вмешательства (например, повреждение системной базы данных).

LOG_CRIT

Опасная ситуация (например, ошибки в работе аппаратуры).

LOG_ERR

Сообщение об ошибке.

LOG_WARNING

Предупреждающее сообщение.

LOG_NOTICE

Ситуация, не являющаяся ошибочной, но, возможно, требующая специальных действий.

LOG_INFO

Информационное сообщение.

LOG_DEBUG

Отладочное сообщение.

Из источников сообщений стандартизован только один (естественно, являющийся подразумеваемым) – пользовательский процесс (флаг LOG_USER). Зарезервированы флаги для системных источников, имена которых говорят сами за себя (LOG_KERN, LOG_MAIL, LOG_NEWS, LOG_UUCP, LOG_DAEMON, LOG_AUTH, LOG_CRON, LOG_LPR) и для абстрактных локальных сущностей (LOG_LOCAL0 – LOG_LOCAL7).

Функция setlogmask() в качестве результата возвращает предыдущую и устанавливает новую маску журналируемых сообщений вызывающего процесса. В системный журнал будут помещаться только те сообщения, уровень серьезности которых присутствует в маске, заданной аргументом maskpri. Для формирования этого аргумента по одному уровню серьезности стандартом предусмотрен макрос LOG_MASK (pri). Для задания маски, включающей несколько уровней, нужно взять побитное ИЛИ подобных выражений.

Если значение maskpri равно нулю, текущая маска остается неизменной. Подразумевая маска является "полной", она специфицирует журналирование всех событий.

Функция openlog() устанавливает значения атрибутов журналирования вызывающего процесса, влияющие на последующие обращения к syslog(). Аргумент ident задает идентифицирующую цепочку, фигурирующую в заголовках всех сообщений. Аргумент logopt специфицирует опции журналирования. Он формируется как побитное ИЛИ следующих флагов.

LOG_PID

Записывать вместе с сообщением идентификатор процесса.

LOG_CONS

Выдавать сообщение на системную консоль, если его не удается поместить в журнал.

LOG_NDELAY

Немедленно открыть системный журнал (обычно открытие откладывается до записи первого сообщения).

LOG_ODELAY

Отложить открытие системного журнала до первого вызова syslog() (выбор между немедленным или отложенным открытием способен повлиять на распределение файловых дескрипторов).

LOG_NOWAIT

Не ждать завершения процессов, которые могли быть порождены в ходе журналирования сообщения.

Эту опцию следует использовать в процессах, которые уведомляются о завершении потомков сигналом SIGCHLD.

Аргумент facility устанавливает подразумеваемое значение для источника тех сообщений, где он (источник) не указан явным образом.

Функции openlog() и syslog() могут открывать (расходовать) файловые дескрипторы. Функция closelog() закроет их.

Вообще говоря, вызывать openlog() до syslog() и setlogmask() не обязательно.

К рассматриваемой прикладной области можно отнести служебную программу logger:

logger цепочка_символов ...

которая неким неспецифицированным образом сохраняет сообщение, содержащее заданные аргументы – цепочки символов. Предполагается, что со временем это сообщение прочитает системный администратор.

Подобная возможность полезна для выдачи диагностических сообщений неинтерактивными приложениями. Например, программа, запущенная в пакетном режиме, может уведомить системного администратора об отсутствии какого-либо файла:

logger $LOGNAME $(date) : не удалось прочитать файл report.txt

Рассмотрим пример применения функций для работы с системным журналом (см. листинг 9.2).

Листинг 9.2. Пример применения функций для работы с системным журналом. (html, txt)

Результатом работы этой программы может быть строка, показанная на листинге 9.3.

Подразумеваемая маска журналирования: ff

Листинг 9.3. Возможные результаты применения функций для работы с системным журналом. (html, txt)

LOG_NOTICE

Ситуация, не являющаяся ошибочной, но, возможно, требующая специальных действий.

LOG_INFO

Информационное сообщение.

LOG_DEBUG

Отладочное сообщение.

Из источников сообщений стандартизован только один (естественно, являющийся подразумеваемым) – пользовательский процесс (флаг LOG_USER). Зарезервированы флаги для системных источников, имена которых говорят сами за себя (LOG_KERN, LOG_MAIL, LOG_NEWS, LOG_UUCP, LOG_DAEMON, LOG_AUTH, LOG_CRON, LOG_LPR) и для абстрактных локальных сущностей (LOG_LOCAL0 – LOG_LOCAL7).

Функция setlogmask() в качестве результата возвращает предыдущую и устанавливает новую маску журналируемых сообщений вызывающего процесса. В системный журнал будут помещаться только те сообщения, уровень серьезности которых присутствует в маске, заданной аргументом maskpri. Для формирования этого аргумента по одному уровню серьезности стандартом предусмотрен макрос LOG_MASK (pri). Для задания маски, включающей несколько уровней, нужно взять побитное ИЛИ подобных выражений.

Если значение maskpri равно нулю, текущая маска остается неизменной. Подразумевая маска является "полной", она специфицирует журналирование всех событий.

Функция openlog() устанавливает значения атрибутов журналирования вызывающего процесса, влияющие на последующие обращения к syslog(). Аргумент ident задает идентифицирующую цепочку, фигурирующую в заголовках всех сообщений. Аргумент logopt специфицирует опции журналирования. Он формируется как побитное ИЛИ следующих флагов.

LOG_PID

Записывать вместе с сообщением идентификатор процесса.

LOG_CONS

Выдавать сообщение на системную консоль, если его не удается поместить в журнал.

LOG_NDELAY

Немедленно открыть системный журнал (обычно открытие откладывается до записи первого сообщения).

LOG_ODELAY

Отложить открытие системного журнала до первого вызова syslog() (выбор между немедленным или отложенным открытием способен повлиять на распределение файловых дескрипторов).

LOG_NOWAIT

Не ждать завершения процессов, которые могли быть порождены в ходе журналирования сообщения.

Эту опцию следует использовать в процессах, которые уведомляются о завершении потомков сигналом SIGCHLD.

Аргумент facility устанавливает подразумеваемое значение для источника тех сообщений, где он (источник) не указан явным образом.

Функции openlog() и syslog() могут открывать (расходовать) файловые дескрипторы. Функция closelog() закроет их.

Вообще говоря, вызывать openlog() до syslog() и setlogmask() не обязательно.

К рассматриваемой прикладной области можно отнести служебную программу logger:

logger цепочка_символов ...

которая неким неспецифицированным образом сохраняет сообщение, содержащее заданные аргументы – цепочки символов. Предполагается, что со временем это сообщение прочитает системный администратор.

Подобная возможность полезна для выдачи диагностических сообщений неинтерактивными приложениями. Например, программа, запущенная в пакетном режиме, может уведомить системного администратора об отсутствии какого-либо файла:

logger $LOGNAME $(date) : не удалось прочитать файл report.txt

Рассмотрим пример применения функций для работы с системным журналом (см. листинг 9.2).

/* * * * * * * * * * * * * * * * * */ /* Пример использования функций */ /* для работы с системным журналом */ /* * * * * * * * * * * * * * * * * */

#include <stdio.h> #include <syslog.h>

int main (void) { int logmask; /* Прежняя маска журналирования */ /* Будем включать в журналируемые сообщения */ /* идентификатор процесса и выдавать их при */ /* возникновении проблем на системную консоль */ openlog ("Intuit syslog test", LOG_PID | LOG_CONS, LOG_USER);

/* Пренебрежем предупреждениями и менее серьезными сообщениями */ logmask = setlogmask (LOG_MASK (LOG_EMERG) | LOG_MASK (LOG_ALERT) | LOG_MASK (LOG_CRIT) | LOG_MASK (LOG_ERR));

printf ("Подразумеваемая маска журналирования: %x\n", logmask);

/* Поместим сообщение в журнал */ syslog (LOG_ALERT | LOG_USER, "Как читать системный журнал?");

/* Восстановим прежнюю маску журналирования */ (void) setlogmask (logmask);

closelog ();

return 0; }

Листинг 9.2. Пример применения функций для работы с системным журналом.

Результатом работы этой программы может быть строка, показанная на листинге 9.3.

Подразумеваемая маска журналирования: ff

Листинг 9.3. Возможные результаты применения функций для работы с системным журналом.

Привлечь внимание системного администратора к возникшим проблемам можно не только помещая сообщения в системный журнал, но и выдавая их в стандартный протокол и/или на системную консоль. Для этого служит функция fmtmsg() (см. листинг 9.4).

#include <fmtmsg.h> int fmtmsg (long classification, const char *label, int severity, const char *text, const char *action, const char *tag);

Листинг 9.4. Описание функции fmtmsg().

Функция fmtmsg() конструирует отформатированное сообщение, включая в него все аргументы, кроме первого.

Аргумент classification определяет источник и способ отображения сообщения. Он формируется как сумма констант, по одной из каждого класса. Классификация верхнего уровня определяет источник проблемы. В этот класс входят константы MM_HARD (аппаратура), MM_SOFT (программное обеспечение), MM_FIRM (программно-аппаратные средства). Сообщения, порожденные программным обеспечением, могут дополнительно классифицироваться константами MM_APPL (приложение), MM_UTIL (служебная программа), MM_OPSYS (операционная система). Проблемы классифицируются также по признаку нейтрализуемости – соответственно, MM_RECOVER и MM_NRECOV.

Если сообщение предполагается направить в стандартный протокол, к значению аргумента classification следует прибавить константу MM_PRINT; вывод на системную консоль задает константа MM_CONSOLE. Возможно одновременное указание обеих констант.

Константа MM_NULLMC означает отсутствие классификационного компонента (естественно, ее значение равно нулю).

Аргумент label специфицирует первый из пяти компонентов выдаваемого сообщения. Он, как и classification, определяет источник сообщения, но делает это по-своему. Указуемая цепочка символов должна состоять из двух полей, разделенных двоеточием.

Первое поле состоит не более чем из десяти байт, второе – из четырнадцати.

Аргумент severity характеризует серьезность проблемы. Стандартом POSIX-2001 предусмотрены следующие уровни серьезности.

MM_HALT

В приложении встретилась серьезная ошибка, его работа остановлена. В выводимую цепочку вставляется текст "HALT".

MM_ERROR

В работе приложения обнаружена ошибка. В выводимую цепочку вставляется текст "ERROR".

MM_WARNING

При работе приложения возникла необычная ситуация, возможно, являющаяся ошибочной и требующая внимания. В выводимую цепочку вставляется текст "WARNING".

MM_INFO

Информация о ситуации, не являющейся ошибочной. В выводимую цепочку вставляется текст "INFO".

MM_NOSEV

Данная константа обозначает отсутствие у сообщения уровня серьезности.

Аргумент text в свободной форме описывает ситуацию, приведшую к генерации сообщения.

Аргумент action также в свободной форме описывает первый шаг по нейтрализации ошибки. Перед цепочкой, на которую указывает action, в сообщение вставляется префикс "TO FIX:".

Аргумент tag служит ссылкой на документацию по выявленной проблеме.

На работу функции fmtmsg() влияет переменная окружения MSGVERB, которая определяет, какие из пяти возможных компонентов сообщения будут выданы в стандартный протокол (на консоль всегда выдается полное сообщение). Значение этой переменной в общем случае состоит из пяти ключевых слов – label, severity, text, action, tag – разделенных двоеточиями. Если какие-то ключевые слова отсутствуют, соответствующие компоненты сообщения в стандартный протокол выданы не будут. Если переменная MSGVERB отсутствует в окружении, имеет пустое или некорректное значение, сообщение выдается целиком.

Возможные результаты функции fmtmsg() устроены необычным образом. Константа MM_OK обозначает полный успех, MM_NOTOK – полную неудачу, MM_NOMSG – невозможность выдать сообщение в стандартный протокол, MM_NOCON – невозможность вывода на консоль.

Приведем не очень серьезный пример применения функции fmtmsg() (см.

листинг 9.5).

#include <stdio.h> #include <fmtmsg.h>

int main (void) { if (fmtmsg (MM_SOFT + MM_OPSYS + MM_RECOVER + MM_PRINT + MM_CONSOLE, "POSIX:fmtmsg", MM_INFO, "Отсутствует функция fmtmsg()", "Установите функцию fmtmsg() или не пользуйтесь ею\n", "См. functions/fmtmsg.html") != MM_OK) { perror ("FMTMSG"); return (1); }

return 0; }

Листинг 9.5. Пример использования функции fmtmsg().

В результате выполнения приведенной программы в стандартный протокол и на системную консоль будет выдано следующее сообщение (см. листинг 9.6).

POSIX:fmtmsg: INFO: Отсутствует функция fmtmsg() TO FIX: Установите функцию fmtmsg() или не пользуйтесь ею См. functions/fmtmsg.html

Листинг 9.6. Возможные результаты выполнения программы, использующей функцию fmtmsg().

Читателю предлагается самостоятельно поэкспериментировать с этой программой, варьируя значение переменной окружения MSGVERB.

Манипулирование пользовательскими контекстами

Согласно стандарту POSIX-2001, пользовательский контекст потока управления включает содержимое машинных регистров, маску сигналов и текущий стек выполнения. Эти данные сосредоточены в структуре типа ucontext_t, содержащей по крайней мере следующие поля.

ucontext_t *uc_link; /* Указатель на контекст, */ /* в котором будет возобновлено */ /* выполнение при выходе из */ /* данного контекста */ sigset_t uc_sigmask; /* Набор сигналов, блокированных */ /* в данном контексте */ stack_t uc_stack; /* Стек, используемый в данном */ /* контексте */ mcontext_t uc_mcontext; /* Машинно-зависимое представление */ /* сохраненного контекста */

Стандарт POSIX-2001 предоставляет функции для опроса (getcontext()), модификации (makecontext()) и смены (setcontext() и swapcontext()) пользовательских контекстов (см. листинг 9.33).

#include <ucontext.h>

int getcontext (ucontext_t *ucp);

void makecontext (ucontext_t *ucp, void (*func) (void), int argc, ...);

int setcontext (const ucontext_t *ucp);

int swapcontext (ucontext_t *restrict oucp, const ucontext_t *restrict ucp);

Листинг 9.33. Описание функций, манипулирующих пользовательскими контекстами потоков управления. (html, txt)

Функция getcontext() – штатное средство получения исходного материала для манипулирования контекстами. Она запоминает текущий контекст вызывающего потока управления в структуре, на которую указывает аргумент ucp. Ее нормальный результат равен нулю.

Функция makecontext() модифицирует контекст, заданный аргументом ucp. Когда (после вызовов setcontext() или swapcontext()) выполнение будет возобновлено в этом контексте, оно продолжится обращением к функции func() с передачей ей аргументов типа int в количестве argc, помещенных после argc при вызове makecontext(). Приложение должно позаботиться о том, чтобы модифицируемый контекст включал стек достаточного размера.

Элемент uc_link структуры типа ucontext_t определяет контекст, в котором будет возобновлено выполнение после выхода из модифицированного функцией makecontext() контекста.
Приложение должно позаботиться об инициализации этого элемента до обращения к makecontext().

Функция setcontext() устанавливает пользовательский контекст вызывающего потока управления в соответствии с содержимым структуры, на которую указывает аргумент ucp. После успешного вызова setcontext() возврата не происходит – выполнение возобновляется с точки, специфицированной новым контекстом, а именно: если этот контекст был сформирован в результате обращения к getcontext(), выполнение возобновляется возвратом из getcontext(); если контекст получен после makecontext(), вызывается функция func(), после возврата из которой поток управления продолжает работу во входном для makecontext() контексте.

Если значением элемента uc_link структуры, на которую указывает аргумент ucp, служит пустой указатель, то данный контекст соответствует функции main(), после выхода из которой выполнение потока управления завершается.

Функция swapcontext() производит перестановку пользовательских контекстов. Текущий контекст сохраняется в структуре, на которую указывает аргумент oucp, а новый контекст формируется по значению аргумента ucp.

Обратим внимание на следующую тонкость. Когда вызывается функция обработки сигнала, текущий пользовательский контекст запоминается, а для выполнения обработчика формируется новый контекст. Стандарт POSIX-2001 не гарантирует, что после нелокального перехода из функции обработки сигнала посредством longjmp() будет аккуратно восстановлен контекст соответствующего вызова setjmp(). В подобных ситуациях рекомендуется применять функции siglongjmp() или setcontext().

В качестве примера применения функций, манипулирующих пользовательскими контекстами, рассмотрим модифицированную программу из текста стандарта POSIX-2001 (см. листинг 9.34).

/* * * * * * * * * * * * * * * * * * * * * * * */ /* Программа демонстрирует применение функций, */ /* манипулирующих пользовательскими контекстами*/ /* * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h> #include <ucontext.h>

/* Размер стеков в формируемых пользовательских контекстах */ #define STACK_SIZE 4096

/* Пространство для стеков */ static char st1 [STACK_SIZE]; static char st2 [STACK_SIZE];

static ucontext_t ctx [3];

static void f1 (int arg) { printf ("Вызвана функция %s с аргументом %d\n", "f1", arg); if (swapcontext (&ctx [1], &ctx [2]) != 0) { perror ("SWAPCONTEXT-1"); } printf ("Выход из функции %s\n", "f1"); }

static void f2 (int arg1, int arg2) { printf ("Вызвана функция %s с аргументами %d, %d\n", "f2", arg1, arg2); if (swapcontext (&ctx [2], &ctx [1]) != 0) { perror ("SWAPCONTEXT-2"); } printf ("Выход из функции %s\n", "f2"); }

int main (void) { (void) getcontext (&ctx [1]);

printf ("Параметры первоначального контекста:\n" "адрес стека %p, размер стека %d\n", ctx[1].uc_stack.ss_sp, ctx[1].uc_stack.ss_size);

/* В соответствии с общими рекомендациями */ /* позаботимся о стеке для модифицируемых контекстов */ ctx[1].uc_stack.ss_sp = st1; ctx[1].uc_stack.ss_size = sizeof (st1); ctx[1].uc_link = &ctx [0]; makecontext (&ctx [1], (void (*) (void)) f1, 1, 2);

(void) getcontext (&ctx [2]); ctx[2].uc_stack.ss_sp = st2; ctx[2].uc_stack.ss_size = sizeof (st2); ctx[2].uc_link = &ctx [1]; makecontext (&ctx [2], (void (*) (void)) f2, 2, 3, 4); if (swapcontext (&ctx [0], &ctx [2]) != 0) { perror ("SWAPCONTEXT-3"); return (1); }

return 0; }

Листинг 9.34. Пример применения функций, манипулирующих пользовательскими контекстами.

Обратим внимание на резервирование пространства под стек перед обращением к функции makecontext(), а также на связывание нескольких контекстов в список посредством поля uc_link.

Результаты выполнения приведенной программы показаны на листинге 9.35.

Параметры первоначального контекста: адрес стека (nil), размер стека 0 Вызвана функция f2 с аргументами 3, 4 Вызвана функция f1 с аргументом 2 Выход из функции f2 Выход из функции f1

Листинг 9.35. Возможные результаты выполнения программы, применяющей функции манипулирования пользовательскими контекстами.

Обход файловой иерархии

Обход файловой иерархии – типовая задача, для решения которой стандартом POSIX-2001 предлагаются две сходные функции – ftw() и nftw() (см. листинг 9.46).

#include <ftw.h>

int ftw (const char *path, int (*fn) (const char *, const struct stat *, int), int depth);

int nftw (const char *path, int (*fn) (const char *, const struct stat *, int, struct FTW *), int depth, int flags);

Листинг 9.46. Описание функций обхода файловой иерархии. (html, txt)

Функция ftw() рекурсивно обходит иерархию каталогов, имеющую своим корнем каталог с маршрутным именем, на которое указывает аргумент path. Для каждого объекта иерархии ftw() вызывает функцию fn(), передавая ей три аргумента: указатель на цепочку символов, ограниченную нулевым байтом и содержащую имя объекта; указатель на структуру типа stat, содержащую информацию об объекте; тип объекта, представленный целым числом.

Возможны следующие значения типа объекта.

FTW_D

Каталог.

FTW_DNR

Каталог, недоступный на чтение.

FTW_F

Обычный файл.

FTW_SL

Символьная ссылка.

FTW_NS

Объект, отличный от символьной ссылки, для которого stat() не может выполниться успешно.

Если тип объекта есть FTW_DNR, элементы этого каталога не просматриваются. Если тип есть FTW_NS, то структура типа stat будет содержать неопределенные значения. Примером объекта, который вызовет передачу функции fn() типа FTW_NS, является файл в каталоге, доступном для чтения, но не для поиска.

Функция ftw() обрабатывает каталог перед обработкой его элементов.

Функция ftw() использует не более одного файлового дескриптора на обход каждого уровня иерархии. Аргумент depth ограничивает количество используемых таким образом дескрипторов; его значение должно принадлежать диапазону [1, OPEN_MAX].

Обход завершится тогда, когда будет обойдена вся иерархия, или функция fn() вернет ненулевое значение, или возникнет ошибка, отличная от EACCES, при работе самой функции ftw() (например, ошибка ввода/вывода). Если дерево обойдено полностью, ftw() в качестве результата возвращает нуль.
Если fn() вернет ненулевое значение, то ftw() прекратит обход и выдаст это значение. Если будет обнаружена ошибка при работе самой функции ftw(), то она вернет -1 и соответствующим образом установит значение переменной errno.

Обратим внимание на следующее (впрочем, довольно очевидное) обстоятельство. Функция ftw() во время своей работы временно резервирует некоторые ресурсы (оперативную память, файловые дескрипторы). Если прервать ее нештатным образом (например, посредством нелокального перехода из функции fn() или обработчика сигнала), эти ресурсы останутся неосвобожденными. Рекомендуемый способ обработки прерываний заключается в том, чтобы зафиксировать факт получения прерывания и при очередном вызове fn() заставить ее вернуть ненулевое значение.

Функция nftw() аналогична ftw(), однако и у нее самой, и у вызываемой ею функции fn() имеется по одному дополнительному аргументу. Дополнительный аргумент flags управляет работой функции nftw(). Его значение формируется как побитное ИЛИ следующих флагов.

FTW_CHDIR

Делать текущим просматриваемый каталог. Если этот флаг не установлен, функция nftw() не изменит текущий каталог.

FTW_DEPTH

Обход вглубь: обрабатывать каталог после обработки его элементов.

FTW_MOUNT

Обрабатывать только файлы из той же файловой системы, что и path.

FTW_PHYS

Осуществлять физический обход без разрешения символьных ссылок.

Третий аргумент функции fn(), по сравнению с ftw() может принимать следующие дополнительные значения.

FTW_DP

Каталог, элементы которого уже обработаны (данное условие может быть истинным только при установленном флаге FTW_DEPTH).

FTW_SLN

Символьная ссылка, именующая отсутствующий файл.

Дополнительный, четвертый аргумент функции fn() является указателем на структуру типа FTW. Согласно стандарту, она должна содержать по крайней мере следующие поля.

int base; /* Смещение простого имени файла */ /* от начала маршрутного имени, */ /* переданного fn() в качестве */ /* первого аргумента */ int level; /* Уровень текущего объекта */ /* относительно корня иерархии */ /* (у самого корня нулевой уровень) */

В качестве примера обхода файловой иерархии рассмотрим программу, подсчитывающую суммарный размер и высоту дерева файлов (см. листинг 9.47);

Листинг 9.47. Пример программы, осуществляющей обход файловой иерархии. (html, txt)

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

Пусть в каталоге /tmp существует непустой подкаталог gaga со следующим режимом доступа:

drw-r--r-- 2 galat sys 4096 May 7 17:26 gaga

Тогда результаты запуска приведенной программы с аргументом /tmp могут выглядеть так, как показано на листинге 9.48.

Листинг 9.48. Возможные результаты выполнения программы, осуществляющей обход файловой иерархии. (html, txt)

Поиск и сортировка

Поиск и сортировка данных, располагающихся в оперативной памяти, – типичная и очень важная часть многих приложений, качество реализации которой во многом определяет технические характеристики программной системы в целом.

Стандарт POSIX-2001 предлагает несколько способов поиска в таблицах разных форматов.

Бинарный поиск (см. листинг 9.13) является самым быстрым среди методов, основанных на сравнении ключей. Он применим к предварительно отсортированным одномерным массивам.

#include <stdlib.h> void *bsearch (const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));

Листинг 9.13. Описание функции бинарного поиска bsearch(). (html, txt)

Функция bsearch() предназначена для выполнения бинарного поиска в соответствии с алгоритмом, описанным Д. Кнутом (см. [4] в дополнительной литературе, пункт 6.2.1, алгоритм B).

Функция bsearch() возвращает указатель внутрь массива на искомые данные или NULL в случае неудачи поиска. Предварительно массив должен быть отсортирован в возрастающем порядке согласно предоставленной функции сравнения compar().

Аргумент key указывает на объект данных, разыскиваемый в массиве (ключ поиска); base указывает на начало (первый элемент) массива; nel задает количество элементов в массиве; width специфицирует размер элемента в массиве.

Аргумент compar() – это функция сравнения, аргументами которой служат два указателя на сравниваемые объекты – ключ и элемент массива. В соответствии с тем, какое целое число она возвращает: меньшее нуля, равное нулю или большее нуля, ключ считается меньшим, равным или большим по отношению к элементу массива.

Для сортировки массивов целесообразно пользоваться функцией qsort() (см. листинг 9.14), реализующей метод быстрой сортировки (называемый также методом обменной сортировки с разделением, см. [4] в дополнительной литературе, пункт 5.2.2, алгоритм Q). Ее аргументы имеют тот же смысл, что и одноименные аргументы функции bsearch().

#include <stdlib.h> void qsort (void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));

Листинг 9.14. Описание функции быстрой сортировки qsort(). (html, txt)

Рассмотрим пример последовательного применения функций qsort() и bsearch() (см. листинг 9.15). Здесь в роли элементов массива выступают указатели на цепочки символов, которые размещены в области StringSpace; тот же тип имеет и ключ поиска. Критерием сравнения служит алфавитная упорядоченность указуемых цепочек.

Листинг 9.15. Пример применения функций быстрой сортировки и бинарного поиска. (html, txt)

Отметим, что при сортировке будут перемещаться элементы массива PtsTable [] – указатели на цепочки символов, но, конечно, не сами цепочки.

Если на компьютере, которым в данный момент пользуется автор, измерить время выполнения приведенной программы посредством утилиты time с опцией -p, результаты будут выглядеть следующим образом (см. листинг 9.16).

Листинг 9.16. Возможные результаты выполнения программы, применяющей функции быстрой сортировки и бинарного поиска. (html, txt)

Читателю предлагается сравнить эти результаты с экспериментально полученными собственными (и с гордостью убедиться, что его компьютер гораздо мощнее), а также оценить зависимость длительности быстрой сортировки и бинарного поиска от размера массива (и подтвердить теоретические оценки из [4]).

Стандартом POSIX-2001, помимо бинарного, предусматривается еще несколько способов поиска – последовательный, с помощью хэш-таблиц и бинарных деревьев. Соответствующие описания сосредоточены в заголовочном файле <search.h>.

В идейном плане самым простым является последовательный поиск. Он может производиться с вставкой (функция lsearch()) или без таковой (lfind()) (см. листинг 9.17).

#include <search.h>

void *lsearch (const void *key, void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));

void *lfind (const void *key, const void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));

Листинг 9.17. Описание функций последовательного поиска. (html, txt)

Функции, реализующие последовательный поиск, по способу вызова напоминают bsearch(), только аргумент nelp является указателем на число элементов в массиве, которое функция lsearch() может увеличить на единицу (если искомого элемента в массиве не было, его добавляют в конец).

Разумеется, для последовательного поиска не требуется, чтобы массив был предварительно отсортирован. Упрощены и требования к функции сравнения compar(): в случае неравенства ее результат должен быть отличен от нуля.

В качестве иллюстрации применения функций последовательного поиска рассмотрим программу, генерирующую случайные цепочки символов до первого повторения (см. листинг 9.18).

Листинг 9.18. Пример применения последовательного поиска с вставкой. (html, txt)

Указатели на порождаемые случайные цепочки помещаются в массив PtsTable [] функцией lsearch(). В этой связи обратим внимание на нескольку вычурную организацию цикла for в функции main(). По сути здесь две переменные цикла – pss и nelst. Первая продвигается стандартным образом, в заголовке цикла, но проверяется на выход за допустимые границы в его теле; вторая, напротив, стандартно проверяется, но нестандартно продвигается (в результате вызова lsearch()).

Возможные результаты выполнения этой программы показаны на листинге 9.19.

Листинг 9.19. Возможные результаты выполнения программы, применяющей функцию последовательного поиска с вставкой. (html, txt)

При экспериментах с приведенной программой следует соблюдать определенную осторожность, поскольку время ее работы квадратично зависит от величины TAB_SIZE.

Листинг 9.16. Возможные результаты выполнения программы, применяющей функции быстрой сортировки и бинарного поиска.

Читателю предлагается сравнить эти результаты с экспериментально полученными собственными (и с гордостью убедиться, что его компьютер гораздо мощнее), а также оценить зависимость длительности быстрой сортировки и бинарного поиска от размера массива (и подтвердить теоретические оценки из [4]).

Стандартом POSIX-2001, помимо бинарного, предусматривается еще несколько способов поиска – последовательный, с помощью хэш-таблиц и бинарных деревьев. Соответствующие описания сосредоточены в заголовочном файле <search.h>.

В идейном плане самым простым является последовательный поиск. Он может производиться с вставкой (функция lsearch()) или без таковой (lfind()) (см. листинг 9.17).

#include <search.h>

void *lsearch (const void *key, void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));

void *lfind (const void *key, const void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));

Листинг 9.17. Описание функций последовательного поиска.

Функции, реализующие последовательный поиск, по способу вызова напоминают bsearch(), только аргумент nelp является указателем на число элементов в массиве, которое функция lsearch() может увеличить на единицу (если искомого элемента в массиве не было, его добавляют в конец). Разумеется, для последовательного поиска не требуется, чтобы массив был предварительно отсортирован. Упрощены и требования к функции сравнения compar(): в случае неравенства ее результат должен быть отличен от нуля.

В качестве иллюстрации применения функций последовательного поиска рассмотрим программу, генерирующую случайные цепочки символов до первого повторения (см. листинг 9.18).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа генерирует случайные цепочки символов до первого */ /* повторения (или до исчерпания отведенного пространства). */ /* Для выявления повторения применяется */ /* последовательный поиск с вставкой */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <search.h> #include <stdio.h> #include <stdlib.h> #include <string.h>

/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 200000

/* Число элементов в таблице указателей на цепочки символов */ #define TAB_SIZE 20000

/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 7

/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];

/* Массив указателей на цепочки символов */ static char *PtsTable [TAB_SIZE];

/* * * * * * * * * * */ /* Функция сравнения */ /* * * * * * * * * * */ static int str_compar (const void *pkey, const void *pelem) { return strcoll (*((char **) pkey), *((char **) pelem)); }

/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Поиск первого повтора в последовательности */ /* случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { char *pss; /* Указатель на свободное место */ /* в области StringSpace */ char **res; /* Результат поиска с вставкой */ size_t nelst; /* Число занятых элементов */ /* в массиве указателей */ size_t onelst; /* Число элементов в массиве */ /* до поиска с вставкой */ for (pss = StringSpace, nelst = 0; nelst < TAB_SIZE; pss += STRING_SIZE) { if (((pss + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (1); }

str_rnd (pss, STRING_SIZE);

onelst = nelst; res = (char **) lsearch (&pss, PtsTable, &nelst, sizeof (PtsTable [0]), str_compar); if (onelst == nelst) { /* Искомая цепочка уже была порождена ранее */ printf ("Для случайных цепочек длины %d\n" "первое совпадение получено на цепочке " "%s\n", STRING_SIZE, pss); printf ("Первый раз цепочка была порождена " "под номером %d,\n" "второй – под номером " "%d\n", (res – PtsTable) / sizeof (PtsTable [0]) + 1, nelst + 1); return 0; } } /* for */

printf ("Из %d случайных цепочек длины %d все " "оказались уникальными\n", TAB_SIZE, STRING_SIZE);

return 0; }

Листинг 9.18. Пример применения последовательного поиска с вставкой.

Указатели на порождаемые случайные цепочки помещаются в массив PtsTable [] функцией lsearch(). В этой связи обратим внимание на нескольку вычурную организацию цикла for в функции main(). По сути здесь две переменные цикла – pss и nelst. Первая продвигается стандартным образом, в заголовке цикла, но проверяется на выход за допустимые границы в его теле; вторая, напротив, стандартно проверяется, но нестандартно продвигается (в результате вызова lsearch()).

Возможные результаты выполнения этой программы показаны на листинге 9.19.

Для случайных цепочек длины 7 первое совпадение получено на цепочке GLPCSX Первый раз цепочка была порождена под номером 2548, второй - под номером 12530 real 34.80 user 13.70 sys 0.03

Листинг 9.19. Возможные результаты выполнения программы, применяющей функцию последовательного поиска с вставкой.

При экспериментах с приведенной программой следует соблюдать определенную осторожность, поскольку время ее работы квадратично зависит от величины TAB_SIZE.

Управление хэш-таблицами поиска производится в соответствии с алгоритмом, описанным Д. Кнутом (см. [4] в дополнительной литературе, раздел 6.4, алгоритм D). Предоставляются функции для создания (hcreate()) и ликвидации (hdestroy()) хэш-таблиц, а также для выполнения в них поиска (hsearch()), быть может, с вставкой (см. листинг 9.20). Сразу отметим, что в каждый момент времени может быть активна только одна хэш-таблица.

#include <search.h>

int hcreate (size_t nel);

void hdestroy (void);

ENTRY *hsearch (ENTRY item, ACTION action);

Пример 9.20. Описание функций управления хэш-таблицами поиска.

Предполагается, что элементы таблицы поиска имеют тип ENTRY, определенный так, как показано на листинге 9.21.

typedef struct entry { char *key; /* Ключ поиска */ void *data; /* Дополнительные данные, */ /* ассоциированные с ключом */ } ENTRY;

Листинг 9.21. Описание типа ENTRY.

Функция hcreate() резервирует достаточное количество памяти для таблицы и должна вызываться перед обращением к hsearch(). Значением аргумента nel является ожидаемое максимальное количество элементов в таблице. Это число можно взять с запасом, чтобы уменьшить среднее время поиска.

Нормальный для hcreate() результат отличен от нуля.

Функция hdestroy() ликвидирует таблицу поиска. За вызовом этой функции может следовать новое обращение к функции создания таблицы hcreate().

Функция hsearch() возвращает указатель внутрь таблицы на искомые данные. Аргумент item – это структура типа ENTRY, содержащая два указателя: item.key указывает на сравниваемый ключ (функцией сравнения при поиске в хэш-таблице служит strcmp()), а item.data – на любые дополнительные данные, ассоциированные с этим ключом.

Аргумент action имеет тип ACTION, определенный так, как показано на листинге 9.22. Он задает способ действий в случае неудачного поиска: значение ENTER предписывает производить поиск с вставкой, то есть в случае неудачи искомый элемент следует поместить в таблицу; значение FIND предписывает в случае неудачи вернуть пустой указатель NULL. Пустой указатель возвращается и тогда, когда значение аргумента action равно ENTER, и таблица заполнена.

enum { FIND, ENTER } ACTION;

Листинг 9.22. Определение типа ACTION.

В качестве примера применения функций, управляющих хэш-таблицами поиска, рассмотрим программу, которая помещает в хэш-таблицу заданное число элементов с указателями на случайные цепочки символов, а затем выполняет в этой таблице поиск новых случайных цепочек, пока он не окажется успешным (см. листинг 9.23).

/* * * * * * * * * * * * * * * * * * * * */ /* Программа помещает в хэш-таблицу */ /* заданное число элементов с указателями*/ /* на случайные цепочки символов, */ /* а затем выполняет в этой таблице */ /* поиск новых случайных цепочек, */ /* пока он не окажется успешным */ /* * * * * * * * * * * * * * * * * * * * */

#include <search.h> #include <stdlib.h> #include <stdio.h>

/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000

/* Число элементов, помещаемых в хэш-таблицу */ #define TAB_NEL 1000000

/* Размер хэш-таблицы */ #define TAB_SIZE (2 * TAB_NEL)

/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10

/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];

/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Заполнение хэш-таблицы, поиск повтора в */ /* последовательности случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { ENTRY item; /* Искомый элемент */ char sbuf [STRING_SIZE]; /* Буфер для формирования */ /* случайных цепочек */ double ntr; /* Номер найденной */ /* случайной цепочки */ size_t i;

if (hcreate (TAB_SIZE) == 0) { fprintf (stderr, "%s: Не удалось создать хэш-таблицу" " размера %d\n", argv [0], TAB_SIZE); return (1); }

item.data = NULL; /* Нет ассоциированных данных */ /* Заполним таблицу */ for (item.key = StringSpace, i = 0; i < TAB_NEL; item.key += STRING_SIZE, i++) { if (((item.key + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (2); }

str_rnd (item.key, STRING_SIZE);

if (hsearch (item, ENTER) == NULL) { fprintf (stderr, "%s: Переполнена хэш-таблица\n", argv [0]); return (3); } } /* for */

/* Будем формировать и искать новые случайные цепочки */ item.key = sbuf; ntr = 0; do { str_rnd (item.key, STRING_SIZE); ntr++; } while (hsearch (item, FIND) == NULL); printf ("Удалось найти %g-ю по счету случайную цепочку %s\n", ntr, item.key);

hdestroy ();

return 0; }

Листинг 9.23. Пример применения функций, управляющих хэш-таблицами поиска.

Обратим внимание на то, что размер хэш-таблицы выбран вдвое большим по сравнению с реально используемым числом элементов; это уменьшает число коллизий (случаев совпадения хэш-кодов разных ключей) и ускоряет их разрешение. При небольшом числе коллизий время поиска одного элемента в хэш-таблице ограничено константой (не зависит от количества элементов в таблице). Это значит, что время работы приведенной программы должно быть пропорционально размеру таблицы, то есть по порядку величины оно меньше, чем для рассмотренной выше комбинации быстрой сортировки и бинарного поиска (убирается множитель, равный логарифму числа элементов). Сделанный вывод подтверждается результатами измерения времени работы программы (см. листинг 9.24).

Удалось найти 168221-ю по счету случайную цепочку VBBDZTNMZ real 9.61 user 9.36 sys 0.25

Листинг 9.24. Возможные результаты выполнения программы, применяющей функции управления хэш-таблицами поиска.

Читателю предлагается измерить время работы этой программы на своем компьютере, сравнить его с аналогичным временем для быстрой сортировки и бинарного поиска, а также оценить зависимость среднего времени поиска от размера таблицы (и подтвердить теоретические оценки из [4]).

Бинарные деревья поиска – замечательное средство, позволяющее эффективно (за время, логарифмически зависящее от числа элементов) осуществлять операций поиска с вставкой (функция tsearch()) и без таковой (tfind()), удаления (tdelete()) и, кроме того, выполнять обход всех элементов (функция twalk()) (см. листинг 9.25). Функции реализуют алгоритмы T и D, описанные в пункте 6.2.2 книги Д. Кнута [4].

#include <search.h>

void *tsearch (const void *key, void **rootp, int (*compar) (const void *, const void *));

void *tfind (const void *key, void *const *rootp, int (*compar) (const void *, const void *));

void *tdelete (const void *restrict key, void **restrict rootp, int (*compar) (const void *, const void *));

void twalk (const void *root, void (*action) (const void *, VISIT, int));

Листинг 9.25. Описание функций управления бинарными деревьями поиска.

Функция tsearch() используется для построения дерева и доступа к нему. Аргумент key является указателем на искомые данные (ключ). Если в дереве есть узел, первым полем которого является ссылка на данные, равные искомым, то результатом функции служит указатель на этот узел. В противном случае в дерево вставляется вновь созданный узел со ссылкой на искомые данные и возвращается указатель на него. Отметим, что копируются только указатели, поэтому прикладная программа сама должна позаботиться о хранении данных.

Аргумент rootp указывает на переменную, которая является указателем на корень дерева. Ее значение, равное NULL, специфицирует пустое дерево; в этом случае в результате выполнения функции tsearch() переменная устанавливается равной указателю на единственный узел – корень вновь созданного дерева.

Подобно функции tsearch(), функция tfind() осуществляет поиск по ключу, возвращая в случае успеха указатель на соответствующий узел. Однако в случае неудачного поиска функция tfind() возвращает пустой указатель NULL.

Функция tdelete(), как и tfind(), сначала производит поиск, но не останавливается на этом, а удаляет найденный узел из бинарного дерева. Результатом tdelete() служит указатель на вышележащий по сравнению с удаляемым узел или NULL, если поиск оказался неудачным.

Функция twalk() осуществляет обход бинарного дерева в глубину, слева направо (дерево строится функцией tsearch() так, что, в соответствии с функцией сравнения compar(), все узлы левого поддерева предшествуют его корню, который, в свою очередь, предшествует узлам правого поддерева). Аргумент root указывает на корень обрабатываемого (под)дерева (любой узел может быть использован в качестве корня для обхода соответствующего поддерева).

Очевидно, в процессе обхода все неконцевые узлы посещаются трижды (при спуске в левое поддерево, при переходе из левого поддерева в правое и при возвращении из правого поддерева), а концевые (листья) – один раз.

Эти посещения обозначаются величинами типа VISIT с исключительно неудачными именами (см. листинг 9.26).

enum { preorder, postorder, endorder, leaf } VISIT;

Листинг 9.26. Определение типа VISIT.

Имена неудачны, потому что они совпадают с названиями разных способов обхода деревьев (см., например, [3] в дополнительной литературе, пункт 2.3.1). В частности, порядок обхода, реализуемый функцией twalk(), называется в [3] прямым (по-английски – preorder). Остается надеяться, что читатель не даст себя запутать и уверенно скажет, что в данном контексте postorder – это второе посещение неконцевого узла бинарного дерева поиска, а не какой-то там обратный порядок обхода.

Аргумент action – это функция, которую twalk() вызывает при попадании в узел во время обхода. Она, в свою очередь, имеет три аргумента. Первым из них служит адрес текущего узла. Структура, на которую указывает этот аргумент, стандартом не специфицируется; оговаривается только, что указатель на узел можно привести к типу "указатель на указатель на хранимые данные" (то есть на данные, ассоциированные с узлом, и содержащие, в частности, ключ поиска). Второй аргумент вызываемой функции – это значение определенного выше типа VISIT. Напомним еще раз, что оно показывает, который раз (первый, второй или третий) осуществляется доступ к неконцевому узлу во время обхода дерева в глубину и слева направо или свидетельствует, что узел является концевым (листом). Третий аргумент – это уровень узла в дереве (в предположении, что корень имеет уровень 0).

Читатель наверняка уже догадался, что далее последует пример программы, строящей бинарное дерево поиска для случайных цепочек символов (см. листинг 9.27). Впрочем, приведенная программа делает и еще кое-что: подсчитывает число узлов и высоту дерева, распечатывает несколько первых по алфавиту цепочек из числа помещенных в дерево и, конечно, генерирует новые случайные цепочки, пока их поиск в дереве не окажется успешным. Для разнообразия узел с найденной цепочкой удаляется.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа осуществляет поиск с вставкой в бинарном */ /* дереве, помещая в него заданное число элементов с */ /* указателями на случайные цепочки символов. */ /* Затем подсчитывается число узлов и высота дерева. */ /* Следующим действием является распечатка */

/* нескольких первых цепочек. */ /* После этого выполняется поиск новых случайных цепочек,*/ /* пока он не окажется успешным. */ /* Найденный элемент удаляется из дерева */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <search.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <setjmp.h>

/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000

/* Число элементов, помещаемых в дерево */ #define TREE_NEL 1000000

/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10

/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];

/* Число узлов в бинарном дереве поиска */ static size_t node_count;

/* Максимальный уровень узла дерева */ static int max_level; /* Буфер для функций setjmp и longjmp */ static jmp_buf buf_env;

/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, которая вызывается при обходе дерева */ /* с целью подсчета числа узлов и высоты */ /* * * * * * * * * * * * * * * * * * * * * * * * */ static void tw_nnh (const void *pnode, VISIT nv, int level) { if (nv == preorder) { node_count++; } else if (nv == leaf) { node_count++; if (level > max_level) { max_level = level; } } }

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, которая вызывается при обходе дерева */ /* с целью распечатки нескольких первых */ /* по алфавиту цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ static void tw_pfs (const void *pnode, VISIT nv, int level) { if (node_count <= 0) { /* Нужное число цепочек выведено,*/ /* прерываем обход дерева */ longjmp (buf_env, 1); } if ((nv == postorder) || (nv == leaf)) { printf ("%s\n", *((char **) pnode)); node_count--; } }

/* * * * * * * * * * * * * * * * * * */ /* Создание бинарного дерева поиска, */ /* определение его характеристик, */ /* поиск повтора в последовательности*/ /* случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { void *root; /* Указатель на корень дерева */ char *key; /* Указатель на искомую */ /* цепочку символов */ char sbuf [STRING_SIZE]; /* Буфер для формирования */ /* случайных цепочек */ double ntr; /* Номер найденной случайной */ /* цепочки */ size_t i;

/* Создадим бинарное дерево поиска */ root = NULL; for (key = StringSpace, i = 0; i < TREE_NEL; key += STRING_SIZE, i++) { if (((key + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (1); }

str_rnd (key, STRING_SIZE);

if (tsearch (key, &root, (int (*) (const void *, const void *)) strcoll) == NULL) { fprintf (stderr, "%s: Поиск с вставкой в бинарное" " дерево " "завершился неудачей\n", argv [0]); return (2); } } /* for */

/* Подсчитаем число узлов и высоту созданного дерева */ node_count = 0; max_level = 0; twalk (root, tw_nnh); printf ("В дереве оказалось %d узлов\n", node_count); printf ("Его высота равна %d\n", max_level);

/* Распечатаем несколько первых (по алфавиту) цепочек, */ /* помещенных в созданное дерево */ node_count = 10; printf ("Первые %d по алфавиту цепочек в дереве:\n", node_count); if (setjmp (buf_env) == 0) { twalk (root, tw_pfs); }

/* Будем формировать и искать новые случайные цепочки */ ntr = 0; do { str_rnd (sbuf, STRING_SIZE); ntr++; } while (tdelete (sbuf, &root, (int (*) (const void *, const void *)) strcoll) == NULL); printf ("Удалось найти и удалить из дерева %g-ю по счету " "случайную цепочку %s\n", ntr, sbuf);

return 0; }

Листинг 9.27. Пример применения функций управления бинарными деревьями поиска.

Отметим гибкость бинарных деревьев поиска как структуры данных.

Не требуется заранее резервировать определенное пространство – деревья растут не более, чем это необходимо. При добавлении и удалении узлов деревья динамически перестраиваются без специального переупорядочения или массовых передвижек.

Обратим внимание на частичный обход дерева при распечатке нескольких первых по алфавиту цепочек, реализуемый с использованием механизма нелокальных переходов. Сама по себе функция twalk() ориентирована, разумеется, на полный обход (также представленный в программе).

Возможные результаты выполнения приведенной программы показаны на листинге 9.28.

В дереве оказалось 1000000 узлов Его высота равна 25 Первые 10 по алфавиту цепочек в дереве: AAAATNRAS AAACHCCLB AAACSJQBP AAADLHFAZ AAAFWLRXM AAAFXGQEC AAAGBMHHA AAAGFAXFI AAAHKLCWW AAAHLOSVQ Удалось найти и удалить из дерева 168221-ю по счету случайную цепочку VBBDZTNMZ real 20.24 user 20.25 sys 0.15

Листинг 9.28. Возможные результаты выполнения программы, применяющей функции управления бинарными деревьями поиска.

Отметим, что среди первых 1000000 случайных цепочек символов длины 10 повторов не оказалось. Дерево поиска получилось весьма сбалансированным, с высотой, лишь немногим большей двоичного логарифма от числа узлов. Приведенные данные о времени выполнения подтверждают высокую эффективность бинарных деревьев как инструмента поиска.

Полноты ради упомянем еще о двух функциях, описанных в заголовочном файле <search.h>: insque() и remque() (см. листинг 9.29). Они предназначены для выполнения операций над очередями, реализованными как двусвязанные списки.

#include <search.h>

void insque (void *element, void *pred);

void remque (void *element);

Листинг 9.29. Описание функций, выполняющих операции над очередями.

Функция insque() осуществляет вставку элемента, на который указывает аргумент element, после элемента pred. В качестве элемента должна выступать структура, первые два поля которой являются указателями на структуры того же типа – соответственно, следующий и предыдущий элементы очереди.

Наличие и назначение других полей определяются нуждами приложения. Имя структурного типа и двух первых полей не стандартизуются.

Функция remque() удаляет заданный элемент из очереди.

Очередь может быть линейной или циклической. В первом случае она ограничена пустыми указателями, во втором крайние указатели должны быть зациклены. Вставка первого элемента в линейную очередь осуществляется вызовом insque (&element, NULL); при инициализации циклической очереди о ссылках должно позаботиться приложение (см. листинг 9.30).

#include <search.h>

. . . struct qelem { struct qelem *q_forw; struct qelem *q_back; char *data; . . . };

struct qelem element1; struct qelem element2;

. . . element1.q_forw = &element1; element1.q_back = &element1;

insque (&element2, &element1);

. . .

Листинг 9.30. Пример инициализации циклической очереди и вставки в нее второго элемента.

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

Из тех же соображений полноты вернемся к теме сортировки и упомянем служебную программу tsort:

tsort [файл]

выполняющую топологическую сортировку элементов заданного файла (или стандартного ввода, если файл не указан), выдавая результаты на стандартный вывод. Подобная сортировка полезна, в частности, при создании библиотек объектных файлов, чтобы выполнять редактирование внешних связей за один проход.

Исходными данными для утилиты tsort служат содержащиеся в файле пары элементов (непустых цепочек символов), разделенных пробелами. Частичная упорядоченность задается парами различных элементов. Пара одинаковых элементов означает лишь наличие элемента и никакой упорядоченности не задает.

Например, если применить утилиту tsort к файлу, содержащему строки, показанные на листинге 9.31, то можно получить результат, приведенный на листинге 9.32.

a b c d d e f g e f h h

Листинг 9.31. Пример исходных данных для служебной программы tsort.

a c h b d e f g

Листинг 9.32. Возможный результат применения служебной программы tsort.

int priority, const char

#include <syslog.h>
void syslog ( int priority, const char *message, ... /* аргументы */);
int setlogmask (int maskpri); void openlog (const char *ident, int logopt, int facility);
void closelog (void);

Листинг 9.1. Описание функций для работы с системным журналом.

Закрыть окно

/* * * * * * * * * * * * * * * * * */ /* Пример использования функций */ /* для работы с системным журналом */ /* * * * * * * * * * * * * * * * * */
#include <stdio.h> #include <syslog.h>
int main (void) { int logmask; /* Прежняя маска журналирования */ /* Будем включать в журналируемые сообщения */ /* идентификатор процесса и выдавать их при */ /* возникновении проблем на системную консоль */ openlog ("Intuit syslog test", LOG_PID | LOG_CONS, LOG_USER);
/* Пренебрежем предупреждениями и менее серьезными сообщениями */ logmask = setlogmask (LOG_MASK (LOG_EMERG) | LOG_MASK (LOG_ALERT) | LOG_MASK (LOG_CRIT) | LOG_MASK (LOG_ERR));
printf ("Подразумеваемая маска журналирования: %x\n", logmask);
/* Поместим сообщение в журнал */ syslog (LOG_ALERT | LOG_USER, "Как читать системный журнал?");
/* Восстановим прежнюю маску журналирования */ (void) setlogmask (logmask);
closelog ();
return 0; }

Листинг 9.2. Пример применения функций для работы с системным журналом.

Закрыть окно

Подразумеваемая маска журналирования: ff

Листинг 9.3. Возможные результаты применения функций для работы с системным журналом.

Закрыть окно

#include <fmtmsg.h> int fmtmsg ( long classification, const char *label, int severity, const char *text, const char *action, const char *tag);

Листинг 9.4. Описание функции fmtmsg().

Закрыть окно

#include <stdio.h> #include <fmtmsg.h>
int main (void) { if (fmtmsg (MM_SOFT + MM_OPSYS + MM_RECOVER + MM_PRINT + MM_CONSOLE, "POSIX:fmtmsg", MM_INFO, "Отсутствует функция fmtmsg()", "Установите функцию fmtmsg() или не пользуйтесь ею\n", "См. functions/fmtmsg.html") != MM_OK) { perror ("FMTMSG"); return (1); }
return 0; }

Листинг 9.5. Пример использования функции fmtmsg().

Закрыть окно

POSIX:fmtmsg: INFO: Отсутствует функция fmtmsg() TO FIX: Установите функцию fmtmsg() или не пользуйтесь ею См. functions/fmtmsg.html

Листинг 9.6. Возможные результаты выполнения программы, использующей функцию fmtmsg().

Закрыть окно

#include <utmpx.h>
struct utmpx *getutxent (void);
struct utmpx *getutxid ( const struct utmpx *id);
struct utmpx *getutxline ( const struct utmpx *line);
struct utmpx *pututxline ( const struct utmpx *utmpx);
void setutxent (void);
void endutxent (void);

Листинг 9.7. Описание функций для работы с базой данных учетной информации о пользователях.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Пример использования функций для работы */ /* с базой данных учетной информации о пользователях */ /* * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h> #include <limits.h> #include <time.h> #include <utmpx.h> #include <string.h>
int main (void) { struct utmpx *utmpx_ptr; /* Указатель на текущую запись */ char dtbuf [LINE_MAX]; /* Буфер для данных о времени */ struct utmpx spat; /* Шаблон для поиска в базе */
/* Прочитаем и распечатаем все записи в базе */ printf ("Содержимое базы данных учетной информации " "о пользователях\n"); while ((utmpx_ptr = getutxent ()) != NULL) { (void) strftime (dtbuf, sizeof (dtbuf), "%c", localtime (&(utmpx_ptr->ut_tv.tv_sec))); switch (utmpx_ptr->ut_type) { case EMPTY: printf ("Пустая запись\n"); break; case BOOT_TIME: printf ("Время загрузки системы: %s\n", dtbuf); break; case OLD_TIME: printf ("Время изменения показаний системных " "часов: %s\n", dtbuf); break; case NEW_TIME: printf ("Показания системных часов после " "изменения: %s\n", dtbuf); break; case USER_PROCESS: printf ("Процесс пользователя: %s, идентификатор: " "%d,\n", utmpx_ptr->ut_user, utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Имя устройства: %s,\n", utmpx_ptr->ut_line); printf ("Время создания записи: %s\n", dtbuf); break; case LOGIN_PROCESS: printf ("Входной процесс: %s, идентификатор: %d,\n", utmpx_ptr->ut_user, utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Время создания записи: %s\n", dtbuf); break; case INIT_PROCESS: printf ("Процесс, порожденный системным процессом " "init:\n"); printf ("Идентификатор: %d,\n", utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Время создания записи: %s\n", dtbuf); break; case DEAD_PROCESS: printf ("Лидер сеанса, завершивший выполнение:\n"); printf ("Идентификатор: %d,\n", utmpx_ptr->ut_pid); printf ("Инициализационный идентификатор процесса: " "%s,\n", utmpx_ptr->ut_id); printf ("Время создания записи: %s\n", dtbuf); break; default: printf ("Нестандартный тип записи: %x\n", utmpx_ptr->ut_type); break; } }
/* Найдем и распечатаем записи, */ /* инициализационный идентификатор которых */ /* равняется S4 */ spat.ut_type = INIT_PROCESS; (void) strncpy (spat.ut_id, "S4", sizeof (spat.ut_id));
/* Позиционируемся на начало базы */ setutxent ();
printf ("Записи, инициализационный идентификатор " "которых равняется S4:\n"); while ((utmpx_ptr = getutxid (&spat)) != NULL) { switch (utmpx_ptr->ut_type) { case USER_PROCESS: printf ("Процесс пользователя: %s, " "идентификатор: %d\n", utmpx_ptr->ut_user, utmpx_ptr->ut_pid); break; case LOGIN_PROCESS: printf ("Входной процесс: %s, идентификатор: " "%d\n",utmpx_ptr->ut_user, utmpx_ptr->ut_pid); break; case INIT_PROCESS: printf ("Процесс, порожденный системным процессом " "init:\n"); printf ("Идентификатор: %d\n", utmpx_ptr->ut_pid); break; case DEAD_PROCESS: printf ("Лидер сеанса, завершивший " "выполнение:\n"); printf ("Идентификатор: %d\n", utmpx_ptr->ut_pid); break; default: printf ("Нестандартный тип результата поиска: " "%x\n", utmpx_ptr->ut_type); break; }
/* Обеспечим сдвиг поиска с текущей записи */ utmpx_ptr->ut_id [0] = 0; }
endutxent ();
return 0; }

Листинг 9.8. Пример применения функций для работы с базой данных учетной информации о пользователях.

Закрыть окно

Содержимое базы данных учетной информации о пользователях Лидер сеанса, завершивший выполнение: Идентификатор: 17, Инициализационный идентификатор процесса: si, Время создания записи: Tue Apr 27 10:08:42 2004 Время загрузки системы: Tue Apr 27 10:08:42 2004 Нестандартный тип записи: 1 Лидер сеанса, завершивший выполнение: Идентификатор: 284, Инициализационный идентификатор процесса: l5, Время создания записи: Tue Apr 27 10:09:15 2004 Лидер сеанса, завершивший выполнение: Идентификатор: 1115, Инициализационный идентификатор процесса: ud, Время создания записи: Tue Apr 27 10:09:15 2004 . . . Входной процесс: LOGIN, идентификатор: 1123, Инициализационный идентификатор процесса: S3, Время создания записи: Tue Apr 27 10:09:15 2004 Процесс пользователя: galat, идентификатор: 1124, Инициализационный идентификатор процесса: S4, Имя устройства: ttyS4, Время создания записи: Tue Apr 27 12:52:51 2004 Процесс пользователя: sambor, идентификатор: 1125, Инициализационный идентификатор процесса: S5, Имя устройства: ttyS5, Время создания записи: Tue Apr 27 13:57:31 2004 Процесс пользователя: kost, идентификатор: 1126, Инициализационный идентификатор процесса: S6, Имя устройства: ttyS6, Время создания записи: Tue Apr 27 10:09:30 2004 . . . Процесс, порожденный системным процессом init: Идентификатор: 1128, Инициализационный идентификатор процесса: x, Время создания записи: Tue Apr 27 10:09:15 2004 . . . Лидер сеанса, завершивший выполнение: Идентификатор: 11708, Инициализационный идентификатор процесса: /1, Время создания записи: Tue Apr 27 11:19:33 2004 . . . Записи, инициализационный идентификатор которых равняется S4: Процесс пользователя: galat, идентификатор: 1124

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

Закрыть окно

#include <ndbm.h>
DBM *dbm_open (const char *file, int open_flags, mode_t file_mode);
void dbm_close (DBM *db);
datum dbm_fetch (DBM *db, datum key);
int dbm_store (DBM *db, datum key, datum content, int store_mode);
int dbm_delete (DBM *db, datum key);
datum dbm_firstkey (DBM *db);
datum dbm_nextkey (DBM *db);
int dbm_error (DBM *db);
int dbm_clearerr (DBM *db);

Листинг 9.10. Описание функций для работы с простыми базами данных.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа перебирает все ключи в базе данных */ /* и выдает ассоциированную с ними информацию. */ /* Предполагается, что ключи и данные – текстовые*/ /* * * * * * * * * * * * * * * * * * * * * * * * */
#include <ndbm.h> #include <stdio.h> #include <fcntl.h>
int main (int argc, char *argv []) { DBM *dbdes; /* Дескриптор открытой базы */ datum ckey; /* Текущий ключ */ datum cdat; /* Текущие данные */ int nkeys = 0; /* Число ключей */
if (argc != 2) { fprintf (stderr, "Использование: %s имя_базы\n", argv [0]); return (1); }
if ((dbdes = dbm_open (argv [1], O_RDONLY, 0777)) == (DBM *) NULL) { fprintf (stderr, " Не удалось открыть базу данных %s\n", argv [1]); return (2); }
for (ckey = dbm_firstkey (dbdes); ckey.dptr != NULL; ckey = dbm_nextkey (dbdes)) { nkeys++; printf ("Длина ключа номер %d: %d\n", nkeys, ckey.dsize); printf ("Ключ номер %d: %s\n", nkeys, ckey.dptr);
if (cdat = dbm_fetch (dbdes, ckey), cdat.dptr != NULL) { printf ("Длина данных для ключа номер %d: %d\n", nkeys, cdat.dsize); printf ("Данные для ключа номер %d: %s\n", nkeys, cdat.dptr); } else { fprintf (stderr, "Отсутствуют данные для " "ключа номер %d\n", nkeys); } }
printf ("Число ключей в базе: %d\n", nkeys);
dbm_close (dbdes);
return 0; }

Листинг 9.11. Пример применения функций для работы с простыми базами данных.

Закрыть окно

Длина ключа номер 1: 16 Ключ номер 1: YP_LAST_MODIFIED Длина данных для ключа номер 1: 10 Данные для ключа номер 1: 0898782331 Длина ключа номер 2: 14 Ключ номер 2: mailer-daemon Длина данных для ключа номер 2: 11 Данные для ключа номер 2: postmaster Длина ключа номер 3: 14 Ключ номер 3: YP_MASTER_NAME Длина данных для ключа номер 3: 3 Данные для ключа номер 3: t41 Длина ключа номер 4: 11 Ключ номер 4: postmaster Длина данных для ключа номер 4: 5 Данные для ключа номер 4: root Длина ключа номер 5: 7 Ключ номер 5: nobody Длина данных для ключа номер 5: 10 Данные для ключа номер 5: /dev/null Длина ключа номер 6: 2 Ключ номер 6: @ Длина данных для ключа номер 6: 2 Данные для ключа номер 6: @ Число ключей в базе: 6

Листинг 9.12. Возможные результаты выполнения программы, применяющей функции для работы с простыми базами данных.

Закрыть окно

#include <stdlib.h> void *bsearch (const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));

Листинг 9.13. Описание функции бинарного поиска bsearch().

Закрыть окно

#include <stdlib.h> void qsort (void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));

Листинг 9.14. Описание функции быстрой сортировки qsort().

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * */ /* Программа сортирует массив указателей */ /* на случайные цепочки символов, а затем */ /* выполняет в этом массиве бинарный поиск */ /* * * * * * * * * * * * * * * * * * * * * */
#include <stdlib.h> #include <stdio.h> #include <string.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000
/* Число элементов в таблице указателей на цепочки символов */ #define TAB_SIZE 1000000
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* Массив указателей на цепочки символов */ static char *PtsTable [TAB_SIZE]; /* Число занятых элементов в массиве указателей */ static size_t nelst;
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * */ /* Заполнение массива указателями */ /* на случайные цепочки символов */ /* * * * * * * * * * * * * * * * * */ static void tabl_fill (void) { char *pss; /* Указатель на свободное место */ /* в области StringSpace */ int i;
for (pss = StringSpace, i = 0; i < TAB_SIZE; pss += STRING_SIZE, i++) { if (((pss + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "tabl_fill: исчерпано " "пространство цепочек\n"); nelst = i; return; } str_rnd (pss, STRING_SIZE); PtsTable [i] = pss; } nelst = TAB_SIZE; }
/* * * * * * * * * * */ /* Функция сравнения */ /* * * * * * * * * * */ static int str_compar (const void *pkey, const void *pelem) { return strcoll (*((char **) pkey), *((char **) pelem)); }
/* * * * * * * * * * * */ /* Сортировка и поиск */ /* * * * * * * * * * * */ int main (void) { char *skey; /* Указатель на искомую цепочку символов */ char **res; /* Результат бинарного поиска */ /* Буфер для формирования случайных цепочек */ char sbuf [STRING_SIZE]; double ntr; /* Номер найденной случайной цепочки */
/* Заполнение массивов */ tabl_fill ();
/* Сортировка массива указателей */ qsort (PtsTable, nelst, sizeof (PtsTable [0]), str_compar);
/* Формирование ключа поиска */ /* (будем искать первую из случайных цепочек) */ skey = StringSpace; if ((res = (char **) bsearch (&skey, PtsTable, nelst, sizeof (PtsTable [0]), str_compar)) != NULL) { printf ("Указатель на первую цепочку %s\n" "после сортировки стал %d-м элементом массива\n", skey, (res – PtsTable) / sizeof (PtsTable [0])); } else { printf ("Не удалось найти цепочку %s\n", skey); }
/* Будем формировать и искать новые случайные цепочки */ skey = sbuf; ntr = 0; do { str_rnd (skey, STRING_SIZE); ntr++;
} while (bsearch (&skey, PtsTable, nelst, sizeof (PtsTable [0]), str_compar) == NULL); printf ("Удалось найти %g-ю по счету случайную цепочку" " %s\n", ntr, skey);
return 0; }

Листинг 9.15. Пример применения функций быстрой сортировки и бинарного поиска.

Закрыть окно

Указатель на первую цепочку NWLRBBMQB после сортировки стал 133253-м элементом массива Удалось найти 168221-ю по счету случайную цепочку VBBDZTNMZ real 15.67 user 15.57 sys 0.10

Листинг 9.16. Возможные результаты выполнения программы, применяющей функции быстрой сортировки и бинарного поиска.

Закрыть окно

#include <search.h>
void *lsearch (const void *key, void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));
void *lfind (const void *key, const void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));

Листинг 9.17. Описание функций последовательного поиска.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа генерирует случайные цепочки символов до первого */ /* повторения (или до исчерпания отведенного пространства). */ /* Для выявления повторения применяется */ /* последовательный поиск с вставкой */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <search.h> #include <stdio.h> #include <stdlib.h> #include <string.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 200000
/* Число элементов в таблице указателей на цепочки символов */ #define TAB_SIZE 20000
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 7
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* Массив указателей на цепочки символов */ static char *PtsTable [TAB_SIZE];
/* * * * * * * * * * */ /* Функция сравнения */ /* * * * * * * * * * */ static int str_compar (const void *pkey, const void *pelem) { return strcoll (*((char **) pkey), *((char **) pelem)); }
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Поиск первого повтора в последовательности */ /* случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { char *pss; /* Указатель на свободное место */ /* в области StringSpace */ char **res; /* Результат поиска с вставкой */ size_t nelst; /* Число занятых элементов */ /* в массиве указателей */ size_t onelst; /* Число элементов в массиве */ /* до поиска с вставкой */ for (pss = StringSpace, nelst = 0; nelst < TAB_SIZE; pss += STRING_SIZE) { if (((pss + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (1); }
str_rnd (pss, STRING_SIZE);
onelst = nelst; res = (char **) lsearch (&pss, PtsTable, &nelst, sizeof (PtsTable [0]), str_compar); if (onelst == nelst) { /* Искомая цепочка уже была порождена ранее */ printf ("Для случайных цепочек длины %d\n" "первое совпадение получено на цепочке " "%s\n", STRING_SIZE, pss); printf ("Первый раз цепочка была порождена " "под номером %d,\n" "второй – под номером " "%d\n", (res – PtsTable) / sizeof (PtsTable [0]) + 1, nelst + 1); return 0; } } /* for */
printf ("Из %d случайных цепочек длины %d все " "оказались уникальными\n", TAB_SIZE, STRING_SIZE);
return 0; }

Листинг 9.18. Пример применения последовательного поиска с вставкой.

Закрыть окно

Для случайных цепочек длины 7 первое совпадение получено на цепочке GLPCSX Первый раз цепочка была порождена под номером 2548, второй - под номером 12530 real 34.80 user 13.70 sys 0.03

Листинг 9.19. Возможные результаты выполнения программы, применяющей функцию последовательного поиска с вставкой.

Закрыть окно

#include <search.h>
int hcreate (size_t nel);
void hdestroy (void);
ENTRY *hsearch ( ENTRY item, ACTION action);

Пример 9.20. Описание функций управления хэш-таблицами поиска.

Закрыть окно

typedef struct entry { char *key; /* Ключ поиска */ void *data; /* Дополнительные данные, */ /* ассоциированные с ключом */ } ENTRY;

Листинг 9.21. Описание типа ENTRY.

Закрыть окно

enum { FIND, ENTER } ACTION;

Листинг 9.22. Определение типа ACTION.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * */ /* Программа помещает в хэш-таблицу */ /* заданное число элементов с указателями*/ /* на случайные цепочки символов, */ /* а затем выполняет в этой таблице */ /* поиск новых случайных цепочек, */ /* пока он не окажется успешным */ /* * * * * * * * * * * * * * * * * * * * */
#include <search.h> #include <stdlib.h> #include <stdio.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000
/* Число элементов, помещаемых в хэш-таблицу */ #define TAB_NEL 1000000
/* Размер хэш-таблицы */ #define TAB_SIZE (2 * TAB_NEL)
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Заполнение хэш-таблицы, поиск повтора в */ /* последовательности случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { ENTRY item; /* Искомый элемент */ char sbuf [STRING_SIZE]; /* Буфер для формирования */ /* случайных цепочек */ double ntr; /* Номер найденной */ /* случайной цепочки */ size_t i;
if (hcreate (TAB_SIZE) == 0) { fprintf (stderr, "%s: Не удалось создать хэш-таблицу" " размера %d\n", argv [0], TAB_SIZE); return (1); }
item.data = NULL; /* Нет ассоциированных данных */ /* Заполним таблицу */ for (item.key = StringSpace, i = 0; i < TAB_NEL; item.key += STRING_SIZE, i++) { if (((item.key + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (2); }
str_rnd (item.key, STRING_SIZE);
if (hsearch (item, ENTER) == NULL) { fprintf (stderr, "%s: Переполнена хэш-таблица\n", argv [0]); return (3); } } /* for */
/* Будем формировать и искать новые случайные цепочки */ item.key = sbuf; ntr = 0; do { str_rnd (item.key, STRING_SIZE); ntr++; } while (hsearch (item, FIND) == NULL); printf ("Удалось найти %g-ю по счету случайную цепочку %s\n", ntr, item.key);
hdestroy ();
return 0; }

Листинг 9.23. Пример применения функций, управляющих хэш-таблицами поиска.

Закрыть окно

Удалось найти 168221- ю по счету случайную цепочку VBBDZTNMZ real 9.61 user 9.36 sys 0.25

Листинг 9.24. Возможные результаты выполнения программы, применяющей функции управления хэш-таблицами поиска.

Закрыть окно

#include <search.h>
void *tsearch (const void *key, void **rootp, int (*compar) (const void *, const void *));
void *tfind (const void *key, void *const *rootp, int (*compar) (const void *, const void *));
void *tdelete (const void *restrict key, void **restrict rootp, int (*compar) (const void *, const void *));
void twalk (const void *root, void (*action) (const void *, VISIT, int));

Листинг 9.25. Описание функций управления бинарными деревьями поиска.

Закрыть окно

enum { preorder, postorder, endorder, leaf } VISIT;

Листинг 9.26. Определение типа VISIT.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа осуществляет поиск с вставкой в бинарном */ /* дереве, помещая в него заданное число элементов с */ /* указателями на случайные цепочки символов. */ /* Затем подсчитывается число узлов и высота дерева. */ /* Следующим действием является распечатка */
/* нескольких первых цепочек. */ /* После этого выполняется поиск новых случайных цепочек,*/ /* пока он не окажется успешным. */ /* Найденный элемент удаляется из дерева */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <search.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <setjmp.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000
/* Число элементов, помещаемых в дерево */ #define TREE_NEL 1000000
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* Число узлов в бинарном дереве поиска */ static size_t node_count;
/* Максимальный уровень узла дерева */ static int max_level; /* Буфер для функций setjmp и longjmp */ static jmp_buf buf_env;
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, которая вызывается при обходе дерева */ /* с целью подсчета числа узлов и высоты */ /* * * * * * * * * * * * * * * * * * * * * * * * */ static void tw_nnh (const void *pnode, VISIT nv, int level) { if (nv == preorder) { node_count++; } else if (nv == leaf) { node_count++; if (level > max_level) { max_level = level; } } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, которая вызывается при обходе дерева */ /* с целью распечатки нескольких первых */ /* по алфавиту цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ static void tw_pfs (const void *pnode, VISIT nv, int level) { if (node_count <= 0) { /* Нужное число цепочек выведено,*/ /* прерываем обход дерева */ longjmp (buf_env, 1); } if ((nv == postorder) || (nv == leaf)) { printf ("%s\n", *((char **) pnode)); node_count--; } }
/* * * * * * * * * * * * * * * * * * */ /* Создание бинарного дерева поиска, */ /* определение его характеристик, */ /* поиск повтора в последовательности*/ /* случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { void *root; /* Указатель на корень дерева */ char *key; /* Указатель на искомую */ /* цепочку символов */ char sbuf [STRING_SIZE]; /* Буфер для формирования */ /* случайных цепочек */ double ntr; /* Номер найденной случайной */ /* цепочки */ size_t i;
/* Создадим бинарное дерево поиска */ root = NULL; for (key = StringSpace, i = 0; i < TREE_NEL; key += STRING_SIZE, i++) { if (((key + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (1); }
str_rnd (key, STRING_SIZE);
if (tsearch (key, &root, (int (*) (const void *, const void *)) strcoll) == NULL) { fprintf (stderr, "%s: Поиск с вставкой в бинарное" " дерево " "завершился неудачей\n", argv [0]); return (2); } } /* for */
/* Подсчитаем число узлов и высоту созданного дерева */ node_count = 0; max_level = 0; twalk (root, tw_nnh); printf ("В дереве оказалось %d узлов\n", node_count); printf ("Его высота равна %d\n", max_level);
/* Распечатаем несколько первых (по алфавиту) цепочек, */ /* помещенных в созданное дерево */ node_count = 10; printf ("Первые %d по алфавиту цепочек в дереве:\n", node_count); if (setjmp (buf_env) == 0) { twalk (root, tw_pfs); }
/* Будем формировать и искать новые случайные цепочки */ ntr = 0; do { str_rnd (sbuf, STRING_SIZE); ntr++; } while (tdelete (sbuf, &root, (int (*) (const void *, const void *)) strcoll) == NULL); printf ("Удалось найти и удалить из дерева %g-ю по счету " "случайную цепочку %s\n", ntr, sbuf);
return 0; }

Листинг 9.27. Пример применения функций управления бинарными деревьями поиска.

Закрыть окно

В дереве оказалось 1000000 узлов Его высота равна 25 Первые 10 по алфавиту цепочек в дереве: AAAATNRAS AAACHCCLB AAACSJQBP AAADLHFAZ AAAFWLRXM AAAFXGQEC AAAGBMHHA AAAGFAXFI AAAHKLCWW AAAHLOSVQ Удалось найти и удалить из дерева 168221-ю по счету случайную цепочку VBBDZTNMZ real 20.24 user 20.25 sys 0.15

Листинг 9.28. Возможные результаты выполнения программы, применяющей функции управления бинарными деревьями поиска.

Закрыть окно

#include <search.h>
void insque (void *element, void *pred);
void remque (void *element);

Листинг 9.29. Описание функций, выполняющих операции над очередями.

Закрыть окно

#include <search.h>
. . . struct qelem { struct qelem *q_forw; struct qelem *q_back; char *data; . . . };
struct qelem element1; struct qelem element2;
. . . element1.q_forw = &element1; element1.q_back = &element1;
insque (&element2, &element1);
. . .

Листинг 9.30. Пример инициализации циклической очереди и вставки в нее второго элемента.

Закрыть окно

a b c d d e f g e f h h

Листинг 9.31. Пример исходных данных для служебной программы tsort.

Закрыть окно

a c h b d e f g

Листинг 9.32. Возможный результат применения служебной программы tsort.

Закрыть окно

#include <ucontext.h>
int getcontext (ucontext_t *ucp);
void makecontext (ucontext_t *ucp, void (*func) (void), int argc, ...);
int setcontext (const ucontext_t *ucp);
int swapcontext (ucontext_t *restrict oucp, const ucontext_t *restrict ucp);

Листинг 9.33. Описание функций, манипулирующих пользовательскими контекстами потоков управления.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * */ /* Программа демонстрирует применение функций, */ /* манипулирующих пользовательскими контекстами*/ /* * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h> #include <ucontext.h>
/* Размер стеков в формируемых пользовательских контекстах */ #define STACK_SIZE 4096
/* Пространство для стеков */ static char st1 [STACK_SIZE]; static char st2 [STACK_SIZE];
static ucontext_t ctx [3];
static void f1 (int arg) { printf ("Вызвана функция %s с аргументом %d\n", "f1", arg); if (swapcontext (&ctx [1], &ctx [2]) != 0) { perror ("SWAPCONTEXT-1"); } printf ("Выход из функции %s\n", "f1"); }
static void f2 (int arg1, int arg2) { printf ("Вызвана функция %s с аргументами %d, %d\n", "f2", arg1, arg2); if (swapcontext (&ctx [2], &ctx [1]) != 0) { perror ("SWAPCONTEXT-2"); } printf ("Выход из функции %s\n", "f2"); }
int main (void) { (void) getcontext (&ctx [1]);
printf ("Параметры первоначального контекста:\n" "адрес стека %p, размер стека %d\n", ctx[1].uc_stack.ss_sp, ctx[1].uc_stack.ss_size);
/* В соответствии с общими рекомендациями */ /* позаботимся о стеке для модифицируемых контекстов */ ctx[1].uc_stack.ss_sp = st1; ctx[1].uc_stack.ss_size = sizeof (st1); ctx[1].uc_link = &ctx [0]; makecontext (&ctx [1], (void (*) (void)) f1, 1, 2);
(void) getcontext (&ctx [2]); ctx[2].uc_stack.ss_sp = st2; ctx[2].uc_stack.ss_size = sizeof (st2); ctx[2].uc_link = &ctx [1]; makecontext (&ctx [2], (void (*) (void)) f2, 2, 3, 4); if (swapcontext (&ctx [0], &ctx [2]) != 0) { perror ("SWAPCONTEXT-3"); return (1); }
return 0; }

Листинг 9.34. Пример применения функций, манипулирующих пользовательскими контекстами.

Закрыть окно

Параметры первоначального контекста: адрес стека (nil), размер стека 0 Вызвана функция f2 с аргументами 3, 4 Вызвана функция f1 с аргументом 2 Выход из функции f2 Выход из функции f1

Листинг 9.35. Возможные результаты выполнения программы, применяющей функции манипулирования пользовательскими контекстами.

Закрыть окно

#include <fenv.h>
int fegetenv (fenv_t *fenvp);
int fesetenv (const fenv_t *fenvp);

Листинг 9.36. Описание функций опроса и установки текущей среды вещественной арифметики.

Закрыть окно

#include <fenv.h> int feholdexcept (fenv_t *fenvp);

Листинг 9.37. Описание функции feholdexcept().

Закрыть окно

#include <fenv.h> int feupdateenv (const fenv_t *fenvp);

Листинг 9.38. Описание функции feupdateenv().

Закрыть окно

#include <fenv.h>
int fegetexceptflag (fexcept_t *flagp, int excepts);
int fesetexceptflag (const fexcept_t *flagp, int excepts);

Листинг 9.39. Описание функций опроса и установки флагов состояния среды вещественной арифметики.

Закрыть окно

#include <fenv.h>
int fetestexcept (int excepts);
int feclearexcept (int excepts);
int feraiseexcept (int excepts);

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

Закрыть окно

#include <fenv.h>
int fegetround (void);
int fesetround (int round);

Листинг 9.41. Описание функций опроса и установки режима округления.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа демонстрирует применение некоторых функций */ /* управления средой вещественной арифметики */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h> #include <fenv.h>
#pragma STDC FENV_ACCESS ON
int main (void) { double d1, d2, d3, s; int res;
printf ("Представление флагов состояния вещественной " "арифметики\n"); printf (" FE_DIVBYZERO: %x\n", FE_DIVBYZERO); printf (" FE_INEXACT: %x\n", FE_INEXACT); printf (" FE_INVALID: %x\n", FE_INVALID); printf (" FE_OVERFLOW: %x\n", FE_OVERFLOW); printf (" FE_UNDERFLOW: %x\n", FE_UNDERFLOW);
printf ("Представление режимов округления\n"); printf (" FE_DOWNWARD: %x\n", FE_DOWNWARD); printf (" FE_TONEAREST: %x\n", FE_TONEAREST); printf (" FE_TOWARDZERO: %x\n", FE_TOWARDZERO); printf (" FE_UPWARD: %x\n", FE_UPWARD);
printf ("Текущие исключительные ситуации: %x\n", fetestexcept (FE_ALL_EXCEPT)); printf ("Текущий режим округления: %x\n", fegetround ());
feclearexcept (FE_ALL_EXCEPT);
/* Вызовем ситуацию исчезновения порядка */ d1 = 1; do { d1 /= 2; } while ((res = fetestexcept (FE_ALL_EXCEPT)) == 0); printf ("Исключительные ситуации: %x\n", res); printf ("2^-inf: %g\n", d1);
feclearexcept (res); /* Вызовем ситуацию переполнения */ d2 = 1; do { d2 *= 2; } while ((res = fetestexcept (FE_ALL_EXCEPT)) == 0); printf ("Исключительные ситуации: %x\n", res); printf ("2^+inf: %g\n", d2);
feclearexcept (res);
/* Вызовем ситуацию деления на нуль */ d3 = 1 / d1; res = fetestexcept (FE_ALL_EXCEPT); printf ("Исключительные ситуации: %x\n", res); printf ("1/0: %g\n", d3);
feclearexcept (res);
/* Пример того, как может возникать потеря точности */ s = 1; do { s = (s + 2 / s) * 0.5; } while ((s * s – 2) > 0); printf ("Исключительные ситуации: %x\n", fetestexcept (FE_ALL_EXCEPT)); printf ("sqrt (2): %g\n", s);
return 0; }

Листинг 9.42. Пример применения некоторых функций управления средой вещественной арифметики.

Закрыть окно

Представление флагов состояния вещественной арифметики FE_DIVBYZERO: 4 FE_INEXACT: 20 FE_INVALID: 1 FE_OVERFLOW: 8 FE_UNDERFLOW: 10 Представление режимов округления FE_DOWNWARD: 400 FE_TONEAREST: 0 FE_TOWARDZERO: c00 FE_UPWARD: 800 Текущие исключительные ситуации: 0 Текущий режим округления: 0 Исключительные ситуации: 30 2^-inf: 0 Исключительные ситуации: 28 2^+inf: inf Исключительные ситуации: 4 1/0: inf Исключительные ситуации: 20 sqrt (2): 1.41421

Листинг 9.43. Возможные результаты выполнения программы, применяющей некоторые функции управления средой вещественной арифметики.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа реализует некоторые операции */ /* интервальной арифметики */ /* * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h> #include <fenv.h>
#pragma STDC FENV_ACCESS ON
/* Интервальное представление числа */ typedef struct ditvl { double lb; double ub; } ditvl_t;
/* * * * * * * * * * * * * * * * * * * * */ /* Сложение интервалов. */ /* Сумма помещается в выходной аргумент. */ /* Нормальный результат равен нулю */ /* * * * * * * * * * * * * * * * * * * * */ int ditvl_add (const ditvl_t *a1, const ditvl_t *a2, ditvl_t *res) { fenv_t cfenv;
/* Сохраним текущую среду вещественной арифметики */ if (fegetenv (&cfenv) != 0) { perror ("FEGETENV"); return (-1); }
/* Нижние границы нужно складывать с округлением вниз */ if (fesetround (FE_DOWNWARD) != 0) { perror ("FESETROUND"); return (-1); } res->lb = a1->lb + a2->lb;
/* Верхние границы складываются с округлением вверх */ if (fesetround (FE_UPWARD) != 0) { perror ("FESETROUND"); return (-1); } res->ub = a1->ub + a2->ub;
/* Восстановим среду вещественной арифметики */ if (fesetenv (&cfenv) != 0) { perror ("FESETENV"); return (-1); }
return 0; }
/* * * * * * * * */ /* Унарный минус */ /* * * * * * * * */ int ditvl_uminus (const ditvl_t *a, ditvl_t *res) { res->lb = -(a->ub); res->ub = -(a->lb);
return 0; }
/* * * * * * * * */ /* Вызов функций */ /* * * * * * * * */ int main (void) { ditvl_t pi = {3.141592, 3.141593}; ditvl_t e = {2.718281, 2.718282}; ditvl_t res; ditvl_t tmp;
printf ("Представление числа pi: (%f, %f)\n", pi.lb, pi.ub); printf ("Представление числа e: (%f, %f)\n", e.lb, e.ub);
/* Вычислим сумму pi и e */ (void) ditvl_add (&pi, &e, &res); printf ("Сумма pi и e: (%f, %f)\n", res.lb, res.ub);
/* Вычислим разность pi и e */ (void) ditvl_uminus (&e, &tmp); (void) ditvl_add (&pi, &tmp, &res); printf ("Разность pi и e: (%f, %f)\n", res.lb, res.ub);
printf ("Текущие исключительные ситуации: %x\n", fetestexcept (FE_ALL_EXCEPT)); printf ("Текущие режимы округления: %x\n", fegetround ());
return 0; }

Листинг 9.44. Пример использования различных режимов округления.

Закрыть окно

Представление числа pi: (3.141592, 3.141593) Представление числа e: (2.718281, 2.718282) Сумма pi и e: (5.859873, 5.859875) Разность pi и e: (0.423310, 0.423312) Текущие исключительные ситуации: 0 Текущие режимы округления: 0

Листинг 9.45. Возможные результаты выполнения программы, реализующей некоторые операции интервальной арифметики.

Закрыть окно

#include <ftw.h>
int ftw (const char *path, int (*fn) (const char *, const struct stat *, int), int depth);
int nftw (const char *path, int (*fn) (const char *, const struct stat *, int, struct FTW *), int depth, int flags);

Листинг 9.46. Описание функций обхода файловой иерархии.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * */ /* Программа определяет суммарный размер */ /* и высоту файловой иерархии */ /* * * * * * * * * * * * * * * * * * * * */
#define _XOPEN_SOURCE 600
#include <ftw.h> #include <stdio.h>
/* Суммарный размер файлов в иерархии */ static off_t fsize = 0;
/* Максимальный уровень файлов в иерархии */ static int flevel = 0;
/* * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, вызываемая для каждого файла в иерархии */ /* * * * * * * * * * * * * * * * * * * * * * * * * * */ static int nftwfunc (const char *filename, const struct stat *statptr, int filetype, struct FTW *pfwt) { /* Если установлен флаг FTW_NS, завершим обход */ if (filetype == FTW_NS) { perror ("STAT"); fprintf (stderr, "Отсутствуют данные о файле %s\n", filename); return 1; } fsize += statptr->st_size; if (pfwt->level > flevel) { flevel = pfwt->level; }
return 0; }
/* * * * * * * * * * * */ /* Организация обхода */ /* * * * * * * * * * * */ int main (int argc, char *argv []) { if (argc != 2) { fprintf (stderr, "Использование: %s корень_иерархии\n", argv [0]); return (1); }
if (nftw (argv [1], nftwfunc, 16, FTW_MOUNT | FTW_PHYS) == -1) { perror ("NFTW"); }
printf ("Суммарный размер обработанных файлов: %ld\n", fsize); printf ("Высота иерархии файлов: %d\n", flevel);
return 0; }

Листинг 9.47. Пример программы, осуществляющей обход файловой иерархии.

Закрыть окно

STAT: Permission denied Отсутствуют данные о файле /tmp/gaga/ gugu Суммарный размер обработанных файлов: 2645778 Высота иерархии файлов: 2

Листинг 9.48. Возможные результаты выполнения программы, осуществляющей обход файловой иерархии.

Закрыть окно

#include <stdlib.h> #include <fcntl.h> int posix_openpt (int oflag);

Листинг 9.49. Описание функции открытия главного устройства псевдотерминала.

Закрыть окно

#include <stdlib.h> int unlockpt (int masterfd);

Листинг 9.50. Описание функции разблокирования подчиненного устройства псевдотерминала.

Закрыть окно

#include <stdlib.h> int grantpt (int masterfd);

Листинг 9.51. Описание функции формирования прав доступа к подчиненному устройству псевдотерминала.

Закрыть окно

#include <stdlib.h> char *ptsname (int masterfd);

Листинг 9.52. Описание функции получения имени подчиненного устройства псевдотерминала.

Закрыть окно

/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа запускает shell на псевдотерминале */ /* * * * * * * * * * * * * * * * * * * * * * * * */
#define _XOPEN_SOURCE 600
#include <stdlib.h> #include <unistd.h> #include <stdio.h> #include <fcntl.h> #include <termios.h> #include <signal.h> #include <poll.h> #include <sys/resource.h> #include <curses.h>
/* * * * * * * * * * * * * * * * * * */ /* Действия при завершении процесса */ /* * * * * * * * * * * * * * * * * * */ static void termination (int errcode) { endwin (); exit (errcode); }
/* * * * * * * * * * * * * * * * * * */ /* Функция обработки сигнала SIGCHLD */ /* * * * * * * * * * * * * * * * * * */ static void chldied (int dummy) { /* Просто кончимся */ termination (34); }
/* * * * * * * * * * * * * * * * * * * * */ /* Организация работы с псевдотерминалом */ /* * * * * * * * * * * * * * * * * * * * */ int main (void) { WINDOW *win1, *win2; /* win1 – окно только для рамки */ /* win2 – окно для shell'а */
int pty, tty; /* Дескрипторы обеих сторон */ /* псевдотерминала */ int fr; /* Результат fork'а */ unsigned char ch; /* Прочитанный символ */ struct termios pt; /* Структура характеристик */ /* псевдотерминала */ struct pollfd fds [2]; /* Массив параметров для */ /* вызова poll */ int w2lines, w2cols; /* Размер создаваемого окна */ int x, y; /* Координаты в окне */ struct sigaction sact; int i;
initscr (); cbreak (); noecho ();
win1 = newwin (LINES, COLS, 0, 0); box (win1, 0, 0); wrefresh (win1);
w2lines = LINES – 2; w2cols = COLS – 4; win2 = newwin (w2lines, w2cols, 1, 2); scrollok (win2, TRUE);
/* Откроем псевдотерминал */ if (((pty = posix_openpt (O_RDWR | O_NOCTTY)) < 0) || (unlockpt (pty) == -1) || (grantpt (pty) == -1) || ((tty = open (ptsname (pty), O_RDWR)) < 0)) { fprintf (stderr, "Не удалось открыть псевдотерминал\n"); perror ("POSIX_OPENPT"); return (1); }
/* Установим подходящие характеристики псевдотерминала */ if (tcgetattr (pty, &pt) < 0) { perror ("PTY TERMIOS GET ERROR"); return (2); } pt.c_iflag = 0; pt.c_oflag = ONLCR; pt.c_cflag = CS8 | HUPCL; pt.c_lflag = ISIG | ICANON | ECHO | ECHOE | ECHOK; pt.c_cc [VINTR] = 3; /* CTRL+C */ pt.c_cc [VEOF] = 4; /* CTRL+D */ if (tcsetattr (pty, TCSADRAIN, &pt) < 0) { perror ("PTY TERMIOS SET ERROR"); return (3); }
/* То же – для стандартного ввода */ (void) tcgetattr (0, &pt); pt.c_lflag &= ~ISIG; (void) tcsetattr (0, TCSADRAIN, &pt);
/* Установим обработку сигнала о завершении потомка */ sact.sa_handler = chldied; (void) sigemptyset (&sact.sa_mask); sact.sa_flags = 0; (void) sigaction (SIGCHLD, &sact, (struct sigaction *) NULL);
/* Раздвоимся на процесс чтения с клавиатуры */ /* и вывода на экран и на процесс, */ /* в рамках которого запустим shell */
if ((fr = fork ()) < 0) { perror ("FORK1 ERROR"); termination (-1); } else if (fr) { /* Это процесс, читающий с клавиатуры */ /* и выводящий на экран */ close (tty);
/* Будем ждать ввода с клавиатуры или псевдотерминала */ fds [0].fd = 0; fds [0].events = POLLIN; fds [1].fd = pty; fds [1].events = POLLIN;
while (1) { if (poll (fds, 2, -1) < 0) { perror ("POLL ERROR"); termination (0); } if (fds [0].revents & POLLIN) { /* Пришел символ со стандартного ввода */ read (0, &ch, 1); write (pty, &ch, 1); } if (fds [1].revents & POLLIN) { /* Пришел символ с псевдотерминала */ read (pty, &ch, 1); switch (ch) { case '\n': { /* Проинтерпретируем перевод строки */ getyx (win2, y, x); if (y == (w2lines – 1)) { wmove (win2, y, w2cols – 1); waddch (win2, (chtype) ch); } else { wmove (win2, y + 1, 0); } break; } default: { /* Символ не интерпретируется */ waddch (win2, (chtype) ch); break; } } wrefresh (win2); } } /* Просто кончимся */ termination (0);
} else { /* Порожденный процесс – запустим в нем shell */ /* Закроем все файлы, кроме псевдотерминала */ for (i = 0; i < RLIMIT_NOFILE; i++) { if (i != tty) { (void) close (i); } }
/* Сделаем процесс лидером сеанса */ (void) setsid ();
/* Свяжем стандартные ввод, вывод и протокол */ /* с псевдотерминалом */ (void) fcntl (tty, F_DUPFD, 0); (void) fcntl (tty, F_DUPFD, 0); (void) fcntl (tty, F_DUPFD, 0); close (tty);
/* Поместим в окружение параметры псевдотерминала */ { char lnbuf [20]; char clbuf [20];
sprintf (lnbuf, "LINES=%2d", w2lines); sprintf (clbuf, "COLUMNS=%2d", w2cols);
putenv (lnbuf); putenv (clbuf); }
if (execl ("/bin/sh", "sh", (char *) NULL) < 0) { perror ("EXECL ERROR"); exit (-1); } }
return 0; }

Листинг 9.53. Пример программы, использующей псевдотерминалы.

Закрыть окно

Управление средой вещественной арифметики

Средства управления средой вещественной арифметики, включенные в стандарт POSIX-2001, позволяют выполнить требования двух других стандартов – вещественной арифметики (IEC 60559:1989) и языка C (ISO/IEC 9899:1999).

Среда вещественной арифметики включает сущности двух видов: флаги состояния и управляющие режимы.

Флаг состояния вещественной арифметики – это системная переменная, значение которой устанавливается (но никогда не очищается) при возбуждении исключительной ситуации и содержит дополнительную информацию о случившемся исключении.

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

Тип данных fenv_t, определенный в заголовочном файле <fenv.h>, представляет всю среду, тип fexcept_t – совокупность флагов состояния, включая ассоциированную с флагами информацию.

Применительно к вещественной арифметике стандарт POSIX-2001 предусматривает следующие исключительные ситуации: FE_DIVBYZERO (деление на нуль), FE_INEXACT (потеря точности), FE_INVALID (некорректная операция), FE_OVERFLOW (переполнение), FE_UNDERFLOW (исчезновение порядка). Побитное ИЛИ перечисленных констант обозначается как FE_ALL_EXCEPT.

Стандартом специфицированы четыре режима (направления) округления: FE_DOWNWARD (вниз, то есть к минус бесконечности), FE_TONEAREST (к ближайшему представимому), FE_TOWARDZERO (к нулю), FE_UPWARD (вверх, то есть к плюс бесконечности).

Подразумеваемая среда вещественной арифметики (существующая на момент начала выполнения прикладной программы) обозначается константой FE_DFL_ENV, имеющей тип указателя на константный объект типа fenv_t.

Если приложение проверяет флаги состояния, устанавливает собственные управляющие режимы или выполняется в режимах, отличных от подразумеваемого, то при компиляции необходимо воспользоваться управляющим комментарием (#pragma) FENV_ACCESS:

#pragma STDC FENV_ACCESS ON

Опросить и установить текущую среду вещественной арифметики можно с помощью функций fegetenv() и fesetenv() (см.
Функция fesetexceptflag() выполняет обратную операцию. Как и в случае функции fesetenv(), исключительные ситуации при этом не возбуждаются.

Функции fetestexcept(), feclearexcept() и feraiseexcept() (см. листинг 9.40) служат, соответственно, для проверки, сброса и возбуждения исключительных ситуаций.

#include <fenv.h>

int fetestexcept (int excepts);

int feclearexcept (int excepts);

int feraiseexcept (int excepts);

Листинг 9.40. Описание функций проверки, сброса и возбуждения исключительных ситуаций. (html, txt)

Функция fetestexcept() проверяет, какие из флагов, заданные аргументом excepts, в данный момент установлены; результатом служит их побитное ИЛИ.

Функция feclearexcept() пытается сбросить, а feraiseexcept() – возбудить заданные исключительные ситуации. Побочным эффектом возбуждения ситуаций переполнения (FE_OVERFLOW) и исчезновения порядка (FE_UNDERFLOW) может стать потеря точности (FE_INEXACT).

Опросить и установить режим округления можно с помощью функций fegetround() и fesetround() (см. листинг 9.41).

#include <fenv.h>

int fegetround (void);

int fesetround (int round);

Листинг 9.41. Описание функций опроса и установки режима округления. (html, txt)

Свидетельством неудачного завершения функции fegetround() служит отрицательный результат.

Продемонстрируем применение некоторых функций управления средой вещественной арифметики (см. листинг 9.42).

Листинг 9.42. Пример применения некоторых функций управления средой вещественной арифметики. (html, txt)

Возможные результаты выполнения приведенной программы показаны на листинге 9.43.

Листинг 9.43. Возможные результаты выполнения программы, применяющей некоторые функции управления средой вещественной арифметики. (html, txt)

Отметим, что и для исключительных ситуаций, и для режима округления подразумеваемые значения равны нулю, но нули это разные: первый свидетельствует об отсутствии исключений, в то время как второй обозначает режим округления до ближайшего представимого числа.

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

В качестве второго примера рассмотрим программу, реализующую некоторые операции интервальной арифметики (см. листинг 9.44).

Листинг 9.44. Пример использования различных режимов округления. (html, txt)

Программа переустанавливает режимы округления, поскольку при сложении нижних границ интервалов округлять нужно вниз, а при сложении верхних – вверх. Разумеется, в функции ditvl_add() для сохранения и восстановления режима округления можно было воспользоваться функциями fegetround()/fesetround(), а не fegetenv()/fesetenv().

На листинге 9.45 показаны возможные результаты выполнения приведенной программы.

Листинг 9.45. Возможные результаты выполнения программы, реализующей некоторые операции интервальной арифметики. (html, txt)

Отметим, что в завершающей части программы подразумеваемая среда вещественной арифметики оказалась успешно восстановленной.

листинг 9.36).

#include <fenv.h>

int fegetenv (fenv_t *fenvp);

int fesetenv (const fenv_t *fenvp);

Листинг 9.36. Описание функций опроса и установки текущей среды вещественной арифметики.

Отметим, что функция fesetenv() не возбуждает исключительных ситуаций, она только задает значения флагов состояния. Нормальным для обеих функций является нулевой результат.

Сохранение текущей среды может сочетаться с ее изменением. Так, функция feholdexcept() (см. листинг 9.37) не только запоминает текущую среду по указателю fenvp, но также очищает флаги состояния и устанавливает "безостановочный" режим (продолжать выполнение при возникновении исключительных ситуаций вещественной арифметики). Очевидно, пользоваться функцией feholdexcept() имеет смысл, если, помимо безостановочного, реализация предоставляет другие режимы обработки исключений.

#include <fenv.h> int feholdexcept (fenv_t *fenvp);

Листинг 9.37. Описание функции feholdexcept().

Функция feupdateenv() (см. листинг 9.38) выполняет еще более сложные действия. Она сохраняет в своей локальной памяти информацию о текущей исключительной ситуации, устанавливает новую среду по аргументу fenvp и затем пытается возбудить в ней сохраненное исключение. Подобные манипуляции полезны, когда массовые вычисления производятся в безостановочном режиме, а затем режим меняется и обрабатывается все то нехорошее, что накопилось за это время.

#include <fenv.h> int feupdateenv (const fenv_t *fenvp);

Листинг 9.38. Описание функции feupdateenv().

Для опроса и установки флагов состояния стандартом POSIX-2001 предусмотрены функции fegetexceptflag() и fesetexceptflag() (см. листинг 9.39).

#include <fenv.h>

int fegetexceptflag (fexcept_t *flagp, int excepts);

int fesetexceptflag (const fexcept_t *flagp, int excepts);

Листинг 9.39. Описание функций опроса и установки флагов состояния среды вещественной арифметики.

Функция fegetexceptflag() помещает по указателю flagp зависящее от реализации представление флагов, заданных аргументом excepts, и ассоциированной с ними информации.

Функция fesetexceptflag() выполняет обратную операцию. Как и в случае функции fesetenv(), исключительные ситуации при этом не возбуждаются.

Функции fetestexcept(), feclearexcept() и feraiseexcept() (см. листинг 9.40) служат, соответственно, для проверки, сброса и возбуждения исключительных ситуаций.

#include <fenv.h>

int fetestexcept (int excepts);

int feclearexcept (int excepts);

int feraiseexcept (int excepts);

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

Функция fetestexcept() проверяет, какие из флагов, заданные аргументом excepts, в данный момент установлены; результатом служит их побитное ИЛИ.

Функция feclearexcept() пытается сбросить, а feraiseexcept() – возбудить заданные исключительные ситуации. Побочным эффектом возбуждения ситуаций переполнения (FE_OVERFLOW) и исчезновения порядка (FE_UNDERFLOW) может стать потеря точности (FE_INEXACT).

Опросить и установить режим округления можно с помощью функций fegetround() и fesetround() (см. листинг 9.41).

#include <fenv.h>

int fegetround (void);

int fesetround (int round);

Листинг 9.41. Описание функций опроса и установки режима округления.

Свидетельством неудачного завершения функции fegetround() служит отрицательный результат.

Продемонстрируем применение некоторых функций управления средой вещественной арифметики (см. листинг 9.42).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа демонстрирует применение некоторых функций */ /* управления средой вещественной арифметики */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h> #include <fenv.h>

#pragma STDC FENV_ACCESS ON

int main (void) { double d1, d2, d3, s; int res;

printf ("Представление флагов состояния вещественной " "арифметики\n"); printf (" FE_DIVBYZERO: %x\n", FE_DIVBYZERO); printf (" FE_INEXACT: %x\n", FE_INEXACT); printf (" FE_INVALID: %x\n", FE_INVALID); printf (" FE_OVERFLOW: %x\n", FE_OVERFLOW); printf (" FE_UNDERFLOW: %x\n", FE_UNDERFLOW);

printf ("Представление режимов округления\n"); printf (" FE_DOWNWARD: %x\n", FE_DOWNWARD); printf (" FE_TONEAREST: %x\n", FE_TONEAREST); printf (" FE_TOWARDZERO: %x\n", FE_TOWARDZERO); printf (" FE_UPWARD: %x\n", FE_UPWARD);

printf ("Текущие исключительные ситуации: %x\n", fetestexcept (FE_ALL_EXCEPT)); printf ("Текущий режим округления: %x\n", fegetround ());

feclearexcept (FE_ALL_EXCEPT);

/* Вызовем ситуацию исчезновения порядка */ d1 = 1; do { d1 /= 2; } while ((res = fetestexcept (FE_ALL_EXCEPT)) == 0); printf ("Исключительные ситуации: %x\n", res); printf ("2^-inf: %g\n", d1);

feclearexcept (res); /* Вызовем ситуацию переполнения */ d2 = 1; do { d2 *= 2; } while ((res = fetestexcept (FE_ALL_EXCEPT)) == 0); printf ("Исключительные ситуации: %x\n", res); printf ("2^+inf: %g\n", d2);

feclearexcept (res);

/* Вызовем ситуацию деления на нуль */ d3 = 1 / d1; res = fetestexcept (FE_ALL_EXCEPT); printf ("Исключительные ситуации: %x\n", res); printf ("1/0: %g\n", d3);

feclearexcept (res);

/* Пример того, как может возникать потеря точности */ s = 1; do { s = (s + 2 / s) * 0.5; } while ((s * s – 2) > 0); printf ("Исключительные ситуации: %x\n", fetestexcept (FE_ALL_EXCEPT)); printf ("sqrt (2): %g\n", s);

return 0; }

Листинг 9.42. Пример применения некоторых функций управления средой вещественной арифметики.

Возможные результаты выполнения приведенной программы показаны на листинге 9.43.

Представление флагов состояния вещественной арифметики FE_DIVBYZERO: 4 FE_INEXACT: 20 FE_INVALID: 1 FE_OVERFLOW: 8 FE_UNDERFLOW: 10 Представление режимов округления FE_DOWNWARD: 400 FE_TONEAREST: 0 FE_TOWARDZERO: c00 FE_UPWARD: 800 Текущие исключительные ситуации: 0 Текущий режим округления: 0 Исключительные ситуации: 30 2^-inf: 0 Исключительные ситуации: 28 2^+inf: inf Исключительные ситуации: 4 1/0: inf Исключительные ситуации: 20 sqrt (2): 1.41421

Листинг 9.43. Возможные результаты выполнения программы, применяющей некоторые функции управления средой вещественной арифметики.

Отметим, что и для исключительных ситуаций, и для режима округления подразумеваемые значения равны нулю, но нули это разные: первый свидетельствует об отсутствии исключений, в то время как второй обозначает режим округления до ближайшего представимого числа.

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

В качестве второго примера рассмотрим программу, реализующую некоторые операции интервальной арифметики (см. листинг 9.44).

/* * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа реализует некоторые операции */ /* интервальной арифметики */ /* * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h> #include <fenv.h>

#pragma STDC FENV_ACCESS ON

/* Интервальное представление числа */ typedef struct ditvl { double lb; double ub; } ditvl_t;

/* * * * * * * * * * * * * * * * * * * * */ /* Сложение интервалов. */ /* Сумма помещается в выходной аргумент. */ /* Нормальный результат равен нулю */ /* * * * * * * * * * * * * * * * * * * * */ int ditvl_add (const ditvl_t *a1, const ditvl_t *a2, ditvl_t *res) { fenv_t cfenv;

/* Сохраним текущую среду вещественной арифметики */ if (fegetenv (&cfenv) != 0) { perror ("FEGETENV"); return (-1); }

/* Нижние границы нужно складывать с округлением вниз */ if (fesetround (FE_DOWNWARD) != 0) { perror ("FESETROUND"); return (-1); } res->lb = a1->lb + a2->lb;

/* Верхние границы складываются с округлением вверх */ if (fesetround (FE_UPWARD) != 0) { perror ("FESETROUND"); return (-1); } res->ub = a1->ub + a2->ub;

/* Восстановим среду вещественной арифметики */ if (fesetenv (&cfenv) != 0) { perror ("FESETENV"); return (-1); }

return 0; }

/* * * * * * * * */ /* Унарный минус */ /* * * * * * * * */ int ditvl_uminus (const ditvl_t *a, ditvl_t *res) { res->lb = -(a->ub); res->ub = -(a->lb);

return 0; }

/* * * * * * * * */ /* Вызов функций */ /* * * * * * * * */ int main (void) { ditvl_t pi = {3.141592, 3.141593}; ditvl_t e = {2.718281, 2.718282}; ditvl_t res; ditvl_t tmp;

printf ("Представление числа pi: (%f, %f)\n", pi.lb, pi.ub); printf ("Представление числа e: (%f, %f)\n", e.lb, e.ub);

/* Вычислим сумму pi и e */ (void) ditvl_add (&pi, &e, &res); printf ("Сумма pi и e: (%f, %f)\n", res.lb, res.ub);

/* Вычислим разность pi и e */ (void) ditvl_uminus (&e, &tmp); (void) ditvl_add (&pi, &tmp, &res); printf ("Разность pi и e: (%f, %f)\n", res.lb, res.ub);

printf ("Текущие исключительные ситуации: %x\n", fetestexcept (FE_ALL_EXCEPT)); printf ("Текущие режимы округления: %x\n", fegetround ());

return 0; }

Листинг 9.44. Пример использования различных режимов округления.

Программа переустанавливает режимы округления, поскольку при сложении нижних границ интервалов округлять нужно вниз, а при сложении верхних – вверх. Разумеется, в функции ditvl_add() для сохранения и восстановления режима округления можно было воспользоваться функциями fegetround()/fesetround(), а не fegetenv()/fesetenv().

На листинге 9.45 показаны возможные результаты выполнения приведенной программы.

Представление числа pi: (3.141592, 3.141593) Представление числа e: (2.718281, 2.718282) Сумма pi и e: (5.859873, 5.859875) Разность pi и e: (0.423310, 0.423312) Текущие исключительные ситуации: 0 Текущие режимы округления: 0

Листинг 9.45. Возможные результаты выполнения программы, реализующей некоторые операции интервальной арифметики.

Отметим, что в завершающей части программы подразумеваемая среда вещественной арифметики оказалась успешно восстановленной.