Текст книги "Linux программирование в примерах"

Автор книги: Арнольд Роббинс

сообщить о нарушении

Текущая страница: 16 (всего у книги 55 страниц)

6.1.4. Преобразование разложенного времени в time_t

Получение от системы значений «секунд с начала Эпохи» просто; именно так даты и времена хранятся в индексах и возвращаются с помощью time() и stat(). Эти значения также легко оценивать на равенство или посредством < и > для простых тестов раньше/позже.

Однако, с датами, введенными людьми, не так легко работать. Например, многие версии команды touch позволяют предусмотреть дату и время, в которое touch должна установить время модификации или доступа к файлу (с помощью utime(), как было описано в разделе 5.5.3 «Изменение отметок времени: utime()»).

Преобразование даты, введенной человеком, в значение time_t трудно: надо принять во внимание високосные годы, учесть часовые пояса и т.д. Поэтому стандарт C89 ввел функцию mktime():

#include /* ISO С */

time_t mktime(struct tm *tm);

Для использования mktime() укажите в struct tm соответствующие значения – год, месяц, день и т.д. Если вы знаете, действовало ли для данной даты летнее время, установите соответствующим образом поле tm_isdst: 0 для «нет» и положительное значение для «да». В противном случае, используйте отрицательное значение для «не знаю». Поля tm_wday и tm_yday игнорируются.

mktime() предполагает, что struct tm представляет локальное время, не UTC. Она возвращает значение time_t, представляющее переданные дату и время, или (time_t)(-1), если данные дата/время не могут быть правильно представлены. После успешного возвращения все значения struct tm выверены на попадание в правильные диапазоны, a tm_wday и tm_yday также корректно установлены. Вот простой пример:

1  /* ch06-echodate.c – демонстрирует mktime(). */

2

3  #include

4  #include

5

6  int main(void)

7  {

8   struct tm tm;

9   time_t then;

10

11  printf("Enter a Date/time as YYYY/MM/DD HH:MM:SS : ");

12  scanf("%d/%d/%d %d:%d:%d",

13   &tm.tm_year, &tm.tm_mon, &tm.tm_mday,

14   &tm.tm_hour, &tm.tm_min, &tm.tm_sec);

15

16  /* Проверка ошибок значений для краткости опущена. */

17  tm.tm_year -= 1900;

18  tm.tm_mon–;

19

20  tm.tm_isdst = -1; /* He знаю о летнем времени */

21

22  then = mktime(&tm);

23

24  printf("Got: %s", ctime(&then));

25  exit(0);

26 }

В строке 11 запрашиваются дата и время, а в строках 12–14 соответствующие значения считываются. (В коде изделия возвращаемые scanf() значения должны проверяться.) Строки 17 и 18 компенсируют различную базу для лет и месяцев соответственно. Строка 20 указывает, что мы не знаем, представляют ли данные дата и время летнее время. Строка 22 вызывает mktime(), а строка 24 выводит результат преобразования. После компилирования и запуска мы видим, что это работает:

$ ch06-echodate

Enter a Date/time as YYYY/MM/DD HH:MM:SS : 2003/5/25 19:07:23

Got: Sun May 25 19:07:23 2003

6.1.5. Получение сведений о часовом поясе

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

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

Интерфейс языка С для сведений о часовых поясах развивался в разных версиях Unix, как на System V, так и Berkley, пока, наконец, не был стандартизован POSIX следующим образом.

#include /* POSIX */

extern char *tzname[2];

extern long timezone;

extern int daylight;

void tzset(void);

Функция tzset() проверяет переменную окружения TZ для получения сведений о часовом поясе и переходе на летнее время.[65]65
  Хотя POSIX стандартизует формат TZ, он не представляет интереса, поэтому мы не стали возиться здесь с его документированием. В конце концов, именно tzset() должна понимать формат, а не код пользователя. Реализации могут использовать и используют форматы, которые расширяют POSIX – Примеч. автора.


[Закрыть] Если эта переменная не установлена, tzset() использует «определенный в реализации часовой пояс по умолчанию», который скорее всего является часовым поясом машины, на которой вы работаете.

После вызова tzset() сведения о локальном часовом поясе доступны в нескольких переменных:

extern char *tzname[2]

Стандартное имя и имя летнего времени для часового пояса. Например, для областей США в восточном часовом поясе именами часового пояса являются 'EST' (Eastern Standard Time) и 'EDT' (Eastern Daylight Time).

extern long timezone

Разница в секундах между текущим часовым поясом и UTC. Стандарт не определяет, как эта разница работает. На практике отрицательные значения представляют часовые пояса восточнее (перед, или те, которые позже) UTC; положительные значения представляют часовые пояса западнее (за, или те, которые раньше) UTC. Если вы посмотрите на это значение как «насколько изменить местное время, чтобы оно стало равно UTC», тогда знак этого значения имеет смысл.

extern int daylight

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

ЗАМЕЧАНИЕ. Переменная daylight не означает, действует ли в настоящий момент летнее время! Вместо этого она просто констатирует, может ли текущий часовой пояс вообще иметь летнее время.

Стандарт POSIX указывает, что ctime(), localtime(), mktime() и strftime() действуют, «как если бы» они вызывали tzset(). Это означает, что им в действительности не нужно вызывать tzset(), но они должны вести себя, как если бы эта функция была вызвана. (Формулировка призвана дать определенную гибкость при реализации, в то же время гарантируя правильное поведение кода уровня пользователя.)

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

6.1.5.1. Системы BSD: timezone(), не timezone

Некоторые производные от BSD 4.4 системы вместо переменной POSIX timezone предоставляют функцию timezone():

#include /* BSD */

char *timezone(int zone, int dst);

Аргумент zone является числом минут западнее GMT, a dst истинно, если действует летнее время. Возвращаемое значение является строкой, дающей имя указанного часового пояса, или значение, выраженное относительно GMT. Эта функция обеспечивает совместимость с функцией V7 с тем же именем и поведением.

Локальное время: откуда оно известно?

Системы GNU/Linux хранят информацию о часовых поясах в файлах и каталогах в /usr/share/zoneinfo:

$ cd /usr/share/zoneinfo

$ ls -FC

Africa/     Canada/ Factory    Iceland   MST7MDT  Portugal  W-SU

America/    Chile/  GB         Indian/   Mexico/  ROC       WET

Antarctica/ Cuba    GB-Eire    Iran      Mideast/ ROK       Zulu

Arctic/     EET     GMT        Israel    NZ       Singapore iso3166.tab

Asia/       EST     GMT+0      Jamaica   NZ-CHAT  SystemV/  posix/

Atlantic/   EST5EDT GMT-0      Japan     Navajo   Turkey    posixrules

Australia/  Egypt   GMT0       Kwajalein PRC      UCT       right/

Brazil/     Eire    Greenwich  Libya     PST8PDT  US/       zone.tab

CET         Etc/    HST        MET       Pacific/ UTC

CST6CDT     Europe/ Hongkong   MST       Poland   Universal

Когда возможно, этот каталог использует прямые ссылки для предоставления одних и тех же данных с разными именами. Например, файлы EST5EDT и US/Eastern на самом деле одни и те же:

$ ls -il EST5EDT US/Eastern

724350 -rw-r–r– 5 root root 1267 Sep б 2002 EST5EDT

724350 -rw-r–r– 5 root root 1267 Sep 6 2002 US/Eastern

Частью установки системы является выбор часового пояса. Надлежащий файл данных часового пояса помещается затем в /etc/localtime:

$ file /etc/localtime

/etc/localtime: timezone data

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

Переменная окружения TZ, если она установлена, перекрывает значение по умолчанию для часового пояса:

$ date /* Дата и время в часовом поясе по умолчанию

        */

Wed Nov 19 06:44:50 EST 2003

$ export TZ=PST8PDT /* Смена часового пояса на Западное

                       побережье США */

$ date /* Вывести дату и время */

Wed Nov 19 03:45:09 PST 2003

Широкое распространение этой функции делает переносимое использование переменной POSIX timezone трудной. К счастью, мы не видим большой потребности в ней strftime() должно быть достаточно едва ли не для большинства необычных потребностей

6.2. Функции сортировки и поиска

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

Все процедуры разделяют общий лейтмотив; данные управляются через указатели void*, а сортировку осуществляют предоставленные пользователем функции. Обратите также внимание, что эти API применяются к данным в памяти. Структуры сортировки и поиска в файлах значительно более сложны и выходят за рамки вводного руководства, подобного данному. (Однако, команда sort хорошо работает для текстовых файлов; см. справочную страницу для sort(1). Сортировка двоичных файлов требует написания специальной программы.)

Поскольку ни один алгоритм не работает одинаково хорошо для всех приложений, имеются несколько различных наборов библиотечных процедур для сопровождения искомых коллекций данных. Данная глава рассматривает лишь один простой интерфейс для поиска. Другой, более развитый интерфейс описан в разделе 14.4 «Расширенный поиск с использованием двоичных деревьев». Более того, мы намеренно не объясняем лежащие в основе алгоритмы, поскольку данная книга об API, а не об алгоритмах и структурах данных. Важно понять, что API можно рассматривать как «черные ящики», выполняющие определенную работу без необходимости понимания подробностей их работы.

6.2.1. Сортировка: qsort()

Сортировка выполняется с помощью qsort():

#include /* ISO С */

void qsort(void *base, size_t nmemb, size_t size,

 int (*compare)(const void*, const void*));

Название qsort() происходит от алгоритма машинного поиска Хоара Quicksort (C.A.R. Hoare's Quicksort algorithm), который использовался в первоначальной реализации Unix. (Ничто в стандарте POSIX не требует использования этого алгоритма для qsort(). Реализация GLIBC использует высоко оптимизированную комбинацию Quicksort и Insertion Sort.)

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

void *base

Адрес начала массива.

size_t nmemb

Общее число элементов в массиве.

size_t size

Размер каждого элемента массива. Лучший способ получения этого значения – оператор С sizeof.

int (*compare)(const void*, const void*)

Возможно устрашающее объявление указателя функции. Оно говорит, что «compare указывает на функцию, которая принимает два параметра 'const void*' и возвращает int».

Большая часть работы заключается в написании соответствующей функции сравнения. Возвращаемое значение должно имитировать соответствующее значение strcmp(): меньше нуля, если первое значение «меньше» второго, ноль, если они равны, и больше нуля, если первое значение «больше» второго. Именно функция сравнения определяет значения «больше» и «меньше» для всего, что вы сравниваете. Например, для сравнения двух значений double мы могли бы использовать эту функцию:

int dcomp(const void *d1p, const void *d2p) {

 const double *d1, *d2;

 d1 = (const double*)d1p; /* Привести указатели к нужному типу */

 d2 = (const double*)d2p;

 if (*d1 < *d2) /* Сравнить и вернуть нужное значение */

  return -1;

 else if (*d1 > *d2)

  return 1;

 else if (*d1 == *d2)

  return 0;

 else

  return -1; /* NaN сортируется до действительных чисел */

}

Это показывает общий стереотип для функций сравнения: привести тип аргументов от void* к указателям на сравниваемый тип, а затем вернуть результат сравнения.

Для чисел с плавающей точкой простое вычитание, подобное 'return *d1 – *d2', не работает, особенно если одно значение очень маленькое или одно или оба значения являются специальными значениями «не число» или «бесконечность». Поэтому нам приходится осуществлять сравнение вручную, принимая во внимание нечисловое значение (которое даже не равно самому себе!)

6.2.1.1. Пример: сортировка сотрудников

Для более сложных структур требуются более сложные функции. Например, рассмотрите следующую (довольно тривиальную) struct employee:

struct employee {

char lastname[30];

char firstname[30];

long emp_id;

time_t start_date;

};

Мы могли бы написать функцию для сортировки сотрудников по фамилии, имени и идентификационному номеру:

int emp_name_id_compare(const void *e1p, const void *e2p) {

 const struct employee *e1, *e2;

 int last, first;

 e1 = (const struct employee*)e1p; /* Преобразовать указатели */

 e2 = (const struct employee*)e2p;

 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)

  /* Сравнить фамилии */

  return last; /* Фамилии различаются */

 /* фамилии совпадают, сравнить имена */

 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)

  /* Сравнить имена */

  return first; /* Имена различаются */

 /* имена совпадают, сравнить номера ID */

 if (e1->emp_id < e2->emp_id) /* Сравнить ID сотрудника */

  return -1;

 else if (e1->emp_id == e2->emp_id)

  return 0;

 else

  return 1;

}

Логика здесь проста: сначала сравниваются фамилии, затем имена, а затем номера ID, если два имени совпадают. Используя для строк strcmp(), мы автоматически получаем правильное отрицательное/нулевое/положительное значение для возвращения.

При сравнении ID сотрудников нельзя просто использовать вычитание: представьте, что long 64-разрядный, а int 32-разрядный, а два значения отличаются лишь в старших 32 битах (скажем, младшие 32 бита равны нулю). В таком случае вычитание автоматически привело бы к приведению типа к int с отбрасыванием старших 32 битов и возвращением неверного результата.

ЗАМЕЧАНИЕ. Возможно, мы остановились при сравнении имен, в этом случае все сотрудники с совпадающими фамилиями и именами оказались бы сгруппированы, но никак не отсортированы

Это важный момент qsort() не гарантирует стабильной сортировки. Стабильна сортировка, в которой, если два элемента равны на основе значения какого-либо ключа(-ей), они сохраняют свой первоначальный порядок друг относительно друга в конечном отсортированном массиве. Например, рассмотрите трех сотрудников с одинаковыми фамилиями и именами и с номерами 17, 42 и 81. Их порядок в первоначальном массиве. возможно, был 42, 81 и 17 (Что означает, что сотрудник 42 находится по индексу с меньшим значением, чем сотрудник 81, который, в свою очередь, находится по индексу с меньшим значением, чем сотрудник 17). После сортировки порядок может оказаться 81, 42 и 17. Если ото представляет проблему, процедура сравнения должна рассматривать все важные ключевые значения (Наша так и делает.)

Просто используя другую функцию, мы можем отсортировать сотрудников по старшинству:

int emp_seniority_compare(const void *e1p,

 const void *e2p) {

 const struct employee *e1, *e2;

 double diff;

 /* Привести указатели к нужному типу */

 e1 = (const struct employee*)e1p;

 e2 = (const struct employee*)e2p;

 /* Сравнить времена */

 diff = difftime(e1->start_date, e2->start_date);

 if (diff < 0)

  return -1;

 else if (diff > 0)

  return 1;

 else

  return 0;

}

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

return (int)difftime(e1->start_date, e2->start_date);

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

Вот пример файла данных со списком пяти президентов США:

$ cat presdata.txt

/* Фамилия, имя, номер президента, инаугурация */

Bush George 43 980013600

Clinton William 42 727552800

Bush George 41 601322400

Reagan Ronald 40 348861600

Carter James 39 222631200

В ch06-sortemp.c приведена простая программа, которая считывает этот файл в массив struct employee, а затем сортирует его, используя две только что представленные функции сравнения.

1   /* ch06-sortemp.c – Демонстрирует qsort() с двумя функциями сравнения. */

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  {

     /* ...как показано ранее, опущено для экономии места... */

39  }

40

41  /* emp_seniority_compare – сравнение по старшинству */

42

43  int emp_seniority_compare(const void *e1p, const void *e2p)

44  {

     /* ...как показано ранее, опущено для экономии места... */

58  }

59

60  /* main – демонстрация сортировки */

61

62  int main(void)

63  {

64   #define NPRES 10

65   struct employee presidents[NPRES];

66   int i, npres;

67   char buf[BUFSIZ];

68

69   /* Очень простой код для чтения данных: */

70   for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;

71    npres++) {

72    sscanf(buf, "%s %s %ld %ldn",

73     presidents[npres].lastname,

74     presidents[npres].firstname,

75     &presidents[npres].emp_id,

76     &presidents[npres].start_date);

77   }

78

79   /* npres теперь содержит число прочитанных строк. */

80

81   /* Сначала сортировка по имени */

82   qsort(presidents, npres, sizeof(struct employee), emp_name_id_compare);

83

84   /* Вывести результат */

85   printf("Sorted by name:n");

86   for (i = 0; i < npres; i++)

87    printf("t%s %st%dt%s",

88     presidents[i].lastname,

89     presidents[i].firstname,

90     presidents[i].emp_id,

91     ctime(&presidents[i].start_date));

92

93   /* Теперь сортировка по старшинству */

94   qsort(presidents, npres, sizeof(struct employee), emp_seniority_compare);

95

96   /* И снова вывести */

97   printf("Sorted by seniority:n");

98   for (i = 0; i < npres; i++)

99    printf("t%s %st%dt%s",

100    presidents[i].lastname,

101    presidents!i].firstname,

102    presidents[i].emp_id,

103    ctime(&presidents[i].start_date));

104 }

Строки 70–77 считывают данные. Обратите внимание, что любое использование scanf() требует от входных данных «хорошего поведения». Если, например, какое-нибудь имя содержит более 29 символов, возникает проблема. В данном случае, мы вне опасности, но в коде изделия нужно быть гораздо более осмотрительным.

Строка 82 сортирует данные по имени и по ID сотрудника, а затем строки 84–91 выводят отсортированные данные. Сходным образом строка 94 пересортировывает данные, на этот раз по старшинству, а строки 97–103 выводят результаты. После компилирования и запуска программа выдает следующие результаты:

$ ch06-sortemp < presdata.txt

Sorted by name:

  Bush George 41 Fri Jan 20 13:00:00 1989

  Bush George 43 Sat Jan 20 13:00:00 2001

  Carter James 39 Thu Jan 20 13:00:00 1977

  Clinton William 42 Wed Jan 20 13:00:00 1993

  Reagan Ronald 40 Tue Jan 20 13:00:00 1981

Sorted by seniority:

  Carter James 39 Thu Jan 20 13:00:00 1977

  Reagan Ronald 40 Tue Jan 20 13:00:00 1981

  Bush George 41 Fri Jan 20 13:00:00 1989

  Clinton William 42 Wed Jan 20 13:00:00 1993

  Bush George 43 Sat Jan 20 13:00:00 2001

(Мы использовали 1 час пополудни как приблизительное время, когда все президенты начали работать.)[66]66
  Вывод, показанный здесь, относится к US Eastern Standard Time. Вы получите различные результаты для одних и тех же программ и данных, если используете другой часовой пояс – Примеч. автора.


[Закрыть]

Стоит заметить одну вещь: qsort() переставляет данные в массиве. Если каждый элемент массива представляет собой большую структуру, при сортировке массива большое количество данных будут копироваться туда-сюда. Вместо этого может оказаться выгодным создать отдельный массив указателей, каждый из которых указывает на один элемент массива. Затем использовать qsort() для сортировки массива указателей, получая доступ к несортированным данным через сортированные указатели.

Платой за это является дополнительная память для размещения указателей и модификация функций сравнения для дополнительного перенаправления указателей при сравнении структур. Полученной выгодой может стать значительное ускорение работы, поскольку на каждом шаге перемещается лишь четырех– или восьмибайтный указатель вместо большой структуры. (Наша struct employee имеет размер по крайней мере 68 байтов. При обмене четырехбайтных указателей перемещается в 17 раз меньше данных, чем при обмене структур.) Для тысяч размещенных в памяти структур разница мажет быть существенной.

ЗАМЕЧАНИЕ. Если вы являетесь программистом С++, знайте! qsort() может быть опасной для использования с массивами объектов! qsort() осуществляет простые перемещения памяти, копируя байты. Она совершенно ничего не знает о конструкциях С++, таких, как конструкторы копирования или функции operator=(). Вместо этого используйте одну из функций сортировки STL[67]67
  STL (Standard Template Library, стандартная библиотека шаблонов). – Примеч. науч. ред.


[Закрыть] или используйте методику отдельного массива указателей.