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 ItemPointerData *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 ItemPointerData *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.

{
    uint64      val;
    unsigned char *p = *ptr;
    uint64      c;
 
    /* 1st byte */
    c = *(p++);
    val = c & 0x7F;
    if (c & 0x80)
    {
        /* 2nd byte */
        c = *(p++);
        val |= (c & 0x7F) << 7;
        if (c & 0x80)
        {
            /* 3rd byte */
            c = *(p++);
            val |= (c & 0x7F) << 14;
            if (c & 0x80)
            {
                /* 4th byte */
                c = *(p++);
                val |= (c & 0x7F) << 21;
                if (c & 0x80)
                {
                    /* 5th byte */
                    c = *(p++);
                    val |= (c & 0x7F) << 28;
                    if (c & 0x80)
                    {
                        /* 6th byte */
                        c = *(p++);
                        val |= (c & 0x7F) << 35;
                        if (c & 0x80)
                        {
                            /* 7th byte, should not have continuation bit */
                            c = *(p++);
                            val |= c << 42;
                            Assert((c & 0x80) == 0);
                        }
                    }
                }
            }
        }
    }
 
    *ptr = p;
 
    return val;
}

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.

{
    unsigned char *p = *ptr;
 
    while (val > 0x7F)
    {
        *(p++) = 0x80 | (val & 0x7F);
        val >>= 7;
    }
    *(p++) = (unsigned char) val;
 
    *ptr = p;
}

References val.

Referenced by ginCompressPostingList().

ginCompressPostingList()

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

Definition at line 197 of file ginpostinglist.c.

{
    uint64      prev;
    int         totalpacked = 0;
    int         maxbytes;
    GinPostingList *result;
    unsigned char *ptr;
    unsigned char *endptr;
 
    maxsize = SHORTALIGN_DOWN(maxsize);
 
    result = palloc(maxsize);
 
    maxbytes = maxsize - offsetof(GinPostingList, bytes);
    Assert(maxbytes > 0);
 
    /* Store the first special item */
    result->first = ipd[0];
 
    prev = itemptr_to_uint64(&result->first);
 
    ptr = result->bytes;
    endptr = result->bytes + maxbytes;
    for (totalpacked = 1; totalpacked < nipd; totalpacked++)
    {
        uint64      val = itemptr_to_uint64(&ipd[totalpacked]);
        uint64      delta = val - prev;
 
        Assert(val > prev);
 
        if (endptr - ptr >= MaxBytesPerInteger)
            encode_varbyte(delta, &ptr);
        else
        {
            /*
             * There are less than 7 bytes left. Have to check if the next
             * item fits in that space before writing it out.
             */
            unsigned char buf[MaxBytesPerInteger];
            unsigned char *p = buf;
 
            encode_varbyte(delta, &p);
            if (p - buf > (endptr - ptr))
                break;          /* output is full */
 
            memcpy(ptr, buf, p - buf);
            ptr += (p - buf);
        }
        prev = val;
    }
    result->nbytes = ptr - result->bytes;
 
    /*
     * If we wrote an odd number of bytes, zero out the padding byte at the
     * end.
     */
    if (result->nbytes != SHORTALIGN(result->nbytes))
        result->bytes[result->nbytes] = 0;
 
    if (nwritten)
        *nwritten = totalpacked;
 
    Assert(SizeOfGinPostingList(result) <= maxsize);
 
    /*
     * Check that the encoded segment decodes back to the original items.
     */
#if defined (CHECK_ENCODING_ROUNDTRIP)
    {
        int         ndecoded;
        ItemPointer tmp = ginPostingListDecode(result, &ndecoded);
 
        Assert(ndecoded == totalpacked);
        Assert(memcmp(tmp, ipd, ndecoded * sizeof(ItemPointerData)) == 0);
        pfree(tmp);
    }
#endif
 
    return result;
}

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.

{
    ItemPointerData *dst;
 
    dst = (ItemPointer) palloc((na + nb) * sizeof(ItemPointerData));
 
    /*
     * If the argument arrays don't overlap, we can just append them to each
     * other.
     */
    if (na == 0 || nb == 0 || ginCompareItemPointers(&a[na - 1], &b[0]) < 0)
    {
        memcpy(dst, a, na * sizeof(ItemPointerData));
        memcpy(&dst[na], b, nb * sizeof(ItemPointerData));
        *nmerged = na + nb;
    }
    else if (ginCompareItemPointers(&b[nb - 1], &a[0]) < 0)
    {
        memcpy(dst, b, nb * sizeof(ItemPointerData));
        memcpy(&dst[nb], a, na * sizeof(ItemPointerData));
        *nmerged = na + nb;
    }
    else
    {
        ItemPointerData *dptr = dst;
        ItemPointerData *aptr = a;
        ItemPointerData *bptr = b;
 
        while (aptr - a < na && bptr - b < nb)
        {
            int         cmp = ginCompareItemPointers(aptr, bptr);
 
            if (cmp > 0)
                *dptr++ = *bptr++;
            else if (cmp == 0)
            {
                /* only keep one copy of the identical items */
                *dptr++ = *bptr++;
                aptr++;
            }
            else
                *dptr++ = *aptr++;
        }
 
        while (aptr - a < na)
            *dptr++ = *aptr++;
 
        while (bptr - b < nb)
            *dptr++ = *bptr++;
 
        *nmerged = dptr - dst;
    }
 
    return dst;
}

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.

{
    return ginPostingListDecodeAllSegments(plist,
                                           SizeOfGinPostingList(plist),
                                           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.

{
    ItemPointer result;
    int         nallocated;
    uint64      val;
    char       *endseg = ((char *) segment) + len;
    int         ndecoded;
    unsigned char *ptr;
    unsigned char *endptr;
 
    /*
     * Guess an initial size of the array.
     */
    nallocated = segment->nbytes * 2 + 1;
    result = palloc(nallocated * sizeof(ItemPointerData));
 
    ndecoded = 0;
    while ((char *) segment < endseg)
    {
        /* enlarge output array if needed */
        if (ndecoded >= nallocated)
        {
            nallocated *= 2;
            result = repalloc(result, nallocated * sizeof(ItemPointerData));
        }
 
        /* copy the first item */
        Assert(OffsetNumberIsValid(ItemPointerGetOffsetNumber(&segment->first)));
        Assert(ndecoded == 0 || ginCompareItemPointers(&segment->first, &result[ndecoded - 1]) > 0);
        result[ndecoded] = segment->first;
        ndecoded++;
 
        val = itemptr_to_uint64(&segment->first);
        ptr = segment->bytes;
        endptr = segment->bytes + segment->nbytes;
        while (ptr < endptr)
        {
            /* enlarge output array if needed */
            if (ndecoded >= nallocated)
            {
                nallocated *= 2;
                result = repalloc(result, nallocated * sizeof(ItemPointerData));
            }
 
            val += decode_varbyte(&ptr);
 
            uint64_to_itemptr(val, &result[ndecoded]);
            ndecoded++;
        }
        segment = GinNextPostingListSegment(segment);
    }
 
    if (ndecoded_out)
        *ndecoded_out = ndecoded;
    return result;
}

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.

{
    int         ndecoded;
    ItemPointer items;
 
    items = ginPostingListDecodeAllSegments(ptr, len, &ndecoded);
    tbm_add_tuples(tbm, items, ndecoded, false);
    pfree(items);
 
    return ndecoded;
}

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

Referenced by GinDataLeafPageGetItemsToTbm().

itemptr_to_uint64()

static uint64 itemptr_to_uint64 ( const ItemPointerData *  iptr )

inlinestatic

Definition at line 87 of file ginpostinglist.c.

{
    uint64      val;
 
    Assert(ItemPointerIsValid(iptr));
    Assert(GinItemPointerGetOffsetNumber(iptr) < (1 << MaxHeapTuplesPerPageBits));
 
    val = GinItemPointerGetBlockNumber(iptr);
    val <<= MaxHeapTuplesPerPageBits;
    val |= GinItemPointerGetOffsetNumber(iptr);
 
    return val;
}

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.

{
    GinItemPointerSetOffsetNumber(iptr, val & ((1 << MaxHeapTuplesPerPageBits) - 1));
    val = val >> MaxHeapTuplesPerPageBits;
    GinItemPointerSetBlockNumber(iptr, val);
 
    Assert(ItemPointerIsValid(iptr));
}

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

Referenced by ginPostingListDecodeAllSegments().