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

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

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

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

3.2.1.4. Изменение размера: realloc()

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

Вдобавок, можно изменять размер динамически выделенной области памяти. Хотя можно сократить размер блока памяти, обычно его увеличивают. Изменение размера осуществляется с помощью realloc(). Продолжая пример с coordinates, типичный код выглядит следующим образом:

int new_count;

size_t new_amount;

struct coord *newcoords; /* установить, например: */

new_count = count * 2; /* удвоить размер памяти */

new_amount = new_count * sizeof(struct coord);

newcoords =

 (struct coord*)realloc(coordinates, new_amount);

if (newcoords == NULL) {

 /* сообщить об ошибке, восстановить или прервать */

}

coordinates = newcoords;

/* продолжить использование coordinates ... */

Как и в случае с malloc(), шаги стереотипны по природе и сходны по идее.

1. Вычислить новый выделяемый размер в байтах.

2. Вызвать realloc() с оригинальным указателем, полученным от malloc() (или от calloc() или предыдущего вызова realloc()) и с новым размером.

3. Привести тип и присвоить возвращенное realloc() значение. Подробнее обсудим дальше.

4. Как и для malloc(), проверить возвращенное значение, чтобы убедиться, что оно не равно NULL. Вызов любой функции выделения памяти может завершиться неудачей.

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

В любом случае вы можете предположить, что если realloc() не возвращает NULL, старые данные были скопированы для вас в новый участок памяти. Более того, старый указатель больше недействителен, как если бы вы вызвали free() с ним, и использовать его больше не следует. Это верно для всех указателей на этот блок данных, а не только для того, который использовался при вызове free().

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

coordinates = realloc(coordinates, new_amount);

Это плохо по следующей причине. Когда realloc() возвращает NULL, первоначальный указатель все еще действителен; можно безопасно продолжить использовать эту память. Но если вы повторно используете ту же самую переменную и realloc() возвращает NULL, вы теряете указатель на первоначальную память. Эту память больше нельзя использовать. Что еще важнее, эту память невозможно освободить! Это создает утечку памяти, которую нужно избежать.

Для версии realloc() в стандартном С есть некоторые особые случаи: когда аргумент ptr равен NULL, realloc() действует подобно malloc() и выделяет свежий блок памяти. Когда аргумент size равен 0, realloc() действует подобно free() и освобождает память, на которую указывает ptr. Поскольку (а) это может сбивать с толку и (б) более старые системы не реализуют эту возможность, мы рекомендуем использовать malloc(), когда вы имеете в виду malloc(), и free(), когда вы имеете в виду free().

Вот другой довольно тонкий момент[42]42
  Он получен от реальной практики работы с gawk – Примеч. автора.


[Закрыть]. Рассмотрим процедуру, которая содержит статический указатель на динамически выделяемые данные, которые время от времени должны расти. Процедура может содержать также автоматические (т.е. локальные) указатели на эти данные. (Для краткости, мы опустим проверки ошибок. В коде продукта не делайте этого.) Например:

void manage_table(void) {

 static struct table *table;

 struct table *cur, *p;

 int i;

 size_t count;

 ...

 table =

  (struct table*)malloc(count * sizeof(struct table));

 /* заполнить таблицу */

 cur = &table[i]; /* указатель на 1-й элемент */

 ...

 cur->i = j; /* использование указателя */

 ...

 if (/* некоторое условие */) {

  /* нужно увеличить таблицу */

  count += count/2;

  p =

  (struct table*)realloc(table, count * sizeof(struct table));

  table = p;

 }

 cur->i = j; /* ПРОБЛЕМА 1: обновление элемента таблицы */

 other_routine(); /* ПРОБЛЕМА 2: см. текст */

 cur->j = k; /* ПРОБЛЕМА 2: см. текст */

 ...

}

Это выглядит просто; manage_table() размешает данные, использует их, изменяет размер и т.д. Но есть кое-какие проблемы, которые не выходят за рамки страницы (или экрана), когда вы смотрите на этот код.

В строке, помеченной 'ПРОБЛЕМА 1', указатель cur используется для обновления элемента таблицы. Однако, cur был инициализирован начальным значением table. Если некоторое условие верно и realloc() вернула другой блок памяти, cur теперь указывает на первоначальный, освобожденный участок памяти! Каждый раз, когда table меняется, нужно обновить также все указатели на этот участок памяти. Здесь после вызова realloc() и переназначения table недостает строки 'cur = &table[i];'.

Две строки, помеченные 'ПРОБЛЕМА 2', еще более тонкие. В частности, предположим, что other_routine() делает рекурсивный вызов manage_table(). Переменная table снова может быть изменена совершенно незаметно! После возвращения из other_routine() значение cur может снова стать недействительным.

Можно подумать (что мы вначале и сделали), что единственным решением является знать это и добавить после вызова функции переназначение cur с соответствующим комментарием. Однако, Брайан Керниган (Brian Kernighan) любезно нас поправил. Если мы используем индексирование, проблема поддержки указателя даже не возникает:

table =

 (struct table*)malloc(count * sizeof(struct table));

...

/* заполнить таблицу */

...

table[i].i = j; /* Обновить член i-го элемента */

...

if (/* некоторое условие */) {

 /* нужно увеличить таблицу */

 count += count/2;

 p =

  (struct table*)realloc(table, count * sizeof(struct table));

 table = p;

}

table[i].i = j; /* ПРОБЛЕМА 1 устраняется */

other_routine();

/* Рекурсивный вызов, модифицирует таблицу */

table[i].j = k; /* ПРОБЛЕМА 2 также устраняется */

Использование индексирования не решает проблему, если вы используете глобальную копию первоначального указателя на выделенные данные; в этом случае, вам все равно нужно побеспокоиться об обновлении своих глобальных структур после вызова realloc().

ЗАМЕЧАНИЕ. Как и в случае с malloc(), когда вы увеличиваете размер памяти, вновь выделенная после realloc() память не инициализируется нулями. Вы сами при необходимости должны очистить память с помощью memset(), поскольку realloc() лишь выделяет новую память и больше ничего не делает.

3.2.1.5. Выделение с инициализацией нулями: calloc()

Функция calloc() является простой оболочкой вокруг malloc(). Главным ее преимуществом является то, что она обнуляет динамически выделенную память. Она также вычисляет за вас размер памяти, принимая в качестве параметра число элементов и размер каждого элемента:

coordinates = (struct coord*)calloc(count, sizeof(struct coord));

По крайней мере идейно, код calloc() довольно простой. Вот одна из возможных реализаций:

void *calloc(size_t nmemb, size_t size) {

 void *p;

 size_t total;

 total = nmemb * size;   /* Вычислить размер */

 p = malloc(total);      /* Выделить память */

 if (p != NULL)          /* Если это сработало – */

 memset(p, '', total); /* Заполнить ее нулями */

 return p; /* Возвращаемое значение NULL или указатель */

}

Многие опытные программисты предпочитают использовать calloc(), поскольку в этом случае никогда не возникает вопросов по поводу вновь выделенной памяти.

Если вы знаете, что вам понадобится инициализированная нулями память, следует также использовать calloc(), поскольку возможно, что память, возвращенная malloc(), уже заполнена нулями. Хотя вы, программист, не можете этого знать, calloc() может это знать и избежать лишнего вызова memset().

3.2.1.6. Подведение итогов из GNU Coding Standards

Чтобы подвести итоги, процитируем, что говорит об использовании процедур выделения памяти GNU Coding Standards:

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

В Unix realloc может разрушить блок памяти, если она возвращает ноль. GNU realloc не содержит подобной ошибки: если она завершается неудачей, исходный блок остается без изменений. Считайте, что ошибка устранена. Если вы хотите запустить свою программу на Unix и хотите избежать потерь в этом случае, вы можете использовать GNU malloc.

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

В этих трех коротких абзацах Ричард Столмен (Richard Stallman) выразил суть важных принципов управления динамической памятью с помощью malloc(). Именно использование динамической памяти и принцип «никаких произвольных ограничений» делают программы GNU такими устойчивыми и более работоспособными по сравнению с их Unix-двойниками.

Мы хотим подчеркнуть, что стандарт С требует, чтобы realloc() не разрушал оригинальный блок памяти, если она возвращает NULL.

3.2.1.7. Использование персональных программ распределения

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

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

Например, GNU awk (gawk) использует эту методику. Выдержка из файла awk.h в дистрибутиве gawk (слегка отредактировано, чтобы уместилось на странице):

#define getnode(n) if (nextfree) n = nextfree,

 nextfree = nextfree->nextp; else n = more_nodes()

#define freenode(n) ((n)->flags = 0, (n)->exec_count = 0,

 (n)->nextp = nextfree, nextfree = (n))

Переменная nextfree указывает на связанный список структур NODE. Макрос getnode() убирает из списка первую структуру, если она там есть. В противном случае она вызывает more_nodes(), чтобы выделить новый список свободных структур NODE. Макрос freenode() освобождает структуру NODE, помещая его в начало списка.

ЗАМЕЧАНИЕ. Первоначально при написании своего приложения делайте это простым способом: непосредственно используйте malloc() и free(). Написание собственного распределителя вы должны рассмотреть лишь в том и только в том случае, если профилирование вашей программы покажет, что она значительную часть времени проводит в функциях выделения памяти.

3.2.1.8. Пример: чтение строк произвольной длины

Поскольку это, в конце концов, Программирование на Linux в примерах, настало время для примера из реальной жизни. Следующий код является функцией readline() из GNU Make 3.80 (ftp://ftp.gnu.org/gnu/make/make-3.80.tar.gz). Ее можно найти в файле read.c.

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

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

struct ebuffer {

 char *buffer;      /* Начало текущей строки в буфере. */

 char *bufnext;     /* Начало следующей строки в буфере. */

 char *bufstart;    /* Начало всего буфера. */

 unsigned int size; /* Размер буфера для malloc. */

 FILE *fp;          /* Файл или NULL, если это внутренний буфер. */

 struct floc floc;  /* Информация о файле в fp (если он есть). */

};

Поле size отслеживает размер всего буфера, a fp является указателем типа FILE для файла ввода. Структура floc не представляет интереса при изучении процедуры.

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

1  static long

2  readline(ebuf) /* static long readline(struct ebuffer *ebuf) */

3  struct ebuffer *ebuf;

4  {

5   char *p;

6   char *end;

7   char *start;

8   long nlines = 0;

9

10  /* Использование строковых буферов и буферов потоков достаточно

11     различается, чтобы использовать разные функции. */

12

13  if (!ebuf->fp)

14   return readstring(ebuf);

15

16  /* При чтении из файла для каждой новой строки мы всегда

17     начинаем с начала буфера. */

18

19  p = start = ebuf->bufstart;

20  end = p + ebuf->size;

21  *p = '';

Для начала заметим, что GNU Make написан на С K&R для максимальной переносимости. В исходной части объявляются переменные, и если ввод осуществляется из строки (как в случае расширения макроса), код вызывает другую функцию, readstring() (строки 13 и 14). Строка '!ebuf->fp' (строка 13) является более короткой (и менее понятной, по нашему мнению) проверкой на пустой указатель; это то же самое, что и 'ebuf->fp==NULL'.

Строки 19-21 инициализируют указатели и вводят байт NUL, который является символом завершения строки С в конце буфера. Затем функция входит в цикл (строки 23–95), который продолжается до завершения всего ввода.

23 while (fgets(p, end – р, ebuf->fp) != 0)

24 {

25  char *p2;

26  unsigned long len;

27  int backslash;

28

29  len = strlen(p);

30  if (len == 0)

31  {

32   /* Это случается лишь тогда, когда первый символ строки ''.

33      Это довольно безнадежный случай, но (верите или нет) ляп Афины

34      бьет снова! (xmkmf помещает NUL в свои makefile.)

35      Здесь на самом деле нечего делать; мы создаем новую строку, чтобы

36      следующая строка не была частью данной строки. */

37   error (&ebuf->floc,

38    _("warning: NUL character seen; rest of line ignored"));

39   p[0] = 'n';

40   len = l;

41  }

Функция fgets() (строка 23) принимает указатель на буфер, количество байтов для прочтения и переменную FILE* для файла, из которого осуществляется чтение. Она читает на один байт меньше указанного, чтобы можно было завершить буфер символом ''. Эта функция подходит, поскольку она позволяет избежать переполнения буфера. Она прекращает чтение, когда встречается с символами конца строки или конца файла; если это символ новой строки, он помещается в буфер. Функция возвращает NULL при неудаче или значение указателя первого аргумента при успешном завершении.

В этом случае аргументами являются указатель на свободную область буфера, размер оставшейся части буфера и указатель FILE для чтения.

Комментарии в строках 32–36 очевидны; если встречается нулевой байт, программа выводит сообщение об ошибке и представляет вывод как пустую строку. После компенсирования нулевого байта (строки 30–41) код продолжает работу.

43 /* Обойти только что прочитанный текст. */

44 p += len;

45

46 /* Если последний символ – не конец строки, она не поместилась

47    целиком в буфер. Увеличить буфер и попытаться снова. */

48 if (p[-1] != 'n')

49  goto more_buffer;

50

51 /* Мы получили новую строку, увеличить число строк. */

52 ++nlines;

Строки 43–52 увеличивают указатель на участок буфера за только что прочитанными данными. Затем код проверяет, является ли последний прочитанный символ символом конца строки. Конструкция p[-1] (строка 48) проверяет символ перед p, также как p[0] является текущим символом, а p[1] – следующим. Сначала это кажется странным, но если вы переведете это на язык математики указателей, *(p-1), это приобретет больший смысл, а индексированная форма, возможно, проще для чтения.

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

54 #if !defined(WINDOWS32) && !defined(__MSDOS__)

55 /* Проверить, что строка завершилась CRLF; если так,

56    игнорировать CR. */

57 if ((p – start) > 1 && p[-2] == 'r')

58 {

59  –p;

60  p[-1] = 'n';

61 }

62 #endif

Строки 54–62 обрабатывают вводимые строки, следующие соглашению Microsoft по завершению строк комбинацией символов возврата каретки и перевода строки (CR-LF), а не просто символом перевода строки (новой строки), который является соглашением Linux/Unix. Обратите внимание, что #ifdef исключает этот код на платформе Microsoft, очевидно, библиотека на этих системах автоматически осуществляет это преобразование. Это верно также для других не-Unix систем, поддерживающих стандартный С.

64  backslash = 0;

65  for (p2 = p – 2; p2 >= start; –p2)

66  {

67   if (*p2 != '\')

68   break;

69   backslash = !backslash;

70  }

71

72  if (!backslash)

73  {

74   p[-1] = '';

75   break;

76  }

77

78  /* Это была комбинация обратный слеш/новая строка. Если есть

79     место, прочесть еще одну строку. */

80  if (end – p >= 80)

81   continue;

82

83  /* В конце буфера нужно больше места, поэтому выделить еще.

84     Позаботиться о сохранении текущего смещения в p. */

85 more_buffer:

86  {

87   unsigned long off = p – start;

88   ebuf->size *= 2;

89   start = ebuf->buffer=ebuf->bufstart=(char*)xrealloc(start,

90    ebuf->size);

91   p = start + off;

92   end = start + ebuf->size;

93   *p = '';

94  }

95 }

До сих пор мы имели дело с механизмом получения в буфер по крайней мере одной полной строки. Следующий участок обрабатывает случай строки с продолжением. Хотя он должен гарантировать, что конечный символ обратного слеша не является частью нескольких обратных слешей в конце строки. Код проверяет, является ли общее число таких символов четным или нечетным путем простого переключения переменной backslash из 0 в 1 и обратно. (Строки 64–70.)

Если число четное, условие '!backshlash' (строка 72) будет истинным. В этом случае конечный символ конца строки замещается байтом NUL, и код выходит из цикла.

С другой стороны, если число нечетно, строка содержит четное число пар обратных слешей (представляющих символы \, как в С), и конечную комбинацию символов обратного слеша и конца строки.[43]43
  Этот код несет с собой аромат практического опыта, не удивительно было узнать, что более ранние версии просто проверяли наличие обратного слеша перед символом конца строки, пока кто-то не пожаловался, что он не работает, когда в конце строки есть несколько обратных слешей – Примеч. автора.


[Закрыть] В этом случае, если в буфере остались по крайней мере 80 свободных байтов, программа продолжает чтение в цикле следующей строки (строки 78–81). (Использование магического числа 80 не очень здорово; было бы лучше определить и использовать макроподстановку.)

По достижении строки 83 программе нужно больше места в буфере. Именно здесь вступает в игру динамическое управление памятью. Обратите внимание на комментарий относительно сохранения значения p (строки 83-84); мы обсуждали это ранее в терминах повторной инициализации указателей для динамической памяти. Значение end также устанавливается повторно. Строка 89 изменяет размер памяти.

Обратите внимание, что здесь вызывается функция xrealloc(). Многие программы GNU используют вместо malloc() и realloc() функции-оболочки, которые автоматически выводят сообщение об ошибке и завершают программу, когда стандартные процедуры возвращают NULL. Такая функция-оболочка может выглядеть таким образом:

extern const char *myname; /* установлено в main() */

void *xrealloc(void *ptr, size_t amount) {

 void *p = realloc(ptr, amount);

 if (p == NULL) {

  fprintf(stderr, "%s: out of memory!n", myname);

  exit(1);

 }

 return p;

}

Таким образом, если функция xrealloc() возвращается, она гарантированно возвращает действительный указатель. (Эта стратегия соответствует принципу «проверки каждого вызова на ошибки», избегая в то же время беспорядка в коде, который происходит при таких проверках с непосредственным использованием стандартных процедур.) Вдобавок, это позволяет эффективно использовать конструкцию 'ptr = xrealloc(ptr, new_size)', против которой мы предостерегали ранее.

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

97   if (ferror(ebuf->fp))

98    pfatal_with_name(ebuf->floc.filenm);

99

100  /* Если обнаружено несколько строк, возвратить их число.

101     Если не несколько, но _что-то_ нашли, значит, прочитана

102     последняя строка файла без завершающего символа конца

103     строки; вернуть 1. Если ничего не прочитано, это EOF;

104     возвратить -1. */

105  return nlines ? nlines : p == ebuf->bufstart ? -1 : 1;

106 }

В заключение, функция readline() проверяет ошибки ввода/вывода, а затем возвращает описательное значение. Функция pfatal_with_name() (строка 98) не возвращается.[44]44
  Эта функция завершает выполнение программы – Примеч. науч. ред.


[Закрыть]