PostgreSQL Source Code git master
Typedefs | Functions
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 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:182
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
Assert(PointerIsAligned(start, uint64))
#define MAX_BUFFERED_VALUES
Definition: integerset.c:186
static void intset_flush_buffered_values(IntegerSet *intset)
Definition: integerset.c:395
x
int x
Definition: isn.c:75

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:767
void * palloc(Size size)
Definition: mcxt.c:1365
MemoryContext CurrentMemoryContext
Definition: mcxt.c:160

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
Definition: integerset.c:146
uint16 num_items
Definition: integerset.c:149
intset_node * downlinks[MAX_INTERNAL_ITEMS]
Definition: integerset.c:156
uint64 values[MAX_INTERNAL_ITEMS]
Definition: integerset.c:155
Definition: integerset.c:169
uint16 num_items
Definition: integerset.c:172
leaf_item items[MAX_LEAF_ITEMS]
Definition: integerset.c:176
Definition: integerset.c:139
uint16 level
Definition: integerset.c:140
Definition: integerset.c:161
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:539
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().

AltStyle によって変換されたページ (->オリジナル) /