[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: |
Thu, 11 Oct 2012 09:00:37 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.2 (gnu/linux) |
address@hidden (Ludovic Courtès) writes:
> Mark H Weaver <address@hidden> skribis:
>
>> 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.
>
> Yes, indeed.
>
> Here’s an updated patch that uses the ‘depth’ argument of ‘scm_hasher’
> for that, as is done for pairs.
I don't think 'depth' is an appropriate name for that argument. The way
it is used when hashing vectors (see below) implies that it is roughly
proportional to the number of elements to traverse, not the depth:
--8<---------------cut here---------------start------------->8---
case scm_tc7_wvect:
case scm_tc7_vector:
{
size_t len = SCM_SIMPLE_VECTOR_LENGTH (obj);
if (len > 5)
{
size_t i = d/2;
unsigned long h = 1;
while (i--)
{
SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
h = ((h << 8) + (scm_hasher (elt, n, 2))) % n;
}
return h;
}
else
{
size_t i = len;
unsigned long h = (n)-1;
while (i--)
{
SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
h = ((h << 8) + (scm_hasher (elt, n, d/len))) % n;
}
return h;
}
}
--8<---------------cut here---------------end--------------->8---
I would do something that preserves the meaning of 'd' consistent with
its use above. Maybe it should be called something like 'effort'.
Thanks,
Mark