lib/libc/db/hash/hash_func.c

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