db2/hash/hash_func.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7 /*
   8  * Copyright (c) 1990, 1993
   9  *      Margo Seltzer.  All rights reserved.
  10  */
  11 /*
  12  * Copyright (c) 1990, 1993
  13  *      The Regents of the University of California.  All rights reserved.
  14  *
  15  * This code is derived from software contributed to Berkeley by
  16  * Margo Seltzer.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions
  20  * are met:
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  * 2. Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  * 3. All advertising materials mentioning features or use of this software
  27  *    must display the following acknowledgement:
  28  *      This product includes software developed by the University of
  29  *      California, Berkeley and its contributors.
  30  * 4. Neither the name of the University nor the names of its contributors
  31  *    may be used to endorse or promote products derived from this software
  32  *    without specific prior written permission.
  33  *
  34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  44  * SUCH DAMAGE.
  45  */
  46
  47 #include "config.h"
  48
  49 #ifndef lint
  50 static const char sccsid[] = "@(#)hash_func.c   10.8 (Sleepycat) 4/10/98";
  51 #endif /* not lint */
  52
  53 #ifndef NO_SYSTEM_INCLUDES
  54 #include <sys/types.h>
  55 #endif
  56
  57 #include "db_int.h"
  58 #include "db_page.h"
  59 #include "hash.h"
  60
  61 /*
  62  * __ham_func2 --
  63  *      Phong Vo's linear congruential hash.
  64  *
  65  * PUBLIC: u_int32_t __ham_func2 __P((const void *, u_int32_t));
  66  */
  67 #define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  68
  69 u_int32_t
  70 __ham_func2(key, len)
  71         const void *key;
  72         u_int32_t len;
  73 {
  74         const u_int8_t *e, *k;
  75         u_int32_t h;
  76         u_int8_t c;
  77
  78         k = key;
  79         e = k + len;
  80         for (h = 0; k != e;) {
  81                 c = *k++;
  82                 if (!c && k > e)
  83                         break;
  84                 DCHARHASH(h, c);
  85         }
  86         return (h);
  87 }
  88
  89 /*
  90  * __ham_func3 --
  91  *      Ozan Yigit's original sdbm hash.
  92  *
  93  * Ugly, but fast.  Break the string up into 8 byte units.  On the first time
  94  * through the loop get the "leftover bytes" (strlen % 8).  On every other
  95  * iteration, perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
  96  * saves us 7 cmp & branch instructions.
  97  *
  98  * PUBLIC: u_int32_t __ham_func3 __P((const void *, u_int32_t));
  99  */
 100 u_int32_t
 101 __ham_func3(key, len)
 102         const void *key;
 103         u_int32_t len;
 104 {
 105         const u_int8_t *k;
 106         u_int32_t n, loop;
 107
 108         if (len == 0)
 109                 return (0);
 110
 111 #define HASHC   n = *k++ + 65599 * n
 112         n = 0;
 113         k = key;
 114
 115         loop = (len + 8 - 1) >> 3;
 116         switch (len & (8 - 1)) {
 117         case 0:
 118                 do {
 119                         HASHC;
 120         case 7:
 121                         HASHC;
 122         case 6:
 123                         HASHC;
 124         case 5:
 125                         HASHC;
 126         case 4:
 127                         HASHC;
 128         case 3:
 129                         HASHC;
 130         case 2:
 131                         HASHC;
 132         case 1:
 133                         HASHC;
 134                 } while (--loop);
 135         }
 136         return (n);
 137 }
 138
 139 /*
 140  * __ham_func4 --
 141  *      Chris Torek's hash function.  Although this function performs only
 142  *      slightly worse than __ham_func5 on strings, it performs horribly on
 143  *      numbers.
 144  *
 145  * PUBLIC: u_int32_t __ham_func4 __P((const void *, u_int32_t));
 146  */
 147 u_int32_t
 148 __ham_func4(key, len)
 149         const void *key;
 150         u_int32_t len;
 151 {
 152         const u_int8_t *k;
 153         u_int32_t h, loop;
 154
 155         if (len == 0)
 156                 return (0);
 157
 158 #define HASH4a  h = (h << 5) - h + *k++;
 159 #define HASH4b  h = (h << 5) + h + *k++;
 160 #define HASH4   HASH4b
 161         h = 0;
 162         k = key;
 163
 164         loop = (len + 8 - 1) >> 3;
 165         switch (len & (8 - 1)) {
 166         case 0:
 167                 do {
 168                         HASH4;
 169         case 7:
 170                         HASH4;
 171         case 6:
 172                         HASH4;
 173         case 5:
 174                         HASH4;
 175         case 4:
 176                         HASH4;
 177         case 3:
 178                         HASH4;
 179         case 2:
 180                         HASH4;
 181         case 1:
 182                         HASH4;
 183                 } while (--loop);
 184         }
 185         return (h);
 186 }
 187
 188 /*
 189  * Fowler/Noll/Vo hash
 190  *
 191  * The basis of the hash algorithm was taken from an idea sent by email to the
 192  * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 193  * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 194  * later improved on their algorithm.
 195  *
 196  * The magic is in the interesting relationship between the special prime
 197  * 16777619 (2^24 + 403) and 2^32 and 2^8.
 198  *
 199  * This hash produces the fewest collisions of any function that we've seen so
 200  * far, and works well on both numbers and strings.
 201  *
 202  * PUBLIC: u_int32_t __ham_func5 __P((const void *, u_int32_t));
 203  */
 204 u_int32_t
 205 __ham_func5(key, len)
 206         const void *key;
 207         u_int32_t len;
 208 {
 209         const u_int8_t *k, *e;
 210         u_int32_t h;
 211
 212         k = key;
 213         e = k + len;
 214         for (h = 0; k < e; ++k) {
 215                 h *= 16777619;
 216                 h ^= *k;
 217         }
 218         return (h);
 219 }