1/*-------------------------------------------------------------------------
2 *
3 * hsearch.h
4 * exported definitions for utils/hash/dynahash.c; see notes therein
5 *
6 *
7 * Portions Copyright (c) 1996-2019, 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 */
55} HASHELEMENT;
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 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 */
103typedef enum
104{
105 HASH_FIND,
106 HASH_ENTER,
107 HASH_REMOVE,
108 HASH_ENTER_NULL
109} HASHACTION;
110
111/* hash_seq status (should be considered an opaque type by callers) */
112typedef struct
113{
114 HTAB *hashp;
115 uint32 curBucket; /* index of current bucket */
116 HASHELEMENT *curEntry; /* current entry in bucket */
117} HASH_SEQ_STATUS;
118
119/*
120 * prototypes for functions in dynahash.c
121 */
122extern HTAB *hash_create(const char *tabname, long nelem,
123 HASHCTL *info, int flags);
124extern void hash_destroy(HTAB *hashp);
125extern void hash_stats(const char *where, HTAB *hashp);
126extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
127 bool *foundPtr);
128extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr);
129extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr,
130 uint32 hashvalue, HASHACTION action,
131 bool *foundPtr);
132extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry,
133 const void *newKeyPtr);
134extern long hash_get_num_entries(HTAB *hashp);
135extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
136extern void *hash_seq_search(HASH_SEQ_STATUS *status);
137extern void hash_seq_term(HASH_SEQ_STATUS *status);
138extern void hash_freeze(HTAB *hashp);
139extern Size hash_estimate_size(long num_entries, Size entrysize);
140extern long hash_select_dirsize(long num_entries);
141extern Size hash_get_shared_size(HASHCTL *info, int flags);
142extern void AtEOXact_HashTables(bool isCommit);
143extern 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 */
152extern uint32 string_hash(const void *key, Size keysize);
153extern uint32 tag_hash(const void *key, Size keysize);
154extern uint32 uint32_hash(const void *key, Size keysize);
155extern uint32 bitmap_hash(const void *key, Size keysize);
156extern 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 */
161