PostgreSQL Source Code  git master
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-2020, 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  Size keysize; /* hash key length in bytes */
72  Size entrysize; /* total user element size in bytes */
73  HashValueFunc hash; /* hash function */
74  HashCompareFunc match; /* key comparison function */
75  HashCopyFunc keycopy; /* key copying function */
76  HashAllocFunc alloc; /* memory allocator */
77  MemoryContext hcxt; /* memory context to use for allocations */
78  HASHHDR *hctl; /* location of header in shared mem */
79 } HASHCTL;
80 
81 /* Flags to indicate which parameters are supplied */
82 #define HASH_PARTITION 0x0001 /* Hashtable is used w/partitioned locking */
83 #define HASH_SEGMENT 0x0002 /* Set segment size */
84 #define HASH_DIRSIZE 0x0004 /* Set directory size (initial and max) */
85 #define HASH_ELEM 0x0010 /* Set keysize and entrysize */
86 #define HASH_BLOBS 0x0020 /* Select support functions for binary keys */
87 #define HASH_FUNCTION 0x0040 /* Set user defined hash function */
88 #define HASH_COMPARE 0x0080 /* Set user defined comparison function */
89 #define HASH_KEYCOPY 0x0100 /* Set user defined key-copying function */
90 #define HASH_ALLOC 0x0200 /* Set memory allocator */
91 #define HASH_CONTEXT 0x0400 /* Set memory allocation context */
92 #define HASH_SHARED_MEM 0x0800 /* Hashtable is in shared memory */
93 #define HASH_ATTACH 0x1000 /* Do not initialize hctl */
94 #define HASH_FIXED_SIZE 0x2000 /* Initial size is a hard limit */
95 
96 
97 /* max_dsize value to indicate expansible directory */
98 #define NO_MAX_DSIZE (-1)
99 
100 /* hash_search operations */
101 typedef enum
102 {
107 } HASHACTION;
108 
109 /* hash_seq status (should be considered an opaque type by callers) */
110 typedef struct
111 {
113  uint32 curBucket; /* index of current bucket */
114  HASHELEMENT *curEntry; /* current entry in bucket */
116 
117 /*
118  * prototypes for functions in dynahash.c
119  *
120  * Note: It is deprecated for callers of hash_create to explicitly specify
121  * string_hash, tag_hash, uint32_hash, or oid_hash. Just set HASH_BLOBS or
122  * not. Use HASH_FUNCTION only when you want something other than those.
123  */
124 extern HTAB *hash_create(const char *tabname, long nelem,
125  HASHCTL *info, int flags);
126 extern void hash_destroy(HTAB *hashp);
127 extern void hash_stats(const char *where, HTAB *hashp);
128 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
129  bool *foundPtr);
130 extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr);
131 extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr,
133  bool *foundPtr);
134 extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry,
135  const void *newKeyPtr);
136 extern long hash_get_num_entries(HTAB *hashp);
137 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
138 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
139 extern void hash_seq_term(HASH_SEQ_STATUS *status);
140 extern void hash_freeze(HTAB *hashp);
141 extern Size hash_estimate_size(long num_entries, Size entrysize);
142 extern long hash_select_dirsize(long num_entries);
143 extern Size hash_get_shared_size(HASHCTL *info, int flags);
144 extern void AtEOXact_HashTables(bool isCommit);
145 extern void AtEOSubXact_HashTables(bool isCommit, int nestDepth);
146 
147 #endif /* HSEARCH_H */
int(* HashCompareFunc)(const void *key1, const void *key2, Size keysize)
Definition: hsearch.h:29
struct HASHCTL HASHCTL
long hash_select_dirsize(long num_entries)
Definition: dynahash.c:792
uint32(* HashValueFunc)(const void *key, Size keysize)
Definition: hsearch.h:21
uint32 curBucket
Definition: hsearch.h:113
struct HASHELEMENT HASHELEMENT
MemoryContext hcxt
Definition: hsearch.h:77
long ssize
Definition: hsearch.h:68
HashCopyFunc keycopy
Definition: hsearch.h:75
void hash_stats(const char *where, HTAB *hashp)
Definition: dynahash.c:846
void hash_freeze(HTAB *hashp)
Definition: dynahash.c:1497
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:932
Size entrysize
Definition: hsearch.h:72
HASHELEMENT * curEntry
Definition: hsearch.h:114
long dsize
Definition: hsearch.h:69
Size hash_get_shared_size(HASHCTL *info, int flags)
Definition: dynahash.c:816
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:326
Definition: dynahash.c:218
long max_dsize
Definition: hsearch.h:70
long num_partitions
Definition: hsearch.h:67
HashAllocFunc alloc
Definition: hsearch.h:76
unsigned int uint32
Definition: c.h:375
HTAB * hashp
Definition: hsearch.h:112
uint32 get_hash_value(HTAB *hashp, const void *keyPtr)
Definition: dynahash.c:873
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
Definition: dynahash.c:1391
void hash_seq_term(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1477
Size hash_estimate_size(long num_entries, Size entrysize)
Definition: dynahash.c:745
void AtEOXact_HashTables(bool isCommit)
Definition: dynahash.c:1848
Size keysize
Definition: hsearch.h:71
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
Definition: hsearch.h:37
HashCompareFunc match
Definition: hsearch.h:74
void *(* HashAllocFunc)(Size request)
Definition: hsearch.h:44
size_t Size
Definition: c.h:474
HASHHDR * hctl
Definition: hsearch.h:78
bool hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr)
Definition: dynahash.c:1127
struct HASHELEMENT * link
Definition: hsearch.h:53
void AtEOSubXact_HashTables(bool isCommit, int nestDepth)
Definition: dynahash.c:1874
void * hash_seq_search(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1401
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:919
void hash_destroy(HTAB *hashp)
Definition: dynahash.c:827
static void static void status(const char *fmt,...) pg_attribute_printf(1
Definition: pg_regress.c:227
uint32 hashvalue
Definition: hsearch.h:54
HASHACTION
Definition: hsearch.h:101
HashValueFunc hash
Definition: hsearch.h:73
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1347