Version 1.1 of acs/ac-00080.txt

Unformatted version of acs/ac-00080.txt version 1.1
Other versions for file acs/ac-00080.txt

!standard 3.08(12)          03-09-17 AC95-00080/01
!class amendment 03-09-17
!status received no action 03-09-17
!status received 03-09-13
!subject Components of an array type
!summary
!appendix

From: Matthew Heaney
Sent: Saturday, September 13, 2003  9:36 PM

Is there any interest (assuming it's even possible) in liberalizing the
language to allow this locution:

  function To_Prime (N : Natural) return Positive;

  type Bucket_Array is (Positive range <>) of Node_Access;

  type Hash_Table_Type (Size : Natural) is
     limited record
        Buckets : Bucket_Array (1 .. To_Prime (Size));
        ...
     end record;

In other words, to be able to invoke a function to specify the upper
bound of the index range of an array component.

As a workaround, I suppose I could do something like:

package P is

   type Size_Type is private;

   function To_Size (N : Natural) return Size_Type;

   type Hash_Table_Type (Size : Size_Type) is limited private;
...
private

   type Size_Type is new Natural;

   type Hash_Table_Type (Size : Size_Type) is ...;

end P;

So users could say:

   HT : Hash_Table_Type (To_Size (10000));

However, I don't know if this latter example will compile: can you pass
a private type as the discriminant type of the partial view?

****************************************************************

From: Nick Roberts
Sent: Sunday, September 14, 2003 10:13 AM

I think this problem relates to AI-318 on the initialisation of objects of a
private limited type.

The idea would be that a function could be declared (in the same package
spec which declares the private limited type) which returns (an access value
referencing) an object appropriately dimensioned according to the call
parameters. For example:

   package My_Hashing is
      type Hash_Table_Type (<>) is limited private;
      ...
      function New_Table (Size: in Natural) return access Hash_Table_Type;
   private
      type Hash_Table_Type (Bucketage: Positive) is limited
         record
            Buckets: array(1..Bucketage) of ...;
            ...
         end record;
   end My_Hashing;

The body of New_Table might look like this:

      function New_Table (Size: in Natural) return access Hash_Table_Type is
         A: return access My_Hash_Type := new My_Hash_Table(To_Prime(Size));
      begin
         ... -- initialisation of the new hash table object
         return A;
      end;

The idea is that user declares her own access type, and then calls New_Table
to get an object of the type Hash_Table_Type. E.g.:

   type My_Table_Ref is access My_Hashing.Hash_Table_Type;
   for My_Table_Ref'Storage_Size use 10_000;
   ...
   Tab_1: My_Table_Ref := New_Table(1000);

Problem solved?

****************************************************************

From: Matthew Heaney
Sent: Sunday, September 14, 2003  11:29 AM

Not really.  I need the hash table to be allocated statically.

****************************************************************

From: Randy Brukardt
Sent: Monday, September 15, 2003  11:24 PM

> In other words, to be able to invoke a function to specify the upper
> bound of the index range of an array component.

and then later comments to Nick:

> I need the hash table to be allocated statically.

Well, then this isn't going to do it, at least on Janus/Ada.
Depends-on-discriminant arrays are always allocated to size and on the heap
in Janus/Ada. OTOH, most other compilers would try to allocate
Natural'Last*Node_Access'Size for this, because they could not figure out at
compile-time how big the object would be (and then they would allocate the
largest possible). In neither case would you get "static allocation".

This wouldn't be hard to implement in Janus/Ada (because we do it all at
runtime anyway), but I suspect that other implementors take advantage of
3.8(12) to do various operations at compile-time. I recall that relaxing
this rule was considered for Ada 95, and (obviously) that didn't happen.

But perhaps you had something else in mind. The rather mysterious title of
"array components" suggests that, because nothing in your question ever says
anything about the component, only the index and size of an array.

****************************************************************

From: Matthew Heaney
Sent: Tuesday, September 16, 2003  7:40 AM

A hash table typically has a length that is a prime number, because this
produces better scatter when computing hash values.

I wanted a user to be able to say: allocate this hash table container on the
stack, and make room for a maximum of N elements, like this:

   Hash_Table : Hash_Table_Type (N);

But I can't simply allocate a buckets array that has N components.  It has to
have a length that corresponds to the smallest prime number greater than or
equal to N, in order to maintain a load factor of 1.  (Hash tables have O(1)
time complexity, on average.)

A possible workaround is to go ahead an allocate the array with a length of N,
but only use the first M components, where M corresponds to the largest prime
number less than or equal to N.  This would mean the load factor is slightly
greater than 1, but perhaps that's good enough.

****************************************************************

Questions? Ask the ACAA Technical Agent