PostgreSQL Source Code git master
hash.h
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * hash.h
4 * header file for postgres hash access method implementation
5 *
6 *
7 * Portions Copyright (c) 1996-2025, 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/amapi.h"
21#include "access/itup.h"
22#include "access/sdir.h"
23#include "catalog/pg_am_d.h"
24#include "common/hashfn.h"
25#include "lib/stringinfo.h"
26#include "storage/bufmgr.h"
27#include "storage/lockdefs.h"
28#include "utils/hsearch.h"
29#include "utils/relcache.h"
30
31/*
32 * Mapping from hash bucket number to physical block number of bucket's
33 * starting page. Beware of multiple evaluations of argument!
34 */
35typedef uint32 Bucket;
36
37#define InvalidBucket ((Bucket) 0xFFFFFFFF)
38
39#define BUCKET_TO_BLKNO(metap,B) \
40 ((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_spareindex((B)+1)-1] : 0)) + 1)
41
42/*
43 * Special space for hash index pages.
44 *
45 * hasho_flag's LH_PAGE_TYPE bits tell us which type of page we're looking at.
46 * Additional bits in the flag word are used for more transient purposes.
47 *
48 * To test a page's type, do (hasho_flag & LH_PAGE_TYPE) == LH_xxx_PAGE.
49 * However, we ensure that each used page type has a distinct bit so that
50 * we can OR together page types for uses such as the allowable-page-types
51 * argument of _hash_checkpage().
52 */
53#define LH_UNUSED_PAGE (0)
54#define LH_OVERFLOW_PAGE (1 << 0)
55#define LH_BUCKET_PAGE (1 << 1)
56#define LH_BITMAP_PAGE (1 << 2)
57#define LH_META_PAGE (1 << 3)
58#define LH_BUCKET_BEING_POPULATED (1 << 4)
59#define LH_BUCKET_BEING_SPLIT (1 << 5)
60#define LH_BUCKET_NEEDS_SPLIT_CLEANUP (1 << 6)
61#define LH_PAGE_HAS_DEAD_TUPLES (1 << 7)
62
63#define LH_PAGE_TYPE \
64 (LH_OVERFLOW_PAGE | LH_BUCKET_PAGE | LH_BITMAP_PAGE | LH_META_PAGE)
65
66/*
67 * In an overflow page, hasho_prevblkno stores the block number of the previous
68 * page in the bucket chain; in a bucket page, hasho_prevblkno stores the
69 * hashm_maxbucket value as of the last time the bucket was last split, or
70 * else as of the time the bucket was created. The latter convention is used
71 * to determine whether a cached copy of the metapage is too stale to be used
72 * without needing to lock or pin the metapage.
73 *
74 * hasho_nextblkno is always the block number of the next page in the
75 * bucket chain, or InvalidBlockNumber if there are no more such pages.
76 */
77typedef struct HashPageOpaqueData
78{
81 Bucket hasho_bucket; /* bucket number this pg belongs to */
82 uint16 hasho_flag; /* page type code + flag bits, see above */
83 uint16 hasho_page_id; /* for identification of hash indexes */
85
87
88#define HashPageGetOpaque(page) ((HashPageOpaque) PageGetSpecialPointer(page))
89
90#define H_NEEDS_SPLIT_CLEANUP(opaque) (((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)
91#define H_BUCKET_BEING_SPLIT(opaque) (((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)
92#define H_BUCKET_BEING_POPULATED(opaque) (((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)
93#define H_HAS_DEAD_TUPLES(opaque) (((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)
94
95/*
96 * The page ID is for the convenience of pg_filedump and similar utilities,
97 * which otherwise would have a hard time telling pages of different index
98 * types apart. It should be the last 2 bytes on the page. This is more or
99 * less "free" due to alignment considerations.
100 */
101#define HASHO_PAGE_ID 0xFF80
102
103typedef struct HashScanPosItem /* what we remember about each match */
104{
105 ItemPointerData heapTid; /* TID of referenced heap item */
106 OffsetNumber indexOffset; /* index item's location within page */
108
109typedef struct HashScanPosData
110{
111 Buffer buf; /* if valid, the buffer is pinned */
112 BlockNumber currPage; /* current hash index page */
113 BlockNumber nextPage; /* next overflow page */
114 BlockNumber prevPage; /* prev overflow or bucket page */
115
116 /*
117 * The items array is always ordered in index order (ie, increasing
118 * indexoffset). When scanning backwards it is convenient to fill the
119 * array back-to-front, so we start at the last slot and fill downwards.
120 * Hence we need both a first-valid-entry and a last-valid-entry counter.
121 * itemIndex is a cursor showing which entry was last returned to caller.
122 */
123 int firstItem; /* first valid index in items[] */
124 int lastItem; /* last valid index in items[] */
125 int itemIndex; /* current index in items[] */
126
129
130#define HashScanPosIsPinned(scanpos) \
131( \
132 AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
133 !BufferIsValid((scanpos).buf)), \
134 BufferIsValid((scanpos).buf) \
135)
136
137#define HashScanPosIsValid(scanpos) \
138( \
139 AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
140 !BufferIsValid((scanpos).buf)), \
141 BlockNumberIsValid((scanpos).currPage) \
142)
143
144#define HashScanPosInvalidate(scanpos) \
145 do { \
146 (scanpos).buf = InvalidBuffer; \
147 (scanpos).currPage = InvalidBlockNumber; \
148 (scanpos).nextPage = InvalidBlockNumber; \
149 (scanpos).prevPage = InvalidBlockNumber; \
150 (scanpos).firstItem = 0; \
151 (scanpos).lastItem = 0; \
152 (scanpos).itemIndex = 0; \
153 } while (0)
154
155/*
156 * HashScanOpaqueData is private state for a hash index scan.
157 */
158typedef struct HashScanOpaqueData
159{
160 /* Hash value of the scan key, ie, the hash key we seek */
162
163 /* remember the buffer associated with primary bucket */
165
166 /*
167 * remember the buffer associated with primary bucket page of bucket being
168 * split. it is required during the scan of the bucket which is being
169 * populated during split operation.
170 */
172
173 /* Whether scan starts on bucket being populated due to split */
175
176 /*
177 * Whether scanning bucket being split? The value of this parameter is
178 * referred only when hashso_buc_populated is true.
179 */
181 /* info about killed items if any (killedItems is NULL if never used) */
182 int *killedItems; /* currPos.items indexes of killed items */
183 int numKilled; /* number of currently stored items */
184
185 /*
186 * Identify all the matching items on a page and save them in
187 * HashScanPosData
188 */
189 HashScanPosData currPos; /* current position data */
191
193
194/*
195 * Definitions for metapage.
196 */
197
198#define HASH_METAPAGE 0 /* metapage is always block 0 */
199
200#define HASH_MAGIC 0x6440640
201#define HASH_VERSION 4
202
203/*
204 * spares[] holds the number of overflow pages currently allocated at or
205 * before a certain splitpoint. For example, if spares[3] = 7 then there are
206 * 7 ovflpages before splitpoint 3 (compare BUCKET_TO_BLKNO macro). The
207 * value in spares[ovflpoint] increases as overflow pages are added at the
208 * end of the index. Once ovflpoint increases (ie, we have actually allocated
209 * the bucket pages belonging to that splitpoint) the number of spares at the
210 * prior splitpoint cannot change anymore.
211 *
212 * ovflpages that have been recycled for reuse can be found by looking at
213 * bitmaps that are stored within ovflpages dedicated for the purpose.
214 * The blknos of these bitmap pages are kept in mapp[]; nmaps is the
215 * number of currently existing bitmaps.
216 *
217 * The limitation on the size of spares[] comes from the fact that there's
218 * no point in having more than 2^32 buckets with only uint32 hashcodes.
219 * (Note: The value of HASH_MAX_SPLITPOINTS which is the size of spares[] is
220 * adjusted in such a way to accommodate multi phased allocation of buckets
221 * after HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE).
222 *
223 * There is no particular upper limit on the size of mapp[], other than
224 * needing to fit into the metapage. (With 8K block size, 1024 bitmaps
225 * limit us to 256 GB of overflow space...). For smaller block size we
226 * can not use 1024 bitmaps as it will lead to the meta page data crossing
227 * the block size boundary. So we use BLCKSZ to determine the maximum number
228 * of bitmaps.
229 */
230#define HASH_MAX_BITMAPS Min(BLCKSZ / 8, 1024)
231
232#define HASH_SPLITPOINT_PHASE_BITS 2
233#define HASH_SPLITPOINT_PHASES_PER_GRP (1 << HASH_SPLITPOINT_PHASE_BITS)
234#define HASH_SPLITPOINT_PHASE_MASK (HASH_SPLITPOINT_PHASES_PER_GRP - 1)
235#define HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE 10
236
237/* defines max number of splitpoint phases a hash index can have */
238#define HASH_MAX_SPLITPOINT_GROUP 32
239#define HASH_MAX_SPLITPOINTS \
240 (((HASH_MAX_SPLITPOINT_GROUP - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) * \
241 HASH_SPLITPOINT_PHASES_PER_GRP) + \
242 HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
243
244typedef struct HashMetaPageData
245{
246 uint32 hashm_magic; /* magic no. for hash tables */
247 uint32 hashm_version; /* version ID */
248 double hashm_ntuples; /* number of tuples stored in the table */
249 uint16 hashm_ffactor; /* target fill factor (tuples/bucket) */
250 uint16 hashm_bsize; /* index page size (bytes) */
251 uint16 hashm_bmsize; /* bitmap array size (bytes) - must be a power
252 * of 2 */
253 uint16 hashm_bmshift; /* log2(bitmap array size in BITS) */
254 uint32 hashm_maxbucket; /* ID of maximum bucket in use */
255 uint32 hashm_highmask; /* mask to modulo into entire table */
256 uint32 hashm_lowmask; /* mask to modulo into lower half of table */
257 uint32 hashm_ovflpoint; /* splitpoint from which ovflpage being
258 * allocated */
259 uint32 hashm_firstfree; /* lowest-number free ovflpage (bit#) */
260 uint32 hashm_nmaps; /* number of bitmap pages */
261 RegProcedure hashm_procid; /* hash function id from pg_proc */
262 uint32 hashm_spares[HASH_MAX_SPLITPOINTS]; /* spare pages before each
263 * splitpoint */
264 BlockNumber hashm_mapp[HASH_MAX_BITMAPS]; /* blknos of ovfl bitmaps */
266
268
269typedef struct HashOptions
270{
271 int32 varlena_header_; /* varlena header (do not touch directly!) */
272 int fillfactor; /* page fill factor in percent (0..100) */
274
275#define HashGetFillFactor(relation) \
276 (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
277 relation->rd_rel->relam == HASH_AM_OID), \
278 (relation)->rd_options ? \
279 ((HashOptions *) (relation)->rd_options)->fillfactor : \
280 HASH_DEFAULT_FILLFACTOR)
281#define HashGetTargetPageUsage(relation) \
282 (BLCKSZ * HashGetFillFactor(relation) / 100)
283
284/*
285 * Maximum size of a hash index item (it's okay to have only one per page)
286 */
287#define HashMaxItemSize(page) \
288 MAXALIGN_DOWN(PageGetPageSize(page) - \
289 SizeOfPageHeaderData - \
290 sizeof(ItemIdData) - \
291 MAXALIGN(sizeof(HashPageOpaqueData)))
292
293#define INDEX_MOVED_BY_SPLIT_MASK INDEX_AM_RESERVED_BIT
294
295#define HASH_MIN_FILLFACTOR 10
296#define HASH_DEFAULT_FILLFACTOR 75
297
298/*
299 * Constants
300 */
301#define BYTE_TO_BIT 3 /* 2^3 bits/byte */
302#define ALL_SET ((uint32) ~0)
303
304/*
305 * Bitmap pages do not contain tuples. They do contain the standard
306 * page headers and trailers; however, everything in between is a
307 * giant bit array. The number of bits that fit on a page obviously
308 * depends on the page size and the header/trailer overhead. We require
309 * the number of bits per page to be a power of 2.
310 */
311#define BMPGSZ_BYTE(metap) ((metap)->hashm_bmsize)
312#define BMPGSZ_BIT(metap) ((metap)->hashm_bmsize << BYTE_TO_BIT)
313#define BMPG_SHIFT(metap) ((metap)->hashm_bmshift)
314#define BMPG_MASK(metap) (BMPGSZ_BIT(metap) - 1)
315
316#define HashPageGetBitmap(page) \
317 ((uint32 *) PageGetContents(page))
318
319#define HashGetMaxBitmapSize(page) \
320 (PageGetPageSize((Page) page) - \
321 (MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(HashPageOpaqueData))))
322
323#define HashPageGetMeta(page) \
324 ((HashMetaPage) PageGetContents(page))
325
326/*
327 * The number of bits in an ovflpage bitmap word.
328 */
329#define BITS_PER_MAP 32 /* Number of bits in uint32 */
330
331/* Given the address of the beginning of a bit map, clear/set the nth bit */
332#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
333#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
334#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
335
336/*
337 * page-level and high-level locking modes (see README)
338 */
339#define HASH_READ BUFFER_LOCK_SHARE
340#define HASH_WRITE BUFFER_LOCK_EXCLUSIVE
341#define HASH_NOLOCK (-1)
342
343/*
344 * When a new operator class is declared, we require that the user supply
345 * us with an amproc function for hashing a key of the new type, returning
346 * a 32-bit hash value. We call this the "standard" hash function. We
347 * also allow an optional "extended" hash function which accepts a salt and
348 * returns a 64-bit hash value. This is highly recommended but, for reasons
349 * of backward compatibility, optional.
350 *
351 * When the salt is 0, the low 32 bits of the value returned by the extended
352 * hash function should match the value that would have been returned by the
353 * standard hash function.
354 */
355#define HASHSTANDARD_PROC 1
356#define HASHEXTENDED_PROC 2
357#define HASHOPTIONS_PROC 3
358#define HASHNProcs 3
359
360
361/* public routines */
362
364 struct IndexInfo *indexInfo);
365extern void hashbuildempty(Relation index);
366extern bool hashinsert(Relation rel, Datum *values, bool *isnull,
367 ItemPointer ht_ctid, Relation heapRel,
368 IndexUniqueCheck checkUnique,
369 bool indexUnchanged,
370 struct IndexInfo *indexInfo);
371extern bool hashgettuple(IndexScanDesc scan, ScanDirection dir);
372extern int64 hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
373extern IndexScanDesc hashbeginscan(Relation rel, int nkeys, int norderbys);
374extern void hashrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
375 ScanKey orderbys, int norderbys);
376extern void hashendscan(IndexScanDesc scan);
380 void *callback_state);
382 IndexBulkDeleteResult *stats);
383extern bytea *hashoptions(Datum reloptions, bool validate);
384extern bool hashvalidate(Oid opclassoid);
385extern void hashadjustmembers(Oid opfamilyoid,
386 Oid opclassoid,
387 List *operators,
388 List *functions);
389
390extern CompareType hashtranslatestrategy(StrategyNumber strategy, Oid opfamily, Oid opcintype);
391extern StrategyNumber hashtranslatecmptype(CompareType cmptype, Oid opfamily, Oid opcintype);
392
393/* private routines */
394
395/* hashinsert.c */
396extern void _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel,
397 bool sorted);
399 Size itemsize, IndexTuple itup,
400 bool appendtup);
401extern void _hash_pgaddmultitup(Relation rel, Buffer buf, IndexTuple *itups,
402 OffsetNumber *itup_offsets, uint16 nitups);
403
404/* hashovfl.c */
405extern Buffer _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf, bool retain_pin);
406extern BlockNumber _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer ovflbuf,
407 Buffer wbuf, IndexTuple *itups, OffsetNumber *itup_offsets,
408 Size *tups_size, uint16 nitups, BufferAccessStrategy bstrategy);
409extern void _hash_initbitmapbuffer(Buffer buf, uint16 bmsize, bool initpage);
410extern void _hash_squeezebucket(Relation rel,
411 Bucket bucket, BlockNumber bucket_blkno,
412 Buffer bucket_buf,
413 BufferAccessStrategy bstrategy);
415
416/* hashpage.c */
417extern Buffer _hash_getbuf(Relation rel, BlockNumber blkno,
418 int access, int flags);
420 BlockNumber blkno, int flags);
422 bool force_refresh);
424 int access,
425 HashMetaPage *cachedmetap);
427extern void _hash_initbuf(Buffer buf, uint32 max_bucket, uint32 num_bucket,
428 uint32 flag, bool initpage);
430 ForkNumber forkNum);
432 int access, int flags,
433 BufferAccessStrategy bstrategy);
434extern void _hash_relbuf(Relation rel, Buffer buf);
435extern void _hash_dropbuf(Relation rel, Buffer buf);
436extern void _hash_dropscanbuf(Relation rel, HashScanOpaque so);
437extern uint32 _hash_init(Relation rel, double num_tuples,
438 ForkNumber forkNum);
439extern void _hash_init_metabuffer(Buffer buf, double num_tuples,
440 RegProcedure procid, uint16 ffactor, bool initpage);
441extern void _hash_pageinit(Page page, Size size);
442extern void _hash_expandtable(Relation rel, Buffer metabuf);
443extern void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf,
444 Bucket obucket, uint32 maxbucket, uint32 highmask,
445 uint32 lowmask);
446
447/* hashsearch.c */
448extern bool _hash_next(IndexScanDesc scan, ScanDirection dir);
449extern bool _hash_first(IndexScanDesc scan, ScanDirection dir);
450
451/* hashsort.c */
452typedef struct HSpool HSpool; /* opaque struct in hashsort.c */
453
454extern HSpool *_h_spoolinit(Relation heap, Relation index, uint32 num_buckets);
455extern void _h_spooldestroy(HSpool *hspool);
456extern void _h_spool(HSpool *hspool, ItemPointer self,
457 const Datum *values, const bool *isnull);
458extern void _h_indexbuild(HSpool *hspool, Relation heapRel);
459
460/* hashutil.c */
461extern bool _hash_checkqual(IndexScanDesc scan, IndexTuple itup);
464extern Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
465 uint32 highmask, uint32 lowmask);
466extern uint32 _hash_spareindex(uint32 num_bucket);
467extern uint32 _hash_get_totalbuckets(uint32 splitpoint_phase);
468extern void _hash_checkpage(Relation rel, Buffer buf, int flags);
471 Datum *user_values, bool *user_isnull,
472 Datum *index_values, bool *index_isnull);
473extern OffsetNumber _hash_binsearch(Page page, uint32 hash_value);
474extern OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value);
478 uint32 lowmask, uint32 maxbucket);
479extern void _hash_kill_items(IndexScanDesc scan);
480
481/* hash.c */
482extern void hashbucketcleanup(Relation rel, Bucket cur_bucket,
483 Buffer bucket_buf, BlockNumber bucket_blkno,
484 BufferAccessStrategy bstrategy,
485 uint32 maxbucket, uint32 highmask, uint32 lowmask,
486 double *tuples_removed, double *num_index_tuples,
487 bool split_cleanup,
488 IndexBulkDeleteCallback callback, void *callback_state);
489
490#endif /* HASH_H */
uint32 BlockNumber
Definition: block.h:31
static Datum values[MAXATTR]
Definition: bootstrap.c:151
int Buffer
Definition: buf.h:23
PageData * Page
Definition: bufpage.h:82
int64_t int64
Definition: c.h:485
regproc RegProcedure
Definition: c.h:607
int32_t int32
Definition: c.h:484
uint16_t uint16
Definition: c.h:487
uint32_t uint32
Definition: c.h:488
size_t Size
Definition: c.h:562
CompareType
Definition: cmptype.h:32
bool(* IndexBulkDeleteCallback)(ItemPointer itemptr, void *state)
Definition: genam.h:89
IndexUniqueCheck
Definition: genam.h:118
void _h_spool(HSpool *hspool, ItemPointer self, const Datum *values, const bool *isnull)
Definition: hashsort.c:109
void _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel, bool sorted)
Definition: hashinsert.c:38
Buffer _hash_getinitbuf(Relation rel, BlockNumber blkno)
Definition: hashpage.c:135
#define HASH_MAX_BITMAPS
Definition: hash.h:230
bool _hash_first(IndexScanDesc scan, ScanDirection dir)
Definition: hashsearch.c:288
HashMetaPage _hash_getcachedmetap(Relation rel, Buffer *metabuf, bool force_refresh)
Definition: hashpage.c:1501
IndexBulkDeleteResult * hashvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
Definition: hash.c:648
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:86
void _hash_initbuf(Buffer buf, uint32 max_bucket, uint32 num_bucket, uint32 flag, bool initpage)
Definition: hashpage.c:157
void _hash_squeezebucket(Relation rel, Bucket bucket, BlockNumber bucket_blkno, Buffer bucket_buf, BufferAccessStrategy bstrategy)
Definition: hashovfl.c:842
uint32 _hash_spareindex(uint32 num_bucket)
Definition: hashutil.c:142
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:266
void _h_indexbuild(HSpool *hspool, Relation heapRel)
Definition: hashsort.c:120
void hashadjustmembers(Oid opfamilyoid, Oid opclassoid, List *operators, List *functions)
Definition: hashvalidate.c:263
BlockNumber _hash_get_newblock_from_oldbucket(Relation rel, Bucket old_bucket)
Definition: hashutil.c:461
uint32 _hash_get_totalbuckets(uint32 splitpoint_phase)
Definition: hashutil.c:174
StrategyNumber hashtranslatecmptype(CompareType cmptype, Oid opfamily, Oid opcintype)
Definition: hash.c:938
Buffer _hash_getbuf_with_condlock_cleanup(Relation rel, BlockNumber blkno, int flags)
Definition: hashpage.c:96
bool hashgettuple(IndexScanDesc scan, ScanDirection dir)
Definition: hash.c:287
struct HashScanPosData HashScanPosData
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:291
bool hashvalidate(Oid opclassoid)
Definition: hashvalidate.c:40
bool _hash_checkqual(IndexScanDesc scan, IndexTuple itup)
Definition: hashutil.c:31
struct HashScanPosItem HashScanPosItem
OffsetNumber _hash_pgaddtup(Relation rel, Buffer buf, Size itemsize, IndexTuple itup, bool appendtup)
Definition: hashinsert.c:274
#define HASH_MAX_SPLITPOINTS
Definition: hash.h:239
OffsetNumber _hash_binsearch(Page page, uint32 hash_value)
Definition: hashutil.c:350
uint32 _hash_datum2hashkey(Relation rel, Datum key)
Definition: hashutil.c:82
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:125
OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value)
Definition: hashutil.c:388
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:210
HSpool * _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
Definition: hashsort.c:60
void _hash_pageinit(Page page, Size size)
Definition: hashpage.c:596
Bucket _hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket, uint32 lowmask, uint32 maxbucket)
Definition: hashutil.c:494
uint32 _hash_init(Relation rel, double num_tuples, ForkNumber forkNum)
Definition: hashpage.c:327
bool hashinsert(Relation rel, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, struct IndexInfo *indexInfo)
Definition: hash.c:255
bool _hash_next(IndexScanDesc scan, ScanDirection dir)
Definition: hashsearch.c:48
void hashbuildempty(Relation index)
Definition: hash.c:205
IndexBuildResult * hashbuild(Relation heap, Relation index, struct IndexInfo *indexInfo)
Definition: hash.c:119
bytea * hashoptions(Datum reloptions, bool validate)
Definition: hashutil.c:275
IndexScanDesc hashbeginscan(Relation rel, int nkeys, int norderbys)
Definition: hash.c:371
void _hash_pgaddmultitup(Relation rel, Buffer buf, IndexTuple *itups, OffsetNumber *itup_offsets, uint16 nitups)
Definition: hashinsert.c:331
HashMetaPageData * HashMetaPage
Definition: hash.h:267
uint32 _hash_ovflblkno_to_bitno(HashMetaPage metap, BlockNumber ovflblkno)
Definition: hashovfl.c:62
BlockNumber _hash_get_oldblock_from_newbucket(Relation rel, Bucket new_bucket)
Definition: hashutil.c:422
void _hash_dropbuf(Relation rel, Buffer buf)
Definition: hashpage.c:277
IndexBulkDeleteResult * hashbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
Definition: hash.c:462
BlockNumber _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer ovflbuf, Buffer wbuf, IndexTuple *itups, OffsetNumber *itup_offsets, Size *tups_size, uint16 nitups, BufferAccessStrategy bstrategy)
Definition: hashovfl.c:490
void _hash_dropscanbuf(Relation rel, HashScanOpaque so)
Definition: hashpage.c:289
void _hash_initbitmapbuffer(Buffer buf, uint16 bmsize, bool initpage)
Definition: hashovfl.c:777
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:70
uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype)
Definition: hashutil.c:102
struct HashScanOpaqueData HashScanOpaqueData
struct HashMetaPageData HashMetaPageData
void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf, Bucket obucket, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashpage.c:1356
CompareType hashtranslatestrategy(StrategyNumber strategy, Oid opfamily, Oid opcintype)
Definition: hash.c:930
Buffer _hash_getbucketbuf_from_hashkey(Relation rel, uint32 hashkey, int access, HashMetaPage *cachedmetap)
Definition: hashpage.c:1559
void _hash_kill_items(IndexScanDesc scan)
Definition: hashutil.c:536
void _hash_init_metabuffer(Buffer buf, double num_tuples, RegProcedure procid, uint16 ffactor, bool initpage)
Definition: hashpage.c:498
uint32 Bucket
Definition: hash.h:35
void hashrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: hash.c:401
void hashendscan(IndexScanDesc scan)
Definition: hash.c:431
HashScanOpaqueData * HashScanOpaque
Definition: hash.h:192
Buffer _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf, bool retain_pin)
Definition: hashovfl.c:112
Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno, int access, int flags, BufferAccessStrategy bstrategy)
Definition: hashpage.c:239
Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno, ForkNumber forkNum)
Definition: hashpage.c:198
int64 hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: hash.c:339
void _hash_expandtable(Relation rel, Buffer metabuf)
Definition: hashpage.c:614
void _h_spooldestroy(HSpool *hspool)
Definition: hashsort.c:99
struct HashPageOpaqueData HashPageOpaqueData
bool _hash_convert_tuple(Relation index, Datum *user_values, bool *user_isnull, Datum *index_values, bool *index_isnull)
Definition: hashutil.c:318
struct HashOptions HashOptions
void hashbucketcleanup(Relation rel, Bucket cur_bucket, Buffer bucket_buf, BlockNumber bucket_blkno, BufferAccessStrategy bstrategy, uint32 maxbucket, uint32 highmask, uint32 lowmask, double *tuples_removed, double *num_index_tuples, bool split_cleanup, IndexBulkDeleteCallback callback, void *callback_state)
Definition: hash.c:687
#define MaxIndexTuplesPerPage
Definition: itup.h:181
uint16 OffsetNumber
Definition: off.h:24
static char * buf
Definition: pg_test_fsync.c:72
uintptr_t Datum
Definition: postgres.h:69
unsigned int Oid
Definition: postgres_ext.h:32
short access
Definition: preproc-type.c:36
static const struct fns functions
Definition: regcomp.c:358
ForkNumber
Definition: relpath.h:56
ScanDirection
Definition: sdir.h:25
static pg_noinline void Size size
Definition: slab.c:607
uint16 StrategyNumber
Definition: stratnum.h:22
uint32 hashm_version
Definition: hash.h:247
BlockNumber hashm_mapp[HASH_MAX_BITMAPS]
Definition: hash.h:264
uint32 hashm_lowmask
Definition: hash.h:256
uint32 hashm_maxbucket
Definition: hash.h:254
RegProcedure hashm_procid
Definition: hash.h:261
uint32 hashm_spares[HASH_MAX_SPLITPOINTS]
Definition: hash.h:262
double hashm_ntuples
Definition: hash.h:248
uint32 hashm_firstfree
Definition: hash.h:259
uint16 hashm_bmsize
Definition: hash.h:251
uint16 hashm_bsize
Definition: hash.h:250
uint32 hashm_ovflpoint
Definition: hash.h:257
uint32 hashm_highmask
Definition: hash.h:255
uint32 hashm_magic
Definition: hash.h:246
uint16 hashm_bmshift
Definition: hash.h:253
uint32 hashm_nmaps
Definition: hash.h:260
uint16 hashm_ffactor
Definition: hash.h:249
int fillfactor
Definition: hash.h:272
int32 varlena_header_
Definition: hash.h:271
BlockNumber hasho_nextblkno
Definition: hash.h:80
uint16 hasho_flag
Definition: hash.h:82
BlockNumber hasho_prevblkno
Definition: hash.h:79
uint16 hasho_page_id
Definition: hash.h:83
Bucket hasho_bucket
Definition: hash.h:81
bool hashso_buc_split
Definition: hash.h:180
HashScanPosData currPos
Definition: hash.h:189
bool hashso_buc_populated
Definition: hash.h:174
Buffer hashso_split_bucket_buf
Definition: hash.h:171
Buffer hashso_bucket_buf
Definition: hash.h:164
int * killedItems
Definition: hash.h:182
uint32 hashso_sk_hash
Definition: hash.h:161
BlockNumber prevPage
Definition: hash.h:114
BlockNumber nextPage
Definition: hash.h:113
BlockNumber currPage
Definition: hash.h:112
HashScanPosItem items[MaxIndexTuplesPerPage]
Definition: hash.h:127
int lastItem
Definition: hash.h:124
int firstItem
Definition: hash.h:123
Buffer buf
Definition: hash.h:111
int itemIndex
Definition: hash.h:125
ItemPointerData heapTid
Definition: hash.h:105
OffsetNumber indexOffset
Definition: hash.h:106
Definition: pg_list.h:54
Definition: type.h:96
Definition: c.h:644
char * flag(int b)
Definition: test-ctype.c:33
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:46