granicus.if.org Git - postgresql/blob - 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-2014, 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 strncpy() 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  0x001   /* Hashtable is used w/partitioned locking */
  84 #define HASH_SEGMENT    0x002   /* Set segment size */
  85 #define HASH_DIRSIZE    0x004   /* Set directory size (initial and max) */
  86 #define HASH_FFACTOR    0x008   /* Set fill factor */
  87 #define HASH_FUNCTION   0x010   /* Set user defined hash function */
  88 #define HASH_ELEM               0x020   /* Set keysize and entrysize */
  89 #define HASH_SHARED_MEM 0x040   /* Hashtable is in shared memory */
  90 #define HASH_ATTACH             0x080   /* Do not initialize hctl */
  91 #define HASH_ALLOC              0x100   /* Set memory allocator */
  92 #define HASH_CONTEXT    0x200   /* Set memory allocation context */
  93 #define HASH_COMPARE    0x400   /* Set user defined comparison function */
  94 #define HASH_KEYCOPY    0x800   /* Set user defined key-copying function */
  95 #define HASH_FIXED_SIZE 0x1000  /* Initial size is a hard limit */
  96
  97
  98 /* max_dsize value to indicate expansible directory */
  99 #define NO_MAX_DSIZE                    (-1)
 100
 101 /* hash_search operations */
 102 typedef enum
 103 {
 104         HASH_FIND,
 105         HASH_ENTER,
 106         HASH_REMOVE,
 107         HASH_ENTER_NULL
 108 } HASHACTION;
 109
 110 /* hash_seq status (should be considered an opaque type by callers) */
 111 typedef struct
 112 {
 113         HTAB       *hashp;
 114         uint32          curBucket;              /* index of current bucket */
 115         HASHELEMENT *curEntry;          /* current entry in bucket */
 116 } HASH_SEQ_STATUS;
 117
 118 /*
 119  * prototypes for functions in dynahash.c
 120  */
 121 extern HTAB *hash_create(const char *tabname, long nelem,
 122                         HASHCTL *info, int flags);
 123 extern void hash_destroy(HTAB *hashp);
 124 extern void hash_stats(const char *where, HTAB *hashp);
 125 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
 126                         bool *foundPtr);
 127 extern uint32 get_hash_value(HTAB *hashp, const void *keyPtr);
 128 extern void *hash_search_with_hash_value(HTAB *hashp, const void *keyPtr,
 129                                                         uint32 hashvalue, HASHACTION action,
 130                                                         bool *foundPtr);
 131 extern bool hash_update_hash_key(HTAB *hashp, void *existingEntry,
 132                                          const void *newKeyPtr);
 133 extern long hash_get_num_entries(HTAB *hashp);
 134 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
 135 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
 136 extern void hash_seq_term(HASH_SEQ_STATUS *status);
 137 extern void hash_freeze(HTAB *hashp);
 138 extern Size hash_estimate_size(long num_entries, Size entrysize);
 139 extern long hash_select_dirsize(long num_entries);
 140 extern Size hash_get_shared_size(HASHCTL *info, int flags);
 141 extern void AtEOXact_HashTables(bool isCommit);
 142 extern void AtEOSubXact_HashTables(bool isCommit, int nestDepth);
 143
 144 /*
 145  * prototypes for functions in hashfn.c
 146  */
 147 extern uint32 string_hash(const void *key, Size keysize);
 148 extern uint32 tag_hash(const void *key, Size keysize);
 149 extern uint32 oid_hash(const void *key, Size keysize);
 150 extern uint32 bitmap_hash(const void *key, Size keysize);
 151 extern int      bitmap_match(const void *key1, const void *key2, Size keysize);
 152
 153 #endif   /* HSEARCH_H */