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:33
#define elog(elevel,...)
Definition: elog.h:218
#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 627 of file integerset.c.

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

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:434
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
void * palloc(Size size)
Definition: mcxt.c:1068

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  int itemno;
569 
570  itemno = intset_binsrch_uint64(x,
571  intset->buffered_values,
572  intset->num_buffered_values,
573  false);
574  if (itemno >= intset->num_buffered_values)
575  return false;
576  else
577  return (intset->buffered_values[itemno] == x);
578  }
579 
580  /*
581  * Start from the root, and walk down the B-tree to find the right leaf
582  * node.
583  */
584  if (!intset->root)
585  return false;
586  node = intset->root;
587  for (level = intset->num_levels - 1; level > 0; level--)
588  {
590 
591  Assert(node->level == level);
592 
593  itemno = intset_binsrch_uint64(x, n->values, n->num_items, true);
594  if (itemno == 0)
595  return false;
596  node = n->downlinks[itemno - 1];
597  }
598  Assert(node->level == 0);
599  leaf = (intset_leaf_node *) node;
600 
601  /*
602  * Binary search to find the right item on the leaf page
603  */
604  itemno = intset_binsrch_leaf(x, leaf->items, leaf->num_items, true);
605  if (itemno == 0)
606  return false;
607  item = &leaf->items[itemno - 1];
608 
609  /* Is this a match to the first value on the item? */
610  if (item->first == x)
611  return true;
612  Assert(x > item->first);
613 
614  /* Is it in the packed codeword? */
615  if (simple8b_contains(item->codeword, x, item->first))
616  return true;
617 
618  return false;
619 }
static int intset_binsrch_uint64(uint64 value, uint64 *arr, int arr_elems, bool nextkey)
Definition: integerset.c:717
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
Definition: integerset.c:1007
static int intset_binsrch_leaf(uint64 value, leaf_item *arr, int arr_elems, bool nextkey)
Definition: integerset.c:750
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 646 of file integerset.c.

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

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