home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / dbm / src / h_func.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  5.4 KB  |  212 lines
  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. 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    8.2 (Berkeley) 2/21/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include "watcomfx.h"
  42.  
  43. #ifndef macintosh
  44. #include <sys/types.h>
  45. #endif
  46. #include "mcom_db.h"
  47. #include "hash.h"
  48. #include "page.h"
  49. /* #include "extern.h" */
  50.  
  51. #if 0
  52. static uint32 hash1 __P((const void *, size_t));
  53. static uint32 hash2 __P((const void *, size_t));
  54. static uint32 hash3 __P((const void *, size_t));
  55. #endif
  56. static uint32 hash4 __P((const void *, size_t));
  57.  
  58. /* Global default hash function */
  59. uint32 (*__default_hash) __P((const void *, size_t)) = hash4;
  60.  
  61. /*
  62.  * HASH FUNCTIONS
  63.  *
  64.  * Assume that we've already split the bucket to which this key hashes,
  65.  * calculate that bucket, and check that in fact we did already split it.
  66.  *
  67.  * This came from ejb's hsearch.
  68.  */
  69.  
  70. #define PRIME1        37
  71. #define PRIME2        1048583
  72.  
  73. #if 0
  74. static uint32
  75. hash1(const void *keyarg, register size_t len)
  76. {
  77.     register const uint8 *key;
  78.     register uint32 h;
  79.  
  80.     /* Convert string to integer */
  81.     for (key = (const uint8 *)keyarg, h = 0; len--;)
  82.         h = h * PRIME1 ^ (*key++ - ' ');
  83.     h %= PRIME2;
  84.     return (h);
  85. }
  86.  
  87. /*
  88.  * Phong's linear congruential hash
  89.  */
  90. #define dcharhash(h, c)    ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  91.  
  92. static uint32
  93. hash2(const void *keyarg, size_t len)
  94. {
  95.     register const uint8 *e, *key;
  96.     register uint32 h;
  97.     register uint8 c;
  98.  
  99.     key = (const uint8 *)keyarg;
  100.     e = key + len;
  101.     for (h = 0; key != e;) {
  102.         c = *key++;
  103.         if (!c && key > e)
  104.             break;
  105.         dcharhash(h, c);
  106.     }
  107.     return (h);
  108. }
  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. static uint32
  120. hash3(const void *keyarg, register size_t len)
  121. {
  122.     register const uint8 *key;
  123.     register size_t loop;
  124.     register uint32 h;
  125.  
  126. #define HASHC   h = *key++ + 65599 * h
  127.  
  128.     h = 0;
  129.     key = (const uint8 *)keyarg;
  130.     if (len > 0) {
  131.         loop = (len + 8 - 1) >> 3;
  132.  
  133.         switch (len & (8 - 1)) {
  134.         case 0:
  135.             do {
  136.                 HASHC;
  137.                 /* FALLTHROUGH */
  138.         case 7:
  139.                 HASHC;
  140.                 /* FALLTHROUGH */
  141.         case 6:
  142.                 HASHC;
  143.                 /* FALLTHROUGH */
  144.         case 5:
  145.                 HASHC;
  146.                 /* FALLTHROUGH */
  147.         case 4:
  148.                 HASHC;
  149.                 /* FALLTHROUGH */
  150.         case 3:
  151.                 HASHC;
  152.                 /* FALLTHROUGH */
  153.         case 2:
  154.                 HASHC;
  155.                 /* FALLTHROUGH */
  156.         case 1:
  157.                 HASHC;
  158.             } while (--loop);
  159.         }
  160.     }
  161.     return (h);
  162. }
  163. #endif /* 0 */
  164.  
  165. /* Hash function from Chris Torek. */
  166. static uint32
  167. hash4(const void *keyarg, register size_t len)
  168. {
  169.     register const uint8 *key;
  170.     register size_t loop;
  171.     register uint32 h;
  172.  
  173. #define HASH4a   h = (h << 5) - h + *key++;
  174. #define HASH4b   h = (h << 5) + h + *key++;
  175. #define HASH4 HASH4b
  176.  
  177.     h = 0;
  178.     key = (const uint8 *)keyarg;
  179.     if (len > 0) {
  180.         loop = (len + 8 - 1) >> 3;
  181.  
  182.         switch (len & (8 - 1)) {
  183.         case 0:
  184.             do {
  185.                 HASH4;
  186.                 /* FALLTHROUGH */
  187.         case 7:
  188.                 HASH4;
  189.                 /* FALLTHROUGH */
  190.         case 6:
  191.                 HASH4;
  192.                 /* FALLTHROUGH */
  193.         case 5:
  194.                 HASH4;
  195.                 /* FALLTHROUGH */
  196.         case 4:
  197.                 HASH4;
  198.                 /* FALLTHROUGH */
  199.         case 3:
  200.                 HASH4;
  201.                 /* FALLTHROUGH */
  202.         case 2:
  203.                 HASH4;
  204.                 /* FALLTHROUGH */
  205.         case 1:
  206.                 HASH4;
  207.             } while (--loop);
  208.         }
  209.     }
  210.     return (h);
  211. }
  212.