guile18/libguile/hash.c

   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 \f
  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 \f
  34
  35 #ifndef floor
  36 extern double floor();
  37 #endif
  38
  39
  40 unsigned long
  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
  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 \f
 167
 168
 169 unsigned long
 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 \f
 197
 198
 199 unsigned long
 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 \f
 233
 234
 235 unsigned long
 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 \f
 256
 257
 258 void
 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 */