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