db.subproj/hash.subproj/hash_func.c

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