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