PostgreSQL Source Code  git master
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)
 
GinPostingListginCompressPostingList (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 }
long val
Definition: informix.c:670
Assert(fmt[strlen(fmt) - 1] !='\n')
char * c

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:806
#define SHORTALIGN(LEN)
Definition: c.h:794
#define SizeOfGinPostingList(plist)
Definition: ginblock.h:342
static uint64 itemptr_to_uint64(const ItemPointer iptr)
static void encode_varbyte(uint64 val, unsigned char **ptr)
ItemPointer ginPostingListDecode(GinPostingList *plist, int *ndecoded_out)
#define MaxBytesPerInteger
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc(Size size)
Definition: mcxt.c:1304
static char * buf
Definition: pg_test_fsync.c:73
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 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:488
int b
Definition: isn.c:70
int a
Definition: isn.c:69
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(), ginRedoRecompress(), and leafRepackItems().

◆ ginPostingListDecode()

ItemPointer ginPostingListDecode ( GinPostingList plist,
int *  ndecoded_out 
)

Definition at line 284 of file ginpostinglist.c.

285 {
286  return ginPostingListDecodeAllSegments(plist,
287  SizeOfGinPostingList(plist),
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(), 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:1528
#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 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:49
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:377

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
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 
108  Assert(ItemPointerIsValid(iptr));
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().