PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hsearch.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * hsearch.h
4  * exported definitions for utils/hash/dynahash.c; see notes therein
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  * src/include/utils/hsearch.h
11  *
12  *-------------------------------------------------------------------------
13  */
14 #ifndef HSEARCH_H
15 #define HSEARCH_H
16 
17 
18 /*
19  * Hash functions must have this signature.
20  */
21 typedef uint32 (*HashValueFunc) (const void *key, Size keysize);
22 
23 /*
24  * Key comparison functions must have this signature. Comparison functions
25  * return zero for match, nonzero for no match. (The comparison function
26  * definition is designed to allow memcmp() and strncmp() to be used directly
27  * as key comparison functions.)
28  */
29 typedef int (*HashCompareFunc) (const void *key1, const void *key2,
30  Size keysize);
31 
32 /*
33  * Key copying functions must have this signature. The return value is not
34  * used. (The definition is set up to allow memcpy() and strlcpy() to be
35  * used directly.)
36  */
37 typedef void *(*HashCopyFunc) (void *dest, const void *src, Size keysize);
38 
39 /*
40  * Space allocation function for a hashtable --- designed to match malloc().
41  * Note: there is no free function API; can't destroy a hashtable unless you
42  * use the default allocator.
43  */
44 typedef void *(*HashAllocFunc) (Size request);
45 
46 /*
47  * HASHELEMENT is the private part of a hashtable entry. The caller's data
48  * follows the HASHELEMENT structure (on a MAXALIGN'd boundary). The hash key
49  * is expected to be at the start of the caller's hash entry data structure.
50  */
51 typedef struct HASHELEMENT
52 {
53  struct HASHELEMENT *link; /* link to next entry in same bucket */
54  uint32 hashvalue; /* hash function result for this entry */
55 } HASHELEMENT;
56 
57 /* Hash table header struct is an opaque type known only within dynahash.c */
58 typedef struct HASHHDR HASHHDR;
59 
60 /* Hash table control struct is an opaque type known only within dynahash.c */
61 typedef struct HTAB HTAB;
62 
63 /* Parameter data structure for hash_create */
64 /* Only those fields indicated by hash_flags need be set */
65 typedef struct HASHCTL
66 {
67  long num_partitions; /* # partitions (must be power of 2) */
68  long ssize; /* segment size */
69  long dsize; /* (initial) directory size */
70  long max_dsize; /* limit to dsize if dir size is limited */
71  long ffactor; /* fill factor */
72  Size keysize; /* hash key length in bytes */
73  Size entrysize; /* total user element size in bytes */
74  HashValueFunc hash; /* hash function */
75  HashCompareFunc match; /* key comparison function */
76  HashCopyFunc keycopy; /* key copying function */
77  HashAllocFunc alloc; /* memory allocator */
78  MemoryContext hcxt; /* memory context to use for allocations */
79  HASHHDR *hctl; /* location of header in shared mem */
80 } HASHCTL;
81 
82 /* Flags to indicate which parameters are supplied */
83 #define HASH_PARTITION 0x0001 /* Hashtable is used w/partitioned locking */
84 #define HASH_SEGMENT 0x0002 /* Set segment size */
85 #define HASH_DIRSIZE 0x0004 /* Set directory size (initial and max) */
86 #define HASH_FFACTOR 0x0008 /* Set fill factor */
87 #define HASH_ELEM 0x0010 /* Set keysize and entrysize */
88 #define HASH_BLOBS 0x0020 /* Select support functions for binary keys */
89 #define HASH_FUNCTION 0x0040 /* Set user defined hash function */
90 #define HASH_COMPARE 0x0080 /* Set user defined comparison function */
91 #define HASH_KEYCOPY 0x0100 /* Set user defined key-copying function */
92 #define HASH_ALLOC 0x0200 /* Set memory allocator */
93 #define HASH_CONTEXT 0x0400 /* Set memory allocation context */
94 #define HASH_SHARED_MEM 0x0800 /* Hashtable is in shared memory */
95 #define HASH_ATTACH 0x1000 /* Do not initialize hctl */
96 #define HASH_FIXED_SIZE 0x2000 /* Initial size is a hard limit */
97 
98 
99 /* max_dsize value to indicate expansible directory */
100 #define NO_MAX_DSIZE (-1)
101 
102 /* hash_search operations */
103 typedef enum
104 {
109 } HASHACTION;
110 
111 /* hash_seq status (should be considered an opaque type by callers) */
112 typedef struct
113 {
115  uint32 curBucket; /* index of current bucket */
116  HASHELEMENT *curEntry; /* current entry in bucket */
118 
119 /*
120  * prototypes for functions in dynahash.c
121  */
122 extern HTAB *hash_create(const char *tabname, long nelem,
123  HASHCTL *info, int flags);
124 extern void hash_destroy(HTAB *hashp);
125 extern void hash_stats(const char *where, HTAB *hashp);
126 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
127  bool *foundPtr);
128 extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr);
129 extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr,
130  uint32 hashvalue, HASHACTION action,
131  bool *foundPtr);
132 extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry,
133  const void *newKeyPtr);
134 extern long hash_get_num_entries(HTAB *hashp);
135 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
136 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
137 extern void hash_seq_term(HASH_SEQ_STATUS *status);
138 extern void hash_freeze(HTAB *hashp);
139 extern Size hash_estimate_size(long num_entries, Size entrysize);
140 extern long hash_select_dirsize(long num_entries);
141 extern Size hash_get_shared_size(HASHCTL *info, int flags);
142 extern void AtEOXact_HashTables(bool isCommit);
143 extern void AtEOSubXact_HashTables(bool isCommit, int nestDepth);
144 
145 /*
146  * prototypes for functions in hashfn.c
147  *
148  * Note: It is deprecated for callers of hash_create to explicitly specify
149  * string_hash, tag_hash, uint32_hash, or oid_hash. Just set HASH_BLOBS or
150  * not. Use HASH_FUNCTION only when you want something other than those.
151  */
152 extern uint32 string_hash(const void *key, Size keysize);
153 extern uint32 tag_hash(const void *key, Size keysize);
154 extern uint32 uint32_hash(const void *key, Size keysize);
155 extern uint32 bitmap_hash(const void *key, Size keysize);
156 extern int bitmap_match(const void *key1, const void *key2, Size keysize);
157 
158 #define oid_hash uint32_hash /* Remove me eventually */
159 
160 #endif /* HSEARCH_H */
struct HASHCTL HASHCTL
long hash_select_dirsize(long num_entries)
Definition: dynahash.c:775
uint32 curBucket
Definition: hsearch.h:115
struct HASHELEMENT HASHELEMENT
MemoryContext hcxt
Definition: hsearch.h:78
long ssize
Definition: hsearch.h:68
HashCopyFunc keycopy
Definition: hsearch.h:76
void hash_stats(const char *where, HTAB *hashp)
Definition: dynahash.c:829
uint32 string_hash(const void *key, Size keysize)
Definition: hashfn.c:34
void *(* HashAllocFunc)(Size request)
Definition: hsearch.h:44
void hash_freeze(HTAB *hashp)
Definition: dynahash.c:1481
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:915
Size entrysize
Definition: hsearch.h:73
HASHELEMENT * curEntry
Definition: hsearch.h:116
uint32(* HashValueFunc)(const void *key, Size keysize)
Definition: hsearch.h:21
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:52
uint32 bitmap_hash(const void *key, Size keysize)
Definition: hashfn.c:76
long dsize
Definition: hsearch.h:69
Size hash_get_shared_size(HASHCTL *info, int flags)
Definition: dynahash.c:799
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:316
Definition: dynahash.c:208
long max_dsize
Definition: hsearch.h:70
long num_partitions
Definition: hsearch.h:67
HashAllocFunc alloc
Definition: hsearch.h:77
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: hashfn.c:86
unsigned int uint32
Definition: c.h:268
HTAB * hashp
Definition: hsearch.h:114
uint32 uint32_hash(const void *key, Size keysize)
Definition: hashfn.c:64
uint32 get_hash_value(HTAB *hashp, const void *keyPtr)
Definition: dynahash.c:856
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
Definition: dynahash.c:1375
void hash_seq_term(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1461
Size hash_estimate_size(long num_entries, Size entrysize)
Definition: dynahash.c:728
void AtEOXact_HashTables(bool isCommit)
Definition: dynahash.c:1830
Size keysize
Definition: hsearch.h:72
HashCompareFunc match
Definition: hsearch.h:75
size_t Size
Definition: c.h:356
HASHHDR * hctl
Definition: hsearch.h:79
long ffactor
Definition: hsearch.h:71
bool hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr)
Definition: dynahash.c:1111
int(* HashCompareFunc)(const void *key1, const void *key2, Size keysize)
Definition: hsearch.h:29
struct HASHELEMENT * link
Definition: hsearch.h:53
void AtEOSubXact_HashTables(bool isCommit, int nestDepth)
Definition: dynahash.c:1856
void * hash_seq_search(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1385
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:902
void hash_destroy(HTAB *hashp)
Definition: dynahash.c:810
static void static void status(const char *fmt,...) pg_attribute_printf(1
Definition: pg_regress.c:224
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
Definition: hsearch.h:37
uint32 hashvalue
Definition: hsearch.h:54
HASHACTION
Definition: hsearch.h:103
HashValueFunc hash
Definition: hsearch.h:74
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1331