From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,95e71dd4ab1859a5,start X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newsfeed.arcor.de!newsspool1.arcor-online.net!news.arcor.de.POSTED!not-for-mail From: "Dmitry A. Kazakov" Subject: A novel design of linked lists (was: Address of an object) Newsgroups: comp.lang.ada User-Agent: 40tude_Dialog/2.0.15.1 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Reply-To: mailbox@dmitry-kazakov.de Organization: cbb software GmbH Date: Tue, 19 Sep 2006 15:30:34 +0200 Message-ID: <1erhzx6bo87fc.lzgqxpirn16r.dlg@40tude.net> NNTP-Posting-Date: 19 Sep 2006 15:30:34 CEST NNTP-Posting-Host: b72f4ac2.newsspool1.arcor-online.net X-Trace: DXC=BJPG`@D[`S X-Complaints-To: usenet-abuse@arcor.de Xref: g2news2.google.com comp.lang.ada:6664 Date: 2006-09-19T15:30:34+02:00 List-Id: [ 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