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 { 113 HASH_FIND, 114 HASH_ENTER, 115 HASH_REMOVE, 116 HASH_ENTER_NULL 117 } HASHACTION; 118 119 /* hash_seq status (should be considered an opaque type by callers) */ 120 typedef struct 121 { 122 HTAB *hashp; 123 uint32 curBucket; /* index of current bucket */ 124 HASHELEMENT *curEntry; /* current entry in bucket */ 125 } HASH_SEQ_STATUS; 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, 138 uint32 hashvalue, HASHACTION action, 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 */ 154