libguile/hash.c

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