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