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

[Fergus Henderson]

----- Forwarded message from Ralph Becket <rbeck at microsoft.com> -----

From: Ralph Becket <rbeck at microsoft.com>
To: "Fergus Henderson (E-mail)" <fjh at cs.mu.OZ.AU>
Subject: Re: [m-dev.] For review: hash table implementation.
Date: Thu, 8 Feb 2001 09:57:00 -0800 

Hi Fergus,

you wanted some changes made to generic_double_hash/3; this is the part
of the file that's changed.  It compiles fine and works with my test
harness, but I've yet to sort out regression tests for the distribution.

Cheers,

Ralph


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

    % There are almost certainly better ones out there...
    %
    % NOTE that H1 \= N since neither of H1 or H2 should be a function
    % of the other under machine integer arithmetic.
    %
int_double_hash(N, H1, H2) :-
    H1 = N * N,
    H2 = N `xor` (N + N).

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

    % There are almost certainly better ones out there...
    %
string_double_hash(S, H1, H2) :-
    H1 = string__hash(S),
    H2 = string__foldl(func(C, N) = char__to_int(C) + N, S, 0).

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

    % There are almost certainly better ones out there...
    %
float_double_hash(F, H1, H2) :-
    H1 = float__hash(F),
    H2 = float__hash(F * F).

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

    % There are almost certainly better ones out there...
    %
char_double_hash(C, H1, H2) :-
    int_double_hash(char__to_int(C), H1, H2).

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

    % 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, Float) then
        float_double_hash(Float, Ha, Hb)
      else if dynamic_cast(T, Char) then
        char_double_hash(Char, Ha, Hb)
      else if dynamic_cast(T, Univ) then
        generic_double_hash(univ_value(Univ), Ha, Hb)
      else if dynamic_cast_to_array(T, Array) then
        {Ha, Hb} =
            array__foldl(
                ( func(X, {HA0, HB0}) = {HA, HB} :-
                    generic_double_hash(X, HXA, HXB),
                    double_munge(HXA, HA0, HA, HXB, HB0, HB)
                ),
                Array,
                {0, 0}
            )
      else
        deconstruct(T, FunctorName, Arity, Args),
        string_double_hash(FunctorName, Ha0, Hb0),
        double_munge(Arity, Ha0, Ha1, Arity, Hb0, Hb1),
        list__foldl2(
            ( pred(U::in, HA0::in, HA::out, HB0::in, HB::out) is det :-
                generic_double_hash(U, HUA, HUB),
                double_munge(HUA, HA0, HA, HUB, HB0, HB)
            ),
            Args,
            Ha1, Ha,
            Hb1, Hb
        )
    ).

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

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

:- pred double_munge(int, int, int, int, int, int).
:- mode double_munge(in, in, out, in, in, out) is det.

double_munge(X, Ha0, Ha, Y, Hb0, Hb) :-
    Ha = munge(munge_factor_a, Ha0, X),
    Hb = munge(munge_factor_b, Hb0, Y).

:- 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.

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

fold(Fn, HT, X) = fold_0(0, Fn, HT, X).



:- func fold_0(int, func(K, V, T) = T, hash_table(K,V), T) = T.
:- mode fold_0(in, func(in,in,in) = out is det, hash_table_ui, in) = out is
det.
:- mode fold_0(in, func(in,in,di) = uo is det, hash_table_ui, di) = uo is
det.
% :- mode fold_0(in, func(in,in,in) = out is det, in, in) = out is det.
% :- mode fold_0(in, func(in,in,di) = uo is det, in, di) = uo is det.

fold_0(I, Fn, HT, X) =
    ( if I >= HT ^ num_buckets then
        X
      else if bitmap__is_clear(HT ^ bitmap, I) then
        fold_0(I + 1, Fn, HT, X)
      else
        fold_0(I + 1, Fn, HT, Fn(HT ^ keys ^ elem(I), HT ^ values ^ elem(I),
X))
    ).

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

    % XXX To go into array.m
    %
    % dynamic_cast/2 won't work for arbitrary arrays since array/1 is
    % not a ground type (that is, dynamic_cast/2 will work when the
    % target type is e.g. array(int), but not when it is array(T)).
    %
:- some [T2] pred dynamic_cast_to_array(T1, array(T2)).
:-           mode dynamic_cast_to_array(in, out) is semidet.

dynamic_cast_to_array(X, A) :-

        % If X is an array then it has a type with one type argument.
        %
    [ArgTypeDesc] = type_args(type_of(X)),

        % Convert ArgTypeDesc to a type variable ArgType.
        %
    (_ `with_type` ArgType) `has_type` ArgTypeDesc,

        % Constrain the type of A to be array(ArgType) and do the
        % cast.
        %
    dynamic_cast(X, A `with_type` array(ArgType)).

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

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

----- End forwarded message -----

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------