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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,95e71dd4ab1859a5 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!postnews.google.com!m7g2000cwm.googlegroups.com!not-for-mail From: "Adam Beneschan" Newsgroups: comp.lang.ada Subject: Re: A novel design of linked lists (was: Address of an object) Date: 19 Sep 2006 13:09:44 -0700 Organization: http://groups.google.com Message-ID: <1158696584.069704.6780@m7g2000cwm.googlegroups.com> References: <1erhzx6bo87fc.lzgqxpirn16r.dlg@40tude.net> NNTP-Posting-Host: 66.126.103.122 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-Trace: posting.google.com 1158696590 14149 127.0.0.1 (19 Sep 2006 20:09:50 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 19 Sep 2006 20:09:50 +0000 (UTC) User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.7.12) Gecko/20050922 Fedora/1.7.12-1.3.1,gzip(gfe),gzip(gfe) Complaints-To: groups-abuse@google.com Injection-Info: m7g2000cwm.googlegroups.com; posting-host=66.126.103.122; posting-account=cw1zeQwAAABOY2vF_g6V_9cdsyY_wV9w Xref: g2news2.google.com comp.lang.ada:6673 Date: 2006-09-19T13:09:44-07:00 List-Id: Dmitry A. Kazakov wrote: > [ 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. I'll have to admit that I don't see what "problem" you have that this isn't a solution to. In fact, I'm not really clear on why it's important to you to adopt the approach you're adopting; your explanation is pretty sketchy. Part of my problem is that you seem to want to define a type, Item_Ptr, that gives you more than it's supposed to give you. Your generic declares type Item_Ptr is access List_Type_Item; where List_Type_Item is whatever type you're making a list out of. I see a type like this, and I think it's just an access to the List_Type_Item, but there's actually additional baggage in this pointer, i.e. a "next" and a "previous" pointer. So if I see code that calls Next on this Item_Ptr, my first thought is "Whooaa! Item_Ptr is just an access to my Employee record, so where the heck is it going to get a pointer to another Employee?" It would be pretty confusing to me. Personally, if I'm going to have something that contains additional information, I'd prefer that it be a different type. The need for downcasting, type conversion, or a Deref function in your generic that takes an Item_Ptr and returns the dereferenced item that I would use instead of .all, doesn't bother me at all. So I don't see what problem there is that needs solving. Plus, you introduce a problem. Assuming the actual for List_Type_Item is T, you've defined Item_Ptr as an access to T; what happens if somewhere else in the program, there is another type that is also an access to T? The language will let you convert between the two access types, but the result would be an absolute disaster. But I just know that someone who doesn't really understand that Item_Ptr isn't just an access to T is going to try it. Put simply, you're trying to trick your Ada compiler into allowing programmers to use Ada syntax to write code in some other language than Ada, and someone who looks at the Ada code and assumes it's Ada is likely to be pretty darn confused. Anyway, now that I've given you my tirade on why I think this is a bad approach, I'm going to give you an idea of how you might implement your bad approach. The problem with your Next function is that if List_Item_Type is an unconstrained array, there will be extra data between the thing Item_Ptr points to and the Item_Header. Since you've already admitted that this is going to be highly implementation-dependent, then you can probably assume that the size of this extra data is going to be the same always (for a given List_Item_Type), and then all you have to do is figure out what that size is the first time Next [or some other routine] is called. Declare a variable in your package body: Dope_Offset : Storage_Offset := -1; Fix your Allocate so that it saves the resulting Storage_Address in some global Global_Storage_Address in the package body before it returns. Inside Next: X : Item_Ptr; ... if Dope_Offset = -1 then X := new List_Item_Type' (Item.all); Dope_Offset := To_Address(X) - Global_Storage_Address; Free(X); end if; where To_Address is from an instance of System.Address_To_Access_Conversions. Now once Dope_Offset has been set up, you can use it as an offset and subtract it from your From_Item_Ptr calls. -- Adam