Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * tidstore.c
4 : : * TID (ItemPointerData) storage implementation.
5 : : *
6 : : * TidStore is a in-memory data structure to store TIDs (ItemPointerData).
7 : : * Internally it uses a radix tree as the storage for TIDs. The key is the
8 : : * BlockNumber and the value is a bitmap of offsets, BlocktableEntry.
9 : : *
10 : : * TidStore can be shared among parallel worker processes by using
11 : : * TidStoreCreateShared(). Other backends can attach to the shared TidStore
12 : : * by TidStoreAttach().
13 : : *
14 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
15 : : * Portions Copyright (c) 1994, Regents of the University of California
16 : : *
17 : : * IDENTIFICATION
18 : : * src/backend/access/common/tidstore.c
19 : : *
20 : : *-------------------------------------------------------------------------
21 : : */
22 : : #include "postgres.h"
23 : :
24 : : #include "access/tidstore.h"
25 : : #include "miscadmin.h"
26 : : #include "nodes/bitmapset.h"
27 : : #include "storage/lwlock.h"
28 : : #include "utils/dsa.h"
29 : :
30 : :
31 : : #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
32 : : #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
33 : :
34 : : /* number of active words for a page: */
35 : : #define WORDS_PER_PAGE(n) ((n) / BITS_PER_BITMAPWORD + 1)
36 : :
37 : : /* number of offsets we can store in the header of a BlocktableEntry */
38 : : #define NUM_FULL_OFFSETS ((sizeof(uintptr_t) - sizeof(uint8) - sizeof(int8)) / sizeof(OffsetNumber))
39 : :
40 : : /*
41 : : * This is named similarly to PagetableEntry in tidbitmap.c
42 : : * because the two have a similar function.
43 : : */
44 : : typedef struct BlocktableEntry
45 : : {
46 : : struct
47 : : {
48 : : #ifndef WORDS_BIGENDIAN
49 : : /*
50 : : * We need to position this member to reserve space for the backing
51 : : * radix tree to tag the lowest bit when struct 'header' is stored
52 : : * inside a pointer or DSA pointer.
53 : : */
54 : : uint8 flags;
55 : :
56 : : int8 nwords;
57 : : #endif
58 : :
59 : : /*
60 : : * We can store a small number of offsets here to avoid wasting space
61 : : * with a sparse bitmap.
62 : : */
63 : : OffsetNumber full_offsets[NUM_FULL_OFFSETS];
64 : :
65 : : #ifdef WORDS_BIGENDIAN
66 : : int8 nwords;
67 : : uint8 flags;
68 : : #endif
69 : : } header;
70 : :
71 : : /*
72 : : * We don't expect any padding space here, but to be cautious, code
73 : : * creating new entries should zero out space up to 'words'.
74 : : */
75 : :
76 : : bitmapword words[FLEXIBLE_ARRAY_MEMBER];
77 : : } BlocktableEntry;
78 : :
79 : : /*
80 : : * The type of 'nwords' limits the max number of words in the 'words' array.
81 : : * This computes the max offset we can actually store in the bitmap. In
82 : : * practice, it's almost always the same as MaxOffsetNumber.
83 : : */
84 : : #define MAX_OFFSET_IN_BITMAP Min(BITS_PER_BITMAPWORD * PG_INT8_MAX - 1, MaxOffsetNumber)
85 : :
86 : : #define MaxBlocktableEntrySize \
87 : : offsetof(BlocktableEntry, words) + \
88 : : (sizeof(bitmapword) * WORDS_PER_PAGE(MAX_OFFSET_IN_BITMAP))
89 : :
90 : : #define RT_PREFIX local_ts
91 : : #define RT_SCOPE static
92 : : #define RT_DECLARE
93 : : #define RT_DEFINE
94 : : #define RT_VALUE_TYPE BlocktableEntry
95 : : #define RT_VARLEN_VALUE_SIZE(page) \
96 : : (offsetof(BlocktableEntry, words) + \
97 : : sizeof(bitmapword) * (page)->header.nwords)
98 : : #define RT_RUNTIME_EMBEDDABLE_VALUE
99 : : #include "lib/radixtree.h"
100 : :
101 : : #define RT_PREFIX shared_ts
102 : : #define RT_SHMEM
103 : : #define RT_SCOPE static
104 : : #define RT_DECLARE
105 : : #define RT_DEFINE
106 : : #define RT_VALUE_TYPE BlocktableEntry
107 : : #define RT_VARLEN_VALUE_SIZE(page) \
108 : : (offsetof(BlocktableEntry, words) + \
109 : : sizeof(bitmapword) * (page)->header.nwords)
110 : : #define RT_RUNTIME_EMBEDDABLE_VALUE
111 : : #include "lib/radixtree.h"
112 : :
113 : : /* Per-backend state for a TidStore */
114 : : struct TidStore
115 : : {
116 : : /* MemoryContext where the TidStore is allocated */
117 : : MemoryContext context;
118 : :
119 : : /* MemoryContext that the radix tree uses */
120 : : MemoryContext rt_context;
121 : :
122 : : /* Storage for TIDs. Use either one depending on TidStoreIsShared() */
123 : : union
124 : : {
125 : : local_ts_radix_tree *local;
126 : : shared_ts_radix_tree *shared;
127 : : } tree;
128 : :
129 : : /* DSA area for TidStore if using shared memory */
130 : : dsa_area *area;
131 : : };
132 : : #define TidStoreIsShared(ts) ((ts)->area != NULL)
133 : :
134 : : /* Iterator for TidStore */
135 : : struct TidStoreIter
136 : : {
137 : : TidStore *ts;
138 : :
139 : : /* iterator of radix tree. Use either one depending on TidStoreIsShared() */
140 : : union
141 : : {
142 : : shared_ts_iter *shared;
143 : : local_ts_iter *local;
144 : : } tree_iter;
145 : :
146 : : /* output for the caller */
147 : : TidStoreIterResult output;
148 : : };
149 : :
150 : : static void tidstore_iter_extract_tids(TidStoreIter *iter, BlockNumber blkno,
151 : : BlocktableEntry *page);
152 : :
153 : : /*
154 : : * Create a TidStore. The TidStore will live in the memory context that is
155 : : * CurrentMemoryContext at the time of this call. The TID storage, backed
156 : : * by a radix tree, will live in its child memory context, rt_context.
157 : : *
158 : : * "max_bytes" is not an internally-enforced limit; it is used only as a
159 : : * hint to cap the memory block size of the memory context for TID storage.
160 : : * This reduces space wastage due to over-allocation. If the caller wants to
161 : : * monitor memory usage, it must compare its limit with the value reported
162 : : * by TidStoreMemoryUsage().
163 : : */
164 : : TidStore *
7 john.naylor@postgres 165 :GNC 84227 : TidStoreCreateLocal(size_t max_bytes, bool insert_only)
166 : : {
167 : : TidStore *ts;
24 msawada@postgresql.o 168 : 84227 : size_t initBlockSize = ALLOCSET_DEFAULT_INITSIZE;
169 : 84227 : size_t minContextSize = ALLOCSET_DEFAULT_MINSIZE;
170 : 84227 : size_t maxBlockSize = ALLOCSET_DEFAULT_MAXSIZE;
171 : :
172 : 84227 : ts = palloc0(sizeof(TidStore));
173 : 84227 : ts->context = CurrentMemoryContext;
174 : :
175 : : /* choose the maxBlockSize to be no larger than 1/16 of max_bytes */
19 176 [ + + ]: 168459 : while (16 * maxBlockSize > max_bytes)
24 177 : 84232 : maxBlockSize >>= 1;
178 : :
179 [ - + ]: 84227 : if (maxBlockSize < ALLOCSET_DEFAULT_INITSIZE)
24 msawada@postgresql.o 180 :UNC 0 : maxBlockSize = ALLOCSET_DEFAULT_INITSIZE;
181 : :
182 : : /* Create a memory context for the TID storage */
7 john.naylor@postgres 183 [ + + ]:GNC 84227 : if (insert_only)
184 : : {
185 : 84226 : ts->rt_context = BumpContextCreate(CurrentMemoryContext,
186 : : "TID storage",
187 : : minContextSize,
188 : : initBlockSize,
189 : : maxBlockSize);
190 : : }
191 : : else
192 : : {
193 : 1 : ts->rt_context = AllocSetContextCreate(CurrentMemoryContext,
194 : : "TID storage",
195 : : minContextSize,
196 : : initBlockSize,
197 : : maxBlockSize);
198 : : }
199 : :
17 msawada@postgresql.o 200 : 84227 : ts->tree.local = local_ts_create(ts->rt_context);
201 : :
24 202 : 84227 : return ts;
203 : : }
204 : :
205 : : /*
206 : : * Similar to TidStoreCreateLocal() but create a shared TidStore on a
207 : : * DSA area. The TID storage will live in the DSA area, and the memory
208 : : * context rt_context will have only meta data of the radix tree.
209 : : *
210 : : * The returned object is allocated in backend-local memory.
211 : : */
212 : : TidStore *
17 213 : 14 : TidStoreCreateShared(size_t max_bytes, int tranche_id)
214 : : {
215 : : TidStore *ts;
216 : : dsa_area *area;
217 : 14 : size_t dsa_init_size = DSA_DEFAULT_INIT_SEGMENT_SIZE;
218 : 14 : size_t dsa_max_size = DSA_MAX_SEGMENT_SIZE;
219 : :
220 : 14 : ts = palloc0(sizeof(TidStore));
221 : 14 : ts->context = CurrentMemoryContext;
222 : :
223 : 14 : ts->rt_context = AllocSetContextCreate(CurrentMemoryContext,
224 : : "TID storage meta data",
225 : : ALLOCSET_SMALL_SIZES);
226 : :
227 : : /*
228 : : * Choose the initial and maximum DSA segment sizes to be no longer than
229 : : * 1/8 of max_bytes.
230 : : */
231 [ + + ]: 257 : while (8 * dsa_max_size > max_bytes)
232 : 243 : dsa_max_size >>= 1;
233 : :
234 [ - + ]: 14 : if (dsa_max_size < DSA_MIN_SEGMENT_SIZE)
17 msawada@postgresql.o 235 :UNC 0 : dsa_max_size = DSA_MIN_SEGMENT_SIZE;
236 : :
17 msawada@postgresql.o 237 [ + + ]:GNC 14 : if (dsa_init_size > dsa_max_size)
238 : 1 : dsa_init_size = dsa_max_size;
239 : :
240 : 14 : area = dsa_create_ext(tranche_id, dsa_init_size, dsa_max_size);
241 : 14 : ts->tree.shared = shared_ts_create(ts->rt_context, area,
242 : : tranche_id);
243 : 14 : ts->area = area;
244 : :
245 : 14 : return ts;
246 : : }
247 : :
248 : : /*
249 : : * Attach to the shared TidStore. 'area_handle' is the DSA handle where
250 : : * the TidStore is created. 'handle' is the dsa_pointer returned by
251 : : * TidStoreGetHandle(). The returned object is allocated in backend-local
252 : : * memory using the CurrentMemoryContext.
253 : : */
254 : : TidStore *
255 : 16 : TidStoreAttach(dsa_handle area_handle, dsa_pointer handle)
256 : : {
257 : : TidStore *ts;
258 : : dsa_area *area;
259 : :
260 [ - + ]: 16 : Assert(area_handle != DSA_HANDLE_INVALID);
24 261 [ - + ]: 16 : Assert(DsaPointerIsValid(handle));
262 : :
263 : : /* create per-backend state */
264 : 16 : ts = palloc0(sizeof(TidStore));
265 : :
17 266 : 16 : area = dsa_attach(area_handle);
267 : :
268 : : /* Find the shared the shared radix tree */
24 269 : 16 : ts->tree.shared = shared_ts_attach(area, handle);
270 : 16 : ts->area = area;
271 : :
272 : 16 : return ts;
273 : : }
274 : :
275 : : /*
276 : : * Detach from a TidStore. This also detaches from radix tree and frees
277 : : * the backend-local resources.
278 : : */
279 : : void
280 : 16 : TidStoreDetach(TidStore *ts)
281 : : {
282 [ - + ]: 16 : Assert(TidStoreIsShared(ts));
283 : :
284 : 16 : shared_ts_detach(ts->tree.shared);
17 285 : 16 : dsa_detach(ts->area);
286 : :
24 287 : 16 : pfree(ts);
288 : 16 : }
289 : :
290 : : /*
291 : : * Lock support functions.
292 : : *
293 : : * We can use the radix tree's lock for shared TidStore as the data we
294 : : * need to protect is only the shared radix tree.
295 : : */
296 : :
297 : : void
298 : 1112 : TidStoreLockExclusive(TidStore *ts)
299 : : {
300 [ + + ]: 1112 : if (TidStoreIsShared(ts))
301 : 103 : shared_ts_lock_exclusive(ts->tree.shared);
302 : 1112 : }
303 : :
304 : : void
305 : 2274220 : TidStoreLockShare(TidStore *ts)
306 : : {
307 [ + + ]: 2274220 : if (TidStoreIsShared(ts))
308 : 210842 : shared_ts_lock_share(ts->tree.shared);
309 : 2274220 : }
310 : :
311 : : void
312 : 2275331 : TidStoreUnlock(TidStore *ts)
313 : : {
314 [ + + ]: 2275331 : if (TidStoreIsShared(ts))
315 : 210945 : shared_ts_unlock(ts->tree.shared);
316 : 2275331 : }
317 : :
318 : : /*
319 : : * Destroy a TidStore, returning all memory.
320 : : *
321 : : * Note that the caller must be certain that no other backend will attempt to
322 : : * access the TidStore before calling this function. Other backend must
323 : : * explicitly call TidStoreDetach() to free up backend-local memory associated
324 : : * with the TidStore. The backend that calls TidStoreDestroy() must not call
325 : : * TidStoreDetach().
326 : : */
327 : : void
328 : 551 : TidStoreDestroy(TidStore *ts)
329 : : {
330 : : /* Destroy underlying radix tree */
331 [ + + ]: 551 : if (TidStoreIsShared(ts))
332 : : {
333 : 14 : shared_ts_free(ts->tree.shared);
334 : :
17 335 : 14 : dsa_detach(ts->area);
336 : : }
337 : : else
24 338 : 537 : local_ts_free(ts->tree.local);
339 : :
340 : 551 : MemoryContextDelete(ts->rt_context);
341 : :
342 : 551 : pfree(ts);
343 : 551 : }
344 : :
345 : : /*
346 : : * Create or replace an entry for the given block and array of offsets.
347 : : *
348 : : * NB: This function is designed and optimized for vacuum's heap scanning
349 : : * phase, so has some limitations:
350 : : *
351 : : * - The offset numbers "offsets" must be sorted in ascending order.
352 : : * - If the block number already exists, the entry will be replaced --
353 : : * there is no way to add or remove offsets from an entry.
354 : : */
355 : : void
356 : 16131 : TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
357 : : int num_offsets)
358 : : {
359 : : union
360 : : {
361 : : char data[MaxBlocktableEntrySize];
362 : : BlocktableEntry force_align_entry;
363 : : } data;
6 john.naylor@postgres 364 : 16131 : BlocktableEntry *page = (BlocktableEntry *) data.data;
365 : : bitmapword word;
366 : : int wordnum;
367 : : int next_word_threshold;
24 msawada@postgresql.o 368 : 16131 : int idx = 0;
369 : :
370 [ - + ]: 16131 : Assert(num_offsets > 0);
371 : :
372 : : /* Check if the given offset numbers are ordered */
373 [ + + ]: 956958 : for (int i = 1; i < num_offsets; i++)
374 [ - + ]: 940827 : Assert(offsets[i] > offsets[i - 1]);
375 : :
6 john.naylor@postgres 376 : 16131 : memset(page, 0, offsetof(BlocktableEntry, words));
377 : :
378 [ + + ]: 16131 : if (num_offsets <= NUM_FULL_OFFSETS)
379 : : {
380 [ + + ]: 4871 : for (int i = 0; i < num_offsets; i++)
381 : : {
382 : 3061 : OffsetNumber off = offsets[i];
383 : :
384 : : /* safety check to ensure we don't overrun bit array bounds */
385 [ + + - + ]: 3061 : if (off == InvalidOffsetNumber || off > MAX_OFFSET_IN_BITMAP)
24 msawada@postgresql.o 386 [ + - ]: 1 : elog(ERROR, "tuple offset out of range: %u", off);
387 : :
6 john.naylor@postgres 388 : 3060 : page->header.full_offsets[i] = off;
389 : : }
390 : :
391 : 1810 : page->header.nwords = 0;
392 : : }
393 : : else
394 : : {
395 : 14320 : for (wordnum = 0, next_word_threshold = BITS_PER_BITMAPWORD;
396 [ + + ]: 47592 : wordnum <= WORDNUM(offsets[num_offsets - 1]);
397 : 33272 : wordnum++, next_word_threshold += BITS_PER_BITMAPWORD)
398 : : {
399 : 33272 : word = 0;
400 : :
401 [ + + ]: 987169 : while (idx < num_offsets)
402 : : {
403 : 972849 : OffsetNumber off = offsets[idx];
404 : :
405 : : /* safety check to ensure we don't overrun bit array bounds */
406 [ + - - + ]: 972849 : if (off == InvalidOffsetNumber || off > MAX_OFFSET_IN_BITMAP)
6 john.naylor@postgres 407 [ # # ]:UNC 0 : elog(ERROR, "tuple offset out of range: %u", off);
408 : :
6 john.naylor@postgres 409 [ + + ]:GNC 972849 : if (off >= next_word_threshold)
410 : 18952 : break;
411 : :
412 : 953897 : word |= ((bitmapword) 1 << BITNUM(off));
413 : 953897 : idx++;
414 : : }
415 : :
416 : : /* write out offset bitmap for this wordnum */
417 : 33272 : page->words[wordnum] = word;
418 : : }
419 : :
420 : 14320 : page->header.nwords = wordnum;
421 [ - + ]: 14320 : Assert(page->header.nwords == WORDS_PER_PAGE(offsets[num_offsets - 1]));
422 : : }
423 : :
24 msawada@postgresql.o 424 [ + + ]: 16130 : if (TidStoreIsShared(ts))
425 : 249 : shared_ts_set(ts->tree.shared, blkno, page);
426 : : else
427 : 15881 : local_ts_set(ts->tree.local, blkno, page);
428 : 16130 : }
429 : :
430 : : /* Return true if the given TID is present in the TidStore */
431 : : bool
432 : 5347177 : TidStoreIsMember(TidStore *ts, ItemPointer tid)
433 : : {
434 : : int wordnum;
435 : : int bitnum;
436 : : BlocktableEntry *page;
437 : 5347177 : BlockNumber blk = ItemPointerGetBlockNumber(tid);
438 : 5347177 : OffsetNumber off = ItemPointerGetOffsetNumber(tid);
439 : :
440 [ + + ]: 5347177 : if (TidStoreIsShared(ts))
441 : 324051 : page = shared_ts_find(ts->tree.shared, blk);
442 : : else
443 : 5023126 : page = local_ts_find(ts->tree.local, blk);
444 : :
445 : : /* no entry for the blk */
446 [ + + ]: 5347177 : if (page == NULL)
447 : 963920 : return false;
448 : :
6 john.naylor@postgres 449 [ + + ]: 4383257 : if (page->header.nwords == 0)
450 : : {
451 : : /* we have offsets in the header */
452 [ + + ]: 498406 : for (int i = 0; i < NUM_FULL_OFFSETS; i++)
453 : : {
454 [ + + ]: 375910 : if (page->header.full_offsets[i] == off)
455 : 5634 : return true;
456 : : }
24 msawada@postgresql.o 457 : 122496 : return false;
458 : : }
459 : : else
460 : : {
6 john.naylor@postgres 461 : 4255127 : wordnum = WORDNUM(off);
462 : 4255127 : bitnum = BITNUM(off);
463 : :
464 : : /* no bitmap for the off */
465 [ + + ]: 4255127 : if (wordnum >= page->header.nwords)
466 : 1963999 : return false;
467 : :
468 : 2291128 : return (page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0;
469 : : }
470 : : }
471 : :
472 : : /*
473 : : * Prepare to iterate through a TidStore.
474 : : *
475 : : * The TidStoreIter struct is created in the caller's memory context, and it
476 : : * will be freed in TidStoreEndIterate.
477 : : *
478 : : * The caller is responsible for locking TidStore until the iteration is
479 : : * finished.
480 : : */
481 : : TidStoreIter *
24 msawada@postgresql.o 482 : 524 : TidStoreBeginIterate(TidStore *ts)
483 : : {
484 : : TidStoreIter *iter;
485 : :
486 : 524 : iter = palloc0(sizeof(TidStoreIter));
487 : 524 : iter->ts = ts;
488 : :
489 : : /*
490 : : * We start with an array large enough to contain at least the offsets
491 : : * from one completely full bitmap element.
492 : : */
493 : 524 : iter->output.max_offset = 2 * BITS_PER_BITMAPWORD;
494 : 524 : iter->output.offsets = palloc(sizeof(OffsetNumber) * iter->output.max_offset);
495 : :
496 [ + + ]: 524 : if (TidStoreIsShared(ts))
497 : 5 : iter->tree_iter.shared = shared_ts_begin_iterate(ts->tree.shared);
498 : : else
499 : 519 : iter->tree_iter.local = local_ts_begin_iterate(ts->tree.local);
500 : :
501 : 524 : return iter;
502 : : }
503 : :
504 : :
505 : : /*
506 : : * Scan the TidStore and return the TIDs of the next block. The offsets in
507 : : * each iteration result are ordered, as are the block numbers over all
508 : : * iterations.
509 : : */
510 : : TidStoreIterResult *
511 : 14298 : TidStoreIterateNext(TidStoreIter *iter)
512 : : {
513 : : uint64 key;
514 : : BlocktableEntry *page;
515 : :
516 [ + + ]: 14298 : if (TidStoreIsShared(iter->ts))
517 : 254 : page = shared_ts_iterate_next(iter->tree_iter.shared, &key);
518 : : else
519 : 14044 : page = local_ts_iterate_next(iter->tree_iter.local, &key);
520 : :
521 [ + + ]: 14298 : if (page == NULL)
522 : 524 : return NULL;
523 : :
524 : : /* Collect TIDs from the key-value pair */
525 : 13774 : tidstore_iter_extract_tids(iter, (BlockNumber) key, page);
526 : :
527 : 13774 : return &(iter->output);
528 : : }
529 : :
530 : : /*
531 : : * Finish the iteration on TidStore.
532 : : *
533 : : * The caller is responsible for releasing any locks.
534 : : */
535 : : void
536 : 524 : TidStoreEndIterate(TidStoreIter *iter)
537 : : {
538 [ + + ]: 524 : if (TidStoreIsShared(iter->ts))
539 : 5 : shared_ts_end_iterate(iter->tree_iter.shared);
540 : : else
541 : 519 : local_ts_end_iterate(iter->tree_iter.local);
542 : :
543 : 524 : pfree(iter->output.offsets);
544 : 524 : pfree(iter);
545 : 524 : }
546 : :
547 : : /*
548 : : * Return the memory usage of TidStore.
549 : : */
550 : : size_t
551 : 342604 : TidStoreMemoryUsage(TidStore *ts)
552 : : {
553 [ + + ]: 342604 : if (TidStoreIsShared(ts))
554 : 378 : return shared_ts_memory_usage(ts->tree.shared);
555 : : else
556 : 342226 : return local_ts_memory_usage(ts->tree.local);
557 : : }
558 : :
559 : : /*
560 : : * Return the DSA area where the TidStore lives.
561 : : */
562 : : dsa_area *
17 563 : 14 : TidStoreGetDSA(TidStore *ts)
564 : : {
565 [ - + ]: 14 : Assert(TidStoreIsShared(ts));
566 : :
567 : 14 : return ts->area;
568 : : }
569 : :
570 : : dsa_pointer
24 571 : 13 : TidStoreGetHandle(TidStore *ts)
572 : : {
573 [ - + ]: 13 : Assert(TidStoreIsShared(ts));
574 : :
575 : 13 : return (dsa_pointer) shared_ts_get_handle(ts->tree.shared);
576 : : }
577 : :
578 : : /* Extract TIDs from the given key-value pair */
579 : : static void
580 : 13774 : tidstore_iter_extract_tids(TidStoreIter *iter, BlockNumber blkno,
581 : : BlocktableEntry *page)
582 : : {
583 : 13774 : TidStoreIterResult *result = (&iter->output);
584 : : int wordnum;
585 : :
586 : 13774 : result->num_offsets = 0;
587 : 13774 : result->blkno = blkno;
588 : :
6 john.naylor@postgres 589 [ + + ]: 13774 : if (page->header.nwords == 0)
590 : : {
591 : : /* we have offsets in the header */
592 [ + + ]: 7188 : for (int i = 0; i < NUM_FULL_OFFSETS; i++)
593 : : {
594 [ + + ]: 5391 : if (page->header.full_offsets[i] != InvalidOffsetNumber)
595 : 3038 : result->offsets[result->num_offsets++] = page->header.full_offsets[i];
596 : : }
597 : : }
598 : : else
599 : : {
600 [ + + ]: 42863 : for (wordnum = 0; wordnum < page->header.nwords; wordnum++)
601 : : {
602 : 30886 : bitmapword w = page->words[wordnum];
603 : 30886 : int off = wordnum * BITS_PER_BITMAPWORD;
604 : :
605 : : /* Make sure there is enough space to add offsets */
606 [ + + ]: 30886 : if ((result->num_offsets + BITS_PER_BITMAPWORD) > result->max_offset)
607 : : {
608 : 130 : result->max_offset *= 2;
609 : 130 : result->offsets = repalloc(result->offsets,
610 : 130 : sizeof(OffsetNumber) * result->max_offset);
611 : : }
612 : :
613 [ + + ]: 1384315 : while (w != 0)
614 : : {
615 [ + + ]: 1353429 : if (w & 1)
616 : 893703 : result->offsets[result->num_offsets++] = (OffsetNumber) off;
617 : 1353429 : off++;
618 : 1353429 : w >>= 1;
619 : : }
620 : : }
621 : : }
24 msawada@postgresql.o 622 : 13774 : }
|
