alloc (Все лабы по инфе за 2ой сем на С++)

ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ

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

Для динамического распределения используется свободная область памяти в адресном пространстве программы, которую принято называть кучей (heap). В зависимости от принятой модели памяти и операционной среды выполнения программы, куча может быть расположена, либо между границами сегментов данных и стека, либо за верхней границей стека. Требуемые объемы памяти могут распределяться из кучи по адресам сегмента данных. Распределенная память кучи может быть освобождена и становится доступной для повторных распределений. В современных операционнах системах прямое обращение за границу сегмента данных блокируют средства защиты памяти. Требуемый доступ в пространство адресов кучи обеспечивает механизм динамического распределения памяти.

Для прикладной реализации механизма динамического распределения памяти в системе программирования C предусмотрены функции malloc, calloc, free и realloc. Программный интерфейс этих функций обеспечивает заголовочный файл <stdlib.h>, где декларированы типы их аргументов и кода возврата. Некоторые известные реализации системы программирования C предоставляют эквивалентную спецификацию в файлах заголовков <alloc.h> и <malloc.h>. Объектный код функций динамического распределения памяти сосредоточен в стандартной библиотеке объектных модулей системы программирования C.

Функция malloc позволяет динамически распределить блок памяти заданного размера. Спецификация формата ее вызова имеет вид:

void* malloc(unsigned size);

Функция malloc реализует просмотр свободных блоков из кучи, чтобы найти сплошное пространство памяти, размер которого в байтах не меньше, чем задано параметром size. В случае успеха она возвращает адреса первого свободного блока памяти достаточного размера. Полученный адрес следует использовать для доступа к содержимому выделенного блока памяти после явного преобразования типа. Если требуемый объем памяти не может быть выделен, или значение параметра size равно 0, функция malloc возвращает нулевой указатель NULL.

Функция calloc обеспечивает динамическое распределение памяти кучи под массив элементов. Спецификация формата ее вызова имеет вид:

void* calloc(unsigned num, unsigned size);

Через аргументы num и size в функцию calloc передаются требуемое число элементов и размер каждого элемента массива. Таким образом, суммарный объем памяти, выделенный при обращении к функции calloc, равен (num*size) байтов. Все элементы выделенного массива автоматически инициализируются нулевыми значениями. При успешном завершении функция calloc возвращает адрес динамически распределенного массива. Если требуемый объем памяти не может быть выделен, или значения аргументов равны 0, функция calloc возвращает нулевой указатель NULL.

Использование функций malloc и calloc иллюстрирует пример динамического распределения памяти для узла списка. В нем предполагается, что каждый узел списка специфицирует программная структура struct Node, декларация которой имеет следующий формат:

struct Node {

char* data; /* информационное поле */

struct Node* next; /* адресное поле */

}; /* Node */

Адресное поле next этой структуры обеспечивает связь со следующим узлом списка. Информационное поле data должно адресовать символьную строку данных узла. При формировании нового узла списка необходимо динамически распределить память под структуру struct Node и для хранения символьной строки данных. Требуемое распределение памяти обеспечивает следующий исходный код прикладной функции alloc.

/* Динамическое распределение узла списка */

struct Node* alloc(char* str, unsigned len) {

struct Node* ptr; /* Указатель на структуру узла списка */

unsigned size; /* Размер структуры узла списка */

int count = 0; /* Счетчик символов в строке данных */

/* Вычислить объем структуры узла списка */

size = sizeof(struct Node);

/* Распределить память для узла списка */

if((ptr = (struct Node *) malloc(size)) == NULL)

return(NULL);

/* Распределить память для информационного поля узла списка */

if((ptr->data = (char* ) calloc((len + 1), 1)) == NULL)

count = len;

/* Копирование данных в информационное поле узла списка */

while(count < len)

ptr->data[count++] = *str++;

/* Возврат адреса распределенного узла списка */

return(ptr);

} /* alloc */

При вызове в функцию alloc следует передать адрес и длину строки данных, которые обозначают аргументы str и len, соответственно. В случае успеха распределения памяти функция alloc возвращает адрес нового узла списка. Его можно использовать, чтобы, например, добавить узел в конец текущего списка или вставить после заданного узла списка.

Эффективность динамического распределения памяти определяет не только способность выделить точно такой объем памяти, какой нужен в программе, но и возможность освобождать распределенную память, когда информация в ней перестает быть необходима. Чтобы освобождать динамически выделенную память, в системе программирования C предусмотрена функция free. Формат ее вызова имеет вид:

void free(void* ptr);

Единственный аргумент функции free должен быть указателем на блок или массив динамически распределенной памяти, которую нужно освободить. При обращении к функции free содержимое области памяти, которую адресует ее аргумент ptr, остается неизменным, но становится недоступным программе в данный момент. Однако, адресное пространство, освобожденное вызовами функции free, может быть выделено повторно при последующих запросах динамического распределения памяти. Следует отметить, что вызов функции free с произвольным указателем, который не адресует динамически распределенную память, приводит к ошибке нарушения сегментации адресного пространства программы. Однако, когда ее аргумент является нулевым указателем NULL, функция free не делает ничего.

В прикладном программировании функция free используется, например, при обработке списка для исключения заданного узла. Предположим, что каждый узел списка специфицирует программная структура struct Node, описание которой приведено выше, а память для узлов списка и их информационных полей была динамически распределена вызовами функций malloc и calloc. Поэтому при исключении узла списка, когда необходимо освободить динамически выделенную память, следует использовать функцию free. Требуемую схему исключения реализует исходный код прикладной процедуры destroy, которой передается адрес узла, следующий за которым нужно исключить из списка. Процедура destroy дважды вызывает функцию free, чтобы последовательно освободить динамически распределенную память информационного поля и структуры узла списка.

/* Исключение следующего узла списка */

void destroy(struct Node* addr) {

struct Node* ptr; /* Адрес следующего узла списка */

/* Получить адрес исключаемого узла списка */

if((ptr = addr->next) == NULL)

return;

/* Переадресация связей в списке */

addr->next = ptr->next;

/* Освободить память информационного поля узла списка */

free((void* ) ptr->data);

/* Освободить память структуры узла списка */

free((void* ) ptr);

} /* destroy */

В некоторых прикладных программах требуется изменять размер динамически распределенной памяти. Необходимую регулировку размера распределенной памяти выполняет функция realloc. Спецификация формата ее вызова имеет вид:

void* realloc(void* ptr, unsigned size);

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

При нулевом значении параметра размера size действие функции realloc эквивалентно вызову функции free. Когда в функцию realloc вместо адреса блока ptr передается нулевой указатель NULL, ее действие эквивалентно вызову malloc. При ненулевых аргументах она комбинирует вызовы функций malloc и free. Внутренний вызов функции free освобождает блок памяти, адресуемый указателем ptr. Вместо него внутренний вызов функции malloc распределяет новый блок памяти c заданным размером size, где содержимое старого блока сохраняется в максимально возможном объеме.

Функция realloc возвращает адрес модифицированного блока памяти, так как не исключена вероятность его перемещения в адресном пространстве программы при увеличении размера. Если перемещение блока не происходит, его адрес до и после модификации размера остается неизменным, поэтому корректный возврат функции realloc совпадает со значением ее аргумента ptr. Когда требуемое изменение размера адресуемой памяти не может быть реализовано, функция realloc возвращает нулевой указатель NULL. При этом содержимое памяти, адресуемой аргументом ptr может быть искажено.

На практике функция realloc обычно применяется для программирования динамических массивов, размер которых меняется в процессе обработки. Динамический массив должен расширяться при поступлении новых данных и сокращаться при исключении информации, сохраняя свойства однородности состава и прямого доступа к своим элементам. Такая организация данных более экономична, чем обычный фиксированный массив или связный список. Фиксированный массив ограничен сверху по объему данных и сохраняет свой предельный размер даже тогда, когда в нем нет информации. Организация списка требует дополнительных затрат памяти для адресных полей связи элементов, причем скорость обработки данных ниже, чем в массиве, потому что структура списка допускает только последовательный доступ к данным. Отсутствие перечисленных ограничений и недостатков делает динамические массивы более привлекательными для обработки однородных наборов данных переменной длины, чем традиционные информационные структуры.

Применение функции realloc для формирования динамически расширяемого массива целых чисел иллюстрирует следующий исходный код, представленный в виде прикладной функции more.

int* more(int* dyn, int item) {

int* ptr; /* адрес расширяемого массива */

unsigned size; /* размер области памяти для размещения массива */

unsigned len; /* число элементов массива */

/* Вычисление требуемой длины и размера массива */

len = dyn[0] + 1;

size = (len + 1) * sizeof(int);

/* Расширение массива */

if((ptr = (int* ) realloc((void *) dyn, size)) == NULL)

return(NULL);

/* Добавление нового элемента в массив */

ptr[len] = item; ptr[0] = len;

/* Возврат адреса массива */

return(ptr);

} /* more */

При вызове в функцию more следует передать адрес динамического массива целых чисел через указатель dyn и добавляемое в него значение целого числа, которое обозначает параметр item. Предполагается, что значение начального элемента адресуемого массива (dyn[0]) сохраняет количество целых чисел, накопленных в нем. Такая структура динамического массива позволяет легко определить его размер для расширения функцией realloc, чтобы добавить еще один элемент для размещения заданного целого числа, которое передает значение параметра item. При успехе перераспределения памяти функция more возвращает адрес расширяемого динамического массива в программу, которая ее вызывает.