libguile/hash.c

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