integerset.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef struct IntegerSet	IntegerSet

Functions
IntegerSet *	intset_create (void)
void	intset_add_member (IntegerSet *intset, uint64 x)
bool	intset_is_member (IntegerSet *intset, uint64 x)
uint64	intset_num_entries (IntegerSet *intset)
uint64	intset_memory_usage (IntegerSet *intset)
void	intset_begin_iterate (IntegerSet *intset)
bool	intset_iterate_next (IntegerSet *intset, uint64 *next)

Typedef Documentation

IntegerSet

typedef struct IntegerSet IntegerSet

Definition at line 1 of file integerset.h.

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_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_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_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().