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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * hsearch.h--
   4  *    for hashing in the new buffer manager
   5  *
   6  *
   7  * Copyright (c) 1994, Regents of the University of California
   8  *
   9  * $Id: hsearch.h,v 1.1 1996/08/28 01:59:04 scrappy Exp $
  10  *
  11  *-------------------------------------------------------------------------
  12  */
  13 #ifndef HSEARCH_H
  14 #define HSEARCH_H
  15
  16 #include "postgres.h"
  17
  18 /*
  19  * Constants
  20  */
  21 # define DEF_BUCKET_SIZE        256
  22 # define DEF_BUCKET_SHIFT       8       /* log2(BUCKET) */
  23 # define DEF_SEGSIZE            256
  24 # define DEF_SEGSIZE_SHIFT              8      /* log2(SEGSIZE)  */
  25 # define DEF_DIRSIZE            256
  26 # define PRIME1                 37
  27 # define PRIME2                 1048583
  28 # define DEF_FFACTOR            1
  29 # define SPLTMAX                8
  30
  31
  32 /*
  33  * Hash bucket is actually bigger than this.  Key field can have
  34  * variable length and a variable length data field follows it.
  35  */
  36 typedef struct element {
  37     unsigned long next;         /* secret from user      */
  38     long key;
  39 } ELEMENT;
  40
  41 typedef unsigned long BUCKET_INDEX;
  42 /* segment is an array of bucket pointers  */
  43 typedef BUCKET_INDEX *SEGMENT;
  44 typedef unsigned long SEG_OFFSET;
  45
  46 typedef struct hashhdr {
  47     long bsize;                 /* Bucket/Page Size */
  48     long bshift;                /* Bucket shift */
  49     long dsize;                 /* Directory Size */
  50     long ssize;                 /* Segment Size */
  51     long sshift;                /* Segment shift */
  52     long max_bucket;            /* ID of Maximum bucket in use */
  53     long high_mask;             /* Mask to modulo into entire table */
  54     long low_mask;              /* Mask to modulo into lower half of table */
  55     long ffactor;               /* Fill factor */
  56     long nkeys;                 /* Number of keys in hash table */
  57     long nsegs;                 /* Number of allocated segments */
  58     long keysize;               /* hash key length in bytes */
  59     long datasize;              /* elem data length in bytes */
  60     long max_dsize;             /* 'dsize' limit if directory is fixed size */
  61     BUCKET_INDEX freeBucketIndex;
  62     /* index of first free bucket */
  63 #ifdef HASH_STATISTICS
  64     long accesses;
  65     long collisions;
  66 #endif
  67 } HHDR;
  68
  69 typedef struct htab {
  70     HHDR        *hctl;          /* shared control information */
  71     long        (*hash)();      /* Hash Function */
  72     char        *segbase;       /* segment base address for
  73                                  * calculating pointer values
  74                                  */
  75     SEG_OFFSET  *dir;           /* 'directory' of segm starts */
  76     long        *(*alloc)();    /* memory allocator
  77                                  * (long * for alignment reasons)
  78                                  */
  79
  80 } HTAB;
  81
  82 typedef struct hashctl {
  83     long bsize;         /* Bucket Size */
  84     long ssize;         /* Segment Size */
  85     long dsize;         /* Dirsize Size */
  86     long ffactor;       /* Fill factor */
  87     long (*hash)();     /* Hash Function */
  88     long keysize;       /* hash key length in bytes */
  89     long datasize;      /* elem data length in bytes */
  90     long max_size;      /* limit to dsize if directory size is limited */
  91     long *segbase;      /* base for calculating bucket + seg ptrs */
  92     long * (*alloc)();  /* memory allocation function */
  93     long *dir;          /* directory if allocated already */
  94     long *hctl;         /* location of header information in shd mem */
  95 } HASHCTL;
  96
  97 /* Flags to indicate action for hctl */
  98 #define HASH_BUCKET     0x001   /* Setting bucket size */
  99 #define HASH_SEGMENT    0x002   /* Setting segment size */
 100 #define HASH_DIRSIZE    0x004   /* Setting directory size */
 101 #define HASH_FFACTOR    0x008   /* Setting fill factor */
 102 #define HASH_FUNCTION   0x010   /* Set user defined hash function */
 103 #define HASH_ELEM       0x020   /* Setting key/data size */
 104 #define HASH_SHARED_MEM 0x040   /* Setting shared mem const */
 105 #define HASH_ATTACH     0x080   /* Do not initialize hctl */
 106 #define HASH_ALLOC      0x100   /* Setting memory allocator */
 107
 108
 109 /* seg_alloc assumes that INVALID_INDEX is 0*/
 110 #define INVALID_INDEX           (0)
 111 #define NO_MAX_DSIZE            (-1)
 112 /* number of hash buckets allocated at once */
 113 #define BUCKET_ALLOC_INCR       (30)
 114
 115 /* hash_search operations */
 116 typedef enum {
 117     HASH_FIND,
 118     HASH_ENTER,
 119     HASH_REMOVE,
 120     HASH_FIND_SAVE,
 121     HASH_REMOVE_SAVED
 122 } HASHACTION;
 123
 124 /*
 125  * prototypes from functions in dynahash.c
 126  */
 127 extern HTAB *hash_create(int nelem, HASHCTL *info, int flags);
 128 extern void hash_destroy(HTAB *hashp);
 129 extern void hash_stats(char *where, HTAB *hashp);
 130 extern long *hash_search(HTAB *hashp, char *keyPtr, HASHACTION action,
 131                          bool *foundPtr);
 132 extern long *hash_seq(HTAB *hashp);
 133
 134 /*
 135  * prototypes from functions in hashfn.c
 136  */
 137 extern long string_hash(char *key, int keysize);
 138 extern long tag_hash(int *key, int keysize);
 139 extern long disk_hash(char *key);
 140
 141 #endif /* HSEARCH_H */