← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/access/hash/hashsearch.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/access/hash/hashsearch.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * hashsearch.c
 
4
 *        search code for postgres hash tables
 
5
 *
 
6
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 *
 
10
 * IDENTIFICATION
 
11
 *        $PostgreSQL: pgsql/src/backend/access/hash/hashsearch.c,v 1.38 2004-12-31 21:59:13 pgsql Exp $
 
12
 *
 
13
 *-------------------------------------------------------------------------
 
14
 */
 
15
#include "postgres.h"
 
16
 
 
17
#include "access/hash.h"
 
18
#include "storage/lmgr.h"
 
19
 
 
20
 
 
21
/*
 
22
 *      _hash_next() -- Get the next item in a scan.
 
23
 *
 
24
 *              On entry, we have a valid currentItemData in the scan, and a
 
25
 *              pin and read lock on the page that contains that item.
 
26
 *              We find the next item in the scan, if any.
 
27
 *              On success exit, we have the page containing the next item
 
28
 *              pinned and locked.
 
29
 */
 
30
bool
 
31
_hash_next(IndexScanDesc scan, ScanDirection dir)
 
32
{
 
33
        Relation        rel = scan->indexRelation;
 
34
        HashScanOpaque so = (HashScanOpaque) scan->opaque;
 
35
        Buffer          buf;
 
36
        Page            page;
 
37
        OffsetNumber offnum;
 
38
        ItemPointer current;
 
39
        HashItem        hitem;
 
40
        IndexTuple      itup;
 
41
 
 
42
        /* we still have the buffer pinned and read-locked */
 
43
        buf = so->hashso_curbuf;
 
44
        Assert(BufferIsValid(buf));
 
45
 
 
46
        /*
 
47
         * step to next valid tuple.
 
48
         */
 
49
        if (!_hash_step(scan, &buf, dir))
 
50
                return false;
 
51
 
 
52
        /* if we're here, _hash_step found a valid tuple */
 
53
        current = &(scan->currentItemData);
 
54
        offnum = ItemPointerGetOffsetNumber(current);
 
55
        page = BufferGetPage(buf);
 
56
        _hash_checkpage(rel, page, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
 
57
        hitem = (HashItem) PageGetItem(page, PageGetItemId(page, offnum));
 
58
        itup = &hitem->hash_itup;
 
59
        scan->xs_ctup.t_self = itup->t_tid;
 
60
 
 
61
        return true;
 
62
}
 
63
 
 
64
/*
 
65
 * Advance to next page in a bucket, if any.
 
66
 */
 
67
static void
 
68
_hash_readnext(Relation rel,
 
69
                           Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
 
70
{
 
71
        BlockNumber blkno;
 
72
 
 
73
        blkno = (*opaquep)->hasho_nextblkno;
 
74
        _hash_relbuf(rel, *bufp);
 
75
        *bufp = InvalidBuffer;
 
76
        if (BlockNumberIsValid(blkno))
 
77
        {
 
78
                *bufp = _hash_getbuf(rel, blkno, HASH_READ);
 
79
                *pagep = BufferGetPage(*bufp);
 
80
                _hash_checkpage(rel, *pagep, LH_OVERFLOW_PAGE);
 
81
                *opaquep = (HashPageOpaque) PageGetSpecialPointer(*pagep);
 
82
        }
 
83
}
 
84
 
 
85
/*
 
86
 * Advance to previous page in a bucket, if any.
 
87
 */
 
88
static void
 
89
_hash_readprev(Relation rel,
 
90
                           Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
 
91
{
 
92
        BlockNumber blkno;
 
93
 
 
94
        blkno = (*opaquep)->hasho_prevblkno;
 
95
        _hash_relbuf(rel, *bufp);
 
96
        *bufp = InvalidBuffer;
 
97
        if (BlockNumberIsValid(blkno))
 
98
        {
 
99
                *bufp = _hash_getbuf(rel, blkno, HASH_READ);
 
100
                *pagep = BufferGetPage(*bufp);
 
101
                _hash_checkpage(rel, *pagep, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
 
102
                *opaquep = (HashPageOpaque) PageGetSpecialPointer(*pagep);
 
103
        }
 
104
}
 
105
 
 
106
/*
 
107
 *      _hash_first() -- Find the first item in a scan.
 
108
 *
 
109
 *              Find the first item in the index that
 
110
 *              satisfies the qualification associated with the scan descriptor. On
 
111
 *              success, the page containing the current index tuple is read locked
 
112
 *              and pinned, and the scan's opaque data entry is updated to
 
113
 *              include the buffer.
 
114
 */
 
115
bool
 
116
_hash_first(IndexScanDesc scan, ScanDirection dir)
 
117
{
 
118
        Relation        rel = scan->indexRelation;
 
119
        HashScanOpaque so = (HashScanOpaque) scan->opaque;
 
120
        uint32          hashkey;
 
121
        Bucket          bucket;
 
122
        BlockNumber blkno;
 
123
        Buffer          buf;
 
124
        Buffer          metabuf;
 
125
        Page            page;
 
126
        HashPageOpaque opaque;
 
127
        HashMetaPage metap;
 
128
        HashItem        hitem;
 
129
        IndexTuple      itup;
 
130
        ItemPointer current;
 
131
        OffsetNumber offnum;
 
132
 
 
133
        current = &(scan->currentItemData);
 
134
        ItemPointerSetInvalid(current);
 
135
 
 
136
        /*
 
137
         * We do not support hash scans with no index qualification, because
 
138
         * we would have to read the whole index rather than just one bucket.
 
139
         * That creates a whole raft of problems, since we haven't got a
 
140
         * practical way to lock all the buckets against splits or
 
141
         * compactions.
 
142
         */
 
143
        if (scan->numberOfKeys < 1)
 
144
                ereport(ERROR,
 
145
                                (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 
146
                           errmsg("hash indexes do not support whole-index scans")));
 
147
 
 
148
        /*
 
149
         * If the constant in the index qual is NULL, assume it cannot match
 
150
         * any items in the index.
 
151
         */
 
152
        if (scan->keyData[0].sk_flags & SK_ISNULL)
 
153
                return false;
 
154
 
 
155
        /*
 
156
         * Okay to compute the hash key.  We want to do this before acquiring
 
157
         * any locks, in case a user-defined hash function happens to be slow.
 
158
         */
 
159
        hashkey = _hash_datum2hashkey(rel, scan->keyData[0].sk_argument);
 
160
 
 
161
        /*
 
162
         * Acquire shared split lock so we can compute the target bucket
 
163
         * safely (see README).
 
164
         */
 
165
        _hash_getlock(rel, 0, HASH_SHARE);
 
166
 
 
167
        /* Read the metapage */
 
168
        metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ);
 
169
        metap = (HashMetaPage) BufferGetPage(metabuf);
 
170
        _hash_checkpage(rel, (Page) metap, LH_META_PAGE);
 
171
 
 
172
        /*
 
173
         * Compute the target bucket number, and convert to block number.
 
174
         */
 
175
        bucket = _hash_hashkey2bucket(hashkey,
 
176
                                                                  metap->hashm_maxbucket,
 
177
                                                                  metap->hashm_highmask,
 
178
                                                                  metap->hashm_lowmask);
 
179
 
 
180
        blkno = BUCKET_TO_BLKNO(metap, bucket);
 
181
 
 
182
        /* done with the metapage */
 
183
        _hash_relbuf(rel, metabuf);
 
184
 
 
185
        /*
 
186
         * Acquire share lock on target bucket; then we can release split
 
187
         * lock.
 
188
         */
 
189
        _hash_getlock(rel, blkno, HASH_SHARE);
 
190
 
 
191
        _hash_droplock(rel, 0, HASH_SHARE);
 
192
 
 
193
        /* Update scan opaque state to show we have lock on the bucket */
 
194
        so->hashso_bucket = bucket;
 
195
        so->hashso_bucket_valid = true;
 
196
        so->hashso_bucket_blkno = blkno;
 
197
 
 
198
        /* Fetch the primary bucket page for the bucket */
 
199
        buf = _hash_getbuf(rel, blkno, HASH_READ);
 
200
        page = BufferGetPage(buf);
 
201
        _hash_checkpage(rel, page, LH_BUCKET_PAGE);
 
202
        opaque = (HashPageOpaque) PageGetSpecialPointer(page);
 
203
        Assert(opaque->hasho_bucket == bucket);
 
204
 
 
205
        /* If a backwards scan is requested, move to the end of the chain */
 
206
        if (ScanDirectionIsBackward(dir))
 
207
        {
 
208
                while (BlockNumberIsValid(opaque->hasho_nextblkno))
 
209
                        _hash_readnext(rel, &buf, &page, &opaque);
 
210
        }
 
211
 
 
212
        /* Now find the first tuple satisfying the qualification */
 
213
        if (!_hash_step(scan, &buf, dir))
 
214
                return false;
 
215
 
 
216
        /* if we're here, _hash_step found a valid tuple */
 
217
        offnum = ItemPointerGetOffsetNumber(current);
 
218
        page = BufferGetPage(buf);
 
219
        _hash_checkpage(rel, page, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
 
220
        hitem = (HashItem) PageGetItem(page, PageGetItemId(page, offnum));
 
221
        itup = &hitem->hash_itup;
 
222
        scan->xs_ctup.t_self = itup->t_tid;
 
223
 
 
224
        return true;
 
225
}
 
226
 
 
227
/*
 
228
 *      _hash_step() -- step to the next valid item in a scan in the bucket.
 
229
 *
 
230
 *              If no valid record exists in the requested direction, return
 
231
 *              false.  Else, return true and set the CurrentItemData for the
 
232
 *              scan to the right thing.
 
233
 *
 
234
 *              'bufP' points to the current buffer, which is pinned and read-locked.
 
235
 *              On success exit, we have pin and read-lock on whichever page
 
236
 *              contains the right item; on failure, we have released all buffers.
 
237
 */
 
238
bool
 
239
_hash_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
 
240
{
 
241
        Relation        rel = scan->indexRelation;
 
242
        HashScanOpaque so = (HashScanOpaque) scan->opaque;
 
243
        ItemPointer current;
 
244
        Buffer          buf;
 
245
        Page            page;
 
246
        HashPageOpaque opaque;
 
247
        OffsetNumber maxoff;
 
248
        OffsetNumber offnum;
 
249
        Bucket          bucket;
 
250
        BlockNumber blkno;
 
251
        HashItem        hitem;
 
252
        IndexTuple      itup;
 
253
 
 
254
        current = &(scan->currentItemData);
 
255
 
 
256
        buf = *bufP;
 
257
        page = BufferGetPage(buf);
 
258
        _hash_checkpage(rel, page, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
 
259
        opaque = (HashPageOpaque) PageGetSpecialPointer(page);
 
260
        bucket = opaque->hasho_bucket;
 
261
 
 
262
        /*
 
263
         * If _hash_step is called from _hash_first, current will not be
 
264
         * valid, so we can't dereference it.  However, in that case, we
 
265
         * presumably want to start at the beginning/end of the page...
 
266
         */
 
267
        maxoff = PageGetMaxOffsetNumber(page);
 
268
        if (ItemPointerIsValid(current))
 
269
                offnum = ItemPointerGetOffsetNumber(current);
 
270
        else
 
271
                offnum = InvalidOffsetNumber;
 
272
 
 
273
        /*
 
274
         * 'offnum' now points to the last tuple we have seen (if any).
 
275
         *
 
276
         * continue to step through tuples until: 1) we get to the end of the
 
277
         * bucket chain or 2) we find a valid tuple.
 
278
         */
 
279
        do
 
280
        {
 
281
                switch (dir)
 
282
                {
 
283
                        case ForwardScanDirection:
 
284
                                if (offnum != InvalidOffsetNumber)
 
285
                                        offnum = OffsetNumberNext(offnum);      /* move forward */
 
286
                                else
 
287
                                        offnum = FirstOffsetNumber; /* new page */
 
288
 
 
289
                                while (offnum > maxoff)
 
290
                                {
 
291
                                        /*
 
292
                                         * either this page is empty (maxoff ==
 
293
                                         * InvalidOffsetNumber) or we ran off the end.
 
294
                                         */
 
295
                                        _hash_readnext(rel, &buf, &page, &opaque);
 
296
                                        if (BufferIsValid(buf))
 
297
                                        {
 
298
                                                maxoff = PageGetMaxOffsetNumber(page);
 
299
                                                offnum = FirstOffsetNumber;
 
300
                                        }
 
301
                                        else
 
302
                                        {
 
303
                                                /* end of bucket */
 
304
                                                maxoff = offnum = InvalidOffsetNumber;
 
305
                                                break;  /* exit while */
 
306
                                        }
 
307
                                }
 
308
                                break;
 
309
 
 
310
                        case BackwardScanDirection:
 
311
                                if (offnum != InvalidOffsetNumber)
 
312
                                        offnum = OffsetNumberPrev(offnum);      /* move back */
 
313
                                else
 
314
                                        offnum = maxoff;        /* new page */
 
315
 
 
316
                                while (offnum < FirstOffsetNumber)
 
317
                                {
 
318
                                        /*
 
319
                                         * either this page is empty (offnum ==
 
320
                                         * InvalidOffsetNumber) or we ran off the end.
 
321
                                         */
 
322
                                        _hash_readprev(rel, &buf, &page, &opaque);
 
323
                                        if (BufferIsValid(buf))
 
324
                                                maxoff = offnum = PageGetMaxOffsetNumber(page);
 
325
                                        else
 
326
                                        {
 
327
                                                /* end of bucket */
 
328
                                                maxoff = offnum = InvalidOffsetNumber;
 
329
                                                break;  /* exit while */
 
330
                                        }
 
331
                                }
 
332
                                break;
 
333
 
 
334
                        default:
 
335
                                /* NoMovementScanDirection */
 
336
                                /* this should not be reached */
 
337
                                break;
 
338
                }
 
339
 
 
340
                /* we ran off the end of the world without finding a match */
 
341
                if (offnum == InvalidOffsetNumber)
 
342
                {
 
343
                        *bufP = so->hashso_curbuf = InvalidBuffer;
 
344
                        ItemPointerSetInvalid(current);
 
345
                        return false;
 
346
                }
 
347
 
 
348
                /* get ready to check this tuple */
 
349
                hitem = (HashItem) PageGetItem(page, PageGetItemId(page, offnum));
 
350
                itup = &hitem->hash_itup;
 
351
        } while (!_hash_checkqual(scan, itup));
 
352
 
 
353
        /* if we made it to here, we've found a valid tuple */
 
354
        blkno = BufferGetBlockNumber(buf);
 
355
        *bufP = so->hashso_curbuf = buf;
 
356
        ItemPointerSet(current, blkno, offnum);
 
357
        return true;
 
358
}