PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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

#define MaxHeapTuplesPerPageBits   11

Definition at line 74 of file ginpostinglist.c.

Referenced by itemptr_to_uint64(), and uint64_to_itemptr().

Function Documentation

static uint64 decode_varbyte ( unsigned char **  ptr)
static

Definition at line 127 of file ginpostinglist.c.

References val.

Referenced by ginPostingListDecodeAllSegments().

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

Definition at line 109 of file ginpostinglist.c.

References val.

Referenced by ginCompressPostingList().

110 {
111  unsigned char *p = *ptr;
112 
113  while (val > 0x7F)
114  {
115  *(p++) = 0x80 | (val & 0x7F);
116  val >>= 7;
117  }
118  *(p++) = (unsigned char) val;
119 
120  *ptr = p;
121 }
long val
Definition: informix.c:689
GinPostingList* ginCompressPostingList ( const ItemPointer  ipd,
int  nipd,
int  maxsize,
int *  nwritten 
)

Definition at line 184 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().

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

Definition at line 367 of file ginpostinglist.c.

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

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

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

Definition at line 273 of file ginpostinglist.c.

References ginPostingListDecodeAllSegments(), and SizeOfGinPostingList.

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

274 {
275  return ginPostingListDecodeAllSegments(plist,
276  SizeOfGinPostingList(plist),
277  ndecoded);
278 }
#define SizeOfGinPostingList(plist)
Definition: ginblock.h:326
ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len, int *ndecoded_out)
ItemPointer ginPostingListDecodeAllSegments ( GinPostingList segment,
int  len,
int *  ndecoded_out 
)

Definition at line 286 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().

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

Definition at line 347 of file ginpostinglist.c.

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

Referenced by GinDataLeafPageGetItemsToTbm().

349 {
350  int ndecoded;
351  ItemPointer items;
352 
353  items = ginPostingListDecodeAllSegments(ptr, len, &ndecoded);
354  tbm_add_tuples(tbm, items, ndecoded, false);
355  pfree(items);
356 
357  return ndecoded;
358 }
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:290
void pfree(void *pointer)
Definition: mcxt.c:992
ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len, int *ndecoded_out)
static uint64 itemptr_to_uint64 ( const ItemPointer  iptr)
inlinestatic

Definition at line 77 of file ginpostinglist.c.

References Assert, BlockIdData::bi_hi, BlockIdData::bi_lo, ItemPointerData::ip_blkid, ItemPointerData::ip_posid, ItemPointerIsValid, MaxHeapTuplesPerPageBits, and val.

Referenced by ginCompressPostingList(), and ginPostingListDecodeAllSegments().

78 {
79  uint64 val;
80 
83 
84  val = iptr->ip_blkid.bi_hi;
85  val <<= 16;
86  val |= iptr->ip_blkid.bi_lo;
88  val |= iptr->ip_posid;
89 
90  return val;
91 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:59
uint16 bi_hi
Definition: block.h:55
BlockIdData ip_blkid
Definition: itemptr.h:38
#define MaxHeapTuplesPerPageBits
#define Assert(condition)
Definition: c.h:671
OffsetNumber ip_posid
Definition: itemptr.h:39
long val
Definition: informix.c:689
uint16 bi_lo
Definition: block.h:56
static void uint64_to_itemptr ( uint64  val,
ItemPointer  iptr 
)
inlinestatic

Definition at line 94 of file ginpostinglist.c.

References Assert, BlockIdData::bi_hi, BlockIdData::bi_lo, ItemPointerData::ip_blkid, ItemPointerData::ip_posid, ItemPointerIsValid, and MaxHeapTuplesPerPageBits.

Referenced by ginPostingListDecodeAllSegments().

95 {
96  iptr->ip_posid = val & ((1 << MaxHeapTuplesPerPageBits) - 1);
98  iptr->ip_blkid.bi_lo = val & 0xFFFF;
99  val = val >> 16;
100  iptr->ip_blkid.bi_hi = val & 0xFFFF;
101 
102  Assert(ItemPointerIsValid(iptr));
103 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:59
uint16 bi_hi
Definition: block.h:55
BlockIdData ip_blkid
Definition: itemptr.h:38
#define MaxHeapTuplesPerPageBits
#define Assert(condition)
Definition: c.h:671
OffsetNumber ip_posid
Definition: itemptr.h:39
long val
Definition: informix.c:689
uint16 bi_lo
Definition: block.h:56