granicus.if.org Git - postgresql/blob - src/include/utils/hsearch.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * hsearch.h
   4  *        for hash tables, particularly hash tables in shared memory
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * $PostgreSQL: pgsql/src/include/utils/hsearch.h,v 1.40 2005/08/20 23:26:37 tgl Exp $
  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  * Constants
  48  *
  49  * A hash table has a top-level "directory", each of whose entries points
  50  * to a "segment" of ssize bucket headers.      The maximum number of hash
  51  * buckets is thus dsize * ssize (but dsize may be expansible).  Of course,
  52  * the number of records in the table can be larger, but we don't want a
  53  * whole lot of records per bucket or performance goes down.
  54  *
  55  * In a hash table allocated in shared memory, the directory cannot be
  56  * expanded because it must stay at a fixed address.  The directory size
  57  * should be selected using hash_select_dirsize (and you'd better have
  58  * a good idea of the maximum number of entries!).      For non-shared hash
  59  * tables, the initial directory size can be left at the default.
  60  */
  61 #define DEF_SEGSIZE                        256
  62 #define DEF_SEGSIZE_SHIFT          8    /* must be log2(DEF_SEGSIZE) */
  63 #define DEF_DIRSIZE                        256
  64 #define DEF_FFACTOR                        1    /* default fill factor */
  65
  66
  67 /*
  68  * HASHELEMENT is the private part of a hashtable entry.  The caller's data
  69  * follows the HASHELEMENT structure (on a MAXALIGN'd boundary).  The hash key
  70  * is expected to be at the start of the caller's hash entry data structure.
  71  */
  72 typedef struct HASHELEMENT
  73 {
  74         struct HASHELEMENT *link;       /* link to next entry in same bucket */
  75         uint32          hashvalue;              /* hash function result for this entry */
  76 } HASHELEMENT;
  77
  78 /* A hash bucket is a linked list of HASHELEMENTs */
  79 typedef HASHELEMENT *HASHBUCKET;
  80
  81 /* A hash segment is an array of bucket headers */
  82 typedef HASHBUCKET *HASHSEGMENT;
  83
  84 /* Header structure for a hash table --- contains all changeable info */
  85 typedef struct HASHHDR
  86 {
  87         long            dsize;                  /* Directory Size */
  88         long            ssize;                  /* Segment Size --- must be power of 2 */
  89         int                     sshift;                 /* Segment shift = log2(ssize) */
  90         uint32          max_bucket;             /* ID of Maximum bucket in use */
  91         uint32          high_mask;              /* Mask to modulo into entire table */
  92         uint32          low_mask;               /* Mask to modulo into lower half of table */
  93         long            ffactor;                /* Fill factor */
  94         long            nentries;               /* Number of entries in hash table */
  95         long            nsegs;                  /* Number of allocated segments */
  96         Size            keysize;                /* hash key length in bytes */
  97         Size            entrysize;              /* total user element size in bytes */
  98         long            max_dsize;              /* 'dsize' limit if directory is fixed
  99                                                                  * size */
 100         int                     nelem_alloc;    /* number of entries to allocate at once */
 101         HASHELEMENT *freeList;          /* linked list of free elements */
 102 #ifdef HASH_STATISTICS
 103         long            accesses;
 104         long            collisions;
 105 #endif
 106 } HASHHDR;
 107
 108 /*
 109  * Top control structure for a hashtable --- need not be shared, since
 110  * no fields change at runtime
 111  */
 112 typedef struct HTAB
 113 {
 114         HASHHDR    *hctl;                       /* shared control information */
 115         HASHSEGMENT *dir;                       /* directory of segment starts */
 116         HashValueFunc hash;                     /* hash function */
 117         HashCompareFunc match;          /* key comparison function */
 118         HashCopyFunc keycopy;           /* key copying function */
 119         HashAllocFunc alloc;            /* memory allocator */
 120         MemoryContext hcxt;                     /* memory context if default allocator
 121                                                                  * used */
 122         char       *tabname;            /* table name (for error messages) */
 123         bool            isshared;               /* true if table is in shared memory */
 124 } HTAB;
 125
 126 /* Parameter data structure for hash_create */
 127 /* Only those fields indicated by hash_flags need be set */
 128 typedef struct HASHCTL
 129 {
 130         long            ssize;                  /* Segment Size */
 131         long            dsize;                  /* (initial) Directory Size */
 132         long            max_dsize;              /* limit to dsize if directory size is
 133                                                                  * limited */
 134         long            ffactor;                /* Fill factor */
 135         Size            keysize;                /* hash key length in bytes */
 136         Size            entrysize;              /* total user element size in bytes */
 137         HashValueFunc hash;                     /* hash function */
 138         HashCompareFunc match;          /* key comparison function */
 139         HashCopyFunc keycopy;           /* key copying function */
 140         HashAllocFunc alloc;            /* memory allocator */
 141         HASHSEGMENT *dir;                       /* directory of segment starts */
 142         HASHHDR    *hctl;                       /* location of header in shared mem */
 143         MemoryContext hcxt;                     /* memory context to use for allocations */
 144 } HASHCTL;
 145
 146 /* Flags to indicate which parameters are supplied */
 147 #define HASH_SEGMENT    0x002   /* Set segment size */
 148 #define HASH_DIRSIZE    0x004   /* Set directory size */
 149 #define HASH_FFACTOR    0x008   /* Set fill factor */
 150 #define HASH_FUNCTION   0x010   /* Set user defined hash function */
 151 #define HASH_ELEM               0x020   /* Set key/entry size */
 152 #define HASH_SHARED_MEM 0x040   /* Hashtable is in shared memory */
 153 #define HASH_ATTACH             0x080   /* Do not initialize hctl */
 154 #define HASH_ALLOC              0x100   /* Set memory allocator */
 155 #define HASH_CONTEXT    0x200   /* Set explicit memory context */
 156 #define HASH_COMPARE    0x400   /* Set user defined comparison function */
 157 #define HASH_KEYCOPY    0x800   /* Set user defined key-copying function */
 158
 159
 160 /* max_dsize value to indicate expansible directory */
 161 #define NO_MAX_DSIZE                    (-1)
 162 /* max number of hash elements allocated at once */
 163 #define HASHELEMENT_ALLOC_MAX   (32)
 164
 165 /* hash_search operations */
 166 typedef enum
 167 {
 168         HASH_FIND,
 169         HASH_ENTER,
 170         HASH_REMOVE,
 171         HASH_ENTER_NULL
 172 } HASHACTION;
 173
 174 /* hash_seq status (should be considered an opaque type by callers) */
 175 typedef struct
 176 {
 177         HTAB       *hashp;
 178         uint32          curBucket;              /* index of current bucket */
 179         HASHELEMENT *curEntry;          /* current entry in bucket */
 180 } HASH_SEQ_STATUS;
 181
 182 /*
 183  * prototypes for functions in dynahash.c
 184  */
 185 extern HTAB *hash_create(const char *tabname, long nelem,
 186                         HASHCTL *info, int flags);
 187 extern void hash_destroy(HTAB *hashp);
 188 extern void hash_stats(const char *where, HTAB *hashp);
 189 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
 190                         bool *foundPtr);
 191 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
 192 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
 193 extern Size hash_estimate_size(long num_entries, Size entrysize);
 194 extern long hash_select_dirsize(long num_entries);
 195
 196 /*
 197  * prototypes for functions in hashfn.c
 198  */
 199 extern uint32 string_hash(const void *key, Size keysize);
 200 extern uint32 tag_hash(const void *key, Size keysize);
 201 extern uint32 oid_hash(const void *key, Size keysize);
 202 extern uint32 bitmap_hash(const void *key, Size keysize);
 203 extern int      bitmap_match(const void *key1, const void *key2, Size keysize);
 204
 205 #endif   /* HSEARCH_H */