[m-dev.] For review: hash table implementation

[Ralph Becket]

>From Fergus Henderson on 03/02/2001 19:44:00
> 
> It would be nice to fix that XXX.
> I think something like the following
> 
>             else if N >= int__bits_per_int then
>              throw("hash_table__new_hash_table: N >= int__bits_per_int")
> 
> should do the trick.

Done.

> > int_hash_pred =
> >     ( pred(N::in, H1::out, H2::out) is det :-
> >         H1 = N * N,
> >         H2 = N `xor` (N + N)
> >     ).
> 
> Why not just `H1 = N'?

I perceived (through highly unscientific testing) that this gave a
better spread where N is small.  It's a weak justification, so I'll
change it back if it offends people :)

I've also renamed those preds to `{int,string,generic}_double_hash'
and introduced generic_double_hash/3 which goes like this:

%
----------------------------------------------------------------------------
%

    % This, again, is straight off the top of my head.
    %
generic_double_hash(T, Ha, Hb) :-
    (      if dynamic_cast(T, Int) then
        int_double_hash(Int, Ha, Hb)
      else if dynamic_cast(T, String) then
        string_double_hash(String, Ha, Hb)
      else if dynamic_cast(T, Univ) then
        generic_double_hash(univ_value(Univ), Ha, Hb)
      else if dynamic_cast(T, Array) then
        {Ha, Hb} =
            array__foldl(
                ( func(X, {HA0, HB0}) = {HA, HB} :-
                    generic_double_hash(X, HXA, HXB),
                    HA = munge(munge_factor_a, HA0, HXA),
                    HB = munge(munge_factor_b, HB0, HXB)
                ),
                Array,
                {0, 0}
            )
      else
        deconstruct(T, FunctorName, Arity, Args),
        string_double_hash(FunctorName, Ha0, Hb0),
        Ha1 = munge(munge_factor_a, Ha0, Arity),
        Hb1 = munge(munge_factor_b, Hb0, Arity),
        list__foldl2(
            ( pred(U::in, HA0::in, HA::out, HB0::in, HB::out) is det :-
                generic_double_hash(U, HUA, HUB),
                HA = munge(munge_factor_a, HA0, HUA),
                HB = munge(munge_factor_b, HB0, HUB)
            ), 
            Args,
            Ha1, Ha, 
            Hb1, Hb
        )
    ).

%
----------------------------------------------------------------------------
%

:- func munge_factor_a = int.           munge_factor_a = 5.
:- func munge_factor_b = int.           munge_factor_b = 3.
    
    

:- func munge(int, int, int) = int.

munge(N, X, Y) =
    (X `unchecked_left_shift` N) `xor`
    (X `unchecked_right_shift` (int__bits_per_int - N)) `xor`
    Y.

%
----------------------------------------------------------------------------
%

    % XXX To go into std_util.m
    %
:- pred dynamic_cast(T1, T2).
:- mode dynamic_cast(in, out) is semidet.

dynamic_cast(T1, T2) :-
    univ_to_type(univ(T1), T2).

%
----------------------------------------------------------------------------
%




--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------