Re: [PATCH] Implement ‘hash’ for structs

[Mark H Weaver]

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