PostgreSQL Source Code git master
Macros | Functions
ginpostinglist.c File Reference
#include "postgres.h"
#include "access/gin_private.h"
Include dependency graph for ginpostinglist.c:

Go to the source code of this file.

Macros

#define  MaxHeapTuplesPerPageBits   11
 
#define  MaxBytesPerInteger   7
 

Functions

static uint64  itemptr_to_uint64 (const ItemPointer iptr)
 
static void  uint64_to_itemptr (uint64 val, ItemPointer iptr)
 
static void  encode_varbyte (uint64 val, unsigned char **ptr)
 
static uint64  decode_varbyte (unsigned char **ptr)
 
GinPostingList *  ginCompressPostingList (const ItemPointer ipd, int nipd, int maxsize, int *nwritten)
 
ItemPointer  ginPostingListDecode (GinPostingList *plist, int *ndecoded_out)
 
ItemPointer  ginPostingListDecodeAllSegments (GinPostingList *segment, int len, int *ndecoded_out)
 
int  ginPostingListDecodeAllSegmentsToTbm (GinPostingList *ptr, int len, TIDBitmap *tbm)
 
ItemPointer  ginMergeItemPointers (ItemPointerData *a, uint32 na, ItemPointerData *b, uint32 nb, int *nmerged)
 

Macro Definition Documentation

◆ MaxBytesPerInteger

#define MaxBytesPerInteger   7

Definition at line 84 of file ginpostinglist.c.

◆ MaxHeapTuplesPerPageBits

#define MaxHeapTuplesPerPageBits   11

Definition at line 81 of file ginpostinglist.c.

Function Documentation

◆ decode_varbyte()

static uint64 decode_varbyte ( unsigned char **  ptr )
static

Definition at line 133 of file ginpostinglist.c.

134{
135 uint64 val;
136 unsigned char *p = *ptr;
137 uint64 c;
138
139 /* 1st byte */
140 c = *(p++);
141 val = c & 0x7F;
142 if (c & 0x80)
143 {
144 /* 2nd byte */
145 c = *(p++);
146 val |= (c & 0x7F) << 7;
147 if (c & 0x80)
148 {
149 /* 3rd byte */
150 c = *(p++);
151 val |= (c & 0x7F) << 14;
152 if (c & 0x80)
153 {
154 /* 4th byte */
155 c = *(p++);
156 val |= (c & 0x7F) << 21;
157 if (c & 0x80)
158 {
159 /* 5th byte */
160 c = *(p++);
161 val |= (c & 0x7F) << 28;
162 if (c & 0x80)
163 {
164 /* 6th byte */
165 c = *(p++);
166 val |= (c & 0x7F) << 35;
167 if (c & 0x80)
168 {
169 /* 7th byte, should not have continuation bit */
170 c = *(p++);
171 val |= c << 42;
172 Assert((c & 0x80) == 0);
173 }
174 }
175 }
176 }
177 }
178 }
179
180 *ptr = p;
181
182 return val;
183}
uint64_t uint64
Definition: c.h:539
Assert(PointerIsAligned(start, uint64))
long val
Definition: informix.c:689
c
char * c
Definition: preproc-cursor.c:31

References Assert(), and val.

Referenced by ginPostingListDecodeAllSegments().

◆ encode_varbyte()

static void encode_varbyte ( uint64  val,
unsigned char **  ptr 
)
static

Definition at line 115 of file ginpostinglist.c.

116{
117 unsigned char *p = *ptr;
118
119 while (val > 0x7F)
120 {
121 *(p++) = 0x80 | (val & 0x7F);
122 val >>= 7;
123 }
124 *(p++) = (unsigned char) val;
125
126 *ptr = p;
127}

References val.

Referenced by ginCompressPostingList().

◆ ginCompressPostingList()

GinPostingList * ginCompressPostingList ( const ItemPointer  ipd,
int  nipd,
int  maxsize,
int *  nwritten 
)

Definition at line 197 of file ginpostinglist.c.

199{
200 uint64 prev;
201 int totalpacked = 0;
202 int maxbytes;
203 GinPostingList *result;
204 unsigned char *ptr;
205 unsigned char *endptr;
206
207 maxsize = SHORTALIGN_DOWN(maxsize);
208
209 result = palloc(maxsize);
210
211 maxbytes = maxsize - offsetof(GinPostingList, bytes);
212 Assert(maxbytes > 0);
213
214 /* Store the first special item */
215 result->first = ipd[0];
216
217 prev = itemptr_to_uint64(&result->first);
218
219 ptr = result->bytes;
220 endptr = result->bytes + maxbytes;
221 for (totalpacked = 1; totalpacked < nipd; totalpacked++)
222 {
223 uint64 val = itemptr_to_uint64(&ipd[totalpacked]);
224 uint64 delta = val - prev;
225
226 Assert(val > prev);
227
228 if (endptr - ptr >= MaxBytesPerInteger)
229 encode_varbyte(delta, &ptr);
230 else
231 {
232 /*
233 * There are less than 7 bytes left. Have to check if the next
234 * item fits in that space before writing it out.
235 */
236 unsigned char buf[MaxBytesPerInteger];
237 unsigned char *p = buf;
238
239 encode_varbyte(delta, &p);
240 if (p - buf > (endptr - ptr))
241 break; /* output is full */
242
243 memcpy(ptr, buf, p - buf);
244 ptr += (p - buf);
245 }
246 prev = val;
247 }
248 result->nbytes = ptr - result->bytes;
249
250 /*
251 * If we wrote an odd number of bytes, zero out the padding byte at the
252 * end.
253 */
254 if (result->nbytes != SHORTALIGN(result->nbytes))
255 result->bytes[result->nbytes] = 0;
256
257 if (nwritten)
258 *nwritten = totalpacked;
259
260 Assert(SizeOfGinPostingList(result) <= maxsize);
261
262 /*
263 * Check that the encoded segment decodes back to the original items.
264 */
265#if defined (CHECK_ENCODING_ROUNDTRIP)
266 {
267 int ndecoded;
268 ItemPointer tmp = ginPostingListDecode(result, &ndecoded);
269
270 Assert(ndecoded == totalpacked);
271 Assert(memcmp(tmp, ipd, ndecoded * sizeof(ItemPointerData)) == 0);
272 pfree(tmp);
273 }
274#endif
275
276 return result;
277}
#define SHORTALIGN_DOWN(LEN)
Definition: c.h:818
#define SHORTALIGN(LEN)
Definition: c.h:806
#define SizeOfGinPostingList(plist)
Definition: ginblock.h:342
static uint64 itemptr_to_uint64(const ItemPointer iptr)
Definition: ginpostinglist.c:87
static void encode_varbyte(uint64 val, unsigned char **ptr)
ItemPointer ginPostingListDecode(GinPostingList *plist, int *ndecoded_out)
#define MaxBytesPerInteger
Definition: ginpostinglist.c:84
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:81
void pfree(void *pointer)
Definition: mcxt.c:1594
void * palloc(Size size)
Definition: mcxt.c:1365
static char * buf
Definition: pg_test_fsync.c:72
ItemPointerData first
Definition: ginblock.h:337
unsigned char bytes[FLEXIBLE_ARRAY_MEMBER]
Definition: ginblock.h:339
uint16 nbytes
Definition: ginblock.h:338

References Assert(), buf, GinPostingList::bytes, encode_varbyte(), GinPostingList::first, ginPostingListDecode(), if(), itemptr_to_uint64(), MaxBytesPerInteger, GinPostingList::nbytes, palloc(), pfree(), SHORTALIGN, SHORTALIGN_DOWN, SizeOfGinPostingList, and val.

Referenced by _gin_build_tuple(), addItemPointersToLeafTuple(), buildFreshLeafTuple(), createPostingTree(), ginRedoRecompress(), ginVacuumEntryPage(), ginVacuumPostingTreeLeaf(), leafRepackItems(), and test_itemptr_pair().

◆ ginMergeItemPointers()

ItemPointer ginMergeItemPointers ( ItemPointerData *  a,
uint32  na,
ItemPointerData *  b,
uint32  nb,
int *  nmerged 
)

Definition at line 378 of file ginpostinglist.c.

381{
382 ItemPointerData *dst;
383
384 dst = (ItemPointer) palloc((na + nb) * sizeof(ItemPointerData));
385
386 /*
387 * If the argument arrays don't overlap, we can just append them to each
388 * other.
389 */
390 if (na == 0 || nb == 0 || ginCompareItemPointers(&a[na - 1], &b[0]) < 0)
391 {
392 memcpy(dst, a, na * sizeof(ItemPointerData));
393 memcpy(&dst[na], b, nb * sizeof(ItemPointerData));
394 *nmerged = na + nb;
395 }
396 else if (ginCompareItemPointers(&b[nb - 1], &a[0]) < 0)
397 {
398 memcpy(dst, b, nb * sizeof(ItemPointerData));
399 memcpy(&dst[nb], a, na * sizeof(ItemPointerData));
400 *nmerged = na + nb;
401 }
402 else
403 {
404 ItemPointerData *dptr = dst;
405 ItemPointerData *aptr = a;
406 ItemPointerData *bptr = b;
407
408 while (aptr - a < na && bptr - b < nb)
409 {
410 int cmp = ginCompareItemPointers(aptr, bptr);
411
412 if (cmp > 0)
413 *dptr++ = *bptr++;
414 else if (cmp == 0)
415 {
416 /* only keep one copy of the identical items */
417 *dptr++ = *bptr++;
418 aptr++;
419 }
420 else
421 *dptr++ = *aptr++;
422 }
423
424 while (aptr - a < na)
425 *dptr++ = *aptr++;
426
427 while (bptr - b < nb)
428 *dptr++ = *bptr++;
429
430 *nmerged = dptr - dst;
431 }
432
433 return dst;
434}
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:497
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73
ItemPointerData * ItemPointer
Definition: itemptr.h:49
struct ItemPointerData ItemPointerData
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743

References a, b, cmp(), ginCompareItemPointers(), and palloc().

Referenced by addItemPointersToLeafTuple(), addItemsToLeaf(), GinBufferStoreTuple(), ginRedoRecompress(), and leafRepackItems().

◆ ginPostingListDecode()

ItemPointer ginPostingListDecode ( GinPostingList *  plist,
int *  ndecoded_out 
)

Definition at line 284 of file ginpostinglist.c.

285{
288 ndecoded_out);
289}
ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len, int *ndecoded_out)

References ginPostingListDecodeAllSegments(), and SizeOfGinPostingList.

Referenced by addItemsToLeaf(), dataBeginPlaceToPageLeaf(), gin_leafpage_items(), ginCompressPostingList(), ginReadTuple(), ginReadTupleWithoutState(), ginRedoRecompress(), ginVacuumEntryPage(), ginVacuumPostingTreeLeaf(), leafRepackItems(), and test_itemptr_pair().

◆ ginPostingListDecodeAllSegments()

ItemPointer ginPostingListDecodeAllSegments ( GinPostingList *  segment,
int  len,
int *  ndecoded_out 
)

Definition at line 297 of file ginpostinglist.c.

298{
299 ItemPointer result;
300 int nallocated;
301 uint64 val;
302 char *endseg = ((char *) segment) + len;
303 int ndecoded;
304 unsigned char *ptr;
305 unsigned char *endptr;
306
307 /*
308 * Guess an initial size of the array.
309 */
310 nallocated = segment->nbytes * 2 + 1;
311 result = palloc(nallocated * sizeof(ItemPointerData));
312
313 ndecoded = 0;
314 while ((char *) segment < endseg)
315 {
316 /* enlarge output array if needed */
317 if (ndecoded >= nallocated)
318 {
319 nallocated *= 2;
320 result = repalloc(result, nallocated * sizeof(ItemPointerData));
321 }
322
323 /* copy the first item */
325 Assert(ndecoded == 0 || ginCompareItemPointers(&segment->first, &result[ndecoded - 1]) > 0);
326 result[ndecoded] = segment->first;
327 ndecoded++;
328
329 val = itemptr_to_uint64(&segment->first);
330 ptr = segment->bytes;
331 endptr = segment->bytes + segment->nbytes;
332 while (ptr < endptr)
333 {
334 /* enlarge output array if needed */
335 if (ndecoded >= nallocated)
336 {
337 nallocated *= 2;
338 result = repalloc(result, nallocated * sizeof(ItemPointerData));
339 }
340
341 val += decode_varbyte(&ptr);
342
343 uint64_to_itemptr(val, &result[ndecoded]);
344 ndecoded++;
345 }
346 segment = GinNextPostingListSegment(segment);
347 }
348
349 if (ndecoded_out)
350 *ndecoded_out = ndecoded;
351 return result;
352}
#define GinNextPostingListSegment(cur)
Definition: ginblock.h:343
static uint64 decode_varbyte(unsigned char **ptr)
static void uint64_to_itemptr(uint64 val, ItemPointer iptr)
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1610
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:39
const void size_t len

References Assert(), GinPostingList::bytes, decode_varbyte(), GinPostingList::first, ginCompareItemPointers(), GinNextPostingListSegment, ItemPointerGetOffsetNumber(), itemptr_to_uint64(), len, GinPostingList::nbytes, OffsetNumberIsValid, palloc(), repalloc(), uint64_to_itemptr(), and val.

Referenced by _gin_parse_tuple_items(), GinDataLeafPageGetItems(), ginPostingListDecode(), and ginPostingListDecodeAllSegmentsToTbm().

◆ ginPostingListDecodeAllSegmentsToTbm()

int ginPostingListDecodeAllSegmentsToTbm ( GinPostingList *  ptr,
int  len,
TIDBitmap *  tbm 
)

Definition at line 358 of file ginpostinglist.c.

360{
361 int ndecoded;
363
364 items = ginPostingListDecodeAllSegments(ptr, len, &ndecoded);
365 tbm_add_tuples(tbm, items, ndecoded, false);
366 pfree(items);
367
368 return ndecoded;
369}
static ItemArray items
Definition: test_tidstore.c:48
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:367

References ginPostingListDecodeAllSegments(), items, len, pfree(), and tbm_add_tuples().

Referenced by GinDataLeafPageGetItemsToTbm().

◆ itemptr_to_uint64()

static uint64 itemptr_to_uint64 ( const ItemPointer  iptr )
inlinestatic

Definition at line 87 of file ginpostinglist.c.

88{
89 uint64 val;
90
93
97
98 return val;
99}
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:146
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:143
#define MaxHeapTuplesPerPageBits
Definition: ginpostinglist.c:81
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition: itemptr.h:83

References Assert(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, ItemPointerIsValid(), MaxHeapTuplesPerPageBits, and val.

Referenced by ginCompressPostingList(), and ginPostingListDecodeAllSegments().

◆ uint64_to_itemptr()

static void uint64_to_itemptr ( uint64  val,
ItemPointer  iptr 
)
inlinestatic

Definition at line 102 of file ginpostinglist.c.

103{
107
109}
#define GinItemPointerSetBlockNumber(pointer, blkno)
Definition: ginblock.h:149
#define GinItemPointerSetOffsetNumber(pointer, offnum)
Definition: ginblock.h:152

References Assert(), GinItemPointerSetBlockNumber, GinItemPointerSetOffsetNumber, ItemPointerIsValid(), MaxHeapTuplesPerPageBits, and val.

Referenced by ginPostingListDecodeAllSegments().

AltStyle によって変換されたページ (->オリジナル) /