| 1 | /* Copyright (C) 1995,1996 Free Software Foundation, Inc. |
| 2 | * |
| 3 | * This program is free software; you can redistribute it and/or modify |
| 4 | * it under the terms of the GNU General Public License as published by |
| 5 | * the Free Software Foundation; either version 2, or (at your option) |
| 6 | * any later version. |
| 7 | * |
| 8 | * This program 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 |
| 11 | * GNU General Public License for more details. |
| 12 | * |
| 13 | * You should have received a copy of the GNU General Public License |
| 14 | * along with this software; see the file COPYING. If not, write to |
| 15 | * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. |
| 16 | * |
| 17 | * As a special exception, the Free Software Foundation gives permission |
| 18 | * for additional uses of the text contained in its release of GUILE. |
| 19 | * |
| 20 | * The exception is that, if you link the GUILE library with other files |
| 21 | * to produce an executable, this does not by itself cause the |
| 22 | * resulting executable to be covered by the GNU General Public License. |
| 23 | * Your use of that executable is in no way restricted on account of |
| 24 | * linking the GUILE library code into it. |
| 25 | * |
| 26 | * This exception does not however invalidate any other reasons why |
| 27 | * the executable file might be covered by the GNU General Public License. |
| 28 | * |
| 29 | * This exception applies only to the code released by the |
| 30 | * Free Software Foundation under the name GUILE. If you copy |
| 31 | * code from other Free Software Foundation releases into a copy of |
| 32 | * GUILE, as the General Public License permits, the exception does |
| 33 | * not apply to the code that you add in this way. To avoid misleading |
| 34 | * anyone as to the status of such modified files, you must delete |
| 35 | * this exception notice from them. |
| 36 | * |
| 37 | * If you write modifications of your own for GUILE, it is your choice |
| 38 | * whether to permit this exception to apply to your modifications. |
| 39 | * If you do not wish that, delete this exception notice. |
| 40 | */ |
| 41 | \f |
| 42 | |
| 43 | #include <stdio.h> |
| 44 | #include "_scm.h" |
| 45 | #include "chars.h" |
| 46 | |
| 47 | #include "hash.h" |
| 48 | \f |
| 49 | |
| 50 | #ifndef floor |
| 51 | extern double floor(); |
| 52 | #endif |
| 53 | |
| 54 | |
| 55 | unsigned long |
| 56 | scm_hasher(obj, n, d) |
| 57 | SCM obj; |
| 58 | unsigned long n; |
| 59 | scm_sizet d; |
| 60 | { |
| 61 | switch (7 & (int) obj) { |
| 62 | case 2: case 6: /* SCM_INUMP(obj) */ |
| 63 | return SCM_INUM(obj) % n; |
| 64 | case 4: |
| 65 | if SCM_ICHRP(obj) |
| 66 | return (unsigned)(scm_downcase(SCM_ICHR(obj))) % n; |
| 67 | switch ((int) obj) { |
| 68 | #ifndef SICP |
| 69 | case (int) SCM_EOL: d = 256; break; |
| 70 | #endif |
| 71 | case (int) SCM_BOOL_T: d = 257; break; |
| 72 | case (int) SCM_BOOL_F: d = 258; break; |
| 73 | case (int) SCM_EOF_VAL: d = 259; break; |
| 74 | default: d = 263; /* perhaps should be error */ |
| 75 | } |
| 76 | return d % n; |
| 77 | default: return 263 % n; /* perhaps should be error */ |
| 78 | case 0: |
| 79 | switch SCM_TYP7(obj) { |
| 80 | default: return 263 % n; |
| 81 | case scm_tc7_smob: |
| 82 | switch SCM_TYP16(obj) { |
| 83 | case scm_tcs_bignums: |
| 84 | bighash: return SCM_INUM(scm_modulo(obj, SCM_MAKINUM(n))); |
| 85 | default: return 263 % n; |
| 86 | #ifdef SCM_FLOATS |
| 87 | case scm_tc16_flo: |
| 88 | if SCM_REALP(obj) { |
| 89 | double r = SCM_REALPART(obj); |
| 90 | if (floor(r)==r) { |
| 91 | obj = scm_inexact_to_exact (obj); |
| 92 | if SCM_IMP(obj) return SCM_INUM(obj) % n; |
| 93 | goto bighash; |
| 94 | } |
| 95 | } |
| 96 | obj = scm_number_to_string(obj, SCM_MAKINUM(10)); |
| 97 | #endif |
| 98 | } |
| 99 | case scm_tcs_symbols: |
| 100 | case scm_tc7_string: |
| 101 | case scm_tc7_mb_string: |
| 102 | case scm_tc7_substring: |
| 103 | case scm_tc7_mb_substring: |
| 104 | return scm_strhash(SCM_ROUCHARS(obj), (scm_sizet) SCM_ROLENGTH(obj), n); |
| 105 | case scm_tc7_wvect: |
| 106 | case scm_tc7_vector: |
| 107 | { |
| 108 | scm_sizet len = SCM_LENGTH(obj); |
| 109 | SCM *data = SCM_VELTS(obj); |
| 110 | if (len>5) |
| 111 | { |
| 112 | scm_sizet i = d/2; |
| 113 | unsigned long h = 1; |
| 114 | while (i--) h = ((h<<8) + (scm_hasher(data[h % len], n, 2))) % n; |
| 115 | return h; |
| 116 | } |
| 117 | else |
| 118 | { |
| 119 | scm_sizet i = len; |
| 120 | unsigned long h = (n)-1; |
| 121 | while (i--) h = ((h<<8) + (scm_hasher(data[i], n, d/len))) % n; |
| 122 | return h; |
| 123 | } |
| 124 | } |
| 125 | case scm_tcs_cons_imcar: case scm_tcs_cons_nimcar: |
| 126 | if (d) return (scm_hasher(SCM_CAR(obj), n, d/2)+scm_hasher(SCM_CDR(obj), n, d/2)) % n; |
| 127 | else return 1; |
| 128 | case scm_tc7_port: |
| 129 | return ((SCM_RDNG & SCM_CAR(obj)) ? 260 : 261) % n; |
| 130 | case scm_tcs_closures: case scm_tc7_contin: case scm_tcs_subrs: |
| 131 | return 262 % n; |
| 132 | } |
| 133 | } |
| 134 | } |
| 135 | |
| 136 | |
| 137 | \f |
| 138 | |
| 139 | |
| 140 | unsigned int |
| 141 | scm_ihashq (obj, n) |
| 142 | SCM obj; |
| 143 | unsigned int n; |
| 144 | { |
| 145 | return (((unsigned int) obj) >> 1) % n; |
| 146 | } |
| 147 | |
| 148 | |
| 149 | SCM_PROC(s_hashq, "hashq", 2, 0, 0, scm_hashq); |
| 150 | |
| 151 | SCM |
| 152 | scm_hashq(obj, n) |
| 153 | SCM obj; |
| 154 | SCM n; |
| 155 | { |
| 156 | SCM_ASSERT(SCM_INUMP(n) && 0 <= n, n, SCM_ARG2, s_hashq); |
| 157 | return SCM_MAKINUM(scm_ihashq (obj, SCM_INUM (n))); |
| 158 | } |
| 159 | |
| 160 | |
| 161 | \f |
| 162 | |
| 163 | |
| 164 | unsigned int |
| 165 | scm_ihashv (obj, n) |
| 166 | SCM obj; |
| 167 | unsigned int n; |
| 168 | { |
| 169 | if (SCM_ICHRP(obj)) |
| 170 | return ((unsigned int)(scm_downcase(SCM_ICHR(obj)))) % n; /* downcase!?!! */ |
| 171 | |
| 172 | if (SCM_NIMP(obj) && SCM_NUMP(obj)) |
| 173 | return (unsigned int) scm_hasher(obj, n, 10); |
| 174 | else |
| 175 | return ((unsigned int)obj) % n; |
| 176 | } |
| 177 | |
| 178 | |
| 179 | SCM_PROC(s_hashv, "hashv", 2, 0, 0, scm_hashv); |
| 180 | |
| 181 | SCM |
| 182 | scm_hashv(obj, n) |
| 183 | SCM obj; |
| 184 | SCM n; |
| 185 | { |
| 186 | SCM_ASSERT(SCM_INUMP(n) && 0 <= n, n, SCM_ARG2, s_hashv); |
| 187 | return SCM_MAKINUM(scm_ihashv (obj, SCM_INUM (n))); |
| 188 | } |
| 189 | |
| 190 | |
| 191 | \f |
| 192 | |
| 193 | |
| 194 | unsigned int |
| 195 | scm_ihash (obj, n) |
| 196 | SCM obj; |
| 197 | unsigned int n; |
| 198 | { |
| 199 | return (unsigned int)scm_hasher (obj, n, 10); |
| 200 | } |
| 201 | |
| 202 | SCM_PROC(s_hash, "hash", 2, 0, 0, scm_hash); |
| 203 | |
| 204 | SCM |
| 205 | scm_hash(obj, n) |
| 206 | SCM obj; |
| 207 | SCM n; |
| 208 | { |
| 209 | SCM_ASSERT(SCM_INUMP(n) && 0 <= n, n, SCM_ARG2, s_hash); |
| 210 | return SCM_MAKINUM(scm_ihash(obj, SCM_INUM(n))); |
| 211 | } |
| 212 | |
| 213 | |
| 214 | \f |
| 215 | |
| 216 | |
| 217 | void |
| 218 | scm_init_hash () |
| 219 | { |
| 220 | #include "hash.x" |
| 221 | } |
| 222 | |