hashed_maps

hashed_maps

[Lucretia]

Hi,

What's the best way to create a hashed_map which maps from
System.Address :-> an access type? I've a need for this in wxAda and
have set up an ordered map which works, but I'm worried that I could
end up with a populated map which is nothing more than a linked list in
which the search is linear.

FYI: This mapping is used to get Ada instances from the C++ pointer, if
one exists, otherwise an unowned proxy will be created temporarily.

Thanks,
Luke.

Re: hashed_maps

[Jeffrey R. Carter]

Lucretia wrote:

> What's the best way to create a hashed_map which maps from
> System.Address :-> an access type? I've a need for this in wxAda and
> have set up an ordered map which works, but I'm worried that I could
> end up with a populated map which is nothing more than a linked list in
> which the search is linear.

Does System.Address_To_Access_Conversions not fill this need?

-- 
Jeff Carter
"Go and boil your bottoms."
Monty Python & the Holy Grail
01

Re: hashed_maps

[Lucretia]

No, because, like I said, I need a mapping from a C++ pointer type to
an Ada instance. The Ada instance constructs the C++ instance.

Luke.

Re: hashed_maps

[Matthew Heaney]

"Lucretia" <lucretia9@lycos.co.uk> writes:

> No, because, like I said, I need a mapping from a C++ pointer type to
> an Ada instance. The Ada instance constructs the C++ instance.

Hmmm... Still not sure what you mean here.  Does the C++ pointer value
designate the Ada instance?  If so, then you can just convert from the
C++ pointer type to an Ada access type, using the method Jeff suggested.

Re: hashed_maps

[Lucretia]

No, it doesn't!

Like I said the Ada type *constructs* the C++ type, there is a dual
hierarchy here!

The Ada instance /= C++ instance AT ALL!

This is why I'm using a map to map between them, i.e. so I can find the
Ada instance associated with the C++ instance.

Luke.

Re: hashed_maps

[Matthew Heaney]

Lucretia wrote:
>
> This is why I'm using a map to map between them, i.e. so I can find the
> Ada instance associated with the C++ instance.

Well, I still don't know what you're doing, but if you need a map then
Ada has those:

ada.containers.hashed_maps
ada.containers.ordered_maps

If you're using GCC 4.0, then you should have these in your path.
Otherwise, you might have to download a reference implementation.

http://charles.tigris.org/

For your problem, either map will do.  Type System.Address has a
relational operator ("<") so you can use that type (or equivalently, an
access type) as the key of the ordered map; or, you can use To_Integer
(declared in package System, or one of its children -- I forget which)
to implement a hash function, and hence use it as the key of the hashed
map.

-Matt

Re: hashed_maps

[Lucretia]

Ok...I have been developing a binding to wxWidgets, so as an example:

package wx.Core.Window is

  type Window_Type is new Event_Handler_Type with private;

  procedure New_Window(Self : in out Window_Type; ...);

end wx.Core.Window;

New_Window contains a function wxWindow_ctor which calls a C function
which in turn calls "new wxWindow(...)" and returns the C++ pointer to
the New_Window procedure. I was originally storing the address of the
Ada instance (using Address_To_Access_Conversions) in the C++ class,
but this was messy and I needed a generic way of doing this for every
instance created on the Ada side, so a mapping seemed like a good idea
(C++ pointer :-> Ada access type)*.

* The "Ada access type" is the address of the newly constructed Ada
instance, from, for example, New_Window!

Now, I just need to know that what I'm doing with the ordered map isn't
going to generate a linked list in which the search will end up linear
as new C++ types are allocated as the key will be the address of the
C++ instance. Should a hashed map be used, if so, how do you do this?
I've only seen examples of hashing with strings.

Thanks,
Luke.

Re: hashed_maps

[Simon Wright]

"Lucretia" <lucretia9@lycos.co.uk> writes:

> Now, I just need to know that what I'm doing with the ordered map
> isn't going to generate a linked list in which the search will end
> up linear as new C++ types are allocated as the key will be the
> address of the C++ instance. Should a hashed map be used, if so, how
> do you do this?  I've only seen examples of hashing with strings.

Matt will confirm, but I'm pretty sure that the ordered map uses a
red-black tree as its implementation. This would give you O(log n)
access time.

Re: hashed_maps

[Björn Persson]

Lucretia wrote:
> What's the best way to create a hashed_map which maps from
> System.Address :-> an access type?

In other words, how do you write a good hash function that turns memory 
addresses into evenly distributed hash values? I seem to recall that 
just this question was discussed here in comp.lang.ada some time ago 
(several months, maybe a year or more ago). You could search in Google 
groups. (That is, if you really expect to have so many windows that you 
need to have a hash table and not a tree.)

-- 
Bj�rn Persson                              PGP key A88682FD
                    omb jor ers @sv ge.
                    r o.b n.p son eri nu

Re: hashed_maps

[Robert A Duff]

Bj�rn Persson <spam-away@nowhere.nil> writes:

> Lucretia wrote:
> > What's the best way to create a hashed_map which maps from
> > System.Address :-> an access type?
> 
> In other words, how do you write a good hash function that turns memory
> addresses into evenly distributed hash values? I seem to recall that
> just this question was discussed here in comp.lang.ada some time ago
> (several months, maybe a year or more ago). You could search in Google
> groups. (That is, if you really expect to have so many windows that you
> need to have a hash table and not a tree.)

Addresses usually have the low 2 or 3 bits equal to zero, because of
alignment concerns.  So use Address_To_Integer and shift right 3 bits.
Then mod by the size of the hash table, or take some high-order bits
and add them into the low-order bits.

- Bob

Re: hashed_maps

[Matthew Heaney]

Simon Wright <simon@pushface.org> writes:

> Matt will confirm, but I'm pretty sure that the ordered map uses a
> red-black tree as its implementation. This would give you O(log n)
> access time.

Yes, that is correct.  The associative containers must do better than
O(n).  If it were otherwise, they wouldn't provide any benefit (you
could just use the sequence containers).

The ordered containers (in GCC 4, and in the ref. impl. at tigris) are
implemented using a red-black tree, and hence provide O(log n) time
complexity even in the worst case.

The hashed containers are implemented using a hash table, and therefore
have O(1) time complexity on average.  But note that hashed container
complexity behavior is very sensitive to quality of hash function.

In the problem here, you can convert an address to an integer, and use
that as its hash value, so your hash function is perfect.

Re: hashed_maps

[Matthew Heaney]

"Lucretia" <lucretia9@lycos.co.uk> writes:

> Now, I just need to know that what I'm doing with the ordered map
> isn't going to generate a linked list in which the search will end up
> linear as new C++ types are allocated as the key will be the address
> of the C++ instance. Should a hashed map be used, if so, how do you do
> this?  I've only seen examples of hashing with strings.

The container standard guarantees that associative containers must
perform better than O(n), so a linked list would not be an acceptable
implementation.

It's probably quicker and easier to use the ordered map, since the "<"
operator for type Address is declared right there in package System.

If you want to use a hash table, then you can use To_Integer declared in
System.Storage_Elements to implement a hash function for type Adddress.
The generic actual for Equivalent_Keys is just "=".

Re: hashed_maps

[Matthew Heaney]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Addresses usually have the low 2 or 3 bits equal to zero, because of
> alignment concerns.  So use Address_To_Integer and shift right 3 bits.
> Then mod by the size of the hash table, or take some high-order bits
> and add them into the low-order bits.

In the case of the standard hashed containers, I'm not sure you would
need to bother, since the mod'ing is done internally by the container.

I think you'd only need to right shift if you were to throw away upper
bits, say because System.Storage_Elements.Integer_Address has a wider
range than Ada.Containers.Hash_Type.

Re: hashed_maps

[Lucretia]

Matthew Heaney wrote:
> If you're using GCC 4.0, then you should have these in your path.
> Otherwise, you might have to download a reference implementation.
>
> http://charles.tigris.org/

Can you see your way to updating the source archive? I've only got
access from the library and they have firewalls galore which means CVS
doesn't work. I've downloaded the source from CVS through the web
interface one file at a time (not fun!) but gave up when I saw the size
of the examples directory.

Maybe a script that will produce a snapshot on order through the web
interface would be a good idea? Or just a script to generate a snapshot
and place it in the downloads section on a daily basis (or when a file
changes)?

Thanks,
Luke.