Container for access values.

Container for access values.

[David Pettersson]

Hi!

If I want to store values of an access type in a Set, how do I do it. I want to implement a simple and inefficient garbage collector and need to store pointers (yes, coming from C) to objects that are roots for the scan for reachable objects.

If I try Hashed_Sets I get in trouble since I don't know how to compute a reasonable hash value for the access. I can do an unchecked cast to integer but the two methods for this that I know is not good for the purpose (?).

If I try Ordered_Sets there is no "<" defined for access and I have to define it myself in the same manner as hash value.

One problem with casting is that I might not get all the information if the destination is smaller than the size of the access (two words on gnat?). Or is it enought to use a long integer?

Is there a standard way to store accesses in Sets. Hashing the target will not work in this case since the targets value might change.

Any thoughts?
David

Re: Container for access values.

[Dmitry A. Kazakov]

On Thu, 3 May 2012 00:08:42 -0700 (PDT), David Pettersson wrote:

> If I try Ordered_Sets there is no "<" defined for access and I have to
> define it myself in the same manner as hash value.

Why? If the set does not use hash table, you don't need to worry about how
"<" is implemented, if the axiomatic properties of the order relation are
respected. If the machine memory is flat, you can compare addresses. I have
a small generic package to generate access comparisons from addresses:

   http://www.dmitry-kazakov.de/ada/components.htm#15.1
 
-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Container for access values.

[David Pettersson]

So "<" is defined for addresses but not for accesses. So all I have to do is to take the address of the accesses' targets and compare them.

Thank you!
David
 

Re: Container for access values.

[Dmitry A. Kazakov]

On Thu, 3 May 2012 01:26:05 -0700 (PDT), David Pettersson wrote:

> So "<" is defined for addresses but not for accesses. So all I have to do 
> is to take the address of the accesses' targets and compare them.

Don't forget checking for null:

   return
      Ptr (Right) /= null
   and then
      (Ptr (Left) = null  or else Left.all'Address < Right.all'Address);

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

Re: Container for access values.

[Robert A Duff]

David Pettersson <jan.karv@gmail.com> writes:

> Hi!
>
> If I want to store values of an access type in a Set, how do I do
> it. I want to implement a simple and inefficient garbage collector and
> need to store pointers (yes, coming from C) to objects that are roots
> for the scan for reachable objects.

The Boehm garbage collector works with Ada.

You should also look into storage pools, including Ada 2012
"subpools".  Maybe you don't need a garbage collector.

> If I try Hashed_Sets I get in trouble since I don't know how to
> compute a reasonable hash value for the access. I can do an unchecked
> cast to integer but the two methods for this that I know is not good
> for the purpose (?).

If you're writing a garbage collector, you're going to need some
low-level hacks, and it's not going to be portable to every
possible Ada implementation.  But you can make it portable
to most machines.

On the other hand, garbage collection is hard when you don't
have control over the compiler.  Are you sure you want to do it?

Look up Integer_Address, Address_To_Access_Conversions, and
Unchecked_Conversion.

Convert to a modular integer, and do your hashing on that.
For a good hash function, you want to ignore the low-order
bits, because addresses are usually aligned.  And ignore the
high-order bits, because objects aren't allocated at high
addresses.  A bit of experimentation should tell you which
bits to use.

> If I try Ordered_Sets there is no "<" defined for access and I have to
> define it myself in the same manner as hash value.

Yes, same issue there.  Hashing is probably faster,
but you'd have to measure to be sure.

> One problem with casting is that I might not get all the information
> if the destination is smaller than the size of the access (two words
> on gnat?). Or is it enought to use a long integer?

All access-to-object values in GNAT are represented as a single machine
address (a "thin pointer"), with one exception:
access-to-unconstrained-array is represented as a "fat pointer", which
contains the address of the dope and the address of the data.  You can
force GNAT to use thin pointers even in that case.

> Is there a standard way to store accesses in Sets.

No.  You have to build your own.

Beware hidden pointers.  For example:

    X : Access_String := new ...;

    procedure P (Y : String) is
    begin
        X := null;
        ...
        -- The object that was X.all is still live here,
        -- accessible via Y.
        Put(Y);
    end P;
    
    P(X); -- GNAT will pass X by reference (as a fat pointer)

Another:

    X : Access_String := new ...;
    Y : String renames X.all;
    
    X := null;
    ...
    Put(Y);

- Bob