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 12 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.

References Assert, IntegerSet::buffered_values, elog, ERROR, IntegerSet::highest_value, intset_flush_buffered_values(), IntegerSet::iter_active, MAX_BUFFERED_VALUES, IntegerSet::num_buffered_values, and IntegerSet::num_entries.

Referenced by gistvacuumpage(), test_huge_distances(), test_pattern(), test_single_value(), and test_single_value_and_filler().

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 
380  {
381  /* Time to flush our buffer */
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 }
bool iter_active
Definition: integerset.c:248
#define MAX_BUFFERED_VALUES
Definition: integerset.c:188
uint64 num_entries
Definition: integerset.c:211
#define ERROR
Definition: elog.h:43
uint64 buffered_values[MAX_BUFFERED_VALUES]
Definition: integerset.c:231
#define Assert(condition)
Definition: c.h:739
int num_buffered_values
Definition: integerset.c:232
static void intset_flush_buffered_values(IntegerSet *intset)
Definition: integerset.c:397
#define elog(elevel,...)
Definition: elog.h:228
uint64 highest_value
Definition: integerset.c:212

◆ intset_begin_iterate()

void intset_begin_iterate ( IntegerSet intset)

Definition at line 627 of file integerset.c.

References IntegerSet::iter_active, IntegerSet::iter_itemno, IntegerSet::iter_node, IntegerSet::iter_num_values, IntegerSet::iter_valueno, IntegerSet::iter_values, IntegerSet::iter_values_buf, and IntegerSet::leftmost_leaf.

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

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 }
int iter_itemno
Definition: integerset.c:255
int iter_num_values
Definition: integerset.c:251
bool iter_active
Definition: integerset.c:248
uint64 iter_values_buf[MAX_VALUES_PER_LEAF_ITEM]
Definition: integerset.c:257
const uint64 * iter_values
Definition: integerset.c:250
intset_leaf_node * leftmost_leaf
Definition: integerset.c:226
intset_leaf_node * iter_node
Definition: integerset.c:254
int iter_valueno
Definition: integerset.c:252

◆ intset_create()

IntegerSet* intset_create ( void  )

Definition at line 285 of file integerset.c.

References IntegerSet::context, CurrentMemoryContext, GetMemoryChunkSpace(), IntegerSet::highest_value, intset(), IntegerSet::iter_active, IntegerSet::iter_itemno, IntegerSet::iter_node, IntegerSet::iter_num_values, IntegerSet::iter_valueno, IntegerSet::iter_values, IntegerSet::leftmost_leaf, IntegerSet::mem_used, IntegerSet::num_buffered_values, IntegerSet::num_entries, IntegerSet::num_levels, palloc(), IntegerSet::rightmost_nodes, and IntegerSet::root.

Referenced by gistvacuumscan(), test_empty(), test_huge_distances(), test_pattern(), test_single_value(), and test_single_value_and_filler().

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 }
Datum intset(PG_FUNCTION_ARGS)
Definition: _int_op.c:183
int iter_itemno
Definition: integerset.c:255
int iter_num_values
Definition: integerset.c:251
int num_levels
Definition: integerset.c:223
bool iter_active
Definition: integerset.c:248
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
intset_node * root
Definition: integerset.c:224
const uint64 * iter_values
Definition: integerset.c:250
uint64 num_entries
Definition: integerset.c:211
intset_leaf_node * leftmost_leaf
Definition: integerset.c:226
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
intset_node * rightmost_nodes[MAX_TREE_LEVELS]
Definition: integerset.c:225
intset_leaf_node * iter_node
Definition: integerset.c:254
int num_buffered_values
Definition: integerset.c:232
void * palloc(Size size)
Definition: mcxt.c:949
int iter_valueno
Definition: integerset.c:252
uint64 highest_value
Definition: integerset.c:212
MemoryContext context
Definition: integerset.c:208
uint64 mem_used
Definition: integerset.c:209

◆ intset_is_member()

bool intset_is_member ( IntegerSet intset,
uint64  x 
)

Definition at line 555 of file integerset.c.

References Assert, IntegerSet::buffered_values, leaf_item::codeword, intset_internal_node::downlinks, leaf_item::first, intset_binsrch_leaf(), intset_binsrch_uint64(), intset_leaf_node::items, intset_node::level, IntegerSet::num_buffered_values, intset_internal_node::num_items, intset_leaf_node::num_items, IntegerSet::num_levels, IntegerSet::root, simple8b_contains(), and intset_internal_node::values.

Referenced by check_with_filler(), gistvacuum_delete_empty_pages(), test_empty(), test_huge_distances(), test_pattern(), and test_single_value().

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 }
int num_levels
Definition: integerset.c:223
intset_node * root
Definition: integerset.c:224
intset_node * downlinks[MAX_INTERNAL_ITEMS]
Definition: integerset.c:158
uint64 codeword
Definition: integerset.c:165
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
Definition: integerset.c:1007
static int intset_binsrch_uint64(uint64 value, uint64 *arr, int arr_elems, bool nextkey)
Definition: integerset.c:717
uint64 first
Definition: integerset.c:164
uint64 values[MAX_INTERNAL_ITEMS]
Definition: integerset.c:157
uint16 level
Definition: integerset.c:142
uint64 buffered_values[MAX_BUFFERED_VALUES]
Definition: integerset.c:231
#define Assert(condition)
Definition: c.h:739
int num_buffered_values
Definition: integerset.c:232
static int intset_binsrch_leaf(uint64 value, leaf_item *arr, int arr_elems, bool nextkey)
Definition: integerset.c:750
leaf_item items[MAX_LEAF_ITEMS]
Definition: integerset.c:178

◆ intset_iterate_next()

bool intset_iterate_next ( IntegerSet intset,
uint64 *  next 
)

Definition at line 646 of file integerset.c.

References Assert, IntegerSet::buffered_values, leaf_item::codeword, leaf_item::first, intset_leaf_node::items, IntegerSet::iter_active, IntegerSet::iter_itemno, IntegerSet::iter_node, IntegerSet::iter_num_values, IntegerSet::iter_valueno, IntegerSet::iter_values, IntegerSet::iter_values_buf, intset_leaf_node::next, IntegerSet::num_buffered_values, intset_leaf_node::num_items, 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().

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:213
int iter_itemno
Definition: integerset.c:255
int iter_num_values
Definition: integerset.c:251
bool iter_active
Definition: integerset.c:248
uint64 iter_values_buf[MAX_VALUES_PER_LEAF_ITEM]
Definition: integerset.c:257
const uint64 * iter_values
Definition: integerset.c:250
static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)
Definition: integerset.c:978
uint64 codeword
Definition: integerset.c:165
intset_leaf_node * next
Definition: integerset.c:176
uint64 first
Definition: integerset.c:164
uint64 buffered_values[MAX_BUFFERED_VALUES]
Definition: integerset.c:231
intset_leaf_node * iter_node
Definition: integerset.c:254
#define Assert(condition)
Definition: c.h:739
int num_buffered_values
Definition: integerset.c:232
int iter_valueno
Definition: integerset.c:252
leaf_item items[MAX_LEAF_ITEMS]
Definition: integerset.c:178

◆ intset_memory_usage()

uint64 intset_memory_usage ( IntegerSet intset)

Definition at line 360 of file integerset.c.

References IntegerSet::mem_used.

Referenced by test_pattern(), and test_single_value_and_filler().

361 {
362  return intset->mem_used;
363 }
uint64 mem_used
Definition: integerset.c:209

◆ intset_num_entries()

uint64 intset_num_entries ( IntegerSet intset)

Definition at line 351 of file integerset.c.

References IntegerSet::num_entries.

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

352 {
353  return intset->num_entries;
354 }
uint64 num_entries
Definition: integerset.c:211