14.3.4. Более точные паузы:
nanosleep()
Функция
sleep()
(см. раздел 10.8.1 «Сигнальные часы:
sleep()
,
alarm()
и
SIGALRM
») дает программе возможность приостановиться на указанное число секунд. Но, как мы видели, она принимает лишь целое число секунд, что делает невозможным задержки на короткие периоды, она потенциально может также взаимодействовать с обработчиками
SIGALRM
. Функция
nanosleep()
компенсирует эти недостатки:
#include <time.h> /* POSIX ТМР */
int nanosleep(const struct timespec *req, struct timespec *rem);
Эта функция является частью необязательного расширения POSIX «Таймеры» (TMR). Два аргумента являются запрошенным временем задержки и оставшимся числом времени в случае раннего возвращения (если
rem
не равен
NULL
). Оба являются значениями
struct timespec
:
struct timespec {
time_t tv_sec; /* секунды */
long tv_nsec; /* наносекунды */
};
Значение
tv_nsec
должно быть в диапазоне от 0 до 999 999 999. Как и в случае со
sleep()
, время задержки может быть больше запрошенного в зависимости оттого, когда и как ядро распределяет время для исполнения процессов.
В отличие от
sleep()
,
nanosleep()
не взаимодействует ни с какими сигналами, делая ее более безопасной и более простой для использования.
Возвращаемое значение равно 0, если выполнение процесса было задержано в течение всего указанного времени. В противном случае оно равно -1, с
errno
, указывающим ошибку. В частности, если
errno
равен
EINTR
,
nanosleep()
была прервана сигналом. В этом случае, если
rem
не равен
NULL
,
struct timespec
, на которую она указывает, содержит оставшееся время задержки. Это облегчает повторный вызов
nanosleep()
для продолжения задержки.
Хотя это выглядит немного странным, вполне допустимо использовать одну и ту же структуру для обоих параметров:
struct timespec sleeptime = /* что угодно */;
int ret;
ret = nanosleep(&sleeptime, &sleeptime);
struct timeval
и
struct timespec
сходны друг с другом, отличаясь лишь компонентом долей секунд. Заголовочный файл GLIBC
<sys/time.h>
определяет для их взаимного преобразования друг в друга два полезных макроса:
#include <sys/time.h> /* GLIBC */
void TIMEVAL_TO_TIMESPEC(struct timeval *tv, struct timespec *ts);
void TIMEPSEC_TO_TIMEVAL(struct timespec *ts, struct timeval *tv);
Вот они:
# define TIMEVAL_TO_TIMESPEC(tv, ts) { \
(ts)->tv_sec = (tv)->tv_sec; \
(ts)->tv_nsec = (tv)->tv_usec * 1000; \
}
# define TIMESPEC_TO_TIMEVAL(tv, ts) { \
(tv)->tv_sec = (ts)->tv_sec; \
(tv)->tv_usec = (ts)->tv_nsec / 1000; \
}
#endif
ЗАМЕЧАНИЕ. To, что некоторые системные вызовы используют микросекунды, а другие — наносекунды, в самом деле сбивает с толку. Причина этого историческая: микросекундные вызовы были разработаны на системах, аппаратные часы которых не имели более высокого разрешения, тогда как наносекундные вызовы были разработаны более недавно для систем со значительно более точными часами. C'est la vie. Почти все, что вы можете сделать, это держать под руками ваше руководство.
14.4. Расширенный поиск с помощью двоичных деревьев
В разделе 6.2 «Функции сортировки и поиска» мы представили функции для поиска и сортировки массивов. В данном разделе мы рассмотрим более продвинутые возможности.
14.4.1. Введение в двоичные деревья
Массивы являются почти простейшим видом структурированных данных. Их просто понимать и использовать. Хотя у них есть недостаток, заключающийся в том, что их размер фиксируется во время компиляции. Таким образом, если у вас больше данных, чем помещается в массив, вам не повезло. Если у вас значительно меньше данных, чем размер массива, память расходуется зря. (Хотя на современных системах много памяти, подумайте об ограничениях программистов, пишущих программы для внедренных систем, таких, как микроволновые печи и мобильные телефоны. С другого конца спектра, подумайте о проблемах программистов, имеющих дело с огромными объемами ввода, таких, как прогнозирование погоды.
В области компьютерных наук были придуманы многочисленные динамические структуры данных, структуры, которые увеличивают и уменьшают свой размер по требованию и которые являются более гибкими, чем простые массивы, даже массивы, создаваемые и изменяемые динамически с помощью
malloc()
и
realloc()
. Массивы при добавлении или удалении новых элементов требуется также повторно сортировать.
Одной из таких структур является дерево двоичного поиска, которое мы для краткости будем называть просто «двоичным деревом» («binary tree»). Двоичное дерево хранит элементы в сортированном порядке, вводя их в дерево в нужном месте при их появлении. Поиск по двоичному дереву также осуществляется быстро, время поиска примерно такое же, как при двоичном поиске в массиве. В отличие от массивов, двоичные деревья не нужно каждый раз повторно сортировать с самого начала при добавлении к ним элементов.
У двоичных деревьев есть один недостаток. В случае, когда вводимые данные уже отсортированы, время поиска в двоичном дереве сводится ко времени линейного поиска. Техническая сторона этого вопроса должна иметь дело с тем, как двоичные деревья управляются внутренне, что вскоре будет описано.
Теперь не избежать некоторой формальной терминологии, относящейся к структурам данных. На рис. 14.1 показано двоичное дерево. В информатике деревья изображаются, начиная сверху и расширяясь вниз. Чем ниже спускаетесь вы по дереву, тем больше его глубина. Каждый объект внутри дерева обозначается как вершина (node). На вершине дерева находится корень дерева с глубиной 0. Внизу находятся концевые вершины различной глубины. Концевые вершины отличают по тому, что у них нет ответвляющихся поддеревьев (subtrees), тогда как у внутренних вершин есть по крайней мере одно поддерево. Вершины с поддеревьями иногда называют родительскими (parent), они содержат порожденные вершины (children).
