Арнольд Роббинс - Linux программирование в примерах
$ cat presdata.txt
Bush George 43 980013600
Clinton William 42 727552800
Bush George 41 601322400
Reagan Ronald 40 348861600
Carter James 39 222631200
Данные сортируются на основе сначала фамилии, затем имени, а затем старшинства. При запуске[160] программа выдает следующий результат:
$ ch14-tsearch < presdata.txt
Depth: 1. Employee:
Bush, George 41 Fri Jan 20 13:00:00 1989
Depth: 0. Employee:
Bush, George 43 Sat Jan 20 13:00:00 2001
Depth: 2. Employee:
Carter, James 39 Thu Jan 20 13:00:00 1977
Depth: 1. Employee:
Clinton, William 42 Wed Jan 20 13:00:00 1993
Depth: 2. Employee:
Reagan, Ronald 40 Tue Jan 20 13:00:00 1981
14.4.6. Удаление вершины дерева и удаление дерева: tdelete() и tdestroy()
Наконец, вы можете удалить элементы из дерева и, на системах GLIBC, удалить само дерево целиком:
void *tdelete(const void *key, void **rootp,
int (*compare)(const void*, const void*));
/* Расширение GLIBC, в POSIX нет: */
void tdestroy(void *root, void (*free_node)(void *nodep));
Аргументы для tdelete() те же, что и для tsearch(): ключ, адрес корня дерева и функция сравнения. Если в дереве найден данный элемент, он удаляется, и tdelete() возвращает указатель на родительскую вершину. В противном случае возвращается NULL. С этим поведением следует обращаться в своем коде осмотрительно, если вам нужен первоначальный удаляемый элемент, например, для освобождения занимаемой им памяти.
struct employee *е, key; /* Объявления переменных */
void *vp, *root;
/* ...заполнить ключ для удаляемого из дерева элемента... */
vp = tfind(&key, root, emp_name_id_compare); /* Найти удаляемый элемент */
if (vp != NULL) {
e = *((struct employee**)vp); /* Преобразовать указатель */
free(e); /* Освободить память */
}
(void)tdelete(&key, &root, emp_name_id_compare); /* Теперь удалить его из дерева */
Хотя это и не указано в справочных страницах или стандарте POSIX, под GNU/Linux, если вы удаляете элемент, хранящийся в корневой вершине, возвращается значение новой корневой вершины. Для переносимого кода не следует полагаться на это поведение
Функция tdestroy() является расширением GLIBC. Она позволяет удалить дерево целиком. Первый аргумент является корнем дерева. Второй является указателем на функцию, которая освобождает данные, на которые указывает каждая вершина дерева. Если с этими данными ничего не надо делать (например, они хранятся в обычном массиве, как в примере нашей программы), эта функция ничего не должна делать. Не передавайте указатель NULL! Это приведет к аварийной ситуации.
14.5. Резюме
• Иногда бывает необходимо выделить память, выровненную по определенной границе. Это осуществляет posix_memalign(). Ее возвращаемое значение отличается от большинства из рассмотренных в данной книге функций. memalign() также выделяет выровненную память, но не все системы поддерживают освобождение памяти с помощью free().
• Блокирование файлов с помощью fcntl() предусматривает блокировку диапазонов, вплоть до блокирования отдельных байтов в файле. Блокировки чтения предотвращают запись в заблокированную область, а блокировки записи предотвращают чтение и запись другими процессами в заблокированную область. По умолчанию используется вспомогательная блокировка, и POSIX стандартизует лишь вспомогательную блокировку. Большинство современных систем Unix поддерживают обязательную блокировку, используя для файла бит setgid прав доступа, а также возможные дополнительные опции монтирования файловой системы.
• GNU/Linux функция lockf() действует в качестве оболочки вокруг блокировки POSIX с помощью fcntl(); блокировки функции BSD flock() совершенно независимы от блокировок fcntl(). Блокировки BSD flock() используются лишь для всего файла в целом и не работают на удаленных файловых системах. По этим причинам использование блокировки flock() не рекомендуется.
• gettimeofday() получает время дня в виде пар (секунды, микросекунды) в struct timeval. Эти значения используются utimes() для обновления времени доступа и модификации файла. Системные вызовы gettimer() и settimer() используют пары struct timeval в struct itimerval для создания интервальных таймеров — сигнальных часов, которые «срабатывают» в установленное время и продолжают срабатывать впоследствии с заданным интервалом. Три различных таймера обеспечивают контроль тех состояний, когда таймер продолжает действовать.
• Функция nanosleep() использует struct timespec, которая указывает время в секундах и наносекундах, чтобы приостановить выполнение процесса в течение определенного интервала времени. У нее есть удачная особенность не взаимодействовать вообще с механизмами сигналов.
• Три API являются стандартным набором функций для хранения и поиска данных, которые сохраняют данные в двоичных деревьях в отсортированном виде. Эти три API очень гибкие, позволяя использовать множество деревьев и произвольные данные.
Упражнения
1. Напишите функцию lockf(), используя fcntl() для осуществления блокировки.
2. Каталог /usr/src/linux/Documentation содержит набор файлов, которые описывают различные аспекты поведения операционной системы. Прочитайте файлы locks.txt и mandatory.txt, чтобы получить больше сведений об обработке Linux блокировок файлов.
3. Запустите на своей системе программу ch14-lockall без обязательной блокировки и посмотрите, сможете ли изменить файл-операнд.
4. Если у вас не-Linux система, поддерживающая обязательную блокировку, попробуйте исполнить на ней программу ch14-lockall.
5. Напишите функцию strftimes() следующего вида:
size_t strftimes(char *buf, size_t size, const char *format,
const struct timeval *tp);
Она должна вести себя подобно стандартной функции strftime() за тем исключением, что должна использовать %q для обозначения «текущего числа микросекунд».
6. Используя только что написанную функцию strftimes(), напишите расширенную версию date, которая принимает форматирующую строку, начинающуюся с ведущего +, и форматирует текущие дату и время (см. date(1)).
7. Обработка тайм-аута в ch14-timers.c довольно примитивна. Перепишите программу с использованием setjmp() после вывода приглашения и longjmp() из обработчика сигнала. Улучшает ли это структуру или ясность программы?
8. Мы заметили, что ch14-timers.c содержит намеренное состояние гонки. Предположим, пользователь вводит ответ в нужное время, но ch14-timers приостановлена, прежде чем сигнал может быть отменен. Какой вызов вы сделаете, чтобы уменьшить размер проблемного окна?
9. Нарисуйте дерево, как показано в выводе ch14-tsearch в разделе 14.4.5 «Обход дерева: twalk()».
10. Исследуйте файл /usr/share/dict/words на системе GNU/Linux. (Это словарь проверки правописания для spell; на различных системах он может находиться в разных местах.) В файле слова размешены в отсортированном порядке, по одному в строке.
Для начала используйте программу awk для создания нового списка в случайном порядке:
$ awk '{ list[$0]++ }
> END { for (i in list) print i }' /usr/share/dict/words > /tmp/wlist
Далее, напишите две программы. Каждая должна читать новый список и сохранять каждое прочитанное слово в дереве и массиве соответственно. Вторая программа должна использовать для сортировки массива qsort(), а для поиска — bsearch(). Получите из дерева или массива слово 'gravy'. Вычислите время работы двух программ, чтобы увидеть, какая быстрее. Вам может потребоваться заключить получение слова внутрь цикла, повторяющегося множество раз (скажем, 1000), чтобы получить достаточное для определения разницы время.
Используйте вывод ps, чтобы посмотреть, сколько памяти используют программы
11. Повторно запустите обе программы, использовав оригинальный отсортированный словарный файл, и посмотрите, как изменятся временные результаты (если они вообще изменятся).
Часть 3
Отладка и заключительный проект
Глава 15
Отладка
Имеется множество правил, начиная с логики программы и расположения данных, через организацию и расположение кода и кончая реализацией, которые могут минимизировать ошибки и проблемы. Мы рекомендуем вам изучить их; найдите хорошие книги по проектированию и дизайну программного обеспечения и реализуйте содержащиеся там советы на практике! Каждая программа, размером превышающая несколько сот строк кода, должна быть тщательно продумана и спроектирована, а не обтяпана, пока не начнет работать.
