Текст книги "Linux программирование в примерах"
Автор книги: Арнольд Роббинс
Жанры:
Программирование
,сообщить о нарушении
Текущая страница: 46 (всего у книги 55 страниц)
tfind() и tsearch()Функции tfind() и tsearch() осуществляют поиск в двоичном дереве по данному ключу. Они принимают тот же самый набор аргументов: ключ для поиска key. указатель на корень дерева, rootp; и compare, указатель на функцию сравнения. Обе функции возвращают указатель на вершину, которая соответствует key.
Как именно использовать указатель, возвращенный tfind() и tsearch()? Во всяком случае, на что именно он указывает? Ответ заключается в том, что он указывает на вершину в дереве. Это внутренний тип; вы не можете увидеть, как он определен. Однако, POSIX гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает:
struct employee { /* Из главы 6 */
char lastname[30];
char firstname[30];
long emp_id;
time_t start_date;
};
/* emp_name_id_compare – сравнение по имени, затем no ID */
int emp_name_id_compare(const void *e1p, const void *e2p) {
/* ...также из главы 6, полностью представлено позже... */
}
struct employee key = { ... };
void *vp, *root;
struct employee *e;
/* ...заполнение данными... */
vp = tfind(&key, root, emp_name_id_compare);
if (vp != NULL) { /* it's there, use it */
e = *((struct employee**)vp); /* Получить хранящиеся в дереве данные */
/* использование данных в *е ... */
}
Как можно указатель на вершину использовать как указатель на указатель данных? Рассмотрим, как была бы реализована вершина двоичного дерева. В каждой вершине хранится по крайней мере указатель на элемент данных пользователя и указатели на потенциальные порожденные вершины справа и слева. Поэтому она должна выглядеть примерно так.
struct binary_tree {
void *user_data; /* Указатель на данные пользователя */
struct binary_tree *left; /* Порожденная вершина слева или NULL */
struct binary_tree *right; /* Порожденная вершина справа или NULL */
/* ...здесь возможны другие поля... */
} node;
С и C++ гарантируют, что поля внутри структуры располагаются в порядке возрастания адресов. Таким образом, выражение '&node.left < &node.right' истинно. Более того, адрес структуры является также адресом ее первого поля (другими словами, игнорируя проблемы типов, '&node == &node.user_data').
Следовательно, концептуально 'е = *((struct employee**)vp);' означает:
1. vp является void*, то есть общим указателем. Это адрес внутренней вершины дерева, но это также адрес части вершины (скорее всего, другого void*), которая указывает на данные пользователя.
2. '(struct employee**)vp' приводит адрес внутреннего указателя к нужному типу; он остается указателем на указатель, но в этот раз на struct employee. Помните, что приведение одного типа указателя к другому не изменяют значения (паттерна битов); оно меняет лишь способ интерпретации компилятором значения для анализа типов.
3. '*((struct employee**)vp)' разыменовывает вновь созданный struct employee**, возвращая годный к употреблению указатель struct employee*.
4. 'е = *((struct employee**)vp)' сохраняет это значение в е для непосредственного использования позже.
Идея проиллюстрирована на рис. 14.2.
Рис. 14.2. Вершины дерева и их указатели
Для упрощения использования возвращенного указателя вы могли бы рассмотреть определение макроса:
#define tree_data(ptr, type)(*(type**)(ptr))
...
struct employee *e;
void *vp;
vp = tfind(&key, root, emp_name_id_compare);
if (vp != NULL) { /* it's there, use it */
e = tree_data(vp, struct employee);
/* использование сведений в *e ... */
}
twalk()Функция twalk() объявлена в
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void twalk(const void *root,
void (*action)(const void *nodep, const VISIT which,
const int depth));
Первый параметр является корнем дерева (не указателем на корень). Второй является указателем на функцию обратного вызова, которая вызывается с тремя аргументами, указателем на исследуемую вершину дерева; типом перечисления, указывающим, как осуществляется обход данной вершины; и целого, обозначающего глубину текущей вершины (корень находится на глубине 0, как объяснялось ранее).
Использование функции обратного вызова здесь такое же, как для nftw() (см. раздел 8.4.3.2 «Функция обратного вызова nftw()»). Там функция обратного вызова вызывается для каждого объекта в файловой системе. Здесь функция обратного вызова вызывается для каждого объекта, хранящегося в дереве.
Есть несколько способов прохождения, или «обхода», двоичного дерева:
• Левая вершина, родительская вершина, правая вершина.
• Родительская вершина, левая вершина, правая вершина.
• Левая вершина, правая вершина, родительская вершина.
Функция GLIBC twalk() использует второй способ: сначала родительская вершина, затем левая, затем правая. Каждый раз при встрече с вершиной говорят, что она посещается.[159]159
В голову приходят образы, как маленькие двоичные структуры данных сидят друг рядом с другом за чаем и пирожными. По крайней мере, такое бывает, если вы проводите слишком много времени перед своим компьютером. – Примеч. автора.
[Закрыть] В ходе посещения порожденной вершины функция должна посетить и родительскую. Соответственно, значения типа VISIT указывают, на какой стадии произошла встреча с этой вершиной:
preorder До посещения порожденных.
postorder После посещения первой, но до посещения второй порожденной вершины.
endorder После посещения обеих порожденных.
leaf Эта вершина является концевой, не имеющей порожденных вершин.
ЗАМЕЧАНИЕ. Использованная здесь терминология не соответствует точно той, которая используется в формальных руководствах по структурированию данных. Там используются термины inorder, preorder и postorder для обозначения соответствующих трех перечисленных ранее способов прохождения дерева. Таким образом,
twalk()использует прохождение по типуpreorder, но использует именованные константы preorder и т.д. для обозначения того, на какой стадии была посещена вершина. Это может сбивать с толку.
Следующая программа, ch14-tsearch.c, демонстрирует построение и обход дерева. Она повторно использует структуру struct employee и функцию emp_name_id_compare() из раздела 6.2 «Функции сортировки и поиска».
1 /* ch14-tsearch.c – демонстрация управления деревом */
2
3 #include
4 #include
5 #include
6
7 struct employee {
8 char lastname[30];
9 char firstname[30];
10 long emp_id;
11 time_t start_date;
12 };
13
14 /* emp_name_id_compare – сравнение по имени, затем no ID */
15
16 int emp_name_id_compare(const void *e1p, const void *e2p)
17 {
18 const struct employee *e1, *e2;
19 int last, first;
20
21 e1 = (const struct employee*)e1p;
22 e2 = (const struct employee*)e2p;
23
24 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)
25 return last;
26
27 /* фамилии совпадают, проверить имена */
28 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)
29 return first;
30
31 /* имена совпадают, проверить ID */
32 if (e1->emp_id < e2->emp_id)
33 return -1;
34 else if (e1->emp_id == e2->emp_id)
35 return 0;
36 else
37 return 1;
38 }
39
40 /* print_emp – вывод структуры employee во время обхода дерева */
41
42 void print_emp(const void *nodep, const VISIT which, const int depth)
43 {
44 struct employee *e = *((struct employee**)nodep);
45
46 switch (which) {
47 case leaf:
48 case postorder:
49 printf("Depth: %d. Employee: n", depth);
50 printf("t%s, %st%dt%sn", e->lastname, e->firstname,
51 e->emp_id, ctime(&e->start_date));
52 break;
53 default:
54 break;
55 }
56 }
Строки 7–12 определяют struct employee, а строки 14–38 определяют emp_name_id_compare().
Строки 40–56 определяют print_emp(), функцию обратного вызова, которая выводит struct employee наряду с глубиной дерева в текущей вершине. Обратите внимание на магическое приведение типа в строке 44 для получения указателя на сохраненные данные.
58 /* main – демонстрация хранения данных в двоичном дереве */
59
60 int main(void)
61 {
62 #define NPRES 10
63 struct employee presidents[NPRES];
64 int i, npres;
65 char buf[BUFSIZ];
66 void *root = NULL;
67
68 /* Очень простой код для чтения данных: */
69 for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;
70 npres++) {
71 sscanf(buf, "%s %s %ld %ldn",
72 presidents[npres].lastname,
73 presidents[npres].firstname,
74 &presidents[npres].emp_id,
75 &presidents[npres].start_date);
76 }
77
78 for (i = 0; i < npres; i++)
79 (void)tsearch(&presidents[i], &root, emp_name_id_compare);
80
81 twalk(root, print_emp);
82 return 0;
83 }
Целью вывода дерева является вывод содержащихся в нем элементов в отсортированном порядке. Помните, что twalk() посещает промежуточные вершины по три раза и что левая вершина меньше родительской, тогда как правая больше. Таким образом, оператор switch выводит сведения о вершине, лишь если which равно leaf, является концевой вершиной, или postorder, что означает, что была посещена левая вершина, а правая еще не была посещена.
Используемые данные представляют собой список президентов, тоже из раздела 6.2 «Функции сортировки и поиска». Чтобы освежить вашу память, полями являются фамилия, имя, номер сотрудника и время начала работы в виде временной отметки в секундах с начала Эпохи:
$ cat presdata.txt
Bush George 43 980013600
Clinton William 42 727552800
Bush George 41 601322400
Reagan Ronald 40 348861600
Carter James 39 222631200
Данные сортируются на основе сначала фамилии, затем имени, а затем старшинства. При запуске[160]160
Этот вывод для часового пояса U.S. Eastern Time zone – Примеч. автора.
[Закрыть] программа выдает следующий результат:
$ 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
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! Это приведет к аварийной ситуации.
• Иногда бывает необходимо выделить память, выровненную по определенной границе. Это осуществляет 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
Отладка
Имеется множество правил, начиная с логики программы и расположения данных, через организацию и расположение кода и кончая реализацией, которые могут минимизировать ошибки и проблемы. Мы рекомендуем вам изучить их; найдите хорошие книги по проектированию и дизайну программного обеспечения и реализуйте содержащиеся там советы на практике! Каждая программа, размером превышающая несколько сот строк кода, должна быть тщательно продумана и спроектирована, а не обтяпана, пока не начнет работать.
Однако, поскольку программисты люди, ошибки программирования неизбежны. Отладка является процессом обнаружения и устранения ошибок в программах. Даже хорошо спроектированные и хорошо реализованные программы иногда не работают; когда что-то идет не так и вы не можете выяснить, почему, хорошей мыслью является нацелить на код отладчик и понаблюдать за появлением ошибки.
Данная глава охватывает ряд тем, начиная с общих методик и советов по отладке (компилирование для отладки и элементарное использование GDB, отладчика GNU), переходя к ряду методик для использования при разработке и отладке программы, упрощающих отладку, и затем рассмотрением ряда инструментов, помогающих в процессе отладки. Глава завершается краткими сведениями по тестированию программного обеспечения и великолепным набором «правил отладки», извлеченных из книги, которую мы весьма рекомендуем.
Большая часть наших советов основана на нашем долгосрочном опыте участия в качестве добровольца в проекте GNU по поддержке gawk (GNU awk). Большинство, если не все, специфические примеры, которые мы представляем, происходят от этой программы. На протяжении главы особые рекомендации помечены словом Рекомендация.
Когда программа ведет себя неправильно, вы можете быть в затруднении, что делать сначала. Часто странное поведение возникает из-за неправильного использования памяти – использования неинициализированных значений, чтения или записи за пределами динамической памяти и т.д. Поэтому вы можете быстрее получить результаты, попробовав средства отладки памяти до того, как заведете отладчик.
Довод заключается в том, что утилиты памяти могут указать вам непосредственно на вызывающую сбой строку кода, тогда как использование отладчика больше напоминает миссию «найти и уничтожить», в которой вам нужно сначала изолировать проблему, а затем исправить ее. Убедившись, что дело не в проблемах памяти, можно переходить к использованию отладчика.
Поскольку отладчик является более универсальным средством, мы рассмотрим его вначале. Далее в главе мы обсудим ряд инструментов для отладки памяти.
15.2. Компиляция для отладкиДля использования отладчика исходного кода, отлаживаемый исполняемый файл должен быть откомпилирован с опцией компилятора -g. Эта опция заставляет компилятор внедрять в объектный код дополнительные отладочные идентификаторы; то есть дополнительные сведения, содержащие имена и типы переменных, констант, функций и так далее. Отладчик затем использует эту информацию для приведения в соответствие местоположения исходного кода с исполняемым кодом и получения или сохранения значений переменных в работающей программе.
На многих системах Unix опция компилятора -g является взаимно исключающей с опцией -O, которая включает оптимизацию. Это потому, что оптимизации могут вызвать перестановку битов и участков объектного кода, так что больше не будет прямого соответствия с тем, что исполняется, и линейным прочтением исходного кода. Отменив оптимизации, вы значительно облегчаете отладчику установление связи между объектным и исходным кодом, и в свою очередь, пошаговое прохождение программы работает очевидным образом. (Пошаговое исполнение вскоре будет описано.)
GCC, GNU Compiler Collection (коллекция компиляторов GNU), на самом деле допускает совместное использование -g и -O. Однако, это привносит как раз ту проблему, которую мы хотим избежать при отладке: следование исполнению в отладчике становится значительно более трудным. Преимуществом совместного использования опций является то, что вы можете оставить отладочные идентификаторы в конечном оптимизированном исполняемом модуле. Они занимают лишь дисковое пространство, а не память. После этого установленный исполняемый файл все еще можно отлаживать при непредвиденных случаях.
По нашему опыту, если нужно использовать отладчик, лучше перекомпилировать приложение с самого начала, использовав лишь опцию -g. Это значительно упрощает трассировку; имеется достаточно деталей, за которыми нужно следить при простом прохождении написанной программы, не беспокоясь о том, как компилятор переставляет код.
Есть одно предостережение: убедитесь, что поведение программы все еще неправильное. Воспроизводимость является ключевой при отладке; если вы не можете воспроизвести проблему, гораздо труднее ее выследить и исправить. В редких случаях компиляция без опции -O может устранить ошибку[161]161
Оптимизации компилятора являются общеизвестным козлом отпущения для логических ошибок. В прошлом обвинения компиляторов были более оправданы. Судя по нашему опыту, используя современные системы и компиляторы, очень редко можно обнаружить случаи, в которых оптимизации компилятора привносят ошибки в работающий код – Примеч. автора.
[Закрыть]. Обычно проблема остается при компиляции без использования опции -O, что означает, что на самом деле действительно имеется какая-то разновидность логической ошибки, ждущая своего обнаружения.
