lib/libc/DB/hash/hash_func.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * 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. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)hash_func.c 5.4 (Berkeley) 2/11/93";
  39 #endif /* LIBC_SCCS and not lint */
  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 static int hash1 __P((u_char *, int));
  49 static int hash2 __P((u_char *, int));
  50 static int hash3 __P((u_char *, int));
  51 static int hash4 __P((u_char *, int));
  52
  53 /* Global default hash function */
  54 int (*__default_hash) __P((u_char *, int)) = hash4;
  55
  56 /******************************* HASH FUNCTIONS **************************/
  57 /*
  58  * Assume that we've already split the bucket to which this key hashes,
  59  * calculate that bucket, and check that in fact we did already split it.
  60  *
  61  * This came from ejb's hsearch.
  62  */
  63
  64 #define PRIME1          37
  65 #define PRIME2          1048583
  66
  67 static int
  68 hash1(key, len)
  69         register u_char *key;
  70         register int len;
  71 {
  72         register int h;
  73
  74         h = 0;
  75         /* Convert string to integer */
  76         while (len--)
  77                 h = h * PRIME1 ^ (*key++ - ' ');
  78         h %= PRIME2;
  79         return (h);
  80 }
  81
  82 /*
  83  * Phong's linear congruential hash
  84  */
  85 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  86
  87 static int
  88 hash2(key, len)
  89         register u_char *key;
  90         int len;
  91 {
  92         register u_char *e, c;
  93         register int h;
  94
  95         e = key + len;
  96         for (h = 0; key != e;) {
  97                 c = *key++;
  98                 if (!c && key > 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  * OZ's original sdbm hash
 113  */
 114 static int
 115 hash3(key, len)
 116         register u_char *key;
 117         register int len;
 118 {
 119         register int n, loop;
 120
 121 #define HASHC   n = *key++ + 65599 * n
 122
 123         n = 0;
 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
 152 /* Hash function from Chris Torek. */
 153 static int
 154 hash4(key, len)
 155         register u_char *key;
 156         register int len;
 157 {
 158         register int h, loop;
 159
 160 #define HASH4a   h = (h << 5) - h + *key++;
 161 #define HASH4b   h = (h << 5) + h + *key++;
 162 #define HASH4 HASH4b
 163
 164         h = 0;
 165         if (len > 0) {
 166                 loop = (len + 8 - 1) >> 3;
 167
 168                 switch (len & (8 - 1)) {
 169                 case 0:
 170                         do {    /* All fall throughs */
 171                                 HASH4;
 172                 case 7:
 173                                 HASH4;
 174                 case 6:
 175                                 HASH4;
 176                 case 5:
 177                                 HASH4;
 178                 case 4:
 179                                 HASH4;
 180                 case 3:
 181                                 HASH4;
 182                 case 2:
 183                                 HASH4;
 184                 case 1:
 185                                 HASH4;
 186                         } while (--loop);
 187                 }
 188
 189         }
 190         return (h);
 191 }