1 /* Copyright (C) 1995,1996,1997, 2000, 2001, 2003, 2004, 2006, 2008 Free Software Foundation, Inc.
2 *
3 * This library is free software; you can redistribute it and/or
4 * modify it under the terms of the GNU Lesser General Public
5 * License as published by the Free Software Foundation; either
6 * version 2.1 of the License, or (at your option) any later version.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * Lesser General Public License for more details.
12 *
13 * You should have received a copy of the GNU Lesser General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16 */
17
18
19
20 #ifdef HAVE_CONFIG_H
21 # include <config.h>
22 #endif
23
24 #include "libguile/_scm.h"
25 #include "libguile/chars.h"
26 #include "libguile/ports.h"
27 #include "libguile/strings.h"
28 #include "libguile/symbols.h"
29 #include "libguile/vectors.h"
30
31 #include "libguile/validate.h"
32 #include "libguile/hash.h"
33
34
35 #ifndef floor
36 extern double floor();
37 #endif
38
39
40 unsigned long
scm_string_hash(const unsigned char * str,size_t len)41 scm_string_hash (const unsigned char *str, size_t len)
42 {
43 /* from suggestion at: */
44 /* http://srfi.schemers.org/srfi-13/mail-archive/msg00112.html */
45
46 unsigned long h = 0;
47 while (len-- > 0)
48 h = *str++ + h*37;
49 return h;
50 }
51
52
53 /* Dirk:FIXME:: why downcase for characters? (2x: scm_hasher, scm_ihashv) */
54 /* Dirk:FIXME:: scm_hasher could be made static. */
55
56
57 unsigned long
scm_hasher(SCM obj,unsigned long n,size_t d)58 scm_hasher(SCM obj, unsigned long n, size_t d)
59 {
60 switch (SCM_ITAG3 (obj)) {
61 case scm_tc3_int_1:
62 case scm_tc3_int_2:
63 return SCM_I_INUM(obj) % n; /* SCM_INUMP(obj) */
64 case scm_tc3_imm24:
65 if (SCM_CHARP(obj))
66 return (unsigned)(scm_c_downcase(SCM_CHAR(obj))) % n;
67 switch (SCM_UNPACK (obj)) {
68 #ifndef SICP
69 case SCM_UNPACK(SCM_EOL):
70 d = 256;
71 break;
72 #endif
73 case SCM_UNPACK(SCM_BOOL_T):
74 d = 257;
75 break;
76 case SCM_UNPACK(SCM_BOOL_F):
77 d = 258;
78 break;
79 case SCM_UNPACK(SCM_EOF_VAL):
80 d = 259;
81 break;
82 default:
83 d = 263; /* perhaps should be error */
84 }
85 return d % n;
86 default:
87 return 263 % n; /* perhaps should be error */
88 case scm_tc3_cons:
89 switch SCM_TYP7(obj) {
90 default:
91 return 263 % n;
92 case scm_tc7_smob:
93 return 263 % n;
94 case scm_tc7_number:
95 switch SCM_TYP16 (obj) {
96 case scm_tc16_big:
97 return scm_to_ulong (scm_modulo (obj, scm_from_ulong (n)));
98 case scm_tc16_real:
99 {
100 double r = SCM_REAL_VALUE (obj);
101 if (floor (r) == r)
102 {
103 obj = scm_inexact_to_exact (obj);
104 return scm_to_ulong (scm_modulo (obj, scm_from_ulong (n)));
105 }
106 }
107 /* Fall through */
108 case scm_tc16_complex:
109 case scm_tc16_fraction:
110 obj = scm_number_to_string (obj, scm_from_int (10));
111 /* Fall through */
112 }
113 /* Fall through */
114 case scm_tc7_string:
115 {
116 unsigned long hash =
117 scm_string_hash ((const unsigned char *) scm_i_string_chars (obj),
118 scm_i_string_length (obj)) % n;
119 scm_remember_upto_here_1 (obj);
120 return hash;
121 }
122 case scm_tc7_symbol:
123 return scm_i_symbol_hash (obj) % n;
124 case scm_tc7_wvect:
125 case scm_tc7_vector:
126 {
127 size_t len = SCM_SIMPLE_VECTOR_LENGTH (obj);
128 if (len > 5)
129 {
130 size_t i = d/2;
131 unsigned long h = 1;
132 while (i--)
133 {
134 SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
135 h = ((h << 8) + (scm_hasher (elt, n, 2))) % n;
136 }
137 return h;
138 }
139 else
140 {
141 size_t i = len;
142 unsigned long h = (n)-1;
143 while (i--)
144 {
145 SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
146 h = ((h << 8) + (scm_hasher (elt, n, d/len))) % n;
147 }
148 return h;
149 }
150 }
151 case scm_tcs_cons_imcar:
152 case scm_tcs_cons_nimcar:
153 if (d) return (scm_hasher (SCM_CAR (obj), n, d/2)
154 + scm_hasher (SCM_CDR (obj), n, d/2)) % n;
155 else return 1;
156 case scm_tc7_port:
157 return ((SCM_RDNG & SCM_CELL_WORD_0 (obj)) ? 260 : 261) % n;
158 case scm_tcs_closures:
159 case scm_tcs_subrs:
160 return 262 % n;
161 }
162 }
163 }
164
165
166
167
168
169 unsigned long
scm_ihashq(SCM obj,unsigned long n)170 scm_ihashq (SCM obj, unsigned long n)
171 {
172 return (SCM_UNPACK (obj) >> 1) % n;
173 }
174
175
176 SCM_DEFINE (scm_hashq, "hashq", 2, 0, 0,
177 (SCM key, SCM size),
178 "Determine a hash value for @var{key} that is suitable for\n"
179 "lookups in a hashtable of size @var{size}, where @code{eq?} is\n"
180 "used as the equality predicate. The function returns an\n"
181 "integer in the range 0 to @var{size} - 1. Note that\n"
182 "@code{hashq} may use internal addresses. Thus two calls to\n"
183 "hashq where the keys are @code{eq?} are not guaranteed to\n"
184 "deliver the same value if the key object gets garbage collected\n"
185 "in between. This can happen, for example with symbols:\n"
186 "@code{(hashq 'foo n) (gc) (hashq 'foo n)} may produce two\n"
187 "different values, since @code{foo} will be garbage collected.")
188 #define FUNC_NAME s_scm_hashq
189 {
190 unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
191 return scm_from_ulong (scm_ihashq (key, sz));
192 }
193 #undef FUNC_NAME
194
195
196
197
198
199 unsigned long
scm_ihashv(SCM obj,unsigned long n)200 scm_ihashv (SCM obj, unsigned long n)
201 {
202 if (SCM_CHARP(obj))
203 return ((unsigned long) (scm_c_downcase (SCM_CHAR (obj)))) % n; /* downcase!?!! */
204
205 if (SCM_NUMP(obj))
206 return (unsigned long) scm_hasher(obj, n, 10);
207 else
208 return SCM_UNPACK (obj) % n;
209 }
210
211
212 SCM_DEFINE (scm_hashv, "hashv", 2, 0, 0,
213 (SCM key, SCM size),
214 "Determine a hash value for @var{key} that is suitable for\n"
215 "lookups in a hashtable of size @var{size}, where @code{eqv?} is\n"
216 "used as the equality predicate. The function returns an\n"
217 "integer in the range 0 to @var{size} - 1. Note that\n"
218 "@code{(hashv key)} may use internal addresses. Thus two calls\n"
219 "to hashv where the keys are @code{eqv?} are not guaranteed to\n"
220 "deliver the same value if the key object gets garbage collected\n"
221 "in between. This can happen, for example with symbols:\n"
222 "@code{(hashv 'foo n) (gc) (hashv 'foo n)} may produce two\n"
223 "different values, since @code{foo} will be garbage collected.")
224 #define FUNC_NAME s_scm_hashv
225 {
226 unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
227 return scm_from_ulong (scm_ihashv (key, sz));
228 }
229 #undef FUNC_NAME
230
231
232
233
234
235 unsigned long
scm_ihash(SCM obj,unsigned long n)236 scm_ihash (SCM obj, unsigned long n)
237 {
238 return (unsigned long) scm_hasher (obj, n, 10);
239 }
240
241 SCM_DEFINE (scm_hash, "hash", 2, 0, 0,
242 (SCM key, SCM size),
243 "Determine a hash value for @var{key} that is suitable for\n"
244 "lookups in a hashtable of size @var{size}, where @code{equal?}\n"
245 "is used as the equality predicate. The function returns an\n"
246 "integer in the range 0 to @var{size} - 1.")
247 #define FUNC_NAME s_scm_hash
248 {
249 unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
250 return scm_from_ulong (scm_ihash (key, sz));
251 }
252 #undef FUNC_NAME
253
254
255
256
257
258 void
scm_init_hash()259 scm_init_hash ()
260 {
261 #include "libguile/hash.x"
262 }
263
264
265 /*
266 Local Variables:
267 c-file-style: "gnu"
268 End:
269 */
270