Типы данных с копированием-при-модификации (простой вариант)

20:00 | Статьи Автор: Vadim Godunko

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

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

В качестве примера будем рассматривать упрощённый аналог стандартного контейнера Ada.Containers.Holders, предназначенный для хранения одного значения определённого при настройке типа данных. Для хранения данных будем использовать структуру данных, состоящую из двух полей: атомарного счётчика ссылок и значения. Над ссылочным типом на эту структуру необходимо иметь три базовые операции:

  • Reference, увеличивающую счётчик ссылок на единицу;
  • Unreference, уменьшающую счётчик ссылок на единицу и освобождающую совместно используемый объект при достижении счётчиком нулевого значения;
  • Detach, выполняющую создание копии объекта для последующей модификации.
1
2
3
4
5
6
7
8
9
10
   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 содержит исключительно вызов подпрограммы увеличения значения счётчика. Для исключения необходимости проверки факта переполнения счётчика предполагается, что он способен хранить достаточно большое значение достигнуть которое невозможно:

1
2
3
4
   procedure Reference (Self : not null Shared_Data_Access) is
   begin
      Counters.Increment (Self.Counter);
   end Reference;

Реализация подпрограммы Unreference вызывает функцию декремента значения счётчика и освобождает задействованный под совместно используемые данные сегмент при достижении счётчиком нулевого значения; в противном случае она просто сбрасывает переданный указатель на значение null (то же самое делает и вызов функции Free):

1
2
3
4
5
6
7
8
9
10
11
  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 можно реализовать весьма просто, как создание нового объекта совместно используемых данных с инициализацией имеющимся значением:

1
2
3
4
5
6
   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 (деструктор):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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:

1
2
3
4
   overriding procedure Adjust (Self : in out Holder) is
   begin
      Reference (Self.Data);
   end Adjust;

Подпрограмма Finalize выполняет вызов подпрограммы Unreference, но необходимо помнить, что язык позволяет осуществлять вызов этой подпрограммы многократно (что имеет место быть в условиях хитросплетённых ситуаций очистки при выявлении непредвиденного поведения программы), поэтому перед вызовом Unreference внутренняя ссылка проверяется на ненулевое значение (значение указателя сбрасывается в null при выполнении подпрограммы Unreference):

1
2
3
4
5
6
   overriding procedure Finalize (Self : in out Holder) is
   begin
      if Self.Data /= null then
         Unreference (Self.Data);
      end if;
   end Finalize;

Подпрограмма Get возвращает хранящееся в совместно используемом объекте значение.

1
2
3
4
   function Get (Self : Holder) return T is
   begin
      return Self.Data.Value;
   end Get;

Подпрограмма Set устанавливает значение внутри совместно используемого объекта, но перед этим выполняет вызов подпрограммы Detach для создания собственной копии данных.

1
2
3
4
5
   procedure Set (Self : in out Holder; Value : T) is
   begin
      Detach (Self.Data);
      Self.Data.Value := Value;
   end Set;

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

В заключение приводится полный исходный текст примера:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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;

Полный комплект исходных текстов можно скачать по ссылке [download id="2"].

Комментарии (2) »