src/include/utils/hsearch.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * hsearch.h
   4  *        exported definitions for utils/hash/dynahash.c; see notes therein
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2023, 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 */