From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Implement =?utf-8?B?4oCYaGFzaOKAmQ==?= for structs Date: Thu, 11 Oct 2012 09:00:37 -0400 Message-ID: <874nm1i2oa.fsf@tines.lan> References: <87626juuzh.fsf@gnu.org> <87ipajkp5p.fsf@tines.lan> <87zk3uoyhu.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1349960472 4250 80.91.229.3 (11 Oct 2012 13:01:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 11 Oct 2012 13:01:12 +0000 (UTC) Cc: guile-devel@gnu.org To: ludo@gnu.org (Ludovic =?utf-8?Q?Court=C3=A8s?=) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Oct 11 15:01:15 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TMINz-00021B-EA for guile-devel@m.gmane.org; Thu, 11 Oct 2012 15:01:11 +0200 Original-Received: from localhost ([::1]:40803 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TMINt-0000bm-3T for guile-devel@m.gmane.org; Thu, 11 Oct 2012 09:01:05 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:53695) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TMINn-0000ba-FJ for guile-devel@gnu.org; Thu, 11 Oct 2012 09:01:03 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TMINh-0007HG-KU for guile-devel@gnu.org; Thu, 11 Oct 2012 09:00:59 -0400 Original-Received: from world.peace.net ([96.39.62.75]:51643) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TMINh-0007Gk-G4; Thu, 11 Oct 2012 09:00:53 -0400 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=tines.lan) by world.peace.net with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1TMINa-0005OR-0E; Thu, 11 Oct 2012 09:00:46 -0400 In-Reply-To: <87zk3uoyhu.fsf@gnu.org> ("Ludovic \=\?utf-8\?Q\?Court\=C3\=A8s\=22'\?\= \=\?utf-8\?Q\?s\?\= message of "Wed, 10 Oct 2012 22:36:45 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 96.39.62.75 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:14968 Archived-At: ludo@gnu.org (Ludovic Court=C3=A8s) writes: > Mark H Weaver 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=E2=80=99s an updated patch that uses the =E2=80=98depth=E2=80=99 arg= ument of =E2=80=98scm_hasher=E2=80=99 > 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 =3D SCM_SIMPLE_VECTOR_LENGTH (obj); if (len > 5) { size_t i =3D d/2; unsigned long h =3D 1; while (i--) { SCM elt =3D SCM_SIMPLE_VECTOR_REF (obj, h % len); h =3D ((h << 8) + (scm_hasher (elt, n, 2))) % n; } return h; } else { size_t i =3D len; unsigned long h =3D (n)-1; while (i--) { SCM elt =3D SCM_SIMPLE_VECTOR_REF (obj, h % len); h =3D ((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