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.19 2001/03/22 04:01:12 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  * Hash bucket is actually bigger than this.  Key field can have
  44  * variable length and a variable length data field follows it.
  45  */
  46 typedef struct element
  47 {
  48         unsigned long next;                     /* secret from user */
  49         long            key;
  50 } ELEMENT;
  51
  52 typedef unsigned long BUCKET_INDEX;
  53
  54 /* segment is an array of bucket pointers */
  55 typedef BUCKET_INDEX *SEGMENT;
  56 typedef unsigned long SEG_OFFSET;
  57
  58 typedef struct hashhdr
  59 {
  60         long            dsize;                  /* Directory Size */
  61         long            ssize;                  /* Segment Size --- must be power of 2 */
  62         long            sshift;                 /* Segment shift */
  63         long            max_bucket;             /* ID of Maximum bucket in use */
  64         long            high_mask;              /* Mask to modulo into entire table */
  65         long            low_mask;               /* Mask to modulo into lower half of table */
  66         long            ffactor;                /* Fill factor */
  67         long            nkeys;                  /* Number of keys in hash table */
  68         long            nsegs;                  /* Number of allocated segments */
  69         long            keysize;                /* hash key length in bytes */
  70         long            datasize;               /* elem data length in bytes */
  71         long            max_dsize;              /* 'dsize' limit if directory is fixed
  72                                                                  * size */
  73         BUCKET_INDEX freeBucketIndex;           /* index of first free bucket */
  74 #ifdef HASH_STATISTICS
  75         long            accesses;
  76         long            collisions;
  77 #endif
  78 } HHDR;
  79
  80 typedef struct htab
  81 {
  82         HHDR       *hctl;                       /* shared control information */
  83         long            (*hash) ();             /* Hash Function */
  84         char       *segbase;            /* segment base address for calculating
  85                                                                  * pointer values */
  86         SEG_OFFSET *dir;                        /* 'directory' of segm starts */
  87         void       *(*alloc) (Size);/* memory allocator */
  88 } HTAB;
  89
  90 typedef struct hashctl
  91 {
  92         long            ssize;                  /* Segment Size */
  93         long            dsize;                  /* Dirsize Size */
  94         long            ffactor;                /* Fill factor */
  95         long            (*hash) ();             /* Hash Function */
  96         long            keysize;                /* hash key length in bytes */
  97         long            datasize;               /* elem data length in bytes */
  98         long            max_dsize;              /* limit to dsize if directory size is
  99                                                                  * limited */
 100         long       *segbase;            /* base for calculating bucket + seg ptrs */
 101         void       *(*alloc) (Size);/* memory allocation function */
 102         long       *dir;                        /* directory if allocated already */
 103         long       *hctl;                       /* location of header information in shd
 104                                                                  * mem */
 105 } HASHCTL;
 106
 107 /* Flags to indicate action for hctl */
 108 #define HASH_SEGMENT    0x002   /* Setting segment size */
 109 #define HASH_DIRSIZE    0x004   /* Setting directory size */
 110 #define HASH_FFACTOR    0x008   /* Setting fill factor */
 111 #define HASH_FUNCTION   0x010   /* Set user defined hash function */
 112 #define HASH_ELEM               0x020   /* Setting key/data size */
 113 #define HASH_SHARED_MEM 0x040   /* Setting shared mem const */
 114 #define HASH_ATTACH             0x080   /* Do not initialize hctl */
 115 #define HASH_ALLOC              0x100   /* Setting memory allocator */
 116
 117
 118 /* seg_alloc assumes that INVALID_INDEX is 0 */
 119 #define INVALID_INDEX                   (0)
 120 #define NO_MAX_DSIZE                    (-1)
 121 /* number of hash buckets allocated at once */
 122 #define BUCKET_ALLOC_INCR               (30)
 123
 124 /* hash_search operations */
 125 typedef enum
 126 {
 127         HASH_FIND,
 128         HASH_ENTER,
 129         HASH_REMOVE,
 130         HASH_FIND_SAVE,
 131         HASH_REMOVE_SAVED
 132 } HASHACTION;
 133
 134 /* hash_seq status (should be considered an opaque type by callers) */
 135 typedef struct
 136 {
 137         HTAB       *hashp;
 138         long            curBucket;
 139         BUCKET_INDEX curIndex;
 140 } HASH_SEQ_STATUS;
 141
 142 /*
 143  * prototypes from functions in dynahash.c
 144  */
 145 extern HTAB *hash_create(int nelem, HASHCTL *info, int flags);
 146 extern void hash_destroy(HTAB *hashp);
 147 extern void hash_stats(char *where, HTAB *hashp);
 148 extern long *hash_search(HTAB *hashp, char *keyPtr, HASHACTION action,
 149                         bool *foundPtr);
 150 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
 151 extern long *hash_seq_search(HASH_SEQ_STATUS *status);
 152 extern long hash_estimate_size(long num_entries, long keysize, long datasize);
 153 extern long hash_select_dirsize(long num_entries);
 154
 155 /*
 156  * prototypes from functions in hashfn.c
 157  */
 158 extern long string_hash(char *key, int keysize);
 159 extern long tag_hash(int *key, int keysize);
 160
 161 #endif   /* HSEARCH_H */