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,2cb1f0b6d642e1dc X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news4.google.com!proxad.net!feeder1-2.proxad.net!newsfeed.straub-nv.de!noris.net!newsfeed.arcor.de!newsspool1.arcor-online.net!news.arcor.de.POSTED!not-for-mail Date: Tue, 29 Mar 2011 01:47:34 +0200 From: Georg Bauhaus User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9 MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Pascal Calling Convention References: <9b04626e-567d-408c-aab3-39b964b3ffd6@l2g2000prg.googlegroups.com> <4d90efdd$1$14806$882e7ee2@usenet-news.net> <330393be-cb82-4cd8-ba44-6e59af7b75bf@v11g2000prb.googlegroups.com> <4d90fd41$1$14782$882e7ee2@usenet-news.net> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <4d911e17$0$6776$9b4e6d93@newsspool3.arcor-online.net> Organization: Arcor NNTP-Posting-Date: 29 Mar 2011 01:47:35 CEST NNTP-Posting-Host: f1cead3f.newsspool3.arcor-online.net X-Trace: DXC=d[2nPCY\c7>ejVho3WUk\B84onC=a1RG5l7Kl X-Complaints-To: usenet-abuse@arcor.de Xref: g2news2.google.com comp.lang.ada:19531 Date: 2011-03-29T01:47:35+02:00 List-Id: On 3/29/11 12:08 AM, Adam Beneschan wrote: > On Mar 28, 2:26 pm, Hyman Rosen wrote: >> On 3/28/2011 5:16 PM, Adam Beneschan wrote: >> >>> I hope your "favorite data structure" comment was sarcastic. I would >>> expect this code to behave incorrectly a large portion of the time; >>> specifically, if I read the code right, once you add any element to >>> the set, the program is likely to think 0 is in the set whether you've >>> added it or not. >> >> I wrote the code from memory so it's possible I made a mistake, >> but I don't think you're correct - you're likely not reading the >> code right. > > OK, I've looked at it again and you may be right. However, it's also > not a relevant example; I don't see how any compiler could reasonably > detect ... Won't this example of a set be the kind of Ada program that Ada 2012 analyzers (of aspect annotations) are waiting for? > On top of that, I don't see why anyone would prefer this over the > trivial structure that just allocates N bytes, initializes them to 0, > and sets a byte to 1 to add an element to the set, etc. I think one can expand the example with little effort to become an efficient hashed set/map, one that requires very little run-time support in comparison to Ada.Containers.*, I should think. (It might have start as one, sorry in case I haven't seen this, or misrepresent it.) A transliteration attempt follows, with these additions in mind. pragma Profile(Ravenscar); pragma Restrictions (No_Allocators); generic type unsigned is mod <>; N : unsigned; -- capacity, hash(d) < N! type t is private; -- values in sets (maps) with function hash (d : t) return unsigned; -- must return the `k` parameter of set (map) operations package Sets is type set is tagged private; function has(this : set; k : unsigned) return Boolean; procedure add(this : in out set; k : unsigned; data : t); procedure del(this : in out set; k : unsigned); procedure clr(this : in out set); private type uptr is array (unsigned range <>) of unsigned; type dptr is array (unsigned range <>) of t; type set is tagged record n : unsigned := 0; d : dptr(0 .. Sets.N - 1); s : uptr(0 .. Sets.N - 1); -- `hash(d(s(k))) = k` if `d` has been stored at `k` end record; end Sets; package body Sets is function has(this : set; k : unsigned) return Boolean is n : unsigned renames this.n; s : uptr renames this.s; d : dptr renames this.d; begin return k < Sets.N and then s(k) < n and then hash(d(s(k))) = k; end has; procedure add(this : in out set; k : unsigned; data : t) is n : unsigned renames this.n; s : uptr renames this.s; d : dptr renames this.d; begin if k < Sets.N and then not this.has(k) then d(n) := data; s(k) := n; n := n + 1; end if; end add; procedure del(this : in out set; k : unsigned) is n : unsigned renames this.n; s : uptr renames this.s; d : dptr renames this.d; begin if this.has(k) then declare i : unsigned := s(k); begin n := n - 1; d(i) := d(n); s(hash(d(i))) := i; end; end if; end del; procedure clr(this : in out set) is n : unsigned renames this.n; begin n := 0; end clr; end sets;