util/X86MAC64/include/postgresql/server/access/hash.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * hash.h
   4  *        header file for postgres hash access method implementation
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * src/include/access/hash.h
  11  *
  12  * NOTES
  13  *              modeled after Margo Seltzer's hash implementation for unix.
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #ifndef HASH_H
  18 #define HASH_H
  19
  20 #include "access/genam.h"
  21 #include "access/itup.h"
  22 #include "access/sdir.h"
  23 #include "access/xlog.h"
  24 #include "fmgr.h"
  25 #include "storage/bufmgr.h"
  26 #include "storage/lock.h"
  27 #include "utils/relcache.h"
  28
  29 /*
  30  * Mapping from hash bucket number to physical block number of bucket's
  31  * starting page.  Beware of multiple evaluations of argument!
  32  */
  33 typedef uint32 Bucket;
  34
  35 #define BUCKET_TO_BLKNO(metap,B) \
  36                 ((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_log2((B)+1)-1] : 0)) + 1)
  37
  38 /*
  39  * Special space for hash index pages.
  40  *
  41  * hasho_flag tells us which type of page we're looking at.  For
  42  * example, knowing overflow pages from bucket pages is necessary
  43  * information when you're deleting tuples from a page. If all the
  44  * tuples are deleted from an overflow page, the overflow is made
  45  * available to other buckets by calling _hash_freeovflpage(). If all
  46  * the tuples are deleted from a bucket page, no additional action is
  47  * necessary.
  48  */
  49 #define LH_UNUSED_PAGE                  (0)
  50 #define LH_OVERFLOW_PAGE                (1 << 0)
  51 #define LH_BUCKET_PAGE                  (1 << 1)
  52 #define LH_BITMAP_PAGE                  (1 << 2)
  53 #define LH_META_PAGE                    (1 << 3)
  54
  55 typedef struct HashPageOpaqueData
  56 {
  57         BlockNumber hasho_prevblkno;    /* previous ovfl (or bucket) blkno */
  58         BlockNumber hasho_nextblkno;    /* next ovfl blkno */
  59         Bucket          hasho_bucket;   /* bucket number this pg belongs to */
  60         uint16          hasho_flag;             /* page type code, see above */
  61         uint16          hasho_page_id;  /* for identification of hash indexes */
  62 } HashPageOpaqueData;
  63
  64 typedef HashPageOpaqueData *HashPageOpaque;
  65
  66 /*
  67  * The page ID is for the convenience of pg_filedump and similar utilities,
  68  * which otherwise would have a hard time telling pages of different index
  69  * types apart.  It should be the last 2 bytes on the page.  This is more or
  70  * less "free" due to alignment considerations.
  71  */
  72 #define HASHO_PAGE_ID           0xFF80
  73
  74 /*
  75  *      HashScanOpaqueData is private state for a hash index scan.
  76  */
  77 typedef struct HashScanOpaqueData
  78 {
  79         /* Hash value of the scan key, ie, the hash key we seek */
  80         uint32          hashso_sk_hash;
  81
  82         /*
  83          * By definition, a hash scan should be examining only one bucket. We
  84          * record the bucket number here as soon as it is known.
  85          */
  86         Bucket          hashso_bucket;
  87         bool            hashso_bucket_valid;
  88
  89         /*
  90          * If we have a share lock on the bucket, we record it here.  When
  91          * hashso_bucket_blkno is zero, we have no such lock.
  92          */
  93         BlockNumber hashso_bucket_blkno;
  94
  95         /*
  96          * We also want to remember which buffer we're currently examining in the
  97          * scan. We keep the buffer pinned (but not locked) across hashgettuple
  98          * calls, in order to avoid doing a ReadBuffer() for every tuple in the
  99          * index.
 100          */
 101         Buffer          hashso_curbuf;
 102
 103         /* Current position of the scan, as an index TID */
 104         ItemPointerData hashso_curpos;
 105
 106         /* Current position of the scan, as a heap TID */
 107         ItemPointerData hashso_heappos;
 108 } HashScanOpaqueData;
 109
 110 typedef HashScanOpaqueData *HashScanOpaque;
 111
 112 /*
 113  * Definitions for metapage.
 114  */
 115
 116 #define HASH_METAPAGE   0               /* metapage is always block 0 */
 117
 118 #define HASH_MAGIC              0x6440640
 119 #define HASH_VERSION    2               /* 2 signifies only hash key value is stored */
 120
 121 /*
 122  * Spares[] holds the number of overflow pages currently allocated at or
 123  * before a certain splitpoint. For example, if spares[3] = 7 then there are
 124  * 7 ovflpages before splitpoint 3 (compare BUCKET_TO_BLKNO macro).  The
 125  * value in spares[ovflpoint] increases as overflow pages are added at the
 126  * end of the index.  Once ovflpoint increases (ie, we have actually allocated
 127  * the bucket pages belonging to that splitpoint) the number of spares at the
 128  * prior splitpoint cannot change anymore.
 129  *
 130  * ovflpages that have been recycled for reuse can be found by looking at
 131  * bitmaps that are stored within ovflpages dedicated for the purpose.
 132  * The blknos of these bitmap pages are kept in bitmaps[]; nmaps is the
 133  * number of currently existing bitmaps.
 134  *
 135  * The limitation on the size of spares[] comes from the fact that there's
 136  * no point in having more than 2^32 buckets with only uint32 hashcodes.
 137  * There is no particular upper limit on the size of mapp[], other than
 138  * needing to fit into the metapage.  (With 8K block size, 128 bitmaps
 139  * limit us to 64 Gb of overflow space...)
 140  */
 141 #define HASH_MAX_SPLITPOINTS            32
 142 #define HASH_MAX_BITMAPS                        128
 143
 144 typedef struct HashMetaPageData
 145 {
 146         uint32          hashm_magic;    /* magic no. for hash tables */
 147         uint32          hashm_version;  /* version ID */
 148         double          hashm_ntuples;  /* number of tuples stored in the table */
 149         uint16          hashm_ffactor;  /* target fill factor (tuples/bucket) */
 150         uint16          hashm_bsize;    /* index page size (bytes) */
 151         uint16          hashm_bmsize;   /* bitmap array size (bytes) - must be a power
 152                                                                  * of 2 */
 153         uint16          hashm_bmshift;  /* log2(bitmap array size in BITS) */
 154         uint32          hashm_maxbucket;        /* ID of maximum bucket in use */
 155         uint32          hashm_highmask; /* mask to modulo into entire table */
 156         uint32          hashm_lowmask;  /* mask to modulo into lower half of table */
 157         uint32          hashm_ovflpoint;/* splitpoint from which ovflpgs being
 158                                                                  * allocated */
 159         uint32          hashm_firstfree;        /* lowest-number free ovflpage (bit#) */
 160         uint32          hashm_nmaps;    /* number of bitmap pages */
 161         RegProcedure hashm_procid;      /* hash procedure id from pg_proc */
 162         uint32          hashm_spares[HASH_MAX_SPLITPOINTS];             /* spare pages before
 163                                                                                                                  * each splitpoint */
 164         BlockNumber hashm_mapp[HASH_MAX_BITMAPS];       /* blknos of ovfl bitmaps */
 165 } HashMetaPageData;
 166
 167 typedef HashMetaPageData *HashMetaPage;
 168
 169 /*
 170  * Maximum size of a hash index item (it's okay to have only one per page)
 171  */
 172 #define HashMaxItemSize(page) \
 173         MAXALIGN_DOWN(PageGetPageSize(page) - \
 174                                   SizeOfPageHeaderData - \
 175                                   sizeof(ItemIdData) - \
 176                                   MAXALIGN(sizeof(HashPageOpaqueData)))
 177
 178 #define HASH_MIN_FILLFACTOR                     10
 179 #define HASH_DEFAULT_FILLFACTOR         75
 180
 181 /*
 182  * Constants
 183  */
 184 #define BYTE_TO_BIT                             3               /* 2^3 bits/byte */
 185 #define ALL_SET                                 ((uint32) ~0)
 186
 187 /*
 188  * Bitmap pages do not contain tuples.  They do contain the standard
 189  * page headers and trailers; however, everything in between is a
 190  * giant bit array.  The number of bits that fit on a page obviously
 191  * depends on the page size and the header/trailer overhead.  We require
 192  * the number of bits per page to be a power of 2.
 193  */
 194 #define BMPGSZ_BYTE(metap)              ((metap)->hashm_bmsize)
 195 #define BMPGSZ_BIT(metap)               ((metap)->hashm_bmsize << BYTE_TO_BIT)
 196 #define BMPG_SHIFT(metap)               ((metap)->hashm_bmshift)
 197 #define BMPG_MASK(metap)                (BMPGSZ_BIT(metap) - 1)
 198
 199 #define HashPageGetBitmap(page) \
 200         ((uint32 *) PageGetContents(page))
 201
 202 #define HashGetMaxBitmapSize(page) \
 203         (PageGetPageSize((Page) page) - \
 204          (MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(HashPageOpaqueData))))
 205
 206 #define HashPageGetMeta(page) \
 207         ((HashMetaPage) PageGetContents(page))
 208
 209 /*
 210  * The number of bits in an ovflpage bitmap word.
 211  */
 212 #define BITS_PER_MAP    32              /* Number of bits in uint32 */
 213
 214 /* Given the address of the beginning of a bit map, clear/set the nth bit */
 215 #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
 216 #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
 217 #define ISSET(A, N)             ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
 218
 219 /*
 220  * page-level and high-level locking modes (see README)
 221  */
 222 #define HASH_READ               BUFFER_LOCK_SHARE
 223 #define HASH_WRITE              BUFFER_LOCK_EXCLUSIVE
 224 #define HASH_NOLOCK             (-1)
 225
 226 #define HASH_SHARE              ShareLock
 227 #define HASH_EXCLUSIVE  ExclusiveLock
 228
 229 /*
 230  *      Strategy number. There's only one valid strategy for hashing: equality.
 231  */
 232 #define HTEqualStrategyNumber                   1
 233 #define HTMaxStrategyNumber                             1
 234
 235 /*
 236  *      When a new operator class is declared, we require that the user supply
 237  *      us with an amproc procudure for hashing a key of the new type.
 238  *      Since we only have one such proc in amproc, it's number 1.
 239  */
 240 #define HASHPROC                1
 241
 242
 243 /* public routines */
 244
 245 extern Datum hashbuild(PG_FUNCTION_ARGS);
 246 extern Datum hashbuildempty(PG_FUNCTION_ARGS);
 247 extern Datum hashinsert(PG_FUNCTION_ARGS);
 248 extern Datum hashbeginscan(PG_FUNCTION_ARGS);
 249 extern Datum hashgettuple(PG_FUNCTION_ARGS);
 250 extern Datum hashgetbitmap(PG_FUNCTION_ARGS);
 251 extern Datum hashrescan(PG_FUNCTION_ARGS);
 252 extern Datum hashendscan(PG_FUNCTION_ARGS);
 253 extern Datum hashmarkpos(PG_FUNCTION_ARGS);
 254 extern Datum hashrestrpos(PG_FUNCTION_ARGS);
 255 extern Datum hashbulkdelete(PG_FUNCTION_ARGS);
 256 extern Datum hashvacuumcleanup(PG_FUNCTION_ARGS);
 257 extern Datum hashoptions(PG_FUNCTION_ARGS);
 258
 259 /*
 260  * Datatype-specific hash functions in hashfunc.c.
 261  *
 262  * These support both hash indexes and hash joins.
 263  *
 264  * NOTE: some of these are also used by catcache operations, without
 265  * any direct connection to hash indexes.  Also, the common hash_any
 266  * routine is also used by dynahash tables.
 267  */
 268 extern Datum hashchar(PG_FUNCTION_ARGS);
 269 extern Datum hashint2(PG_FUNCTION_ARGS);
 270 extern Datum hashint4(PG_FUNCTION_ARGS);
 271 extern Datum hashint8(PG_FUNCTION_ARGS);
 272 extern Datum hashoid(PG_FUNCTION_ARGS);
 273 extern Datum hashenum(PG_FUNCTION_ARGS);
 274 extern Datum hashfloat4(PG_FUNCTION_ARGS);
 275 extern Datum hashfloat8(PG_FUNCTION_ARGS);
 276 extern Datum hashoidvector(PG_FUNCTION_ARGS);
 277 extern Datum hashint2vector(PG_FUNCTION_ARGS);
 278 extern Datum hashname(PG_FUNCTION_ARGS);
 279 extern Datum hashtext(PG_FUNCTION_ARGS);
 280 extern Datum hashvarlena(PG_FUNCTION_ARGS);
 281 extern Datum hash_any(register const unsigned char *k, register int keylen);
 282 extern Datum hash_uint32(uint32 k);
 283
 284 /* private routines */
 285
 286 /* hashinsert.c */
 287 extern void _hash_doinsert(Relation rel, IndexTuple itup);
 288 extern OffsetNumber _hash_pgaddtup(Relation rel, Buffer buf,
 289                            Size itemsize, IndexTuple itup);
 290
 291 /* hashovfl.c */
 292 extern Buffer _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf);
 293 extern BlockNumber _hash_freeovflpage(Relation rel, Buffer ovflbuf,
 294                                    BufferAccessStrategy bstrategy);
 295 extern void _hash_initbitmap(Relation rel, HashMetaPage metap,
 296                                  BlockNumber blkno, ForkNumber forkNum);
 297 extern void _hash_squeezebucket(Relation rel,
 298                                         Bucket bucket, BlockNumber bucket_blkno,
 299                                         BufferAccessStrategy bstrategy);
 300
 301 /* hashpage.c */
 302 extern void _hash_getlock(Relation rel, BlockNumber whichlock, int access);
 303 extern bool _hash_try_getlock(Relation rel, BlockNumber whichlock, int access);
 304 extern void _hash_droplock(Relation rel, BlockNumber whichlock, int access);
 305 extern Buffer _hash_getbuf(Relation rel, BlockNumber blkno,
 306                          int access, int flags);
 307 extern Buffer _hash_getinitbuf(Relation rel, BlockNumber blkno);
 308 extern Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno,
 309                                 ForkNumber forkNum);
 310 extern Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno,
 311                                                    int access, int flags,
 312                                                    BufferAccessStrategy bstrategy);
 313 extern void _hash_relbuf(Relation rel, Buffer buf);
 314 extern void _hash_dropbuf(Relation rel, Buffer buf);
 315 extern void _hash_wrtbuf(Relation rel, Buffer buf);
 316 extern void _hash_chgbufaccess(Relation rel, Buffer buf, int from_access,
 317                                    int to_access);
 318 extern uint32 _hash_metapinit(Relation rel, double num_tuples,
 319                                 ForkNumber forkNum);
 320 extern void _hash_pageinit(Page page, Size size);
 321 extern void _hash_expandtable(Relation rel, Buffer metabuf);
 322
 323 /* hashscan.c */
 324 extern void _hash_regscan(IndexScanDesc scan);
 325 extern void _hash_dropscan(IndexScanDesc scan);
 326 extern bool _hash_has_active_scan(Relation rel, Bucket bucket);
 327 extern void ReleaseResources_hash(void);
 328
 329 /* hashsearch.c */
 330 extern bool _hash_next(IndexScanDesc scan, ScanDirection dir);
 331 extern bool _hash_first(IndexScanDesc scan, ScanDirection dir);
 332 extern bool _hash_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir);
 333
 334 /* hashsort.c */
 335 typedef struct HSpool HSpool;   /* opaque struct in hashsort.c */
 336
 337 extern HSpool *_h_spoolinit(Relation heap, Relation index, uint32 num_buckets);
 338 extern void _h_spooldestroy(HSpool *hspool);
 339 extern void _h_spool(IndexTuple itup, HSpool *hspool);
 340 extern void _h_indexbuild(HSpool *hspool);
 341
 342 /* hashutil.c */
 343 extern bool _hash_checkqual(IndexScanDesc scan, IndexTuple itup);
 344 extern uint32 _hash_datum2hashkey(Relation rel, Datum key);
 345 extern uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype);
 346 extern Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
 347                                          uint32 highmask, uint32 lowmask);
 348 extern uint32 _hash_log2(uint32 num);
 349 extern void _hash_checkpage(Relation rel, Buffer buf, int flags);
 350 extern uint32 _hash_get_indextuple_hashkey(IndexTuple itup);
 351 extern IndexTuple _hash_form_tuple(Relation index,
 352                                  Datum *values, bool *isnull);
 353 extern OffsetNumber _hash_binsearch(Page page, uint32 hash_value);
 354 extern OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value);
 355
 356 /* hash.c */
 357 extern void hash_redo(XLogRecPtr lsn, XLogRecord *record);
 358 extern void hash_desc(StringInfo buf, uint8 xl_info, char *rec);
 359
 360 #endif   /* HASH_H */