db.1.85/hash/hash_func.c

   1 /*-
   2  * Copyright (c) 1990, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Margo Seltzer.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/types.h>
  42
  43 #include <db.h>
  44 #include "hash.h"
  45 #include "page.h"
  46 #include "extern.h"
  47
  48 static u_int32_t hash1 __P((const void *, size_t));
  49 static u_int32_t hash2 __P((const void *, size_t));
  50 static u_int32_t hash3 __P((const void *, size_t));
  51 static u_int32_t hash4 __P((const void *, size_t));
  52
  53 /* Global default hash function */
  54 u_int32_t (*__default_hash) __P((const void *, size_t)) = hash4;
  55
  56 /*
  57  * HASH FUNCTIONS
  58  *
  59  * Assume that we've already split the bucket to which this key hashes,
  60  * calculate that bucket, and check that in fact we did already split it.
  61  *
  62  * This came from ejb's hsearch.
  63  */
  64
  65 #define PRIME1          37
  66 #define PRIME2          1048583
  67
  68 static u_int32_t
  69 hash1(keyarg, len)
  70         const void *keyarg;
  71         register size_t len;
  72 {
  73         register const u_char *key;
  74         register u_int32_t h;
  75
  76         /* Convert string to integer */
  77         for (key = keyarg, h = 0; len--;)
  78                 h = h * PRIME1 ^ (*key++ - ' ');
  79         h %= PRIME2;
  80         return (h);
  81 }
  82
  83 /*
  84  * Phong's linear congruential hash
  85  */
  86 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  87
  88 static u_int32_t
  89 hash2(keyarg, len)
  90         const void *keyarg;
  91         size_t len;
  92 {
  93         register const u_char *e, *key;
  94         register u_int32_t h;
  95         register u_char c;
  96
  97         key = keyarg;
  98         e = key + len;
  99         for (h = 0; key != e;) {
 100                 c = *key++;
 101                 if (!c && key > e)
 102                         break;
 103                 dcharhash(h, c);
 104         }
 105         return (h);
 106 }
 107
 108 /*
 109  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
 110  * units.  On the first time through the loop we get the "leftover bytes"
 111  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
 112  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
 113  * this routine is heavily used enough, it's worth the ugly coding.
 114  *
 115  * OZ's original sdbm hash
 116  */
 117 static u_int32_t
 118 hash3(keyarg, len)
 119         const void *keyarg;
 120         register size_t len;
 121 {
 122         register const u_char *key;
 123         register size_t loop;
 124         register u_int32_t h;
 125
 126 #define HASHC   h = *key++ + 65599 * h
 127
 128         h = 0;
 129         key = keyarg;
 130         if (len > 0) {
 131                 loop = (len + 8 - 1) >> 3;
 132
 133                 switch (len & (8 - 1)) {
 134                 case 0:
 135                         do {
 136                                 HASHC;
 137                                 /* FALLTHROUGH */
 138                 case 7:
 139                                 HASHC;
 140                                 /* FALLTHROUGH */
 141                 case 6:
 142                                 HASHC;
 143                                 /* FALLTHROUGH */
 144                 case 5:
 145                                 HASHC;
 146                                 /* FALLTHROUGH */
 147                 case 4:
 148                                 HASHC;
 149                                 /* FALLTHROUGH */
 150                 case 3:
 151                                 HASHC;
 152                                 /* FALLTHROUGH */
 153                 case 2:
 154                                 HASHC;
 155                                 /* FALLTHROUGH */
 156                 case 1:
 157                                 HASHC;
 158                         } while (--loop);
 159                 }
 160         }
 161         return (h);
 162 }
 163
 164 /* Hash function from Chris Torek. */
 165 static u_int32_t
 166 hash4(keyarg, len)
 167         const void *keyarg;
 168         register size_t len;
 169 {
 170         register const u_char *key;
 171         register size_t loop;
 172         register u_int32_t h;
 173
 174 #define HASH4a   h = (h << 5) - h + *key++;
 175 #define HASH4b   h = (h << 5) + h + *key++;
 176 #define HASH4 HASH4b
 177
 178         h = 0;
 179         key = keyarg;
 180         if (len > 0) {
 181                 loop = (len + 8 - 1) >> 3;
 182
 183                 switch (len & (8 - 1)) {
 184                 case 0:
 185                         do {
 186                                 HASH4;
 187                                 /* FALLTHROUGH */
 188                 case 7:
 189                                 HASH4;
 190                                 /* FALLTHROUGH */
 191                 case 6:
 192                                 HASH4;
 193                                 /* FALLTHROUGH */
 194                 case 5:
 195                                 HASH4;
 196                                 /* FALLTHROUGH */
 197                 case 4:
 198                                 HASH4;
 199                                 /* FALLTHROUGH */
 200                 case 3:
 201                                 HASH4;
 202                                 /* FALLTHROUGH */
 203                 case 2:
 204                                 HASH4;
 205                                 /* FALLTHROUGH */
 206                 case 1:
 207                                 HASH4;
 208                         } while (--loop);
 209                 }
 210         }
 211         return (h);
 212 }