-/* Copyright (C) 1995,1996,1997, 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
- *
+/* Copyright (C) 1995, 1996, 1997, 2000, 2001, 2003, 2004, 2006, 2008,
+ * 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 as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 3 of
+ * the License, or (at your option) any later version.
*
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301 USA
*/
\f
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#ifdef HAVE_WCHAR_H
+#include <wchar.h>
+#endif
+
+#include <math.h>
+#include <unistr.h>
#include "libguile/_scm.h"
#include "libguile/chars.h"
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)
return h;
}
+unsigned long
+scm_i_string_hash (SCM str)
+{
+ size_t len = scm_i_string_length (str);
+ size_t i = 0;
+
+ unsigned long h = 0;
+ while (len-- > 0)
+ h = (unsigned long) scm_i_string_ref (str, i++) + h * 37;
+
+ scm_remember_upto_here_1 (str);
+ return h;
+}
+
+unsigned long
+scm_i_locale_string_hash (const char *str, size_t len)
+{
+#ifdef HAVE_WCHAR_H
+ mbstate_t state;
+ wchar_t c;
+ size_t byte_idx = 0, nbytes;
+ unsigned long h = 0;
+
+ if (len == (size_t) -1)
+ len = strlen (str);
+
+ while ((nbytes = mbrtowc (&c, str + byte_idx, len - byte_idx, &state)) > 0)
+ {
+ if (nbytes >= (size_t) -2)
+ /* Invalid input string; punt. */
+ return scm_i_string_hash (scm_from_locale_stringn (str, len));
+
+ h = (unsigned long) c + h * 37;
+ byte_idx += nbytes;
+ }
+
+ return h;
+#else
+ return scm_i_string_hash (scm_from_locale_stringn (str, len));
+#endif
+}
+
+unsigned long
+scm_i_latin1_string_hash (const char *str, size_t len)
+{
+ const scm_t_uint8 *ustr = (const scm_t_uint8 *) str;
+ size_t i = 0;
+ unsigned long h = 0;
+
+ if (len == (size_t) -1)
+ len = strlen (str);
+
+ for (; i < len; i++)
+ h = (unsigned long) ustr[i] + h * 37;
+
+ return h;
+}
+
+unsigned long
+scm_i_utf8_string_hash (const char *str, size_t len)
+{
+ const scm_t_uint8 *ustr = (const scm_t_uint8 *) str;
+ size_t byte_idx = 0;
+ unsigned long h = 0;
+
+ if (len == (size_t) -1)
+ len = strlen (str);
+
+ while (byte_idx < len)
+ {
+ ucs4_t c;
+ int nbytes;
+
+ nbytes = u8_mbtouc (&c, ustr + byte_idx, len - byte_idx);
+ if (nbytes == 0)
+ break;
+ else if (nbytes < 0)
+ /* Bad UTF-8; punt. */
+ return scm_i_string_hash (scm_from_utf8_stringn (str, len));
+
+ h = (unsigned long) c + h * 37;
+ byte_idx += nbytes;
+ }
+
+ return h;
+}
+
/* Dirk:FIXME:: why downcase for characters? (2x: scm_hasher, scm_ihashv) */
/* Dirk:FIXME:: scm_hasher could be made static. */
if (SCM_CHARP(obj))
return (unsigned)(scm_c_downcase(SCM_CHAR(obj))) % n;
switch (SCM_UNPACK (obj)) {
-#ifndef SICP
- case SCM_UNPACK(SCM_EOL):
+ case SCM_EOL_BITS:
d = 256;
break;
-#endif
- case SCM_UNPACK(SCM_BOOL_T):
+ case SCM_BOOL_T_BITS:
d = 257;
break;
- case SCM_UNPACK(SCM_BOOL_F):
+ case SCM_BOOL_F_BITS:
d = 258;
break;
- case SCM_UNPACK(SCM_EOF_VAL):
+ case SCM_EOF_VAL_BITS:
d = 259;
break;
default:
case scm_tc16_real:
{
double r = SCM_REAL_VALUE (obj);
- if (floor (r) == r)
+ if (floor (r) == r && !isinf (r) && !isnan (r))
{
obj = scm_inexact_to_exact (obj);
return scm_to_ulong (scm_modulo (obj, scm_from_ulong (n)));
case scm_tc7_string:
{
unsigned long hash =
- scm_string_hash ((const unsigned char *) scm_i_string_chars (obj),
- scm_i_string_length (obj)) % n;
- scm_remember_upto_here_1 (obj);
+ scm_i_string_hash (obj) % n;
return hash;
}
case scm_tc7_symbol:
return scm_i_symbol_hash (obj) % n;
- case scm_tc7_wvect:
- case scm_tc7_vector:
+ case scm_tc7_pointer:
{
- 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;
- }
+ /* Pointer objects are typically used to store addresses of heap
+ objects. On most platforms, these are at least 3-byte
+ aligned (on x86_64-*-gnu, `malloc' returns 4-byte aligned
+ addresses), so get rid of the least significant bits. */
+ scm_t_uintptr significant_bits;
+
+ significant_bits = (scm_t_uintptr) SCM_POINTER_VALUE (obj) >> 4UL;
+ return (size_t) significant_bits % n;
}
+ case scm_tcs_struct:
+ return scm_i_struct_hash (obj, n, d);
+ case scm_tc7_wvect:
+ case scm_tc7_vector:
+ 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 = len > 0 ? (d - 1) / len : 0;
+ }
+
+ 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)
else return 1;
case scm_tc7_port:
return ((SCM_RDNG & SCM_CELL_WORD_0 (obj)) ? 260 : 261) % n;
- case scm_tcs_closures:
- case scm_tcs_subrs:
+ case scm_tc7_program:
return 262 % n;
}
}