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-2021, 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  /* Used if HASH_PARTITION flag is set: */
68  long num_partitions; /* # partitions (must be power of 2) */
69  /* Used if HASH_SEGMENT flag is set: */
70  long ssize; /* segment size */
71  /* Used if HASH_DIRSIZE flag is set: */
72  long dsize; /* (initial) directory size */
73  long max_dsize; /* limit to dsize if dir size is limited */
74  /* Used if HASH_ELEM flag is set (which is now required): */
75  Size keysize; /* hash key length in bytes */
76  Size entrysize; /* total user element size in bytes */
77  /* Used if HASH_FUNCTION flag is set: */
78  HashValueFunc hash; /* hash function */
79  /* Used if HASH_COMPARE flag is set: */
80  HashCompareFunc match; /* key comparison function */
81  /* Used if HASH_KEYCOPY flag is set: */
82  HashCopyFunc keycopy; /* key copying function */
83  /* Used if HASH_ALLOC flag is set: */
84  HashAllocFunc alloc; /* memory allocator */
85  /* Used if HASH_CONTEXT flag is set: */
86  MemoryContext hcxt; /* memory context to use for allocations */
87  /* Used if HASH_SHARED_MEM flag is set: */
88  HASHHDR *hctl; /* location of header in shared mem */
89 } HASHCTL;
90 
91 /* Flag bits for hash_create; most indicate which parameters are supplied */
92 #define HASH_PARTITION 0x0001 /* Hashtable is used w/partitioned locking */
93 #define HASH_SEGMENT 0x0002 /* Set segment size */
94 #define HASH_DIRSIZE 0x0004 /* Set directory size (initial and max) */
95 #define HASH_ELEM 0x0008 /* Set keysize and entrysize (now required!) */
96 #define HASH_STRINGS 0x0010 /* Select support functions for string keys */
97 #define HASH_BLOBS 0x0020 /* Select support functions for binary keys */
98 #define HASH_FUNCTION 0x0040 /* Set user defined hash function */
99 #define HASH_COMPARE 0x0080 /* Set user defined comparison function */
100 #define HASH_KEYCOPY 0x0100 /* Set user defined key-copying function */
101 #define HASH_ALLOC 0x0200 /* Set memory allocator */
102 #define HASH_CONTEXT 0x0400 /* Set memory allocation context */
103 #define HASH_SHARED_MEM 0x0800 /* Hashtable is in shared memory */
104 #define HASH_ATTACH 0x1000 /* Do not initialize hctl */
105 #define HASH_FIXED_SIZE 0x2000 /* Initial size is a hard limit */
106 
107 /* max_dsize value to indicate expansible directory */
108 #define NO_MAX_DSIZE (-1)
109 
110 /* hash_search operations */
111 typedef enum
112 {
117 } HASHACTION;
118 
119 /* hash_seq status (should be considered an opaque type by callers) */
120 typedef struct
121 {
123  uint32 curBucket; /* index of current bucket */
124  HASHELEMENT *curEntry; /* current entry in bucket */
126 
127 /*
128  * prototypes for functions in dynahash.c
129  */
130 extern HTAB *hash_create(const char *tabname, long nelem,
131  const HASHCTL *info, int flags);
132 extern void hash_destroy(HTAB *hashp);
133 extern void hash_stats(const char *where, HTAB *hashp);
134 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
135  bool *foundPtr);
136 extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr);
137 extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr,
139  bool *foundPtr);
140 extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry,
141  const void *newKeyPtr);
142 extern long hash_get_num_entries(HTAB *hashp);
143 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
144 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
145 extern void hash_seq_term(HASH_SEQ_STATUS *status);
146 extern void hash_freeze(HTAB *hashp);
147 extern Size hash_estimate_size(long num_entries, Size entrysize);
148 extern long hash_select_dirsize(long num_entries);
149 extern Size hash_get_shared_size(HASHCTL *info, int flags);
150 extern void AtEOXact_HashTables(bool isCommit);
151 extern void AtEOSubXact_HashTables(bool isCommit, int nestDepth);
152 
153 #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:827
uint32(* HashValueFunc)(const void *key, Size keysize)
Definition: hsearch.h:21
uint32 curBucket
Definition: hsearch.h:123
struct HASHELEMENT HASHELEMENT
MemoryContext hcxt
Definition: hsearch.h:86
long ssize
Definition: hsearch.h:70
HashCopyFunc keycopy
Definition: hsearch.h:82
void hash_stats(const char *where, HTAB *hashp)
Definition: dynahash.c:881
void hash_freeze(HTAB *hashp)
Definition: dynahash.c:1532
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:967
Size entrysize
Definition: hsearch.h:76
HASHELEMENT * curEntry
Definition: hsearch.h:124
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
Definition: dynahash.c:349
long dsize
Definition: hsearch.h:72
Size hash_get_shared_size(HASHCTL *info, int flags)
Definition: dynahash.c:851
Definition: dynahash.c:219
long max_dsize
Definition: hsearch.h:73
long num_partitions
Definition: hsearch.h:68
HashAllocFunc alloc
Definition: hsearch.h:84
unsigned int uint32
Definition: c.h:441
HTAB * hashp
Definition: hsearch.h:122
uint32 get_hash_value(HTAB *hashp, const void *keyPtr)
Definition: dynahash.c:908
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
Definition: dynahash.c:1426
void hash_seq_term(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1512
Size hash_estimate_size(long num_entries, Size entrysize)
Definition: dynahash.c:780
void AtEOXact_HashTables(bool isCommit)
Definition: dynahash.c:1883
Size keysize
Definition: hsearch.h:75
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
Definition: hsearch.h:37
HashCompareFunc match
Definition: hsearch.h:80
void *(* HashAllocFunc)(Size request)
Definition: hsearch.h:44
size_t Size
Definition: c.h:540
HASHHDR * hctl
Definition: hsearch.h:88
bool hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr)
Definition: dynahash.c:1162
struct HASHELEMENT * link
Definition: hsearch.h:53
void AtEOSubXact_HashTables(bool isCommit, int nestDepth)
Definition: dynahash.c:1909
void * hash_seq_search(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1436
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:954
void hash_destroy(HTAB *hashp)
Definition: dynahash.c:862
static void static void status(const char *fmt,...) pg_attribute_printf(1
Definition: pg_regress.c:229
uint32 hashvalue
Definition: hsearch.h:54
HASHACTION
Definition: hsearch.h:111
HashValueFunc hash
Definition: hsearch.h:78
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1382