A novel design of linked lists (was: Address of an object)

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

[ It seems to me that some people have an impression that I am looking for
something extraordinary when asking for the object address, so I feel
necessary to provide an elaborated example where it were needed. ]

Let's consider referential double-linked lists as an example. The drawbacks
of the Ada.Containers design are obvious. A typical design of such lists in
other languages would be adding Prev, Next pointers to the elements. Note
also, that we wished to have linked lists of elements which might
participate in many lists simultaneously. We also liked to statically check
the types of such lists, so that paths in different lists could never
converge.

There are two ways to do add links Prevs and Nexts. One of them is to do it
upon inheritance. Another is by using new elements containing pointers to
the "true" elements.

1. The variant with inheritance is not an option in current Ada, because of
lack of MI. Even with MI it faces the problem that links has to be added to
the base type. That would require downcasting later, all over the program.
Adding links in the leaves of the type hierarchy would break it apart and
also freeze the types for future derivation. Ad-hoc supertypes could help,
but, firstly, they are not supported and, secondly, they barely could have
referential semantics. So the elements will require copying.

2. The variant with pointers is not a solution at all, because, honestly,
it would be a list of pointers rather than of the elements.

An alternative to these two variants would be to add links transparently
without intervening with *what* is the element. Ada's pools provide this
functionality. The package could go as follows:

with System;                   use System;
with System.Storage_Elements;  use System.Storage_Elements;
with System.Storage_Pools;     use System.Storage_Pools;

generic
   type List_Identification_Type is (<>);
   type List_Item_Type (<>) is limited private;
   Pool : in out Root_Storage_Pool'Class;
package Generic_Linked_Lists is

Here:

- List_Identification_Type is an enumeration type to name the lists. An
element may participate in exactly one list corresponding to the given
value of List_Identification_Type.
- List_Item_Type is the type of elements.
- Pool is the pool where elements will be eventually allocated

The package defines its own pool type, which takes memory from another pool
and the object Items_Pool of this type bound to the actual pool passed as
the generic formal parameter Pool. [ It would be nice to default it to the
standard pool, but, I don't know any good way to do it. ]

   type Items_Storage_Pool (Host : access Root_Storage_Pool'Class) is
      new Root_Storage_Pool with null record;
   ...
   Items_Pool : Items_Storage_Pool (Pool'Access);

Then it defines a pointer type to refer the list items:

   type Item_Ptr is access List_Item_Type;
   for Item_Ptr'Storage_Pool use Items_Pool;

Then it defines the list operations in the terms of this pointer type. Note
that unlikely to Ada.Containers the semantics is referential. Nothing is
copied. So Insert looks like:

   procedure Insert
             (  List  : List_Identification_Type;
                Head  : in out Item_Ptr;
                Item  : Item_Ptr;
                Order : Item_Disposition := After
             );

- List identifies the list type we are dealing with. The same item can be
situated in as many lists as the range of List_Identification_Type.

- Head is the pointer to the list. In can be null. when the first item is
inserted.

- Item is the pointer to the item to insert.

- Order is an enumeration After or Before. When Item is placed before Head,
Head is set to Item.

The use of Insert is trivial and need not to be illustrated. A new Item is
created using plain "new." Other operations could be:

   procedure Move
             (  List   : List_Identification_Type;
                Target : in out Item_Ptr;
                Item   : Item_Ptr;
                Source : in out Item_Ptr;
                Order  : Item_Disposition := After
             );

Moves Item form one list to another. Both lists are of the same type.

   function Next
            (  List : List_Identification_Type;
               Item : Item_Ptr
            )  return Item_Ptr;

Returns the next item in the list

   function Previous
            (  List : List_Identification_Type;
               Item : Item_Ptr
            )  return Item_Ptr;

   procedure Remove
             (  List : List_Identification_Type;
                Head  : in out Item_Ptr; 
                Item  : Item_Ptr;
                Order : Item_Disposition := After
             );

Removes Item from the list.

For dealing with the elements of one list type without specifying the type,
a small wrapper package could be provided:

generic
   List : List_Identification_Type;
package Generic_Linked_Lists.Generic_List is
   type List_Ptr is new Item_Ptr;
   procedure Insert
             (  Head  : in out List_Ptr;
                Item  : Item_Ptr;
                Order : Item_Disposition := After
             );
   procedure Move
             (  Target : in out List_Ptr;
                Item   : Item_Ptr;
                Source : in out List_Ptr;
                Order  : Item_Disposition := After
             );
   function Next (Item : Item_Ptr)  return List_Ptr;
   function Previous (Item : Item_Ptr) return List_Ptr;
   procedure Remove
             (  Head  : in out List_Ptr; 
                Item  : Item_Ptr;
                Order : Item_Disposition := After
             );
end Generic_Linked_Lists.Generic_List;

Note that locally defined List_Ptr is a "list specific" pointer, while Item
is a sort of "class-wide" pointer, valid across all list types. So Item in
all calls is just a pointer to an item, while Head controls "dispatch" to
the proper list. [ Of course no dynamic dispatch happens. It is a static
polymorphism. ]

Now how this works. When an element is allocated, Allocate of
Items_Storage_Pool places the array of links

   type List_Header is record
      Next : Address;
      Prev : Address;
   end record;
   type Item_Header is array (List_Identification_Type) of List_Header;

in front of it. Allocate looks like this:

   procedure Allocate
             (  Pool            : in out Items_Storage_Pool;
                Storage_Address : out Address; 
                Size            : Storage_Count;
                Alignment       : Storage_Count
             )  is
      Header_Alignment : constant Storage_Count :=
         Storage_Count'Max (Item_Header'Alignment, Alignment);
      Header_Offset    : constant Storage_Offset :=
         Header_Size + (-Header_Size) mod Header_Alignment;
   begin
      Allocate -- Grab memory in the host pool
      (  Pool.Host.all,
         Storage_Address,
         Size + Header_Offset,
         Header_Alignment
      );
      Storage_Address := Storage_Address + Header_Offset;
      declare
         Header : Item_Header renames To_Header (Storage_Address).all;
      begin
         for List in Header'Range loop
            Header (List).Next := Null_Address; -- Links initialization
         end loop;
      end;
   end Allocate;

When Next, Insert etc are called Item_Header is obtained from the pointer
and, the rest is obvious. For example Next:

   function Next
            (  List : List_Identification_Type;
               Item : Item_Ptr
            )  return Item_Ptr is
   begin
      return To_Item_Ptr (To_Header (From_Item_Ptr (Item)) (List).Next);
   end Next;

It works perfectly well for all types except ones for which the compiler
mangles pointers, as I have explained in other thread.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de