1 /*-------------------------------------------------------------------------
2 *
3 * hashfn.c
4 * Hash functions for use in dynahash.c hashtables
5 *
6 *
7 * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 *
11 * IDENTIFICATION
12 * src/backend/utils/hash/hashfn.c
13 *
14 * NOTES
15 * It is expected that every bit of a hash function's 32-bit result is
16 * as random as every other; failure to ensure this is likely to lead
17 * to poor performance of hash tables. In most cases a hash
18 * function should use hash_any() or its variant hash_uint32().
19 *
20 *-------------------------------------------------------------------------
21 */
22 #include "postgres.h"
23
24 #include "access/hash.h"
25 #include "utils/hsearch.h"
26
27
28 /*
29 * string_hash: hash function for keys that are NUL-terminated strings.
30 *
31 * NOTE: this is the default hash function if none is specified.
32 */
33 uint32
string_hash(const void * key,Size keysize)34 string_hash(const void *key, Size keysize)
35 {
36 /*
37 * If the string exceeds keysize-1 bytes, we want to hash only that many,
38 * because when it is copied into the hash table it will be truncated at
39 * that length.
40 */
41 Size s_len = strlen((const char *) key);
42
43 s_len = Min(s_len, keysize - 1);
44 return DatumGetUInt32(hash_any((const unsigned char *) key,
45 (int) s_len));
46 }
47
48 /*
49 * tag_hash: hash function for fixed-size tag values
50 */
51 uint32
tag_hash(const void * key,Size keysize)52 tag_hash(const void *key, Size keysize)
53 {
54 return DatumGetUInt32(hash_any((const unsigned char *) key,
55 (int) keysize));
56 }
57
58 /*
59 * uint32_hash: hash function for keys that are uint32 or int32
60 *
61 * (tag_hash works for this case too, but is slower)
62 */
63 uint32
uint32_hash(const void * key,Size keysize)64 uint32_hash(const void *key, Size keysize)
65 {
66 Assert(keysize == sizeof(uint32));
67 return DatumGetUInt32(hash_uint32(*((const uint32 *) key)));
68 }
69
70 /*
71 * bitmap_hash: hash function for keys that are (pointers to) Bitmapsets
72 *
73 * Note: don't forget to specify bitmap_match as the match function!
74 */
75 uint32
bitmap_hash(const void * key,Size keysize)76 bitmap_hash(const void *key, Size keysize)
77 {
78 Assert(keysize == sizeof(Bitmapset *));
79 return bms_hash_value(*((const Bitmapset *const *) key));
80 }
81
82 /*
83 * bitmap_match: match function to use with bitmap_hash
84 */
85 int
bitmap_match(const void * key1,const void * key2,Size keysize)86 bitmap_match(const void *key1, const void *key2, Size keysize)
87 {
88 Assert(keysize == sizeof(Bitmapset *));
89 return !bms_equal(*((const Bitmapset *const *) key1),
90 *((const Bitmapset *const *) key2));
91 }
92