[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Guile-commits] GNU Guile branch, stable-2.0, updated. v2.0.9-140-gcc1cd
From: |
Mark H Weaver |
Subject: |
[Guile-commits] GNU Guile branch, stable-2.0, updated. v2.0.9-140-gcc1cd04 |
Date: |
Sun, 12 Jan 2014 08:16:38 +0000 |
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU Guile".
http://git.savannah.gnu.org/cgit/guile.git/commit/?id=cc1cd04f8111c306cf48b93e131d5c1765c808a3
The branch, stable-2.0 has been updated
via cc1cd04f8111c306cf48b93e131d5c1765c808a3 (commit)
from 0e18163366c2f2a0caecde18241dbd7987b4db7c (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit cc1cd04f8111c306cf48b93e131d5c1765c808a3
Author: Mark H Weaver <address@hidden>
Date: Sat Jan 11 10:18:40 2014 -0500
Fix hashing of vectors to run in bounded time.
* libguile/hash.c (SCM_MIN): New macro.
(scm_hasher): In vector case, do nothing if d is 0. Make sure to
recurse with a reduced d. Move the loop out of the 'if'.
-----------------------------------------------------------------------
Summary of changes:
libguile/hash.c | 56 +++++++++++++++++++++++++++++-------------------------
1 files changed, 30 insertions(+), 26 deletions(-)
diff --git a/libguile/hash.c b/libguile/hash.c
index 8b00a0c..c0a6109 100644
--- a/libguile/hash.c
+++ b/libguile/hash.c
@@ -1,5 +1,5 @@
/* Copyright (C) 1995, 1996, 1997, 2000, 2001, 2003, 2004, 2006, 2008,
- * 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
+ * 2009, 2010, 2011, 2012, 2014 Free Software Foundation, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public License
@@ -45,6 +45,7 @@
extern double floor();
#endif
+#define SCM_MIN(A, B) ((A) < (B) ? (A) : (B))
unsigned long
scm_string_hash (const unsigned char *str, size_t len)
@@ -228,31 +229,34 @@ scm_hasher(SCM obj, unsigned long n, size_t d)
return scm_i_struct_hash (obj, n, d);
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;
- }
- }
+ if (d > 0)
+ {
+ size_t len, i, d2;
+ unsigned long h;
+
+ len = SCM_SIMPLE_VECTOR_LENGTH (obj);
+ if (len > 5)
+ {
+ i = d / 2;
+ h = 1;
+ d2 = SCM_MIN (2, d - 1);
+ }
+ else
+ {
+ i = len;
+ h = n - 1;
+ d2 = (d - 1) / len;
+ }
+
+ while (i--)
+ {
+ SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
+ h = ((h << 8) + (scm_hasher (elt, n, d2))) % n;
+ }
+ return h;
+ }
+ else
+ return 1;
case scm_tcs_cons_imcar:
case scm_tcs_cons_nimcar:
if (d) return (scm_hasher (SCM_CAR (obj), n, d/2)
hooks/post-receive
--
GNU Guile
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Guile-commits] GNU Guile branch, stable-2.0, updated. v2.0.9-140-gcc1cd04,
Mark H Weaver <=