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