lib/libc/db/hash/hash_func.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   3  *
   4  * Copyright (c) 1990, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Margo Seltzer.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #if defined(LIBC_SCCS) && !defined(lint)
  36 static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94";
  37 #endif /* LIBC_SCCS and not lint */
  38 #include <sys/cdefs.h>
  39 __FBSDID("$FreeBSD$");
  40
  41 #include <sys/types.h>
  42
  43 #include <db.h>
  44 #include "hash.h"
  45 #include "page.h"
  46 #include "extern.h"
  47
  48 #ifdef notdef
  49 static u_int32_t hash1(const void *, size_t) __unused;
  50 static u_int32_t hash2(const void *, size_t) __unused;
  51 static u_int32_t hash3(const void *, size_t) __unused;
  52 #endif
  53 static u_int32_t hash4(const void *, size_t);
  54
  55 /* Default hash function. */
  56 u_int32_t (*__default_hash)(const void *, size_t) = hash4;
  57
  58 #ifdef notdef
  59 /*
  60  * Assume that we've already split the bucket to which this key hashes,
  61  * calculate that bucket, and check that in fact we did already split it.
  62  *
  63  * EJB's original hsearch hash.
  64  */
  65 #define PRIME1          37
  66 #define PRIME2          1048583
  67
  68 u_int32_t
  69 hash1(const void *key, size_t len)
  70 {
  71         u_int32_t h;
  72         u_int8_t *k;
  73
  74         h = 0;
  75         k = (u_int8_t *)key;
  76         /* Convert string to integer */
  77         while (len--)
  78                 h = h * PRIME1 ^ (*k++ - ' ');
  79         h %= PRIME2;
  80         return (h);
  81 }
  82
  83 /*
  84  * Phong Vo's linear congruential hash
  85  */
  86 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  87
  88 u_int32_t
  89 hash2(const void *key, size_t len)
  90 {
  91         u_int32_t h;
  92         u_int8_t *e, c, *k;
  93
  94         k = (u_int8_t *)key;
  95         e = k + len;
  96         for (h = 0; k != e;) {
  97                 c = *k++;
  98                 if (!c && k > e)
  99                         break;
 100                 dcharhash(h, c);
 101         }
 102         return (h);
 103 }
 104
 105 /*
 106  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
 107  * units.  On the first time through the loop we get the "leftover bytes"
 108  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
 109  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
 110  * this routine is heavily used enough, it's worth the ugly coding.
 111  *
 112  * Ozan Yigit's original sdbm hash.
 113  */
 114 u_int32_t
 115 hash3(const void *key, size_t len)
 116 {
 117         u_int32_t n, loop;
 118         u_int8_t *k;
 119
 120 #define HASHC   n = *k++ + 65599 * n
 121
 122         n = 0;
 123         k = (u_int8_t *)key;
 124         if (len > 0) {
 125                 loop = (len + 8 - 1) >> 3;
 126
 127                 switch (len & (8 - 1)) {
 128                 case 0:
 129                         do {    /* All fall throughs */
 130                                 HASHC;
 131                 case 7:
 132                                 HASHC;
 133                 case 6:
 134                                 HASHC;
 135                 case 5:
 136                                 HASHC;
 137                 case 4:
 138                                 HASHC;
 139                 case 3:
 140                                 HASHC;
 141                 case 2:
 142                                 HASHC;
 143                 case 1:
 144                                 HASHC;
 145                         } while (--loop);
 146                 }
 147
 148         }
 149         return (n);
 150 }
 151 #endif /* notdef */
 152
 153 /* Chris Torek's hash function. */
 154 u_int32_t
 155 hash4(const void *key, size_t len)
 156 {
 157         u_int32_t h, loop;
 158         const u_int8_t *k;
 159
 160 #define HASH4a   h = (h << 5) - h + *k++;
 161 #define HASH4b   h = (h << 5) + h + *k++;
 162 #define HASH4 HASH4b
 163
 164         h = 0;
 165         k = key;
 166         if (len > 0) {
 167                 loop = (len + 8 - 1) >> 3;
 168
 169                 switch (len & (8 - 1)) {
 170                 case 0:
 171                         do {    /* All fall throughs */
 172                                 HASH4;
 173                 case 7:
 174                                 HASH4;
 175                 case 6:
 176                                 HASH4;
 177                 case 5:
 178                                 HASH4;
 179                 case 4:
 180                                 HASH4;
 181                 case 3:
 182                                 HASH4;
 183                 case 2:
 184                                 HASH4;
 185                 case 1:
 186                                 HASH4;
 187                         } while (--loop);
 188                 }
 189
 190         }
 191         return (h);
 192 }