integerset.c File Reference

#include "postgres.h"
#include "lib/integerset.h"
#include "port/pg_bitutils.h"
#include "utils/memutils.h"

Include dependency graph for integerset.c:

Go to the source code of this file.

Data Structures
struct	intset_node
struct	intset_internal_node
struct	leaf_item
struct	intset_leaf_node
struct	IntegerSet
struct	simple8b_mode

Macros
#define	SIMPLE8B_MAX_VALUES_PER_CODEWORD   240
#define	MAX_INTERNAL_ITEMS   64
#define	MAX_LEAF_ITEMS   64
#define	MAX_TREE_LEVELS   11
#define	MAX_VALUES_PER_LEAF_ITEM   (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)
#define	MAX_BUFFERED_VALUES   (MAX_VALUES_PER_LEAF_ITEM * 2)
#define	EMPTY_CODEWORD   UINT64CONST(0x0FFFFFFFFFFFFFFF)

Typedefs
typedef struct intset_node	intset_node
typedef struct intset_leaf_node	intset_leaf_node
typedef struct intset_internal_node	intset_internal_node

Functions
static void	intset_update_upper (IntegerSet *intset, int level, intset_node *child, uint64 child_key)
static void	intset_flush_buffered_values (IntegerSet *intset)
static int	intset_binsrch_uint64 (uint64 item, uint64 *arr, int arr_elems, bool nextkey)
static int	intset_binsrch_leaf (uint64 item, leaf_item *arr, int arr_elems, bool nextkey)
static uint64	simple8b_encode (const uint64 *ints, int *num_encoded, uint64 base)
static int	simple8b_decode (uint64 codeword, uint64 *decoded, uint64 base)
static bool	simple8b_contains (uint64 codeword, uint64 key, uint64 base)
IntegerSet *	intset_create (void)
static intset_internal_node *	intset_new_internal_node (IntegerSet *intset)
static intset_leaf_node *	intset_new_leaf_node (IntegerSet *intset)
uint64	intset_num_entries (IntegerSet *intset)
uint64	intset_memory_usage (IntegerSet *intset)
void	intset_add_member (IntegerSet *intset, uint64 x)
bool	intset_is_member (IntegerSet *intset, uint64 x)
void	intset_begin_iterate (IntegerSet *intset)
bool	intset_iterate_next (IntegerSet *intset, uint64 *next)

Variables
static const struct simple8b_mode	simple8b_modes [17]

Macro Definition Documentation

EMPTY_CODEWORD

#define EMPTY_CODEWORD   UINT64CONST(0x0FFFFFFFFFFFFFFF)

Definition at line 857 of file integerset.c.

MAX_BUFFERED_VALUES

#define MAX_BUFFERED_VALUES   (MAX_VALUES_PER_LEAF_ITEM * 2)

Definition at line 187 of file integerset.c.

MAX_INTERNAL_ITEMS

#define MAX_INTERNAL_ITEMS   64

Definition at line 95 of file integerset.c.

MAX_LEAF_ITEMS

#define MAX_LEAF_ITEMS   64

Definition at line 96 of file integerset.c.

MAX_TREE_LEVELS

#define MAX_TREE_LEVELS   11

Definition at line 110 of file integerset.c.

MAX_VALUES_PER_LEAF_ITEM

#define MAX_VALUES_PER_LEAF_ITEM   (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)

Definition at line 167 of file integerset.c.

SIMPLE8B_MAX_VALUES_PER_CODEWORD

#define SIMPLE8B_MAX_VALUES_PER_CODEWORD   240

Definition at line 84 of file integerset.c.

Typedef Documentation

intset_internal_node

typedef struct intset_internal_node intset_internal_node

Definition at line 1 of file integerset.c.

intset_leaf_node

typedef struct intset_leaf_node intset_leaf_node

Definition at line 1 of file integerset.c.

intset_node

typedef struct intset_node intset_node

Definition at line 1 of file integerset.c.

Function Documentation

intset_add_member()

void intset_add_member	(	IntegerSet *	intset,
		uint64	x
	)

Definition at line 370 of file integerset.c.

{
    if (intset->iter_active)
        elog(ERROR, "cannot add new values to integer set while iteration is in progress");
 
    if (x <= intset->highest_value && intset->num_entries > 0)
        elog(ERROR, "cannot add value to integer set out of order");
 
    if (intset->num_buffered_values >= MAX_BUFFERED_VALUES)
    {
        /* Time to flush our buffer */
        intset_flush_buffered_values(intset);
        Assert(intset->num_buffered_values < MAX_BUFFERED_VALUES);
    }
 
    /* Add it to the buffer of newly-added values */
    intset->buffered_values[intset->num_buffered_values] = x;
    intset->num_buffered_values++;
    intset->num_entries++;
    intset->highest_value = x;
}

References Assert, elog, ERROR, intset(), intset_flush_buffered_values(), MAX_BUFFERED_VALUES, and x.

Referenced by gistvacuumpage(), test_huge_distances(), test_pattern(), test_single_value(), and test_single_value_and_filler().

intset_begin_iterate()

void intset_begin_iterate

(

IntegerSet *

intset

)

Definition at line 624 of file integerset.c.

{
    /* Note that we allow an iteration to be abandoned midway */
    intset->iter_active = true;
    intset->iter_node = intset->leftmost_leaf;
    intset->iter_itemno = 0;
    intset->iter_valueno = 0;
    intset->iter_num_values = 0;
    intset->iter_values = intset->iter_values_buf;
}

References intset().

Referenced by gistvacuum_delete_empty_pages(), test_empty(), test_huge_distances(), test_pattern(), test_single_value(), and test_single_value_and_filler().

intset_binsrch_leaf()

static int intset_binsrch_leaf ( uint64  item, leaf_item *  arr, int  arr_elems, bool  nextkey  )

static

Definition at line 747 of file integerset.c.

{
    int         low,
                high,
                mid;
 
    low = 0;
    high = arr_elems;
    while (high > low)
    {
        mid = low + (high - low) / 2;
 
        if (nextkey)
        {
            if (item >= arr[mid].first)
                low = mid + 1;
            else
                high = mid;
        }
        else
        {
            if (item > arr[mid].first)
                low = mid + 1;
            else
                high = mid;
        }
    }
 
    return low;
}

Referenced by intset_is_member().

intset_binsrch_uint64()

static int intset_binsrch_uint64 ( uint64  item, uint64 *  arr, int  arr_elems, bool  nextkey  )

static

Definition at line 714 of file integerset.c.

{
    int         low,
                high,
                mid;
 
    low = 0;
    high = arr_elems;
    while (high > low)
    {
        mid = low + (high - low) / 2;
 
        if (nextkey)
        {
            if (item >= arr[mid])
                low = mid + 1;
            else
                high = mid;
        }
        else
        {
            if (item > arr[mid])
                low = mid + 1;
            else
                high = mid;
        }
    }
 
    return low;
}

Referenced by intset_is_member().

intset_create()

IntegerSet* intset_create

(

void

)

Definition at line 284 of file integerset.c.

{
    IntegerSet *intset;
 
    intset = (IntegerSet *) palloc(sizeof(IntegerSet));
    intset->context = CurrentMemoryContext;
    intset->mem_used = GetMemoryChunkSpace(intset);
 
    intset->num_entries = 0;
    intset->highest_value = 0;
 
    intset->num_levels = 0;
    intset->root = NULL;
    memset(intset->rightmost_nodes, 0, sizeof(intset->rightmost_nodes));
    intset->leftmost_leaf = NULL;
 
    intset->num_buffered_values = 0;
 
    intset->iter_active = false;
    intset->iter_node = NULL;
    intset->iter_itemno = 0;
    intset->iter_valueno = 0;
    intset->iter_num_values = 0;
    intset->iter_values = NULL;
 
    return intset;
}

References CurrentMemoryContext, GetMemoryChunkSpace(), intset(), and palloc().

Referenced by gistvacuumscan(), test_empty(), test_huge_distances(), test_pattern(), test_single_value(), and test_single_value_and_filler().

intset_flush_buffered_values()

static void intset_flush_buffered_values ( IntegerSet *  intset )

static

Definition at line 396 of file integerset.c.

{
    uint64     *values = intset->buffered_values;
    uint64      num_values = intset->num_buffered_values;
    int         num_packed = 0;
    intset_leaf_node *leaf;
 
    leaf = (intset_leaf_node *) intset->rightmost_nodes[0];
 
    /*
     * If the tree is completely empty, create the first leaf page, which is
     * also the root.
     */
    if (leaf == NULL)
    {
        /*
         * This is the very first item in the set.
         *
         * Allocate root node. It's also a leaf.
         */
        leaf = intset_new_leaf_node(intset);
 
        intset->root = (intset_node *) leaf;
        intset->leftmost_leaf = leaf;
        intset->rightmost_nodes[0] = (intset_node *) leaf;
        intset->num_levels = 1;
    }
 
    /*
     * If there are less than MAX_VALUES_PER_LEAF_ITEM values in the buffer,
     * stop.  In most cases, we cannot encode that many values in a single
     * value, but this way, the encoder doesn't have to worry about running
     * out of input.
     */
    while (num_values - num_packed >= MAX_VALUES_PER_LEAF_ITEM)
    {
        leaf_item   item;
        int         num_encoded;
 
        /*
         * Construct the next leaf item, packing as many buffered values as
         * possible.
         */
        item.first = values[num_packed];
        item.codeword = simple8b_encode(&values[num_packed + 1],
                                        &num_encoded,
                                        item.first);
 
        /*
         * Add the item to the node, allocating a new node if the old one is
         * full.
         */
        if (leaf->num_items >= MAX_LEAF_ITEMS)
        {
            /* Allocate new leaf and link it to the tree */
            intset_leaf_node *old_leaf = leaf;
 
            leaf = intset_new_leaf_node(intset);
            old_leaf->next = leaf;
            intset->rightmost_nodes[0] = (intset_node *) leaf;
            intset_update_upper(intset, 1, (intset_node *) leaf, item.first);
        }
        leaf->items[leaf->num_items++] = item;
 
        num_packed += 1 + num_encoded;
    }
 
    /*
     * Move any remaining buffered values to the beginning of the array.
     */
    if (num_packed < intset->num_buffered_values)
    {
        memmove(&intset->buffered_values[0],
                &intset->buffered_values[num_packed],
                (intset->num_buffered_values - num_packed) * sizeof(uint64));
    }
    intset->num_buffered_values -= num_packed;
}

References leaf_item::codeword, leaf_item::first, if(), intset(), intset_new_leaf_node(), intset_update_upper(), intset_leaf_node::items, MAX_LEAF_ITEMS, MAX_VALUES_PER_LEAF_ITEM, intset_leaf_node::next, intset_leaf_node::num_items, simple8b_encode(), and values.

Referenced by intset_add_member().

intset_is_member()

bool intset_is_member	(	IntegerSet *	intset,
		uint64	x
	)

Definition at line 554 of file integerset.c.

{
    intset_node *node;
    intset_leaf_node *leaf;
    int         level;
    int         itemno;
    leaf_item  *item;
 
    /*
     * The value might be in the buffer of newly-added values.
     */
    if (intset->num_buffered_values > 0 && x >= intset->buffered_values[0])
    {
        itemno = intset_binsrch_uint64(x,
                                       intset->buffered_values,
                                       intset->num_buffered_values,
                                       false);
        if (itemno >= intset->num_buffered_values)
            return false;
        else
            return (intset->buffered_values[itemno] == x);
    }
 
    /*
     * Start from the root, and walk down the B-tree to find the right leaf
     * node.
     */
    if (!intset->root)
        return false;
    node = intset->root;
    for (level = intset->num_levels - 1; level > 0; level--)
    {
        intset_internal_node *n = (intset_internal_node *) node;
 
        Assert(node->level == level);
 
        itemno = intset_binsrch_uint64(x, n->values, n->num_items, true);
        if (itemno == 0)
            return false;
        node = n->downlinks[itemno - 1];
    }
    Assert(node->level == 0);
    leaf = (intset_leaf_node *) node;
 
    /*
     * Binary search to find the right item on the leaf page
     */
    itemno = intset_binsrch_leaf(x, leaf->items, leaf->num_items, true);
    if (itemno == 0)
        return false;
    item = &leaf->items[itemno - 1];
 
    /* Is this a match to the first value on the item? */
    if (item->first == x)
        return true;
    Assert(x > item->first);
 
    /* Is it in the packed codeword? */
    if (simple8b_contains(item->codeword, x, item->first))
        return true;
 
    return false;
}

References Assert, leaf_item::codeword, intset_internal_node::downlinks, leaf_item::first, intset(), intset_binsrch_leaf(), intset_binsrch_uint64(), intset_leaf_node::items, intset_node::level, intset_internal_node::num_items, intset_leaf_node::num_items, simple8b_contains(), intset_internal_node::values, and x.

Referenced by check_with_filler(), gistvacuum_delete_empty_pages(), test_empty(), test_huge_distances(), test_pattern(), and test_single_value().

intset_iterate_next()

bool intset_iterate_next	(	IntegerSet *	intset,
		uint64 *	next
	)

Definition at line 643 of file integerset.c.

{
    Assert(intset->iter_active);
    for (;;)
    {
        /* Return next iter_values[] entry if any */
        if (intset->iter_valueno < intset->iter_num_values)
        {
            *next = intset->iter_values[intset->iter_valueno++];
            return true;
        }
 
        /* Decode next item in current leaf node, if any */
        if (intset->iter_node &&
            intset->iter_itemno < intset->iter_node->num_items)
        {
            leaf_item  *item;
            int         num_decoded;
 
            item = &intset->iter_node->items[intset->iter_itemno++];
 
            intset->iter_values_buf[0] = item->first;
            num_decoded = simple8b_decode(item->codeword,
                                          &intset->iter_values_buf[1],
                                          item->first);
            intset->iter_num_values = num_decoded + 1;
            intset->iter_valueno = 0;
            continue;
        }
 
        /* No more items on this leaf, step to next node */
        if (intset->iter_node)
        {
            intset->iter_node = intset->iter_node->next;
            intset->iter_itemno = 0;
            continue;
        }
 
        /*
         * We have reached the end of the B-tree.  But we might still have
         * some integers in the buffer of newly-added values.
         */
        if (intset->iter_values == (const uint64 *) intset->iter_values_buf)
        {
            intset->iter_values = intset->buffered_values;
            intset->iter_num_values = intset->num_buffered_values;
            intset->iter_valueno = 0;
            continue;
        }
 
        break;
    }
 
    /* No more results. */
    intset->iter_active = false;
    *next = 0;                  /* prevent uninitialized-variable warnings */
    return false;
}

References Assert, leaf_item::codeword, leaf_item::first, intset(), next, and simple8b_decode().

Referenced by gistvacuum_delete_empty_pages(), test_empty(), test_huge_distances(), test_pattern(), test_single_value(), and test_single_value_and_filler().

intset_memory_usage()

uint64 intset_memory_usage

(

IntegerSet *

intset

)

Definition at line 359 of file integerset.c.

{
    return intset->mem_used;
}

References intset().

Referenced by test_pattern(), and test_single_value_and_filler().

intset_new_internal_node()

static intset_internal_node* intset_new_internal_node ( IntegerSet *  intset )

static

Definition at line 316 of file integerset.c.

{
    intset_internal_node *n;
 
    n = (intset_internal_node *) MemoryContextAlloc(intset->context,
                                                    sizeof(intset_internal_node));
    intset->mem_used += GetMemoryChunkSpace(n);
 
    n->level = 0;               /* caller must set */
    n->num_items = 0;
 
    return n;
}

References GetMemoryChunkSpace(), intset(), intset_internal_node::level, MemoryContextAlloc(), and intset_internal_node::num_items.

Referenced by intset_update_upper().

intset_new_leaf_node()

static intset_leaf_node* intset_new_leaf_node ( IntegerSet *  intset )

static

Definition at line 331 of file integerset.c.

{
    intset_leaf_node *n;
 
    n = (intset_leaf_node *) MemoryContextAlloc(intset->context,
                                                sizeof(intset_leaf_node));
    intset->mem_used += GetMemoryChunkSpace(n);
 
    n->level = 0;
    n->num_items = 0;
    n->next = NULL;
 
    return n;
}

References GetMemoryChunkSpace(), intset(), intset_leaf_node::level, MemoryContextAlloc(), intset_leaf_node::next, and intset_leaf_node::num_items.

Referenced by intset_flush_buffered_values().

intset_num_entries()

uint64 intset_num_entries

(

IntegerSet *

intset

)

Definition at line 350 of file integerset.c.

{
    return intset->num_entries;
}

References intset().

Referenced by gistvacuum_delete_empty_pages(), test_pattern(), test_single_value(), and test_single_value_and_filler().

intset_update_upper()

static void intset_update_upper ( IntegerSet *  intset, int  level, intset_node *  child, uint64  child_key  )

static

Definition at line 481 of file integerset.c.

{
    intset_internal_node *parent;
 
    Assert(level > 0);
 
    /*
     * Create a new root node, if necessary.
     */
    if (level >= intset->num_levels)
    {
        intset_node *oldroot = intset->root;
        uint64      downlink_key;
 
        /* MAX_TREE_LEVELS should be more than enough, this shouldn't happen */
        if (intset->num_levels == MAX_TREE_LEVELS)
            elog(ERROR, "could not expand integer set, maximum number of levels reached");
        intset->num_levels++;
 
        /*
         * Get the first value on the old root page, to be used as the
         * downlink.
         */
        if (intset->root->level == 0)
            downlink_key = ((intset_leaf_node *) oldroot)->items[0].first;
        else
            downlink_key = ((intset_internal_node *) oldroot)->values[0];
 
        parent = intset_new_internal_node(intset);
        parent->level = level;
        parent->values[0] = downlink_key;
        parent->downlinks[0] = oldroot;
        parent->num_items = 1;
 
        intset->root = (intset_node *) parent;
        intset->rightmost_nodes[level] = (intset_node *) parent;
    }
 
    /*
     * Place the downlink on the parent page.
     */
    parent = (intset_internal_node *) intset->rightmost_nodes[level];
 
    if (parent->num_items < MAX_INTERNAL_ITEMS)
    {
        parent->values[parent->num_items] = child_key;
        parent->downlinks[parent->num_items] = child;
        parent->num_items++;
    }
    else
    {
        /*
         * Doesn't fit.  Allocate new parent, with the downlink as the first
         * item on it, and recursively insert the downlink to the new parent
         * to the grandparent.
         */
        parent = intset_new_internal_node(intset);
        parent->level = level;
        parent->values[0] = child_key;
        parent->downlinks[0] = child;
        parent->num_items = 1;
 
        intset->rightmost_nodes[level] = (intset_node *) parent;
 
        intset_update_upper(intset, level + 1, (intset_node *) parent, child_key);
    }
}

References Assert, intset_internal_node::downlinks, elog, ERROR, if(), intset(), intset_new_internal_node(), intset_internal_node::level, MAX_INTERNAL_ITEMS, MAX_TREE_LEVELS, intset_internal_node::num_items, and intset_internal_node::values.

Referenced by intset_flush_buffered_values().

simple8b_contains()

static bool simple8b_contains ( uint64  codeword, uint64  key, uint64  base  )

static

Definition at line 1004 of file integerset.c.

{
    int         selector = (codeword >> 60);
    int         nints = simple8b_modes[selector].num_ints;
    int         bits = simple8b_modes[selector].bits_per_int;
 
    if (codeword == EMPTY_CODEWORD)
        return false;
 
    if (bits == 0)
    {
        /* Special handling for 0-bit cases. */
        return (key - base) <= nints;
    }
    else
    {
        uint64      mask = (UINT64CONST(1) << bits) - 1;
        uint64      curr_value;
 
        curr_value = base;
        for (int i = 0; i < nints; i++)
        {
            uint64      diff = codeword & mask;
 
            curr_value += 1 + diff;
 
            if (curr_value >= key)
            {
                if (curr_value == key)
                    return true;
                else
                    return false;
            }
 
            codeword >>= bits;
        }
    }
    return false;
}

References simple8b_mode::bits_per_int, EMPTY_CODEWORD, i, sort-test::key, simple8b_mode::num_ints, and simple8b_modes.

Referenced by intset_is_member().

simple8b_decode()

static int simple8b_decode ( uint64  codeword, uint64 *  decoded, uint64  base  )

static

Definition at line 975 of file integerset.c.

{
    int         selector = (codeword >> 60);
    int         nints = simple8b_modes[selector].num_ints;
    int         bits = simple8b_modes[selector].bits_per_int;
    uint64      mask = (UINT64CONST(1) << bits) - 1;
    uint64      curr_value;
 
    if (codeword == EMPTY_CODEWORD)
        return 0;
 
    curr_value = base;
    for (int i = 0; i < nints; i++)
    {
        uint64      diff = codeword & mask;
 
        curr_value += 1 + diff;
        decoded[i] = curr_value;
        codeword >>= bits;
    }
    return nints;
}

References simple8b_mode::bits_per_int, EMPTY_CODEWORD, i, simple8b_mode::num_ints, and simple8b_modes.

Referenced by intset_iterate_next().

simple8b_encode()

static uint64 simple8b_encode ( const uint64 *  ints, int *  num_encoded, uint64  base  )

static

Definition at line 873 of file integerset.c.

{
    int         selector;
    int         nints;
    int         bits;
    uint64      diff;
    uint64      last_val;
    uint64      codeword;
    int         i;
 
    Assert(ints[0] > base);
 
    /*
     * Select the "mode" to use for this codeword.
     *
     * In each iteration, check if the next value can be represented in the
     * current mode we're considering.  If it's too large, then step up the
     * mode to a wider one, and repeat.  If it fits, move on to the next
     * integer.  Repeat until the codeword is full, given the current mode.
     *
     * Note that we don't have any way to represent unused slots in the
     * codeword, so we require each codeword to be "full".  It is always
     * possible to produce a full codeword unless the very first delta is too
     * large to be encoded.  For example, if the first delta is small but the
     * second is too large to be encoded, we'll end up using the last "mode",
     * which has nints == 1.
     */
    selector = 0;
    nints = simple8b_modes[0].num_ints;
    bits = simple8b_modes[0].bits_per_int;
    diff = ints[0] - base - 1;
    last_val = ints[0];
    i = 0;                      /* number of deltas we have accepted */
    for (;;)
    {
        if (diff >= (UINT64CONST(1) << bits))
        {
            /* too large, step up to next mode */
            selector++;
            nints = simple8b_modes[selector].num_ints;
            bits = simple8b_modes[selector].bits_per_int;
            /* we might already have accepted enough deltas for this mode */
            if (i >= nints)
                break;
        }
        else
        {
            /* accept this delta; then done if codeword is full */
            i++;
            if (i >= nints)
                break;
            /* examine next delta */
            Assert(ints[i] > last_val);
            diff = ints[i] - last_val - 1;
            last_val = ints[i];
        }
    }
 
    if (nints == 0)
    {
        /*
         * The first delta is too large to be encoded with Simple-8b.
         *
         * If there is at least one not-too-large integer in the input, we
         * will encode it using mode 15 (or a more compact mode).  Hence, we
         * can only get here if the *first* delta is >= 2^60.
         */
        Assert(i == 0);
        *num_encoded = 0;
        return EMPTY_CODEWORD;
    }
 
    /*
     * Encode the integers using the selected mode.  Note that we shift them
     * into the codeword in reverse order, so that they will come out in the
     * correct order in the decoder.
     */
    codeword = 0;
    if (bits > 0)
    {
        for (i = nints - 1; i > 0; i--)
        {
            diff = ints[i] - ints[i - 1] - 1;
            codeword |= diff;
            codeword <<= bits;
        }
        diff = ints[0] - base - 1;
        codeword |= diff;
    }
 
    /* add selector to the codeword, and return */
    codeword |= (uint64) selector << 60;
 
    *num_encoded = nints;
    return codeword;
}

References Assert, simple8b_mode::bits_per_int, EMPTY_CODEWORD, i, simple8b_mode::num_ints, and simple8b_modes.

Referenced by intset_flush_buffered_values().

Variable Documentation

simple8b_modes

const struct simple8b_mode simple8b_modes[17]

static

Initial value:

=
 
{
    {0, 240},                   
    {0, 120},                   
    {1, 60},                    
    {2, 30},                    
    {3, 20},                    
    {4, 15},                    
    {5, 12},                    
    {6, 10},                    
    {7, 8},                     
    {8, 7},                     
    {10, 6},                    
    {12, 5},                    
    {15, 4},                    
    {20, 3},                    
    {30, 2},                    
    {60, 1},                    
 
    {0, 0}                      
}

Referenced by simple8b_contains(), simple8b_decode(), and simple8b_encode().