db/hash/hash_func.c

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