#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"
#include "libguile/ports.h"
#include "libguile/strings.h"
#include "libguile/symbols.h"
#include "libguile/vectors.h"
#include "libguile/validate.h"
#include "libguile/hash.h"
#ifndef floor
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)
{
unsigned long h = 0;
while (len-- > 0)
h = *str++ + h*37;
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)
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)
return scm_i_string_hash (scm_from_utf8_stringn (str, len));
h = (unsigned long) c + h * 37;
byte_idx += nbytes;
}
return h;
}
unsigned long
scm_hasher(SCM obj, unsigned long n, size_t d)
{
switch (SCM_ITAG3 (obj)) {
case scm_tc3_int_1:
case scm_tc3_int_2:
return SCM_I_INUM(obj) % n;
case scm_tc3_imm24:
if (SCM_CHARP(obj))
return (unsigned)(scm_c_downcase(SCM_CHAR(obj))) % n;
switch (SCM_UNPACK (obj)) {
case SCM_EOL_BITS:
d = 256;
break;
case SCM_BOOL_T_BITS:
d = 257;
break;
case SCM_BOOL_F_BITS:
d = 258;
break;
case SCM_EOF_VAL_BITS:
d = 259;
break;
default:
d = 263;
}
return d % n;
default:
return 263 % n;
case scm_tc3_cons:
switch SCM_TYP7(obj) {
default:
return 263 % n;
case scm_tc7_smob:
return 263 % n;
case scm_tc7_number:
switch SCM_TYP16 (obj) {
case scm_tc16_big:
return scm_to_ulong (scm_modulo (obj, scm_from_ulong (n)));
case scm_tc16_real:
{
double r = SCM_REAL_VALUE (obj);
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_tc16_complex:
case scm_tc16_fraction:
obj = scm_number_to_string (obj, scm_from_int (10));
}
case scm_tc7_string:
{
unsigned long hash =
scm_i_string_hash (obj) % n;
return hash;
}
case scm_tc7_symbol:
return scm_i_symbol_hash (obj) % n;
case scm_tc7_pointer:
{
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)
+ scm_hasher (SCM_CDR (obj), n, d/2)) % n;
else return 1;
case scm_tc7_port:
return ((SCM_RDNG & SCM_CELL_WORD_0 (obj)) ? 260 : 261) % n;
case scm_tc7_program:
return 262 % n;
}
}
}
unsigned long
scm_ihashq (SCM obj, unsigned long n)
{
return (SCM_UNPACK (obj) >> 1) % n;
}
SCM_DEFINE (scm_hashq, "hashq", 2, 0, 0,
(SCM key, SCM size),
"Determine a hash value for @var{key} that is suitable for\n"
"lookups in a hashtable of size @var{size}, where @code{eq?} is\n"
"used as the equality predicate. The function returns an\n"
"integer in the range 0 to @var{size} - 1. Note that\n"
"@code{hashq} may use internal addresses. Thus two calls to\n"
"hashq where the keys are @code{eq?} are not guaranteed to\n"
"deliver the same value if the key object gets garbage collected\n"
"in between. This can happen, for example with symbols:\n"
"@code{(hashq 'foo n) (gc) (hashq 'foo n)} may produce two\n"
"different values, since @code{foo} will be garbage collected.")
#define FUNC_NAME s_scm_hashq
{
unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
return scm_from_ulong (scm_ihashq (key, sz));
}
#undef FUNC_NAME
unsigned long
scm_ihashv (SCM obj, unsigned long n)
{
if (SCM_CHARP(obj))
return ((unsigned long) (scm_c_downcase (SCM_CHAR (obj)))) % n;
if (SCM_NUMP(obj))
return (unsigned long) scm_hasher(obj, n, 10);
else
return SCM_UNPACK (obj) % n;
}
SCM_DEFINE (scm_hashv, "hashv", 2, 0, 0,
(SCM key, SCM size),
"Determine a hash value for @var{key} that is suitable for\n"
"lookups in a hashtable of size @var{size}, where @code{eqv?} is\n"
"used as the equality predicate. The function returns an\n"
"integer in the range 0 to @var{size} - 1. Note that\n"
"@code{(hashv key)} may use internal addresses. Thus two calls\n"
"to hashv where the keys are @code{eqv?} are not guaranteed to\n"
"deliver the same value if the key object gets garbage collected\n"
"in between. This can happen, for example with symbols:\n"
"@code{(hashv 'foo n) (gc) (hashv 'foo n)} may produce two\n"
"different values, since @code{foo} will be garbage collected.")
#define FUNC_NAME s_scm_hashv
{
unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
return scm_from_ulong (scm_ihashv (key, sz));
}
#undef FUNC_NAME
unsigned long
scm_ihash (SCM obj, unsigned long n)
{
return (unsigned long) scm_hasher (obj, n, 10);
}
SCM_DEFINE (scm_hash, "hash", 2, 0, 0,
(SCM key, SCM size),
"Determine a hash value for @var{key} that is suitable for\n"
"lookups in a hashtable of size @var{size}, where @code{equal?}\n"
"is used as the equality predicate. The function returns an\n"
"integer in the range 0 to @var{size} - 1.")
#define FUNC_NAME s_scm_hash
{
unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
return scm_from_ulong (scm_ihash (key, sz));
}
#undef FUNC_NAME
void
scm_init_hash ()
{
#include "libguile/hash.x"
}