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
 

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)
 
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

◆ MaxHeapTuplesPerPageBits

#define MaxHeapTuplesPerPageBits   11

Definition at line 74 of file ginpostinglist.c.

Referenced by itemptr_to_uint64(), and uint64_to_itemptr().

Function Documentation

◆ decode_varbyte()

static uint64 decode_varbyte ( unsigned char **  ptr)
static

Definition at line 123 of file ginpostinglist.c.

References val.

Referenced by ginPostingListDecodeAllSegments().

124 {
125  uint64 val;
126  unsigned char *p = *ptr;
127  uint64 c;
128 
129  c = *(p++);
130  val = c & 0x7F;
131  if (c & 0x80)
132  {
133  c = *(p++);
134  val |= (c & 0x7F) << 7;
135  if (c & 0x80)
136  {
137  c = *(p++);
138  val |= (c & 0x7F) << 14;
139  if (c & 0x80)
140  {
141  c = *(p++);
142  val |= (c & 0x7F) << 21;
143  if (c & 0x80)
144  {
145  c = *(p++);
146  val |= (c & 0x7F) << 28;
147  if (c & 0x80)
148  {
149  c = *(p++);
150  val |= (c & 0x7F) << 35;
151  if (c & 0x80)
152  {
153  /* last byte, no continuation bit */
154  c = *(p++);
155  val |= c << 42;
156  }
157  }
158  }
159  }
160  }
161  }
162 
163  *ptr = p;
164 
165  return val;
166 }
char * c
long val
Definition: informix.c:689

◆ encode_varbyte()

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

Definition at line 105 of file ginpostinglist.c.

References val.

Referenced by ginCompressPostingList().

106 {
107  unsigned char *p = *ptr;
108 
109  while (val > 0x7F)
110  {
111  *(p++) = 0x80 | (val & 0x7F);
112  val >>= 7;
113  }
114  *(p++) = (unsigned char) val;
115 
116  *ptr = p;
117 }
long val
Definition: informix.c:689

◆ ginCompressPostingList()

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

Definition at line 180 of file ginpostinglist.c.

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

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

182 {
183  uint64 prev;
184  int totalpacked = 0;
185  int maxbytes;
186  GinPostingList *result;
187  unsigned char *ptr;
188  unsigned char *endptr;
189 
190  maxsize = SHORTALIGN_DOWN(maxsize);
191 
192  result = palloc(maxsize);
193 
194  maxbytes = maxsize - offsetof(GinPostingList, bytes);
195  Assert(maxbytes > 0);
196 
197  /* Store the first special item */
198  result->first = ipd[0];
199 
200  prev = itemptr_to_uint64(&result->first);
201 
202  ptr = result->bytes;
203  endptr = result->bytes + maxbytes;
204  for (totalpacked = 1; totalpacked < nipd; totalpacked++)
205  {
206  uint64 val = itemptr_to_uint64(&ipd[totalpacked]);
207  uint64 delta = val - prev;
208 
209  Assert(val > prev);
210 
211  if (endptr - ptr >= 6)
212  encode_varbyte(delta, &ptr);
213  else
214  {
215  /*
216  * There are less than 6 bytes left. Have to check if the next
217  * item fits in that space before writing it out.
218  */
219  unsigned char buf[6];
220  unsigned char *p = buf;
221 
222  encode_varbyte(delta, &p);
223  if (p - buf > (endptr - ptr))
224  break; /* output is full */
225 
226  memcpy(ptr, buf, p - buf);
227  ptr += (p - buf);
228  }
229  prev = val;
230  }
231  result->nbytes = ptr - result->bytes;
232 
233  /*
234  * If we wrote an odd number of bytes, zero out the padding byte at the
235  * end.
236  */
237  if (result->nbytes != SHORTALIGN(result->nbytes))
238  result->bytes[result->nbytes] = 0;
239 
240  if (nwritten)
241  *nwritten = totalpacked;
242 
243  Assert(SizeOfGinPostingList(result) <= maxsize);
244 
245  /*
246  * Check that the encoded segment decodes back to the original items.
247  */
248 #if defined (CHECK_ENCODING_ROUNDTRIP)
249  {
250  int ndecoded;
251  ItemPointer tmp = ginPostingListDecode(result, &ndecoded);
252  int i;
253 
254  Assert(ndecoded == totalpacked);
255  for (i = 0; i < ndecoded; i++)
256  Assert(memcmp(&tmp[i], &ipd[i], sizeof(ItemPointerData)) == 0);
257  pfree(tmp);
258  }
259 #endif
260 
261  return result;
262 }
ItemPointer ginPostingListDecode(GinPostingList *plist, int *ndecoded)
#define SHORTALIGN_DOWN(LEN)
Definition: c.h:641
ItemPointerData first
Definition: ginblock.h:328
void pfree(void *pointer)
Definition: mcxt.c:936
unsigned char bytes[FLEXIBLE_ARRAY_MEMBER]
Definition: ginblock.h:330
static char * buf
Definition: pg_test_fsync.c:67
uint16 nbytes
Definition: ginblock.h:329
#define Assert(condition)
Definition: c.h:680
static uint64 itemptr_to_uint64(const ItemPointer iptr)
static void encode_varbyte(uint64 val, unsigned char **ptr)
void * palloc(Size size)
Definition: mcxt.c:835
#define SizeOfGinPostingList(plist)
Definition: ginblock.h:333
int i
#define SHORTALIGN(LEN)
Definition: c.h:629
long val
Definition: informix.c:689
#define offsetof(type, field)
Definition: c.h:603

◆ ginMergeItemPointers()

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

Definition at line 363 of file ginpostinglist.c.

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

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

366 {
367  ItemPointerData *dst;
368 
369  dst = (ItemPointer) palloc((na + nb) * sizeof(ItemPointerData));
370 
371  /*
372  * If the argument arrays don't overlap, we can just append them to each
373  * other.
374  */
375  if (na == 0 || nb == 0 || ginCompareItemPointers(&a[na - 1], &b[0]) < 0)
376  {
377  memcpy(dst, a, na * sizeof(ItemPointerData));
378  memcpy(&dst[na], b, nb * sizeof(ItemPointerData));
379  *nmerged = na + nb;
380  }
381  else if (ginCompareItemPointers(&b[nb - 1], &a[0]) < 0)
382  {
383  memcpy(dst, b, nb * sizeof(ItemPointerData));
384  memcpy(&dst[nb], a, na * sizeof(ItemPointerData));
385  *nmerged = na + nb;
386  }
387  else
388  {
389  ItemPointerData *dptr = dst;
390  ItemPointerData *aptr = a;
391  ItemPointerData *bptr = b;
392 
393  while (aptr - a < na && bptr - b < nb)
394  {
395  int cmp = ginCompareItemPointers(aptr, bptr);
396 
397  if (cmp > 0)
398  *dptr++ = *bptr++;
399  else if (cmp == 0)
400  {
401  /* only keep one copy of the identical items */
402  *dptr++ = *bptr++;
403  aptr++;
404  }
405  else
406  *dptr++ = *aptr++;
407  }
408 
409  while (aptr - a < na)
410  *dptr++ = *aptr++;
411 
412  while (bptr - b < nb)
413  *dptr++ = *bptr++;
414 
415  *nmerged = dptr - dst;
416  }
417 
418  return dst;
419 }
ItemPointerData * ItemPointer
Definition: itemptr.h:49
struct ItemPointerData ItemPointerData
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:461
void * palloc(Size size)
Definition: mcxt.c:835
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ ginPostingListDecode()

ItemPointer ginPostingListDecode ( GinPostingList plist,
int *  ndecoded 
)

Definition at line 269 of file ginpostinglist.c.

References ginPostingListDecodeAllSegments(), and SizeOfGinPostingList.

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

270 {
271  return ginPostingListDecodeAllSegments(plist,
272  SizeOfGinPostingList(plist),
273  ndecoded);
274 }
#define SizeOfGinPostingList(plist)
Definition: ginblock.h:333
ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len, int *ndecoded_out)

◆ ginPostingListDecodeAllSegments()

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

Definition at line 282 of file ginpostinglist.c.

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

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

283 {
284  ItemPointer result;
285  int nallocated;
286  uint64 val;
287  char *endseg = ((char *) segment) + len;
288  int ndecoded;
289  unsigned char *ptr;
290  unsigned char *endptr;
291 
292  /*
293  * Guess an initial size of the array.
294  */
295  nallocated = segment->nbytes * 2 + 1;
296  result = palloc(nallocated * sizeof(ItemPointerData));
297 
298  ndecoded = 0;
299  while ((char *) segment < endseg)
300  {
301  /* enlarge output array if needed */
302  if (ndecoded >= nallocated)
303  {
304  nallocated *= 2;
305  result = repalloc(result, nallocated * sizeof(ItemPointerData));
306  }
307 
308  /* copy the first item */
310  Assert(ndecoded == 0 || ginCompareItemPointers(&segment->first, &result[ndecoded - 1]) > 0);
311  result[ndecoded] = segment->first;
312  ndecoded++;
313 
314  val = itemptr_to_uint64(&segment->first);
315  ptr = segment->bytes;
316  endptr = segment->bytes + segment->nbytes;
317  while (ptr < endptr)
318  {
319  /* enlarge output array if needed */
320  if (ndecoded >= nallocated)
321  {
322  nallocated *= 2;
323  result = repalloc(result, nallocated * sizeof(ItemPointerData));
324  }
325 
326  val += decode_varbyte(&ptr);
327 
328  uint64_to_itemptr(val, &result[ndecoded]);
329  ndecoded++;
330  }
331  segment = GinNextPostingListSegment(segment);
332  }
333 
334  if (ndecoded_out)
335  *ndecoded_out = ndecoded;
336  return result;
337 }
static uint64 decode_varbyte(unsigned char **ptr)
ItemPointerData first
Definition: ginblock.h:328
#define GinNextPostingListSegment(cur)
Definition: ginblock.h:334
static void uint64_to_itemptr(uint64 val, ItemPointer iptr)
unsigned char bytes[FLEXIBLE_ARRAY_MEMBER]
Definition: ginblock.h:330
uint16 nbytes
Definition: ginblock.h:329
#define Assert(condition)
Definition: c.h:680
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:95
static uint64 itemptr_to_uint64(const ItemPointer iptr)
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:949
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:461
void * palloc(Size size)
Definition: mcxt.c:835
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:40
long val
Definition: informix.c:689

◆ ginPostingListDecodeAllSegmentsToTbm()

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

Definition at line 343 of file ginpostinglist.c.

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

Referenced by GinDataLeafPageGetItemsToTbm().

345 {
346  int ndecoded;
347  ItemPointer items;
348 
349  items = ginPostingListDecodeAllSegments(ptr, len, &ndecoded);
350  tbm_add_tuples(tbm, items, ndecoded, false);
351  pfree(items);
352 
353  return ndecoded;
354 }
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
void pfree(void *pointer)
Definition: mcxt.c:936
ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len, int *ndecoded_out)

◆ itemptr_to_uint64()

static uint64 itemptr_to_uint64 ( const ItemPointer  iptr)
inlinestatic

Definition at line 77 of file ginpostinglist.c.

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

Referenced by ginCompressPostingList(), and ginPostingListDecodeAllSegments().

78 {
79  uint64 val;
80 
83 
84  val = GinItemPointerGetBlockNumber(iptr);
86  val |= GinItemPointerGetOffsetNumber(iptr);
87 
88  return val;
89 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:60
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:137
#define MaxHeapTuplesPerPageBits
#define Assert(condition)
Definition: c.h:680
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:134
long val
Definition: informix.c:689

◆ uint64_to_itemptr()

static void uint64_to_itemptr ( uint64  val,
ItemPointer  iptr 
)
inlinestatic

Definition at line 92 of file ginpostinglist.c.

References Assert, GinItemPointerSetBlockNumber, GinItemPointerSetOffsetNumber, ItemPointerIsValid, and MaxHeapTuplesPerPageBits.

Referenced by ginPostingListDecodeAllSegments().

93 {
97 
99 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:60
#define MaxHeapTuplesPerPageBits
#define Assert(condition)
Definition: c.h:680
#define GinItemPointerSetOffsetNumber(pointer, offnum)
Definition: ginblock.h:143
#define GinItemPointerSetBlockNumber(pointer, blkno)
Definition: ginblock.h:140
long val
Definition: informix.c:689