← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/include/access/hash.h

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

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