Бертран Мейер - Основы объектно-ориентированного программирования

Допустим, класс LINKED_LIST имеет только две процедуры вставки: put_right и put_left , вставляющие новый элемент справа или слева от текущей позиции курсора. Каждой процедуре вставки необходимо создать ровно один новый LINKABLE объект. Типичная реализация приведена ниже:

put_right (v: ELEMENT_TYPE) is

- Вставка элемента со значением v правее позиции курсора.

require

...

local

new: LINKABLE

do

create new.make (v)

active.put_linkable_right (new)

... Инструкции по изменению других связей...

end

Рис. 9.11. Связный список

Инструкция создания create new.make (v) дает указание уровню реализации языка разместить в памяти новый объект.

Точно так же, как мы управляем тем, где создавать объекты, мы точно знаем, где они становятся недостижимыми, - в процедурах удаления. Пусть в нашем классе три такие процедуры: remove , remove_right , remove_left . Могут быть также и другие процедуры, такие как remove_all_occurrences (которая удаляет все экземпляры с определенным значением) и wipe_out (удаляет все элементы списка). Допустим, что если они присутствуют, то используют первые три процедуры удаления. Процедура remove , например, может иметь следующую форму:

remove is

- удаляет элемент текущей позиции курсора.

do

...

previous.put_linkable_right (next)

... Инструкции по изменению других связей...

active := next

end

Рис. 9.12. Удаление объекта

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

Предположим, экземпляры LINKABLE хранятся в структуре данных, называемой available . Она будет представлена ниже. Тогда можно заменить инструкции создания типа create new.make (v) в put_right и put_left на

new := fresh (v)

где fresh закрытая функция класса LINKED_LIST , возвращающая готовый к использованию экземпляр linkable . Функция fresh пытается получить память из available списка, и выполнит создание нового элемента только, когда этот список пуст.

Элементы будут попадать в available в процедурах удаления. Например, тело процедуры remove теперь должно быть:

do

recycle (active)

- остальное без изменений:

... Инструкции по обновлению связей: previous, next, first_element, active...

где recycle новая процедура LINKED_LIST играет роль, противоположную fresh , добавляя свой аргумент в available . Эта процедура будет закрытой, она нужна только для внутреннего использования.

Для реализации fresh и recycle , можно среди других возможных вариантов представить available как стек: fresh будет удалять элемент из стека, а recycle будет помещать элемент в стек. Создадим класс STACK_OF_LINKABLES для этого случая и добавим следующие закрытые компоненты в класс LINKED_LIST (В упражнении У23.1. требуется определить, будет ли корректным появление у функции fresh побочных эффектов.):

available: STACK_OF_LINKABLES

fresh (v: ELEMENT_TYPE): LINKABLE is

- Новый элемент со значением v, для повторного

- использования во вставке

do

if available.empty then

- Создание нового элемента

create Result.make (v)

else

- Повторное использование linkable

Result := available.item; Result.put (v); available.remove

end

end

recycle (dead: LINKABLE) is

-Возвращает dead в список достижимых элементов.

require

dead /= Void

do

available.put (dead)

end

Мы можем объявить класс STACK_OF_LINKABLES следующим образом:

class