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