Re: Pascal Calling Convention

[Georg Bauhaus <rm-host.bauhaus@maps.futureapps.de>]

On 3/29/11 12:08 AM, Adam Beneschan wrote:
> On Mar 28, 2:26 pm, Hyman Rosen<hyro...@mail.com>  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;