db/hash/hash_func.c

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