hash_func.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:5k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996-2002
  5.  * Sleepycat Software.  All rights reserved.
  6.  */
  7. /*
  8.  * Copyright (c) 1990, 1993
  9.  * Margo Seltzer.  All rights reserved.
  10.  */
  11. /*
  12.  * Copyright (c) 1990, 1993
  13.  * The Regents of the University of California.  All rights reserved.
  14.  *
  15.  * This code is derived from software contributed to Berkeley by
  16.  * Margo Seltzer.
  17.  *
  18.  * Redistribution and use in source and binary forms, with or without
  19.  * modification, are permitted provided that the following conditions
  20.  * are met:
  21.  * 1. Redistributions of source code must retain the above copyright
  22.  *    notice, this list of conditions and the following disclaimer.
  23.  * 2. Redistributions in binary form must reproduce the above copyright
  24.  *    notice, this list of conditions and the following disclaimer in the
  25.  *    documentation and/or other materials provided with the distribution.
  26.  * 3. Neither the name of the University nor the names of its contributors
  27.  *    may be used to endorse or promote products derived from this software
  28.  *    without specific prior written permission.
  29.  *
  30.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  31.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  32.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  34.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  35.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  36.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  38.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  39.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  40.  * SUCH DAMAGE.
  41.  */
  42. #include "db_config.h"
  43. #ifndef lint
  44. static const char revid[] = "$Id: hash_func.c,v 11.12 2002/03/28 19:49:42 bostic Exp $";
  45. #endif /* not lint */
  46. #ifndef NO_SYSTEM_INCLUDES
  47. #include <sys/types.h>
  48. #endif
  49. #include "db_int.h"
  50. /*
  51.  * __ham_func2 --
  52.  * Phong Vo's linear congruential hash.
  53.  *
  54.  * PUBLIC: u_int32_t __ham_func2 __P((DB *, const void *, u_int32_t));
  55.  */
  56. #define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  57. u_int32_t
  58. __ham_func2(dbp, key, len)
  59. DB *dbp;
  60. const void *key;
  61. u_int32_t len;
  62. {
  63. const u_int8_t *e, *k;
  64. u_int32_t h;
  65. u_int8_t c;
  66. if (dbp != NULL)
  67. COMPQUIET(dbp, NULL);
  68. k = key;
  69. e = k + len;
  70. for (h = 0; k != e;) {
  71. c = *k++;
  72. if (!c && k > e)
  73. break;
  74. DCHARHASH(h, c);
  75. }
  76. return (h);
  77. }
  78. /*
  79.  * __ham_func3 --
  80.  * Ozan Yigit's original sdbm hash.
  81.  *
  82.  * Ugly, but fast.  Break the string up into 8 byte units.  On the first time
  83.  * through the loop get the "leftover bytes" (strlen % 8).  On every other
  84.  * iteration, perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
  85.  * saves us 7 cmp & branch instructions.
  86.  *
  87.  * PUBLIC: u_int32_t __ham_func3 __P((DB *, const void *, u_int32_t));
  88.  */
  89. u_int32_t
  90. __ham_func3(dbp, key, len)
  91. DB *dbp;
  92. const void *key;
  93. u_int32_t len;
  94. {
  95. const u_int8_t *k;
  96. u_int32_t n, loop;
  97. if (dbp != NULL)
  98. COMPQUIET(dbp, NULL);
  99. if (len == 0)
  100. return (0);
  101. #define HASHC n = *k++ + 65599 * n
  102. n = 0;
  103. k = key;
  104. loop = (len + 8 - 1) >> 3;
  105. switch (len & (8 - 1)) {
  106. case 0:
  107. do {
  108. HASHC;
  109. case 7:
  110. HASHC;
  111. case 6:
  112. HASHC;
  113. case 5:
  114. HASHC;
  115. case 4:
  116. HASHC;
  117. case 3:
  118. HASHC;
  119. case 2:
  120. HASHC;
  121. case 1:
  122. HASHC;
  123. } while (--loop);
  124. }
  125. return (n);
  126. }
  127. /*
  128.  * __ham_func4 --
  129.  * Chris Torek's hash function.  Although this function performs only
  130.  * slightly worse than __ham_func5 on strings, it performs horribly on
  131.  * numbers.
  132.  *
  133.  * PUBLIC: u_int32_t __ham_func4 __P((DB *, const void *, u_int32_t));
  134.  */
  135. u_int32_t
  136. __ham_func4(dbp, key, len)
  137. DB *dbp;
  138. const void *key;
  139. u_int32_t len;
  140. {
  141. const u_int8_t *k;
  142. u_int32_t h, loop;
  143. if (dbp != NULL)
  144. COMPQUIET(dbp, NULL);
  145. if (len == 0)
  146. return (0);
  147. #define HASH4a h = (h << 5) - h + *k++;
  148. #define HASH4b h = (h << 5) + h + *k++;
  149. #define HASH4 HASH4b
  150. h = 0;
  151. k = key;
  152. loop = (len + 8 - 1) >> 3;
  153. switch (len & (8 - 1)) {
  154. case 0:
  155. do {
  156. HASH4;
  157. case 7:
  158. HASH4;
  159. case 6:
  160. HASH4;
  161. case 5:
  162. HASH4;
  163. case 4:
  164. HASH4;
  165. case 3:
  166. HASH4;
  167. case 2:
  168. HASH4;
  169. case 1:
  170. HASH4;
  171. } while (--loop);
  172. }
  173. return (h);
  174. }
  175. /*
  176.  * Fowler/Noll/Vo hash
  177.  *
  178.  * The basis of the hash algorithm was taken from an idea sent by email to the
  179.  * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
  180.  * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
  181.  * later improved on their algorithm.
  182.  *
  183.  * The magic is in the interesting relationship between the special prime
  184.  * 16777619 (2^24 + 403) and 2^32 and 2^8.
  185.  *
  186.  * This hash produces the fewest collisions of any function that we've seen so
  187.  * far, and works well on both numbers and strings.
  188.  *
  189.  * PUBLIC: u_int32_t __ham_func5 __P((DB *, const void *, u_int32_t));
  190.  */
  191. u_int32_t
  192. __ham_func5(dbp, key, len)
  193. DB *dbp;
  194. const void *key;
  195. u_int32_t len;
  196. {
  197. const u_int8_t *k, *e;
  198. u_int32_t h;
  199. if (dbp != NULL)
  200. COMPQUIET(dbp, NULL);
  201. k = key;
  202. e = k + len;
  203. for (h = 0; k < e; ++k) {
  204. h *= 16777619;
  205. h ^= *k;
  206. }
  207. return (h);
  208. }
  209. /*
  210.  * __ham_test --
  211.  *
  212.  * PUBLIC: u_int32_t __ham_test __P((DB *, const void *, u_int32_t));
  213.  */
  214. u_int32_t
  215. __ham_test(dbp, key, len)
  216. DB *dbp;
  217. const void *key;
  218. u_int32_t len;
  219. {
  220. COMPQUIET(dbp, NULL);
  221. COMPQUIET(len, 0);
  222. return ((u_int32_t)*(char *)key);
  223. }