Ada：泛型、不完整类型和自引用结构的困难

Question

在 Ada 中很容易做到这一点：

type ITEM_RECORD;
type ITEM_ACCESS is access ITEM_RECORD;
type ITEM_RECORD Is
record
   ITEM: item_type;
   Next: item_access;
   Pred: item_access;
end record;

简单吧？现在，如果我想 ITEM_ACCESS 成为在通用包中声明的 smart/safe 指针，我该怎么办？我直觉地这样做，如果它有效的话：

type ITEM_access;
type Item_Record is record
  Item : Item_Type;
  Next : Item_Access;
  Pred : Item_Access;
end record;
type pointers_on_record is access Item_record;
package pointers_p is new pointers(Item_Record, pointers_on_record);
type item_access is new pointers_p.Pointer_Type;

仿制药的规格如下：

generic
   type Item_Type(<>) is limited private;
   type Access_Type is access Item_Type;
package Pointers is
   type Pointer_Type is private;

我还没想好怎么做。

谢谢！

Answer 1

由于循环依赖性，无法创建您要创建的结构。想想看：

通用包定义了一个指针。 Pointer_Type 的结构和实现（可能）取决于通用参数 Item_Type （这不一定是真的，但如果不是，就没有必要 Item_Type 作为通用参数）。现在，通用包实例化中的 Item_Type 包含来自通用包的两个智能指针，因此取决于 Pointer_Type 的结构。这是一个经典的 chicken-or-the-egg 问题。

因此解决方案是更改类型的设计。让我给你一些建议（没有双关语）：

您似乎正在实施 doubly-linked 列表。请注意，由于列表的循环性质，使用实现引用计数的智能指针是一个严重的错误。如果您的列表至少有两个项目，则不会释放任何东西，因为它们总是指向彼此。因此，除非您的智能指针正在进行循环检测（根据您的规范这是不可能的），否则您不能使用 smart 指向您想要的方式。

一个可能的解决方案是将智能指针指向 Item_Type，而不是记录。您将需要手动取消分配记录，但无论如何您都需要按照上述说明进行操作。

另一种解决方案是为整个列表设置一个全局引用计数器。创建一个不透明的列表类型，为列表提供访问器和迭代器子例程，这些子例程将智能指针分发给项目。智能指针增加和减少整个列表的引用计数，一旦对列表的最后一个引用消失，整个列表将被释放。因此，只要存在对其中某物的至少一个引用，该列表就存在。此解决方案需要您自己实现引用计数，因为它专门用于列表结构。

最后，您当然可以像 Jeffrey 建议的那样使用 Ada.Containers.Doubly_Linked_Lists。正如我在第一个解决方案中所建议的那样，您可以在其中放置指向 Item_Type 的智能指针。

Answer 2

为了使用智能指针实现，您的智能指针必须使用不完整的类型。因此，您还必须提供删除访问变量（当然还有访问类型）的终结过程。这当然也意味着您的分配函数需要采用访问类型而不是变量。最后，你绝对需要使用弱指针来打破引用计数智能指针产生的循环引用。

generic
   type Item_Type(<>);
   type Item_Access is access Item_Type;
   with procedure Finalize(Ref : in out Item_Access);
package Pointers is
   function Make(Ref : not null Item_Access) return Smart_Pointer;
   -- other stuff
end Pointers;

然后你可以这样做：

   type Node_Impl;
   type Node_Access is access Node_Impl;
   procedure Finalize(Ref : in out Node_Access);

   package Ptrs is new Pointers(Node_Impl,Node_Access,Finalize);

   subtype Node is Ptrs.Smart_Pointer;
   subtype Weak_Node is Ptrs.Weak_Pointer;

   type Node_Impl is record
      Value : Some_Type;
      Next : Node;
      Prev : Weak_Node;
   end record;

这是我用来制作带有智能指针的 AVL 树的示例规范。我手边没有链表示例。

package Trees is
   type Node;
   type Node_Access is access Node;
   procedure Finalize(Memory : in out Node_Access);

   package Node_Smart_Access is new Smart_Access
      (Item_Type        => Node,
       Item_Access      => Node_Access,
       Finalize         => Finalize,
       Atomic_Increment => True);

   type Node is record
      Value  : Integer := 0;
      Height : Integer := 1;
      Parent : Node_Smart_Access.Weak_Access;
      Left   : Node_Smart_Access.Shared_Access;
      Right  : Node_Smart_Access.Shared_Access;
   end record;

   type Tree is tagged record
      Root : Node_Smart_Access.Shared_Access;
   end record;

end Trees;

我的智能指针规格是：

generic
   type Item_Type(<>);
   type Item_Access is access Item_Type;
   with procedure Finalize(Memory : in out Item_Access);
   Atomic_Increment : Boolean := True;
package Smart_Access is

   type Shared_Access is new Ada.Finalization.Controlled with private;
   type Weak_Access is new Ada.Finalization.Controlled with private;

   -- more stuff

   package Make is
      function Shared_Access
         (Source : in not null Item_Access)
          return Smart_Access.Shared_Access;
      -- more stuff
   end Make;
private
   -- implementation
end Smart_Access;

这很麻烦，但是如果您想在 Ada 中使用智能指针创建自引用类型，则需要这样做。另请注意，如果您在智能指针规范中使用不完整类型，则某些版本的 GNAT 会在 Implicit_Dereference 方面存在编译器错误。如果您使用的版本有错误，它们将在您编译时导致编译器崩溃。

Ada：泛型、不完整类型和自引用结构的困难

Ada: Difficulties with generics, incomplete types and self-referencing structures

generics

packages

ada

package