PostgreSQL Source Code  git master
integerset.c File Reference
#include "postgres.h"
#include "access/htup_details.h"
#include "lib/integerset.h"
#include "port/pg_bitutils.h"
#include "utils/memutils.h"
Include dependency graph for integerset.c:

Go to the source code of this file.

Data Structures

struct  intset_node
 
struct  intset_internal_node
 
struct  leaf_item
 
struct  intset_leaf_node
 
struct  IntegerSet
 
struct  simple8b_mode
 

Macros

#define SIMPLE8B_MAX_VALUES_PER_CODEWORD   240
 
#define MAX_INTERNAL_ITEMS   64
 
#define MAX_LEAF_ITEMS   64
 
#define MAX_TREE_LEVELS   11
 
#define MAX_VALUES_PER_LEAF_ITEM   (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)
 
#define MAX_BUFFERED_VALUES   (MAX_VALUES_PER_LEAF_ITEM * 2)
 
#define EMPTY_CODEWORD   UINT64CONST(0x0FFFFFFFFFFFFFFF)
 

Typedefs

typedef struct intset_node intset_node
 
typedef struct intset_leaf_node intset_leaf_node
 
typedef struct intset_internal_node intset_internal_node
 

Functions

static void intset_update_upper (IntegerSet *intset, int level, intset_node *child, uint64 child_key)
 
static void intset_flush_buffered_values (IntegerSet *intset)
 
static int intset_binsrch_uint64 (uint64 value, uint64 *arr, int arr_elems, bool nextkey)
 
static int intset_binsrch_leaf (uint64 value, leaf_item *arr, int arr_elems, bool nextkey)
 
static uint64 simple8b_encode (const uint64 *ints, int *num_encoded, uint64 base)
 
static int simple8b_decode (uint64 codeword, uint64 *decoded, uint64 base)
 
static bool simple8b_contains (uint64 codeword, uint64 key, uint64 base)
 
IntegerSetintset_create (void)
 
static intset_internal_nodeintset_new_internal_node (IntegerSet *intset)
 
static intset_leaf_nodeintset_new_leaf_node (IntegerSet *intset)
 
uint64 intset_num_entries (IntegerSet *intset)
 
uint64 intset_memory_usage (IntegerSet *intset)
 
void intset_add_member (IntegerSet *intset, uint64 x)
 
bool intset_is_member (IntegerSet *intset, uint64 x)
 
void intset_begin_iterate (IntegerSet *intset)
 
bool intset_iterate_next (IntegerSet *intset, uint64 *next)
 

Variables

static const struct simple8b_mode simple8b_modes [17]
 

Macro Definition Documentation

◆ EMPTY_CODEWORD

#define EMPTY_CODEWORD   UINT64CONST(0x0FFFFFFFFFFFFFFF)

Definition at line 860 of file integerset.c.

Referenced by simple8b_contains(), simple8b_decode(), and simple8b_encode().

◆ MAX_BUFFERED_VALUES

#define MAX_BUFFERED_VALUES   (MAX_VALUES_PER_LEAF_ITEM * 2)

Definition at line 188 of file integerset.c.

Referenced by intset_add_member().

◆ MAX_INTERNAL_ITEMS

#define MAX_INTERNAL_ITEMS   64

Definition at line 96 of file integerset.c.

Referenced by intset_update_upper().

◆ MAX_LEAF_ITEMS

#define MAX_LEAF_ITEMS   64

Definition at line 97 of file integerset.c.

Referenced by intset_flush_buffered_values().

◆ MAX_TREE_LEVELS

#define MAX_TREE_LEVELS   11

Definition at line 111 of file integerset.c.

Referenced by intset_update_upper().

◆ MAX_VALUES_PER_LEAF_ITEM

#define MAX_VALUES_PER_LEAF_ITEM   (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)

Definition at line 168 of file integerset.c.

Referenced by intset_flush_buffered_values().

◆ SIMPLE8B_MAX_VALUES_PER_CODEWORD

#define SIMPLE8B_MAX_VALUES_PER_CODEWORD   240

Definition at line 85 of file integerset.c.

Typedef Documentation

◆ intset_internal_node

Definition at line 137 of file integerset.c.

◆ intset_leaf_node

Definition at line 136 of file integerset.c.

◆ intset_node

typedef struct intset_node intset_node

Definition at line 135 of file integerset.c.

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

static int intset_binsrch_leaf ( uint64  value,
leaf_item arr,
int  arr_elems,
bool  nextkey 
)
static

Definition at line 750 of file integerset.c.

Referenced by intset_is_member().

751 {
752  int low,
753  high,
754  mid;
755 
756  low = 0;
757  high = arr_elems;
758  while (high > low)
759  {
760  mid = low + (high - low) / 2;
761 
762  if (nextkey)
763  {
764  if (item >= arr[mid].first)
765  low = mid + 1;
766  else
767  high = mid;
768  }
769  else
770  {
771  if (item > arr[mid].first)
772  low = mid + 1;
773  else
774  high = mid;
775  }
776  }
777 
778  return low;
779 }

◆ intset_binsrch_uint64()

static int intset_binsrch_uint64 ( uint64  value,
uint64 *  arr,
int  arr_elems,
bool  nextkey 
)
static

Definition at line 717 of file integerset.c.

Referenced by intset_is_member().

718 {
719  int low,
720  high,
721  mid;
722 
723  low = 0;
724  high = arr_elems;
725  while (high > low)
726  {
727  mid = low + (high - low) / 2;
728 
729  if (nextkey)
730  {
731  if (item >= arr[mid])
732  low = mid + 1;
733  else
734  high = mid;
735  }
736  else
737  {
738  if (item > arr[mid])
739  low = mid + 1;
740  else
741  high = mid;
742  }
743  }
744 
745  return low;
746 }

◆ 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_flush_buffered_values()

static void intset_flush_buffered_values ( IntegerSet intset)
static

Definition at line 397 of file integerset.c.

References IntegerSet::buffered_values, leaf_item::codeword, leaf_item::first, intset_new_leaf_node(), intset_update_upper(), intset_leaf_node::items, IntegerSet::leftmost_leaf, MAX_LEAF_ITEMS, MAX_VALUES_PER_LEAF_ITEM, memmove, intset_leaf_node::next, IntegerSet::num_buffered_values, intset_leaf_node::num_items, IntegerSet::num_levels, IntegerSet::rightmost_nodes, IntegerSet::root, simple8b_encode(), and values.

Referenced by intset_add_member().

398 {
399  uint64 *values = intset->buffered_values;
400  uint64 num_values = intset->num_buffered_values;
401  int num_packed = 0;
402  intset_leaf_node *leaf;
403 
404  leaf = (intset_leaf_node *) intset->rightmost_nodes[0];
405 
406  /*
407  * If the tree is completely empty, create the first leaf page, which is
408  * also the root.
409  */
410  if (leaf == NULL)
411  {
412  /*
413  * This is the very first item in the set.
414  *
415  * Allocate root node. It's also a leaf.
416  */
417  leaf = intset_new_leaf_node(intset);
418 
419  intset->root = (intset_node *) leaf;
420  intset->leftmost_leaf = leaf;
421  intset->rightmost_nodes[0] = (intset_node *) leaf;
422  intset->num_levels = 1;
423  }
424 
425  /*
426  * If there are less than MAX_VALUES_PER_LEAF_ITEM values in the buffer,
427  * stop. In most cases, we cannot encode that many values in a single
428  * value, but this way, the encoder doesn't have to worry about running
429  * out of input.
430  */
431  while (num_values - num_packed >= MAX_VALUES_PER_LEAF_ITEM)
432  {
433  leaf_item item;
434  int num_encoded;
435 
436  /*
437  * Construct the next leaf item, packing as many buffered values as
438  * possible.
439  */
440  item.first = values[num_packed];
441  item.codeword = simple8b_encode(&values[num_packed + 1],
442  &num_encoded,
443  item.first);
444 
445  /*
446  * Add the item to the node, allocating a new node if the old one is
447  * full.
448  */
449  if (leaf->num_items >= MAX_LEAF_ITEMS)
450  {
451  /* Allocate new leaf and link it to the tree */
452  intset_leaf_node *old_leaf = leaf;
453 
454  leaf = intset_new_leaf_node(intset);
455  old_leaf->next = leaf;
456  intset->rightmost_nodes[0] = (intset_node *) leaf;
457  intset_update_upper(intset, 1, (intset_node *) leaf, item.first);
458  }
459  leaf->items[leaf->num_items++] = item;
460 
461  num_packed += 1 + num_encoded;
462  }
463 
464  /*
465  * Move any remaining buffered values to the beginning of the array.
466  */
467  if (num_packed < intset->num_buffered_values)
468  {
469  memmove(&intset->buffered_values[0],
470  &intset->buffered_values[num_packed],
471  (intset->num_buffered_values - num_packed) * sizeof(uint64));
472  }
473  intset->num_buffered_values -= num_packed;
474 }
static uint64 simple8b_encode(const uint64 *ints, int *num_encoded, uint64 base)
Definition: integerset.c:876
int num_levels
Definition: integerset.c:223
intset_node * root
Definition: integerset.c:224
uint64 codeword
Definition: integerset.c:165
#define memmove(d, s, c)
Definition: c.h:1267
intset_leaf_node * next
Definition: integerset.c:176
intset_leaf_node * leftmost_leaf
Definition: integerset.c:226
uint64 first
Definition: integerset.c:164
static void intset_update_upper(IntegerSet *intset, int level, intset_node *child, uint64 child_key)
Definition: integerset.c:482
intset_node * rightmost_nodes[MAX_TREE_LEVELS]
Definition: integerset.c:225
static intset_leaf_node * intset_new_leaf_node(IntegerSet *intset)
Definition: integerset.c:332
#define MAX_VALUES_PER_LEAF_ITEM
Definition: integerset.c:168
uint64 buffered_values[MAX_BUFFERED_VALUES]
Definition: integerset.c:231
int num_buffered_values
Definition: integerset.c:232
#define MAX_LEAF_ITEMS
Definition: integerset.c:97
static Datum values[MAXATTR]
Definition: bootstrap.c:167
leaf_item items[MAX_LEAF_ITEMS]
Definition: integerset.c:178

◆ 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_new_internal_node()

static intset_internal_node* intset_new_internal_node ( IntegerSet intset)
static

Definition at line 317 of file integerset.c.

References IntegerSet::context, GetMemoryChunkSpace(), intset_internal_node::level, IntegerSet::mem_used, MemoryContextAlloc(), and intset_internal_node::num_items.

Referenced by intset_update_upper().

318 {
320 
322  sizeof(intset_internal_node));
323  intset->mem_used += GetMemoryChunkSpace(n);
324 
325  n->level = 0; /* caller must set */
326  n->num_items = 0;
327 
328  return n;
329 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:796
MemoryContext context
Definition: integerset.c:208
uint64 mem_used
Definition: integerset.c:209

◆ intset_new_leaf_node()

static intset_leaf_node* intset_new_leaf_node ( IntegerSet intset)
static

Definition at line 332 of file integerset.c.

References IntegerSet::context, GetMemoryChunkSpace(), intset_leaf_node::level, IntegerSet::mem_used, MemoryContextAlloc(), intset_leaf_node::next, and intset_leaf_node::num_items.

Referenced by intset_flush_buffered_values().

333 {
334  intset_leaf_node *n;
335 
337  sizeof(intset_leaf_node));
338  intset->mem_used += GetMemoryChunkSpace(n);
339 
340  n->level = 0;
341  n->num_items = 0;
342  n->next = NULL;
343 
344  return n;
345 }
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:427
intset_leaf_node * next
Definition: integerset.c:176
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:796
MemoryContext context
Definition: integerset.c:208
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

◆ intset_update_upper()

static void intset_update_upper ( IntegerSet intset,
int  level,
intset_node child,
uint64  child_key 
)
static

Definition at line 482 of file integerset.c.

References Assert, intset_internal_node::downlinks, elog, ERROR, intset_new_internal_node(), intset_node::level, intset_internal_node::level, MAX_INTERNAL_ITEMS, MAX_TREE_LEVELS, intset_internal_node::num_items, IntegerSet::num_levels, IntegerSet::rightmost_nodes, IntegerSet::root, and intset_internal_node::values.

Referenced by intset_flush_buffered_values().

484 {
485  intset_internal_node *parent;
486 
487  Assert(level > 0);
488 
489  /*
490  * Create a new root node, if necessary.
491  */
492  if (level >= intset->num_levels)
493  {
494  intset_node *oldroot = intset->root;
495  uint64 downlink_key;
496 
497  /* MAX_TREE_LEVELS should be more than enough, this shouldn't happen */
498  if (intset->num_levels == MAX_TREE_LEVELS)
499  elog(ERROR, "could not expand integer set, maximum number of levels reached");
500  intset->num_levels++;
501 
502  /*
503  * Get the first value on the old root page, to be used as the
504  * downlink.
505  */
506  if (intset->root->level == 0)
507  downlink_key = ((intset_leaf_node *) oldroot)->items[0].first;
508  else
509  downlink_key = ((intset_internal_node *) oldroot)->values[0];
510 
511  parent = intset_new_internal_node(intset);
512  parent->level = level;
513  parent->values[0] = downlink_key;
514  parent->downlinks[0] = oldroot;
515  parent->num_items = 1;
516 
517  intset->root = (intset_node *) parent;
518  intset->rightmost_nodes[level] = (intset_node *) parent;
519  }
520 
521  /*
522  * Place the downlink on the parent page.
523  */
524  parent = (intset_internal_node *) intset->rightmost_nodes[level];
525 
526  if (parent->num_items < MAX_INTERNAL_ITEMS)
527  {
528  parent->values[parent->num_items] = child_key;
529  parent->downlinks[parent->num_items] = child;
530  parent->num_items++;
531  }
532  else
533  {
534  /*
535  * Doesn't fit. Allocate new parent, with the downlink as the first
536  * item on it, and recursively insert the downlink to the new parent
537  * to the grandparent.
538  */
539  parent = intset_new_internal_node(intset);
540  parent->level = level;
541  parent->values[0] = child_key;
542  parent->downlinks[0] = child;
543  parent->num_items = 1;
544 
545  intset->rightmost_nodes[level] = (intset_node *) parent;
546 
547  intset_update_upper(intset, level + 1, (intset_node *) parent, child_key);
548  }
549 }
int num_levels
Definition: integerset.c:223
intset_node * root
Definition: integerset.c:224
#define ERROR
Definition: elog.h:43
intset_node * downlinks[MAX_INTERNAL_ITEMS]
Definition: integerset.c:158
#define MAX_INTERNAL_ITEMS
Definition: integerset.c:96
static void intset_update_upper(IntegerSet *intset, int level, intset_node *child, uint64 child_key)
Definition: integerset.c:482
intset_node * rightmost_nodes[MAX_TREE_LEVELS]
Definition: integerset.c:225
uint64 values[MAX_INTERNAL_ITEMS]
Definition: integerset.c:157
uint16 level
Definition: integerset.c:142
#define MAX_TREE_LEVELS
Definition: integerset.c:111
#define Assert(condition)
Definition: c.h:739
#define elog(elevel,...)
Definition: elog.h:228
static intset_internal_node * intset_new_internal_node(IntegerSet *intset)
Definition: integerset.c:317

◆ simple8b_contains()

static bool simple8b_contains ( uint64  codeword,
uint64  key,
uint64  base 
)
static

Definition at line 1007 of file integerset.c.

References simple8b_mode::bits_per_int, EMPTY_CODEWORD, i, simple8b_mode::num_ints, and simple8b_modes.

Referenced by intset_is_member().

1008 {
1009  int selector = (codeword >> 60);
1010  int nints = simple8b_modes[selector].num_ints;
1011  int bits = simple8b_modes[selector].bits_per_int;
1012 
1013  if (codeword == EMPTY_CODEWORD)
1014  return false;
1015 
1016  if (bits == 0)
1017  {
1018  /* Special handling for 0-bit cases. */
1019  return (key - base) <= nints;
1020  }
1021  else
1022  {
1023  uint64 mask = (UINT64CONST(1) << bits) - 1;
1024  uint64 curr_value;
1025 
1026  curr_value = base;
1027  for (int i = 0; i < nints; i++)
1028  {
1029  uint64 diff = codeword & mask;
1030 
1031  curr_value += 1 + diff;
1032 
1033  if (curr_value >= key)
1034  {
1035  if (curr_value == key)
1036  return true;
1037  else
1038  return false;
1039  }
1040 
1041  codeword >>= bits;
1042  }
1043  }
1044  return false;
1045 }
uint8 bits_per_int
Definition: integerset.c:826
#define EMPTY_CODEWORD
Definition: integerset.c:860
int i
static const struct simple8b_mode simple8b_modes[17]
uint8 num_ints
Definition: integerset.c:827

◆ simple8b_decode()

static int simple8b_decode ( uint64  codeword,
uint64 *  decoded,
uint64  base 
)
static

Definition at line 978 of file integerset.c.

References simple8b_mode::bits_per_int, EMPTY_CODEWORD, i, simple8b_mode::num_ints, and simple8b_modes.

Referenced by intset_iterate_next().

979 {
980  int selector = (codeword >> 60);
981  int nints = simple8b_modes[selector].num_ints;
982  int bits = simple8b_modes[selector].bits_per_int;
983  uint64 mask = (UINT64CONST(1) << bits) - 1;
984  uint64 curr_value;
985 
986  if (codeword == EMPTY_CODEWORD)
987  return 0;
988 
989  curr_value = base;
990  for (int i = 0; i < nints; i++)
991  {
992  uint64 diff = codeword & mask;
993 
994  curr_value += 1 + diff;
995  decoded[i] = curr_value;
996  codeword >>= bits;
997  }
998  return nints;
999 }
uint8 bits_per_int
Definition: integerset.c:826
#define EMPTY_CODEWORD
Definition: integerset.c:860
int i
static const struct simple8b_mode simple8b_modes[17]
uint8 num_ints
Definition: integerset.c:827

◆ simple8b_encode()

static uint64 simple8b_encode ( const uint64 *  ints,
int *  num_encoded,
uint64  base 
)
static

Definition at line 876 of file integerset.c.

References Assert, simple8b_mode::bits_per_int, EMPTY_CODEWORD, i, simple8b_mode::num_ints, and simple8b_modes.

Referenced by intset_flush_buffered_values().

877 {
878  int selector;
879  int nints;
880  int bits;
881  uint64 diff;
882  uint64 last_val;
883  uint64 codeword;
884  int i;
885 
886  Assert(ints[0] > base);
887 
888  /*
889  * Select the "mode" to use for this codeword.
890  *
891  * In each iteration, check if the next value can be represented in the
892  * current mode we're considering. If it's too large, then step up the
893  * mode to a wider one, and repeat. If it fits, move on to the next
894  * integer. Repeat until the codeword is full, given the current mode.
895  *
896  * Note that we don't have any way to represent unused slots in the
897  * codeword, so we require each codeword to be "full". It is always
898  * possible to produce a full codeword unless the very first delta is too
899  * large to be encoded. For example, if the first delta is small but the
900  * second is too large to be encoded, we'll end up using the last "mode",
901  * which has nints == 1.
902  */
903  selector = 0;
904  nints = simple8b_modes[0].num_ints;
905  bits = simple8b_modes[0].bits_per_int;
906  diff = ints[0] - base - 1;
907  last_val = ints[0];
908  i = 0; /* number of deltas we have accepted */
909  for (;;)
910  {
911  if (diff >= (UINT64CONST(1) << bits))
912  {
913  /* too large, step up to next mode */
914  selector++;
915  nints = simple8b_modes[selector].num_ints;
916  bits = simple8b_modes[selector].bits_per_int;
917  /* we might already have accepted enough deltas for this mode */
918  if (i >= nints)
919  break;
920  }
921  else
922  {
923  /* accept this delta; then done if codeword is full */
924  i++;
925  if (i >= nints)
926  break;
927  /* examine next delta */
928  Assert(ints[i] > last_val);
929  diff = ints[i] - last_val - 1;
930  last_val = ints[i];
931  }
932  }
933 
934  if (nints == 0)
935  {
936  /*
937  * The first delta is too large to be encoded with Simple-8b.
938  *
939  * If there is at least one not-too-large integer in the input, we
940  * will encode it using mode 15 (or a more compact mode). Hence, we
941  * can only get here if the *first* delta is >= 2^60.
942  */
943  Assert(i == 0);
944  *num_encoded = 0;
945  return EMPTY_CODEWORD;
946  }
947 
948  /*
949  * Encode the integers using the selected mode. Note that we shift them
950  * into the codeword in reverse order, so that they will come out in the
951  * correct order in the decoder.
952  */
953  codeword = 0;
954  if (bits > 0)
955  {
956  for (i = nints - 1; i > 0; i--)
957  {
958  diff = ints[i] - ints[i - 1] - 1;
959  codeword |= diff;
960  codeword <<= bits;
961  }
962  diff = ints[0] - base - 1;
963  codeword |= diff;
964  }
965 
966  /* add selector to the codeword, and return */
967  codeword |= (uint64) selector << 60;
968 
969  *num_encoded = nints;
970  return codeword;
971 }
uint8 bits_per_int
Definition: integerset.c:826
#define EMPTY_CODEWORD
Definition: integerset.c:860
#define Assert(condition)
Definition: c.h:739
int i
static const struct simple8b_mode simple8b_modes[17]
uint8 num_ints
Definition: integerset.c:827

Variable Documentation

◆ simple8b_modes

const struct simple8b_mode simple8b_modes[17]
static
Initial value:
=
{
{0, 240},
{0, 120},
{1, 60},
{2, 30},
{3, 20},
{4, 15},
{5, 12},
{6, 10},
{7, 8},
{8, 7},
{10, 6},
{12, 5},
{15, 4},
{20, 3},
{30, 2},
{60, 1},
{0, 0}
}

Referenced by simple8b_contains(), simple8b_decode(), and simple8b_encode().