PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hashfn.c
Go to the documentation of this file.
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
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
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
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
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
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 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
uint32 string_hash(const void *key, Size keysize)
Definition: hashfn.c:34
#define Min(x, y)
Definition: c.h:806
uint32 uint32_hash(const void *key, Size keysize)
Definition: hashfn.c:64
uint32 bitmap_hash(const void *key, Size keysize)
Definition: hashfn.c:76
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:954
unsigned int uint32
Definition: c.h:268
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: hashfn.c:86
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:52
#define Assert(condition)
Definition: c.h:675
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
size_t Size
Definition: c.h:356
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130