Back to index

lightning-sunbird  0.9+nobinonly
h_func.c
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Margo Seltzer.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. ***REMOVED*** - see 
00017  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00018  * 4. Neither the name of the University nor the names of its contributors
00019  *    may be used to endorse or promote products derived from this software
00020  *    without specific prior written permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00023  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00026  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00027  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00028  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00029  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00031  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00032  * SUCH DAMAGE.
00033  */
00034 
00035 #if defined(LIBC_SCCS) && !defined(lint)
00036 static char sccsid[] = "@(#)hash_func.c   8.2 (Berkeley) 2/21/94";
00037 #endif /* LIBC_SCCS and not lint */
00038 
00039 #include "watcomfx.h"
00040 
00041 #ifndef macintosh
00042 #include <sys/types.h>
00043 #endif
00044 #include "mcom_db.h"
00045 #include "hash.h"
00046 #include "page.h"
00047 /* #include "extern.h" */
00048 
00049 #if 0
00050 static uint32 hash1 __P((const void *, size_t));
00051 static uint32 hash2 __P((const void *, size_t));
00052 static uint32 hash3 __P((const void *, size_t));
00053 #endif
00054 static uint32 hash4 __P((const void *, size_t));
00055 
00056 /* Global default hash function */
00057 uint32 (*__default_hash) __P((const void *, size_t)) = hash4;
00058 
00059 /*
00060  * HASH FUNCTIONS
00061  *
00062  * Assume that we've already split the bucket to which this key hashes,
00063  * calculate that bucket, and check that in fact we did already split it.
00064  *
00065  * This came from ejb's hsearch.
00066  */
00067 
00068 #define PRIME1              37
00069 #define PRIME2              1048583
00070 
00071 #if 0
00072 static uint32
00073 hash1(const void *keyarg, register size_t len)
00074 {
00075        register const uint8 *key;
00076        register uint32 h;
00077 
00078        /* Convert string to integer */
00079        for (key = (const uint8 *)keyarg, h = 0; len--;)
00080               h = h * PRIME1 ^ (*key++ - ' ');
00081        h %= PRIME2;
00082        return (h);
00083 }
00084 
00085 /*
00086  * Phong's linear congruential hash
00087  */
00088 #define dcharhash(h, c)     ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
00089 
00090 static uint32
00091 hash2(const void *keyarg, size_t len)
00092 {
00093        register const uint8 *e, *key;
00094        register uint32 h;
00095        register uint8 c;
00096 
00097        key = (const uint8 *)keyarg;
00098        e = key + len;
00099        for (h = 0; key != e;) {
00100               c = *key++;
00101               if (!c && key > e)
00102                      break;
00103               dcharhash(h, c);
00104        }
00105        return (h);
00106 }
00107 
00108 /*
00109  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
00110  * units.  On the first time through the loop we get the "leftover bytes"
00111  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
00112  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
00113  * this routine is heavily used enough, it's worth the ugly coding.
00114  *
00115  * OZ's original sdbm hash
00116  */
00117 static uint32
00118 hash3(const void *keyarg, register size_t len)
00119 {
00120        register const uint8 *key;
00121        register size_t loop;
00122        register uint32 h;
00123 
00124 #define HASHC   h = *key++ + 65599 * h
00125 
00126        h = 0;
00127        key = (const uint8 *)keyarg;
00128        if (len > 0) {
00129               loop = (len + 8 - 1) >> 3;
00130 
00131               switch (len & (8 - 1)) {
00132               case 0:
00133                      do {
00134                             HASHC;
00135                             /* FALLTHROUGH */
00136               case 7:
00137                             HASHC;
00138                             /* FALLTHROUGH */
00139               case 6:
00140                             HASHC;
00141                             /* FALLTHROUGH */
00142               case 5:
00143                             HASHC;
00144                             /* FALLTHROUGH */
00145               case 4:
00146                             HASHC;
00147                             /* FALLTHROUGH */
00148               case 3:
00149                             HASHC;
00150                             /* FALLTHROUGH */
00151               case 2:
00152                             HASHC;
00153                             /* FALLTHROUGH */
00154               case 1:
00155                             HASHC;
00156                      } while (--loop);
00157               }
00158        }
00159        return (h);
00160 }
00161 #endif /* 0 */
00162 
00163 /* Hash function from Chris Torek. */
00164 static uint32
00165 hash4(const void *keyarg, register size_t len)
00166 {
00167        register const uint8 *key;
00168        register size_t loop;
00169        register uint32 h;
00170 
00171 #define HASH4a   h = (h << 5) - h + *key++;
00172 #define HASH4b   h = (h << 5) + h + *key++;
00173 #define HASH4 HASH4b
00174 
00175        h = 0;
00176        key = (const uint8 *)keyarg;
00177        if (len > 0) {
00178               loop = (len + 8 - 1) >> 3;
00179 
00180               switch (len & (8 - 1)) {
00181               case 0:
00182                      do {
00183                             HASH4;
00184                             /* FALLTHROUGH */
00185               case 7:
00186                             HASH4;
00187                             /* FALLTHROUGH */
00188               case 6:
00189                             HASH4;
00190                             /* FALLTHROUGH */
00191               case 5:
00192                             HASH4;
00193                             /* FALLTHROUGH */
00194               case 4:
00195                             HASH4;
00196                             /* FALLTHROUGH */
00197               case 3:
00198                             HASH4;
00199                             /* FALLTHROUGH */
00200               case 2:
00201                             HASH4;
00202                             /* FALLTHROUGH */
00203               case 1:
00204                             HASH4;
00205                      } while (--loop);
00206               }
00207        }
00208        return (h);
00209 }