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 {
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) */
112 typedef 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  */
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 */
161