home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / ixemul-45.0-src.tgz / tar.out / contrib / ixemul / db / hash / hash_func.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  5KB  |  223 lines
  1. /*    $NetBSD: hash_func.c,v 1.5 1995/02/27 13:22:27 cgd 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. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)hash_func.c    8.2 (Berkeley) 2/21/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: hash_func.c,v 1.5 1995/02/27 13:22:27 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. #include <sys/types.h>
  48.  
  49. #include <db.h>
  50. #include "hash.h"
  51. #include "page.h"
  52. #include "extern.h"
  53.  
  54. #if 0
  55. static u_int32_t hash1 __P((const void *, size_t));
  56. static u_int32_t hash2 __P((const void *, size_t));
  57. static u_int32_t hash3 __P((const void *, size_t));
  58. #endif
  59. static u_int32_t hash4 __P((const void *, size_t));
  60.  
  61. /* Global default hash function */
  62. u_int32_t (*__default_hash) __P((const void *, size_t)) = hash4;
  63.  
  64. /*
  65.  * HASH FUNCTIONS
  66.  *
  67.  * Assume that we've already split the bucket to which this key hashes,
  68.  * calculate that bucket, and check that in fact we did already split it.
  69.  *
  70.  * This came from ejb's hsearch.
  71.  */
  72.  
  73. #define PRIME1        37
  74. #define PRIME2        1048583
  75.  
  76. #if 0
  77. static u_int32_t
  78. hash1(keyarg, len)
  79.     const void *keyarg;
  80.     register size_t len;
  81. {
  82.     register const u_char *key;
  83.     register u_int32_t h;
  84.  
  85.     /* Convert string to integer */
  86.     for (key = keyarg, h = 0; len--;)
  87.         h = h * PRIME1 ^ (*key++ - ' ');
  88.     h %= PRIME2;
  89.     return (h);
  90. }
  91.  
  92. /*
  93.  * Phong's linear congruential hash
  94.  */
  95. #define dcharhash(h, c)    ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  96.  
  97. static u_int32_t
  98. hash2(keyarg, len)
  99.     const void *keyarg;
  100.     size_t len;
  101. {
  102.     register const u_char *e, *key;
  103.     register u_int32_t h;
  104.     register u_char c;
  105.  
  106.     key = keyarg;
  107.     e = key + len;
  108.     for (h = 0; key != e;) {
  109.         c = *key++;
  110.         if (!c && key > e)
  111.             break;
  112.         dcharhash(h, c);
  113.     }
  114.     return (h);
  115. }
  116.  
  117. /*
  118.  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
  119.  * units.  On the first time through the loop we get the "leftover bytes"
  120.  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
  121.  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
  122.  * this routine is heavily used enough, it's worth the ugly coding.
  123.  *
  124.  * OZ's original sdbm hash
  125.  */
  126. static u_int32_t
  127. hash3(keyarg, len)
  128.     const void *keyarg;
  129.     register size_t len;
  130. {
  131.     register const u_char *key;
  132.     register size_t loop;
  133.     register u_int32_t h;
  134.  
  135. #define HASHC   h = *key++ + 65599 * h
  136.  
  137.     h = 0;
  138.     key = keyarg;
  139.     if (len > 0) {
  140.         loop = (len + 8 - 1) >> 3;
  141.  
  142.         switch (len & (8 - 1)) {
  143.         case 0:
  144.             do {
  145.                 HASHC;
  146.                 /* FALLTHROUGH */
  147.         case 7:
  148.                 HASHC;
  149.                 /* FALLTHROUGH */
  150.         case 6:
  151.                 HASHC;
  152.                 /* FALLTHROUGH */
  153.         case 5:
  154.                 HASHC;
  155.                 /* FALLTHROUGH */
  156.         case 4:
  157.                 HASHC;
  158.                 /* FALLTHROUGH */
  159.         case 3:
  160.                 HASHC;
  161.                 /* FALLTHROUGH */
  162.         case 2:
  163.                 HASHC;
  164.                 /* FALLTHROUGH */
  165.         case 1:
  166.                 HASHC;
  167.             } while (--loop);
  168.         }
  169.     }
  170.     return (h);
  171. }
  172. #endif 
  173.  
  174. /* Hash function from Chris Torek. */
  175. static u_int32_t
  176. hash4(keyarg, len)
  177.     const void *keyarg;
  178.     register size_t len;
  179. {
  180.     register const u_char *key;
  181.     register size_t loop;
  182.     register u_int32_t h;
  183.  
  184. #define HASH4a   h = (h << 5) - h + *key++;
  185. #define HASH4b   h = (h << 5) + h + *key++;
  186. #define HASH4 HASH4b
  187.  
  188.     h = 0;
  189.     key = keyarg;
  190.     if (len > 0) {
  191.         loop = (len + 8 - 1) >> 3;
  192.  
  193.         switch (len & (8 - 1)) {
  194.         case 0:
  195.             do {
  196.                 HASH4;
  197.                 /* FALLTHROUGH */
  198.         case 7:
  199.                 HASH4;
  200.                 /* FALLTHROUGH */
  201.         case 6:
  202.                 HASH4;
  203.                 /* FALLTHROUGH */
  204.         case 5:
  205.                 HASH4;
  206.                 /* FALLTHROUGH */
  207.         case 4:
  208.                 HASH4;
  209.                 /* FALLTHROUGH */
  210.         case 3:
  211.                 HASH4;
  212.                 /* FALLTHROUGH */
  213.         case 2:
  214.                 HASH4;
  215.                 /* FALLTHROUGH */
  216.         case 1:
  217.                 HASH4;
  218.             } while (--loop);
  219.         }
  220.     }
  221.     return (h);
  222. }
  223.