hash tables and class-wide types as fields in a record

hash tables and class-wide types as fields in a record

[Anna Esparcia]

I'm trying to build a (generic) hash table that can store data belonging to
various subclasses of a base class - which subclass won't be known till run
time.
The code is as follows:

generic
   type DATA_TYPE is tagged private;
   type IDENT_TYPE is private;
   TABLE_SIZE : POSITIVE;
---
   type ELEMENT_TYPE;
   type INDEX_TYPE is access all ELEMENT_TYPE;
   type ELEMENT_TYPE is
      record
         DATA  : DATA_TYPE;
         IDENT : IDENT_TYPE;
         NEXT  : INDEX_TYPE:= null;
      end record;

   HASH_TABLE : array(0..TABLE_SIZE-1) of INDEX_TYPE:= (others => null);

What i would like to do is this:
 DATA  : DATA_TYPE'Class;
so that i could store objects of type DATA_TYPE or any of its subclasses,
but the compiler doesn't like it 'cos it's an "unconstrained subtype in
component declaration"
Now, I could declare a type pointer as follows:

type DATA_POINTER is access all DATA_TYPE'Class;

and an object of this type could point to any object of type DATA_TYPE or
any of its subclasses.
So, in my record above i can declare:
 DATA  : DATA_POINTER;
and the compiler accepts it, but when i add objects to the table the
pointers end up pointing to nothing (when the actual objects disappear).

Now, i could declare the record as originally (with DATA  : DATA_TYPE, i.e.
an object and not a pointer) but do the argument passing in the methods with
pointers e.g. i would have a method
ADD(p: DATA_POINTER)
which would copy the object pointed to by p into the field DATA of the
record. But the compiler doesn't let me do this either.

Any ideas? Any other way of implementing the hash table?
BTW the hash tables will be in shared memory and once they've been created
they'll stay there forever, so that they can be accessible to anybody. Can i
copy the objects pointed to onto global objects in this shared memory so
that they don't vanish into thin air? Will this defeat the whole point of
having a hash table?

Anna

Re: hash tables and class-wide types as fields in a record

[Matthew Heaney]

In article <38986a06.0@noticias.ncsa.es> , "Anna Esparcia" <aea@gtd.es> 
wrote:

> Now, I could declare a type pointer as follows:
>
> type DATA_POINTER is access all DATA_TYPE'Class;
>
> and an object of this type could point to any object of type DATA_TYPE or
> any of its subclasses.
> So, in my record above i can declare:
>  DATA  : DATA_POINTER;
> and the compiler accepts it, but when i add objects to the table the
> pointers end up pointing to nothing (when the actual objects disappear).

If you deallocate the object, of course you must remove that entry in
the hash table.


> Any ideas? Any other way of implementing the hash table?

A hash table comes with GNAT.  It's called gnat.htable (or something
like that).  Look in your ada-include directory.

Another way to implement a table entry is, instead of having each node
in the linked list point to an object, make the node itself an object:

Here's one way:

generic
  type Data_Type (<>) is limited private;
  type Data_Access is access all Data_Type;
  with function Get_Next
    (Data : Data_Type) return Data_Access is <>;
  with procedure Set_Next
    (Data : in out Data_Type;
     Next : in     Data_Access) is <>;
...

Now you can declare a data type pretty much any way you want.  For
example:

type T;
type T_Access is access all T'Class;

type T is tagged record
  <whatever>
  Next : T_Access;
end record;

procedure Set_Next
  (O : in out T;
   Next : in T_Access) is
begin
  O.Next := Next;
end;

package HTable is new Generic_HTable (T, T_Access);


Another way to declare the generic is to import a record whose type is
known explicitly:

package P is

  type T;
  type TA is access all T'Class;

  type T is tagged record
    Next : TA;
  end record;

end P;


with P;
generic
  type T is new P.T with private;
...

Now, since you know T's type, you know that it comes with a Next
component.

I don't really know if this is going to solve your problem, because I'm
not sure why your objects are disappearing.

Maybe what you need to do is declare the types together, so that each
object knows that hash table it's in.  When you delete the instance, the
instance can remove itself from it's hash table:

package P is

  type Hash_Table (Size : Positive) is limited private;

  type T (<>) is tagged limited private;
  type TA is access all T'Class;

  function New_T (Table : access Hash_Table) return TA;

  procedure Free (O : in out TA);

...
private

  type TA is access all T'Class;

  type T (Table : access Hash_Table) is tagged limited record
    <whatever>
    Next : TA;
  end record;

  type T_Array is array (Positive range <>) of TA;

  type Hash_Table (Size : Positive) is
    record
      Items : T_Array (1 .. Size);
    end record;
...
end P;


So when you declare an instance, you have to bind to a hash table
object:

  Table : aliased Hash_Table;

  Data : TA := New_T (Table'Access);

Better yet you could use a smart pointer to do the deallocation
automatically, to ensure there are no dangling references.

Another way to do it is statically:

  Table : aliased Hash_Table;

  Data : T (Table'Access);

and the constructor for the type could enter the object in the table,
and automatically remove it when it disappears.