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-2004, 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.31 2004/08/29 04:13:11 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #ifndef HSEARCH_H
  15 #define HSEARCH_H
  16
  17
  18 /*
  19  * Hash and comparison functions must have these signatures.  Comparison
  20  * functions return zero for match, nonzero for no match.  (The comparison
  21  * function definition is designed to allow memcmp() and strncmp() to be
  22  * used directly as key comparison functions.)
  23  */
  24 typedef uint32 (*HashValueFunc) (const void *key, Size keysize);
  25 typedef int (*HashCompareFunc) (const void *key1, const void *key2,
  26                                                                 Size keysize);
  27
  28 /*
  29  * Space allocation function for a hashtable --- designed to match malloc().
  30  * Note: there is no free function API; can't destroy a hashtable unless you
  31  * use the default allocator.
  32  */
  33 typedef void *(*HashAllocFunc) (Size request);
  34
  35 /*
  36  * Constants
  37  *
  38  * A hash table has a top-level "directory", each of whose entries points
  39  * to a "segment" of ssize bucket headers.      The maximum number of hash
  40  * buckets is thus dsize * ssize (but dsize may be expansible).  Of course,
  41  * the number of records in the table can be larger, but we don't want a
  42  * whole lot of records per bucket or performance goes down.
  43  *
  44  * In a hash table allocated in shared memory, the directory cannot be
  45  * expanded because it must stay at a fixed address.  The directory size
  46  * should be selected using hash_select_dirsize (and you'd better have
  47  * a good idea of the maximum number of entries!).      For non-shared hash
  48  * tables, the initial directory size can be left at the default.
  49  */
  50 #define DEF_SEGSIZE                        256
  51 #define DEF_SEGSIZE_SHIFT          8    /* must be log2(DEF_SEGSIZE) */
  52 #define DEF_DIRSIZE                        256
  53 #define DEF_FFACTOR                        1    /* default fill factor */
  54
  55
  56 /*
  57  * HASHELEMENT is the private part of a hashtable entry.  The caller's data
  58  * follows the HASHELEMENT structure (on a MAXALIGN'd boundary).  The hash key
  59  * is expected to be at the start of the caller's hash entry data structure.
  60  */
  61 typedef struct HASHELEMENT
  62 {
  63         struct HASHELEMENT *link;       /* link to next entry in same bucket */
  64         uint32  hashvalue;                      /* hash function result for this entry */
  65 } HASHELEMENT;
  66
  67 /* A hash bucket is a linked list of HASHELEMENTs */
  68 typedef HASHELEMENT *HASHBUCKET;
  69
  70 /* A hash segment is an array of bucket headers */
  71 typedef HASHBUCKET *HASHSEGMENT;
  72
  73 /* Header structure for a hash table --- contains all changeable info */
  74 typedef struct HASHHDR
  75 {
  76         long            dsize;                  /* Directory Size */
  77         long            ssize;                  /* Segment Size --- must be power of 2 */
  78         int                     sshift;                 /* Segment shift = log2(ssize) */
  79         uint32          max_bucket;             /* ID of Maximum bucket in use */
  80         uint32          high_mask;              /* Mask to modulo into entire table */
  81         uint32          low_mask;               /* Mask to modulo into lower half of table */
  82         long            ffactor;                /* Fill factor */
  83         long            nentries;               /* Number of entries in hash table */
  84         long            nsegs;                  /* Number of allocated segments */
  85         Size            keysize;                /* hash key length in bytes */
  86         Size            entrysize;              /* total user element size in bytes */
  87         long            max_dsize;              /* 'dsize' limit if directory is fixed
  88                                                                  * size */
  89         HASHELEMENT *freeList;          /* linked list of free elements */
  90 #ifdef HASH_STATISTICS
  91         long            accesses;
  92         long            collisions;
  93 #endif
  94 } HASHHDR;
  95
  96 /*
  97  * Top control structure for a hashtable --- need not be shared, since
  98  * no fields change at runtime
  99  */
 100 typedef struct HTAB
 101 {
 102         HASHHDR    *hctl;                       /* shared control information */
 103         HASHSEGMENT *dir;                       /* directory of segment starts */
 104         HashValueFunc hash;                     /* hash function */
 105         HashCompareFunc match;          /* key comparison function */
 106         HashAllocFunc alloc;            /* memory allocator */
 107         MemoryContext hcxt;                     /* memory context if default allocator
 108                                                                  * used */
 109         char       *tabname;            /* table name (for error messages) */
 110         bool            isshared;               /* true if table is in shared memory */
 111 } HTAB;
 112
 113 /* Parameter data structure for hash_create */
 114 /* Only those fields indicated by hash_flags need be set */
 115 typedef struct HASHCTL
 116 {
 117         long            ssize;                  /* Segment Size */
 118         long            dsize;                  /* (initial) Directory Size */
 119         long            max_dsize;              /* limit to dsize if directory size is
 120                                                                  * limited */
 121         long            ffactor;                /* Fill factor */
 122         Size            keysize;                /* hash key length in bytes */
 123         Size            entrysize;              /* total user element size in bytes */
 124         HashValueFunc hash;                     /* hash function */
 125         HashCompareFunc match;          /* key comparison function */
 126         HashAllocFunc alloc;            /* memory allocator */
 127         HASHSEGMENT *dir;                       /* directory of segment starts */
 128         HASHHDR    *hctl;                       /* location of header in shared mem */
 129         MemoryContext hcxt;                     /* memory context to use for allocations */
 130 } HASHCTL;
 131
 132 /* Flags to indicate which parameters are supplied */
 133 #define HASH_SEGMENT    0x002   /* Set segment size */
 134 #define HASH_DIRSIZE    0x004   /* Set directory size */
 135 #define HASH_FFACTOR    0x008   /* Set fill factor */
 136 #define HASH_FUNCTION   0x010   /* Set user defined hash function */
 137 #define HASH_ELEM               0x020   /* Set key/entry size */
 138 #define HASH_SHARED_MEM 0x040   /* Set shared mem const */
 139 #define HASH_ATTACH             0x080   /* Do not initialize hctl */
 140 #define HASH_ALLOC              0x100   /* Set memory allocator */
 141 #define HASH_CONTEXT    0x200   /* Set explicit memory context */
 142 #define HASH_COMPARE    0x400   /* Set user defined comparison function */
 143
 144
 145 /* max_dsize value to indicate expansible directory */
 146 #define NO_MAX_DSIZE                    (-1)
 147 /* number of hash elements allocated at once */
 148 #define HASHELEMENT_ALLOC_INCR  (32)
 149
 150 /* hash_search operations */
 151 typedef enum
 152 {
 153         HASH_FIND,
 154         HASH_ENTER,
 155         HASH_REMOVE,
 156         HASH_FIND_SAVE,
 157         HASH_REMOVE_SAVED
 158 } HASHACTION;
 159
 160 /* hash_seq status (should be considered an opaque type by callers) */
 161 typedef struct
 162 {
 163         HTAB       *hashp;
 164         uint32          curBucket;              /* index of current bucket */
 165         HASHELEMENT *curEntry;          /* current entry in bucket */
 166 } HASH_SEQ_STATUS;
 167
 168 /*
 169  * prototypes for functions in dynahash.c
 170  */
 171 extern HTAB *hash_create(const char *tabname, long nelem,
 172                         HASHCTL *info, int flags);
 173 extern void hash_destroy(HTAB *hashp);
 174 extern void hash_stats(const char *where, HTAB *hashp);
 175 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
 176                         bool *foundPtr);
 177 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
 178 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
 179 extern long hash_estimate_size(long num_entries, Size entrysize);
 180 extern long hash_select_dirsize(long num_entries);
 181
 182 /*
 183  * prototypes for functions in hashfn.c
 184  */
 185 extern uint32 string_hash(const void *key, Size keysize);
 186 extern uint32 tag_hash(const void *key, Size keysize);
 187
 188 #endif   /* HSEARCH_H */