Функциональные и свободные списки

6.7.1 Общая характеристика функционального и свободного списка

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

Свободный список формируется из элементов, исключаемых из функционального списка. Операцию исключения можно изобразить с помощью рисунка 6.14, на котором показана операция исключения третьего узла. Если на удаляемом элементе не сохранить указатель (как на рисунке 6.14 6), то его слот перестанет быть адресуемым, то есть в куче появится неадресуемое пространство - «дыра». С целью экономии памяти исключенный элемент следует включить в список, сформированный из других исключенных элементов одинакового формата, то есть в свободный список. В дальнейшем прежде чем добавить в функциональный список новый элемент, следует проверить соответствующий свободный список, и, если в свободном списке есть элементы, то взять элемент из него, а не создавать в памяти новый элемент.

Рисунок 6.14 - Исключение в связном списке

В Delphi распределением и освобождением памяти занимается очень сложный диспетчер кучи. Диспетчер кучи содержит код, который позволяет манипулировать кусками памяти. Диспетчер кучи Delphi использует свободный список освобожденных блоков памяти различного размера. Некоторые массивы в Delphi используют цепочку удаленных элементов, которая является ни чем иным, как другим названием свободного списка. Многие базы данных поддерживают скрытый свободный список удаленных записей, которые можно использовать повторно.

6.7.2 Методы формирования свободного списка

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

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

В методе сборки мусора (garbage collection) не требуется при разрыве каждой связки делать проверку элемента и возвращать освободившийся элемент в свободный список. Освободившийся элемент как бы «повисает» до тех пор, пока не будет исчерпан свободный список. И только после этого запускается процедура «сборки мусора», которая отыскивает все освободившиеся к тому времени элементы и включает их в свободный список. Для реализации метода сборки мусора в каждом элементе многосвязной структуры резервируется минимально возможное поле памяти для маркера, который используется на этапе поиска освободившегося элемента. С этой целью процедура маркирует все доступные элементы многосвязной структуры, т. е. такие элементы, к которым направлен хотя бы один указатель. Затем просматривается вся область памяти, отведенная для элементов, и в свободный список включаются все элементы, в которых отсутствует маркер.

Диспетчер кучи Delphi создает список свободных областей (free space list) по мере выполнения процедур «уничтожения» динамических переменных, таких, например, как Dispose.