[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] Implement ‘hash’ for structs
From: |
Mark H Weaver |
Subject: |
Re: [PATCH] Implement ‘hash’ for structs |
Date: |
Tue, 09 Oct 2012 22:59:46 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.2 (gnu/linux) |
Hi Ludovic!
address@hidden (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