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