PostgreSQL Source Code  git master
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 1 of file integerset.h.

Function Documentation

◆ intset_add_member()

void intset_add_member ( IntegerSet intset,
uint64  x 
)

Definition at line 371 of file integerset.c.

372 {
373  if (intset->iter_active)
374  elog(ERROR, "cannot add new values to integer set while iteration is in progress");
375 
376  if (x <= intset->highest_value && intset->num_entries > 0)
377  elog(ERROR, "cannot add value to integer set out of order");
378 
379  if (intset->num_buffered_values >= MAX_BUFFERED_VALUES)
380  {
381  /* Time to flush our buffer */
383  Assert(intset->num_buffered_values < MAX_BUFFERED_VALUES);
384  }
385 
386  /* Add it to the buffer of newly-added values */
387  intset->buffered_values[intset->num_buffered_values] = x;
388  intset->num_buffered_values++;
389  intset->num_entries++;
390  intset->highest_value = x;
391 }
Datum intset(PG_FUNCTION_ARGS)
Definition: _int_op.c:179
#define ERROR
Definition: elog.h:39
#define MAX_BUFFERED_VALUES
Definition: integerset.c:188
static void intset_flush_buffered_values(IntegerSet *intset)
Definition: integerset.c:397
int x
Definition: isn.c:71
Assert(fmt[strlen(fmt) - 1] !='\n')

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

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

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

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

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

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

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

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

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

361 {
362  return intset->mem_used;
363 }

References intset().

Referenced by test_pattern(), and test_single_value_and_filler().

◆ intset_num_entries()

uint64 intset_num_entries ( IntegerSet intset)

Definition at line 351 of file integerset.c.

352 {
353  return intset->num_entries;
354 }

References intset().

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