15.4.891  src/lib/src/hash-string.pkg

## hash-string.pkg

# Compiled by:
#     src/lib/std/standard.lib



###             "A doctor can bury his mistakes
###              but an architect can only
###              advise his clients to plant vines."
###
###                         -- Frank Lloyd Wright



stipulate
    package ss  =  substring;                           # substring             is from   src/lib/std/substring.pkg
herein

    package hash_string
    : (weak)
    api {

        hash_string:   String -> Unt;

        hash_substring:  Substring -> Unt;

    }
    {

        fun char_to_unt c
            =
            unt::from_int (char::to_int c);

        # A function to hash a character.
        # The computation is:
        #
        #     h = 33 * h + 720 + c
        #
        fun hash_char (c, h)
            =
            unt::(<<) (h, 0u5) + h + 0u720 + (char_to_unt c);

        # NOTE: another function we might try is h = 5*h + c,
        # which is used in STL.
        #
        #  fun hash_string s = vector_of_chars::fold_forward hash_char 0u0 s 

        stipulate
            fun x + y
                =
                unt::to_int_x (unt::(+) (unt::from_int x, unt::from_int y));

            get = unsafe::vector_of_chars::get;

            fun hash (s, i0, e)
                =
                loop (0u0, i0)
                where 
                    fun loop (h, i)
                        =
                        if   (i >= e)   h;
                        else            loop (hash_char (get (s, i), h), i + 1);
                        fi;

                end;
        herein
            fun hash_string s
                =
                hash (s, 0, size s);

            fun hash_substring ss
                =
                {   (ss::burst_substring  ss)
                        ->
                        (s, i0, len);

                    hash (s, i0, i0 + len);
                };
        end;                            # stipulate

    };                                  # package hash_string 
end;

## COPYRIGHT (c) 1992 by AT&T Bell Laboratories
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.