Re: [PATCH] Implement ‘hash’ for structs

[Mark H Weaver <mhw@netris.org>]

Hi Ludovic!

ludo@gnu.org (Ludovic Courtès) writes:
> As incredible as it may seem, ‘hash’ until now always returned 263 % n
> for structs, leading to interesting experiences when using structs as
> hash table keys.

Yes, do you remember us talking about this long ago on IRC?  I wanted to
fix this, but asked whether changing the hash function was okay for 2.0,
and you never gave me an answer :)

Andy said that he improved the hash function on the master branch.
You might want to look at what he did.

[...]

> diff --git a/libguile/struct.c b/libguile/struct.c
> index 5837b7c..6287163 100644
> --- a/libguile/struct.c
> +++ b/libguile/struct.c
> @@ -922,6 +922,52 @@ scm_struct_ihashq (SCM obj, unsigned long n, void *closure)
>    return SCM_UNPACK (obj) % n;
>  }
>  
> +unsigned long
> +scm_i_struct_hash (SCM obj, unsigned long n)
> +#define FUNC_NAME "hash"
> +{
> +  SCM layout;
> +  scm_t_bits *data;
> +  size_t struct_size, field_num;
> +  unsigned long hash;
> +
> +  SCM_VALIDATE_STRUCT (1, obj);
> +
> +  layout = SCM_STRUCT_LAYOUT (obj);
> +  struct_size = scm_i_symbol_length (layout) / 2;
> +  data = SCM_STRUCT_DATA (obj);
> +
> +  hash = (unsigned long) SCM_PACK (SCM_STRUCT_VTABLE (obj));
> +  for (field_num = 0; field_num < struct_size; field_num++)
> +    {
> +      int protection;
> +
> +      protection = scm_i_symbol_ref (layout, field_num * 2 + 1);
> +      if (protection != 'h' && protection != 'o')
> +	{
> +	  int type;
> +	  type = scm_i_symbol_ref (layout, field_num * 2);
> +	  switch (type)
> +	    {
> +	    case 'p':
> +	      if (!scm_is_eq (obj, SCM_PACK (data[field_num])))
> +		hash ^= scm_ihash (SCM_PACK (data[field_num]), n);

I guess this 'if' is to avoid an infinite loop if the struct points back
to itself.  However, it apparently fails to detect cycles in the general
case.  I think this is a show stopper.  I think we need to detect cycles
and DTRT.

     Mark