db/hash/hash_func-fbsd.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 #include <sys/cdefs.h>
  41 __FBSDID("$FreeBSD: src/lib/libc/db/hash/hash_func.c,v 1.5 2003/02/16 17:29:09 nectar Exp $");
  42
  43 #include <sys/types.h>
  44
  45 #include <db.h>
  46 #include "hash.h"
  47 #include "page.h"
  48 #include "hash_extern.h"
  49
  50 static u_int32_t hash1(const void *, size_t) __unused;
  51 static u_int32_t hash2(const void *, size_t) __unused;
  52 static u_int32_t hash3(const void *, size_t) __unused;
  53 static u_int32_t hash4(const void *, size_t);
  54
  55 /* Global default hash function */
  56 u_int32_t (*__default_hash)(const void *, size_t) = hash4;
  57
  58 /*
  59  * HASH FUNCTIONS
  60  *
  61  * Assume that we've already split the bucket to which this key hashes,
  62  * calculate that bucket, and check that in fact we did already split it.
  63  *
  64  * This came from ejb's hsearch.
  65  */
  66
  67 #define PRIME1          37
  68 #define PRIME2          1048583
  69
  70 static u_int32_t
  71 hash1(keyarg, len)
  72         const void *keyarg;
  73         size_t len;
  74 {
  75         const u_char *key;
  76         u_int32_t h;
  77
  78         /* Convert string to integer */
  79         for (key = keyarg, h = 0; len--;)
  80                 h = h * PRIME1 ^ (*key++ - ' ');
  81         h %= PRIME2;
  82         return (h);
  83 }
  84
  85 /*
  86  * Phong's linear congruential hash
  87  */
  88 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  89
  90 static u_int32_t
  91 hash2(keyarg, len)
  92         const void *keyarg;
  93         size_t len;
  94 {
  95         const u_char *e, *key;
  96         u_int32_t h;
  97         u_char c;
  98
  99         key = keyarg;
 100         e = key + len;
 101         for (h = 0; key != e;) {
 102                 c = *key++;
 103                 if (!c && key > e)
 104                         break;
 105                 dcharhash(h, c);
 106         }
 107         return (h);
 108 }
 109
 110 /*
 111  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
 112  * units.  On the first time through the loop we get the "leftover bytes"
 113  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
 114  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
 115  * this routine is heavily used enough, it's worth the ugly coding.
 116  *
 117  * OZ's original sdbm hash
 118  */
 119 static u_int32_t
 120 hash3(keyarg, len)
 121         const void *keyarg;
 122         size_t len;
 123 {
 124         const u_char *key;
 125         size_t loop;
 126         u_int32_t h;
 127
 128 #define HASHC   h = *key++ + 65599 * h
 129
 130         h = 0;
 131         key = keyarg;
 132         if (len > 0) {
 133                 loop = (len + 8 - 1) >> 3;
 134
 135                 switch (len & (8 - 1)) {
 136                 case 0:
 137                         do {
 138                                 HASHC;
 139                                 /* FALLTHROUGH */
 140                 case 7:
 141                                 HASHC;
 142                                 /* FALLTHROUGH */
 143                 case 6:
 144                                 HASHC;
 145                                 /* FALLTHROUGH */
 146                 case 5:
 147                                 HASHC;
 148                                 /* FALLTHROUGH */
 149                 case 4:
 150                                 HASHC;
 151                                 /* FALLTHROUGH */
 152                 case 3:
 153                                 HASHC;
 154                                 /* FALLTHROUGH */
 155                 case 2:
 156                                 HASHC;
 157                                 /* FALLTHROUGH */
 158                 case 1:
 159                                 HASHC;
 160                         } while (--loop);
 161                 }
 162         }
 163         return (h);
 164 }
 165
 166 /* Hash function from Chris Torek. */
 167 static u_int32_t
 168 hash4(keyarg, len)
 169         const void *keyarg;
 170         size_t len;
 171 {
 172         const u_char *key;
 173         size_t loop;
 174         u_int32_t h;
 175
 176 #define HASH4a   h = (h << 5) - h + *key++;
 177 #define HASH4b   h = (h << 5) + h + *key++;
 178 #define HASH4 HASH4b
 179
 180         h = 0;
 181         key = keyarg;
 182         if (len > 0) {
 183                 loop = (len + 8 - 1) >> 3;
 184
 185                 switch (len & (8 - 1)) {
 186                 case 0:
 187                         do {
 188                                 HASH4;
 189                                 /* FALLTHROUGH */
 190                 case 7:
 191                                 HASH4;
 192                                 /* FALLTHROUGH */
 193                 case 6:
 194                                 HASH4;
 195                                 /* FALLTHROUGH */
 196                 case 5:
 197                                 HASH4;
 198                                 /* FALLTHROUGH */
 199                 case 4:
 200                                 HASH4;
 201                                 /* FALLTHROUGH */
 202                 case 3:
 203                                 HASH4;
 204                                 /* FALLTHROUGH */
 205                 case 2:
 206                                 HASH4;
 207                                 /* FALLTHROUGH */
 208                 case 1:
 209                                 HASH4;
 210                         } while (--loop);
 211                 }
 212         }
 213         return (h);
 214 }