Типы данных с копированием‐при‐модификации
простой вариант
Автор: Vadim Godunko
Дата: 16.09.2012
Типы данных с копированием‐при‐модификации находят широкое применение в современной программной индустрии с целью упрощения управления и минимизации объёма использованной динамической памяти. Менее известными, но подчас более важными свойствами таких типов данных является константное время выполнения операции присваивания и использование небольшого и независящего от фактического размера данных объёма памяти стэка, используемой для объектов.
Для реализации обычно используется технология неявного совместного использования данных, когда объект хранит только ссылку на сегмент совместно используемых данных, а управление освобождением сегмента совместно используемых данных осуществляется с использованием счётчика ссылок. В общем случае эта технология имеет одно важное ограничение, не позволяющее активно использовать её в Ada программах — сегмент совместно используемых данных не должен использоваться более чем одной задачей. Для снятия этого ограничения достаточно защитить счётчик ссылок от одновременного доступа несколькими задачами. В предыдущей статье обуждался вопрос эффективной реализации атомарного счётчика ссылок с достаточной степенью переносимости, что даёт возможность создания эффективной реализации типов данных с копированием‐при‐модификации.
В качестве примера будем рассматривать упрощённый аналог стандартного контейнера Ada.Containers.Holders, предназначенный для хранения одного значения определённого при настройке типа данных. Для хранения данных будем использовать структуру данных, состоящую из двух полей: атомарного счётчика ссылок и значения. Над ссылочным типом на эту структуру необходимо иметь три базовые операции:
- Reference, увеличивающую счётчик ссылок на единицу;
- Unreference, уменьшающую счётчик ссылок на единицу и освобождающую совместно используемый объект при достижении счётчиком нулевого значения;
- Detach, выполняющую создание копии объекта для последующей модификации.
#ada
type Shared_Data is record
Counter : aliased Counters.Counter;
Value : T;
end record;
type Shared_Data_Access is access all Shared_Data;
procedure Reference (Self : not null Shared_Data_Access);
procedure Unreference (Self : in out Shared_Data_Access);
procedure Detach (Self : in out not null Shared_Data_Access);
Реализация подпрограммы Reference содержит исключительно вызов подпрограммы увеличения значения счётчика. Для исключения необходимости проверки факта переполнения счётчика предполагается, что он способен хранить достаточно большое значение достигнуть которое невозможно:
#ada
procedure Reference (Self : not null Shared_Data_Access) is
begin
Counters.Increment (Self.Counter);
end Reference;
Реализация подпрограммы Unreference вызывает функцию декремента значения счётчика и освобождает задействованный под совместно используемые данные сегмент при достижении счётчиком нулевого значения; в противном случае она просто сбрасывает переданный указатель на значение null (то же самое делает и вызов функции Free):
#ada
procedure Unreference (Self : in out Shared_Data_Access) is
procedure Free is
new Ada.Unchecked_Deallocation (Shared_Data, Shared_Data_Access);
begin
if Counters.Decrement (Self.Counter'Access) then
Free (Self);
else
Self := null;
end if;
end Unreference;
Подпрограмму Detach можно реализовать весьма просто, как создание нового объекта совместно используемых данных с инициализацией имеющимся значением:
#ada
procedure Detach (Self : in out not null Shared_Data_Access) is
Old : Shared_Data_Access := Self;
begin
Self := new Shared_Data'(Counter => <>, Value => Old.Value);
Unreference (Old);
end Detach;
Интерфейс настраиваемого пакета состоит из типа‐контейнера, константы этого типа, представляющей «пустое» значение и подпрограмм для установки и получения значения; тип‐контейнер является контролируемым и для него переопределяются стандартные подпрограммы Adjust (копирование) и Finalize (деструктор):
#ada
private with Ada.Finalization;
private with Counters;
generic
type T is private;
package Holders is
type Holder is private;
Empty : constant Holder;
procedure Set (Self : in out Holder; Value : T);
function Get (Self : Holder) return T;
private
...
type Holder is new Ada.Finalization.Controlled with record
Data : Shared_Data_Access := new Shared_Data;
end record;
overriding procedure Adjust (Self : in out Holder);
overriding procedure Finalize (Self : in out Holder);
Empty : constant Holder := (Ada.Finalization.Controlled with others => <>);
end Holders;
Тип Holder содержит одно единственное поле — ссылку на совместно испольуемый объект данных. Это поле автоматически инициализируется при создании объекта типа Holder ссылкой на выделенный совместно используемый объект. Поскольку, согласно соглашению, счётчик автоматически инициализируется значением 1 нет необходимости увеличивать его значение и переопределять подпрограмму Initialize.
Подпрограмма Adjust выполняет вызов описанной выше подпрограммы Reference:
overriding procedure Adjust (Self : in out Holder) is
begin
Reference (Self.Data);
end Adjust;
Подпрограмма Finalize выполняет вызов подпрограммы Unreference, но необходимо помнить, что язык позволяет осуществлять вызов этой подпрограммы многократно (что имеет место быть в условиях хитросплетённых ситуаций очистки при выявлении непредвиденного поведения программы), поэтому перед вызовом Unreference внутренняя ссылка проверяется на ненулевое значение (значение указателя сбрасывается в null при выполнении подпрограммы Unreference):
#ada
overriding procedure Finalize (Self : in out Holder) is
begin
if Self.Data /= null then
Unreference (Self.Data);
end if;
end Finalize;
Подпрограмма Get возвращает хранящееся в совместно используемом объекте значение.
#ada
function Get (Self : Holder) return T is
begin
return Self.Data.Value;
end Get;
Подпрограмма Set устанавливает значение внутри совместно используемого объекта, но перед этим выполняет вызов подпрограммы Detach для создания собственной копии данных.
#ada
procedure Set (Self : in out Holder; Value : T) is
begin
Detach (Self.Data);
Self.Data.Value := Value;
end Set;
Как видно из примера, шаблон реализации типов с копированием‐при‐модификации достаточно прост. Отметим, что рассмотренная реализация может быть усовершенствована для повышения производительности, эффективности использования памяти, возможности использования в пакетах категории Preelaborate, а в некоторых случаях и для использования Preelaborable_Initialization типов. Вопросы возможной оптимизации будут рассмотрены в следующей статье.
В заключение приводится полный исходный текст примера:
private with Ada.Finalization;
private with Counters;
generic
type T is private;
package Holders is
type Holder is private;
Empty : constant Holder;
procedure Set (Self : in out Holder; Value : T);
function Get (Self : Holder) return T;
private
type Shared_Data is record
Counter : aliased Counters.Counter;
Value : T;
end record;
type Shared_Data_Access is access all Shared_Data;
procedure Reference (Self : not null Shared_Data_Access);
procedure Unreference (Self : in out Shared_Data_Access);
procedure Detach (Self : in out not null Shared_Data_Access);
type Holder is new Ada.Finalization.Controlled with record
Data : Shared_Data_Access := new Shared_Data;
end record;
overriding procedure Adjust (Self : in out Holder);
overriding procedure Finalize (Self : in out Holder);
Empty : constant Holder
:= (Ada.Finalization.Controlled with others => <>);
end Holders;
#ada
with Ada.Unchecked_Deallocation;
package body Holders is
------------
-- Adjust --
------------
overriding procedure Adjust (Self : in out Holder) is
begin
Reference (Self.Data);
end Adjust;
------------
-- Detach --
------------
procedure Detach (Self : in out not null Shared_Data_Access) is
Old : Shared_Data_Access := Self;
begin
Self := new Shared_Data'(Counter => <>, Value => Old.Value);
Unreference (Old);
end Detach;
--------------
-- Finalize --
--------------
overriding procedure Finalize (Self : in out Holder) is
begin
if Self.Data /= null then
Unreference (Self.Data);
end if;
end Finalize;
---------
-- Get --
---------
function Get (Self : Holder) return T is
begin
return Self.Data.Value;
end Get;
---------------
-- Reference --
---------------
procedure Reference (Self : not null Shared_Data_Access) is
begin
Counters.Increment (Self.Counter);
end Reference;
---------
-- Set --
---------
procedure Set (Self : in out Holder; Value : T) is
begin
Detach (Self.Data);
Self.Data.Value := Value;
end Set;
-----------------
-- Unreference --
-----------------
procedure Unreference (Self : in out Shared_Data_Access) is
procedure Free is
new Ada.Unchecked_Deallocation (Shared_Data, Shared_Data_Access);
begin
if Counters.Decrement (Self.Counter'Access) then
Free (Self);
else
Self := null;
end if;
end Unreference;
end Holders;
|
