PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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-2025, 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 */
21typedef 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 */
29typedef 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 */
37typedef 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 */
44typedef 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 */
51typedef struct HASHELEMENT
52{
53 struct HASHELEMENT *link; /* link to next entry in same bucket */
54 uint32 hashvalue; /* hash function result for this entry */
56
57/* Hash table header struct is an opaque type known only within dynahash.c */
58typedef struct HASHHDR HASHHDR;
59
60/* Hash table control struct is an opaque type known only within dynahash.c */
61typedef struct HTAB HTAB;
62
63/* Parameter data structure for hash_create */
64/* Only those fields indicated by hash_flags need be set */
65typedef 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 */
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 */
111typedef enum
112{
117} HASHACTION;
118
119/* hash_seq status (should be considered an opaque type by callers) */
120typedef struct
121{
123 uint32 curBucket; /* index of current bucket */
124 HASHELEMENT *curEntry; /* current entry in bucket */
125 bool hasHashvalue; /* true if hashvalue was provided */
126 uint32 hashvalue; /* hashvalue to start seqscan over hash */
128
129/*
130 * prototypes for functions in dynahash.c
131 */
132extern HTAB *hash_create(const char *tabname, long nelem,
133 const HASHCTL *info, int flags);
134extern void hash_destroy(HTAB *hashp);
135extern void hash_stats(const char *where, HTAB *hashp);
136extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
137 bool *foundPtr);
138extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr);
139extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr,
140 uint32 hashvalue, HASHACTION action,
141 bool *foundPtr);
142extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry,
143 const void *newKeyPtr);
144extern long hash_get_num_entries(HTAB *hashp);
145extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
147 HTAB *hashp,
148 uint32 hashvalue);
149extern void *hash_seq_search(HASH_SEQ_STATUS *status);
150extern void hash_seq_term(HASH_SEQ_STATUS *status);
151extern void hash_freeze(HTAB *hashp);
152extern Size hash_estimate_size(long num_entries, Size entrysize);
153extern long hash_select_dirsize(long num_entries);
154extern Size hash_get_shared_size(HASHCTL *info, int flags);
155extern void AtEOXact_HashTables(bool isCommit);
156extern void AtEOSubXact_HashTables(bool isCommit, int nestDepth);
157
158#endif /* HSEARCH_H */
uint32_t uint32
Definition: c.h:502
size_t Size
Definition: c.h:576
void hash_seq_init_with_hash_value(HASH_SEQ_STATUS *status, HTAB *hashp, uint32 hashvalue)
Definition: dynahash.c:1405
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:955
struct HASHELEMENT HASHELEMENT
void *(* HashAllocFunc)(Size request)
Definition: hsearch.h:44
void AtEOXact_HashTables(bool isCommit)
Definition: dynahash.c:1912
int(* HashCompareFunc)(const void *key1, const void *key2, Size keysize)
Definition: hsearch.h:29
HASHACTION
Definition: hsearch.h:112
@ HASH_FIND
Definition: hsearch.h:113
@ HASH_REMOVE
Definition: hsearch.h:115
@ HASH_ENTER
Definition: hsearch.h:114
@ HASH_ENTER_NULL
Definition: hsearch.h:116
Size hash_get_shared_size(HASHCTL *info, int flags)
Definition: dynahash.c:854
void AtEOSubXact_HashTables(bool isCommit, int nestDepth)
Definition: dynahash.c:1938
void hash_destroy(HTAB *hashp)
Definition: dynahash.c:865
void * hash_search_with_hash_value(HTAB *hashp, const void *keyPtr, uint32 hashvalue, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:968
void * hash_seq_search(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1420
uint32(* HashValueFunc)(const void *key, Size keysize)
Definition: hsearch.h:21
void hash_seq_term(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1514
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1341
long hash_select_dirsize(long num_entries)
Definition: dynahash.c:830
Size hash_estimate_size(long num_entries, Size entrysize)
Definition: dynahash.c:783
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
Definition: dynahash.c:352
void hash_stats(const char *where, HTAB *hashp)
Definition: dynahash.c:884
void hash_freeze(HTAB *hashp)
Definition: dynahash.c:1534
bool hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr)
Definition: dynahash.c:1145
uint32 get_hash_value(HTAB *hashp, const void *keyPtr)
Definition: dynahash.c:911
void *(* HashCopyFunc)(void *dest, const void *src, Size keysize)
Definition: hsearch.h:37
struct HASHCTL HASHCTL
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
Definition: dynahash.c:1385
long ssize
Definition: hsearch.h:70
HashAllocFunc alloc
Definition: hsearch.h:84
Size keysize
Definition: hsearch.h:75
HashValueFunc hash
Definition: hsearch.h:78
Size entrysize
Definition: hsearch.h:76
long dsize
Definition: hsearch.h:72
HashCompareFunc match
Definition: hsearch.h:80
HASHHDR * hctl
Definition: hsearch.h:88
MemoryContext hcxt
Definition: hsearch.h:86
long num_partitions
Definition: hsearch.h:68
HashCopyFunc keycopy
Definition: hsearch.h:82
long max_dsize
Definition: hsearch.h:73
struct HASHELEMENT * link
Definition: hsearch.h:53
uint32 hashvalue
Definition: hsearch.h:54
uint32 hashvalue
Definition: hsearch.h:126
HASHELEMENT * curEntry
Definition: hsearch.h:124
uint32 curBucket
Definition: hsearch.h:123
HTAB * hashp
Definition: hsearch.h:122
bool hasHashvalue
Definition: hsearch.h:125
Definition: dynahash.c:220