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

IntegerSetintset_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 12 of file integerset.h.

Function Documentation

◆ intset_add_member()

void intset_add_member ( IntegerSet intset,
uint64  x 
)

Definition at line 369 of file integerset.c.

370{
371 if (intset->iter_active)
372 elog(ERROR, "cannot add new values to integer set while iteration is in progress");
373
374 if (x <= intset->highest_value && intset->num_entries > 0)
375 elog(ERROR, "cannot add value to integer set out of order");
376
377 if (intset->num_buffered_values >= MAX_BUFFERED_VALUES)
378 {
379 /* Time to flush our buffer */
381 Assert(intset->num_buffered_values < MAX_BUFFERED_VALUES);
382 }
383
384 /* Add it to the buffer of newly-added values */
385 intset->buffered_values[intset->num_buffered_values] = x;
386 intset->num_buffered_values++;
387 intset->num_entries++;
388 intset->highest_value = x;
389}
Datum intset(PG_FUNCTION_ARGS)
Definition: _int_op.c:179
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
Assert(PointerIsAligned(start, uint64))
#define MAX_BUFFERED_VALUES
Definition: integerset.c:186
static void intset_flush_buffered_values(IntegerSet *intset)
Definition: integerset.c:395
int x
Definition: isn.c:70

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 623 of file integerset.c.

624{
625 /* Note that we allow an iteration to be abandoned midway */
626 intset->iter_active = true;
627 intset->iter_node = intset->leftmost_leaf;
628 intset->iter_itemno = 0;
629 intset->iter_valueno = 0;
630 intset->iter_num_values = 0;
631 intset->iter_values = intset->iter_values_buf;
632}

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 283 of file integerset.c.

284{
286
287 intset = (IntegerSet *) palloc(sizeof(IntegerSet));
288 intset->context = CurrentMemoryContext;
289 intset->mem_used = GetMemoryChunkSpace(intset);
290
291 intset->num_entries = 0;
292 intset->highest_value = 0;
293
294 intset->num_levels = 0;
295 intset->root = NULL;
296 memset(intset->rightmost_nodes, 0, sizeof(intset->rightmost_nodes));
297 intset->leftmost_leaf = NULL;
298
299 intset->num_buffered_values = 0;
300
301 intset->iter_active = false;
302 intset->iter_node = NULL;
303 intset->iter_itemno = 0;
304 intset->iter_valueno = 0;
305 intset->iter_num_values = 0;
306 intset->iter_values = NULL;
307
308 return intset;
309}
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:721
void * palloc(Size size)
Definition: mcxt.c:1317
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143

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 553 of file integerset.c.

554{
555 intset_node *node;
556 intset_leaf_node *leaf;
557 int level;
558 int itemno;
559 leaf_item *item;
560
561 /*
562 * The value might be in the buffer of newly-added values.
563 */
564 if (intset->num_buffered_values > 0 && x >= intset->buffered_values[0])
565 {
566 itemno = intset_binsrch_uint64(x,
567 intset->buffered_values,
568 intset->num_buffered_values,
569 false);
570 if (itemno >= intset->num_buffered_values)
571 return false;
572 else
573 return (intset->buffered_values[itemno] == x);
574 }
575
576 /*
577 * Start from the root, and walk down the B-tree to find the right leaf
578 * node.
579 */
580 if (!intset->root)
581 return false;
582 node = intset->root;
583 for (level = intset->num_levels - 1; level > 0; level--)
584 {
586
587 Assert(node->level == level);
588
589 itemno = intset_binsrch_uint64(x, n->values, n->num_items, true);
590 if (itemno == 0)
591 return false;
592 node = n->downlinks[itemno - 1];
593 }
594 Assert(node->level == 0);
595 leaf = (intset_leaf_node *) node;
596
597 /*
598 * Binary search to find the right item on the leaf page
599 */
600 itemno = intset_binsrch_leaf(x, leaf->items, leaf->num_items, true);
601 if (itemno == 0)
602 return false;
603 item = &leaf->items[itemno - 1];
604
605 /* Is this a match to the first value on the item? */
606 if (item->first == x)
607 return true;
608 Assert(x > item->first);
609
610 /* Is it in the packed codeword? */
611 if (simple8b_contains(item->codeword, x, item->first))
612 return true;
613
614 return false;
615}
static int intset_binsrch_uint64(uint64 item, uint64 *arr, int arr_elems, bool nextkey)
Definition: integerset.c:713
static int intset_binsrch_leaf(uint64 item, leaf_item *arr, int arr_elems, bool nextkey)
Definition: integerset.c:746
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
Definition: integerset.c:1003
intset_node * downlinks[MAX_INTERNAL_ITEMS]
Definition: integerset.c:156
uint64 values[MAX_INTERNAL_ITEMS]
Definition: integerset.c:155
leaf_item items[MAX_LEAF_ITEMS]
Definition: integerset.c:176
uint16 level
Definition: integerset.c:140
uint64 codeword
Definition: integerset.c:163
uint64 first
Definition: integerset.c:162

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 642 of file integerset.c.

643{
644 Assert(intset->iter_active);
645 for (;;)
646 {
647 /* Return next iter_values[] entry if any */
648 if (intset->iter_valueno < intset->iter_num_values)
649 {
650 *next = intset->iter_values[intset->iter_valueno++];
651 return true;
652 }
653
654 /* Decode next item in current leaf node, if any */
655 if (intset->iter_node &&
656 intset->iter_itemno < intset->iter_node->num_items)
657 {
658 leaf_item *item;
659 int num_decoded;
660
661 item = &intset->iter_node->items[intset->iter_itemno++];
662
663 intset->iter_values_buf[0] = item->first;
664 num_decoded = simple8b_decode(item->codeword,
665 &intset->iter_values_buf[1],
666 item->first);
667 intset->iter_num_values = num_decoded + 1;
668 intset->iter_valueno = 0;
669 continue;
670 }
671
672 /* No more items on this leaf, step to next node */
673 if (intset->iter_node)
674 {
675 intset->iter_node = intset->iter_node->next;
676 intset->iter_itemno = 0;
677 continue;
678 }
679
680 /*
681 * We have reached the end of the B-tree. But we might still have
682 * some integers in the buffer of newly-added values.
683 */
684 if (intset->iter_values == (const uint64 *) intset->iter_values_buf)
685 {
686 intset->iter_values = intset->buffered_values;
687 intset->iter_num_values = intset->num_buffered_values;
688 intset->iter_valueno = 0;
689 continue;
690 }
691
692 break;
693 }
694
695 /* No more results. */
696 intset->iter_active = false;
697 *next = 0; /* prevent uninitialized-variable warnings */
698 return false;
699}
static int32 next
Definition: blutils.c:224
uint64_t uint64
Definition: c.h:503
static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)
Definition: integerset.c:974

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 358 of file integerset.c.

359{
360 return intset->mem_used;
361}

References intset().

Referenced by test_pattern(), and test_single_value_and_filler().

◆ intset_num_entries()

uint64 intset_num_entries ( IntegerSet intset)

Definition at line 349 of file integerset.c.

350{
351 return intset->num_entries;
352}

References intset().

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