83#define SIMPLE8B_MAX_VALUES_PER_CODEWORD 240
94#define MAX_INTERNAL_ITEMS 64
95#define MAX_LEAF_ITEMS 64
109#define MAX_TREE_LEVELS 11
166#define MAX_VALUES_PER_LEAF_ITEM (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)
186#define MAX_BUFFERED_VALUES (MAX_VALUES_PER_LEAF_ITEM * 2)
292 intset->highest_value = 0;
296 memset(
intset->rightmost_nodes, 0,
sizeof(
intset->rightmost_nodes));
297 intset->leftmost_leaf = NULL;
299 intset->num_buffered_values = 0;
301 intset->iter_active =
false;
305 intset->iter_num_values = 0;
306 intset->iter_values = NULL;
351 return intset->num_entries;
372 elog(
ERROR,
"cannot add new values to integer set while iteration is in progress");
374 if (x <= intset->highest_value &&
intset->num_entries > 0)
375 elog(
ERROR,
"cannot add value to integer set out of order");
386 intset->num_buffered_values++;
418 intset->leftmost_leaf = leaf;
453 old_leaf->
next = leaf;
459 num_packed += 1 + num_encoded;
465 if (num_packed < intset->num_buffered_values)
467 memmove(&
intset->buffered_values[0],
468 &
intset->buffered_values[num_packed],
469 (
intset->num_buffered_values - num_packed) *
sizeof(
uint64));
471 intset->num_buffered_values -= num_packed;
490 if (level >=
intset->num_levels)
497 elog(
ERROR,
"could not expand integer set, maximum number of levels reached");
504 if (
intset->root->level == 0)
510 parent->
level = level;
511 parent->
values[0] = downlink_key;
538 parent->
level = level;
539 parent->
values[0] = child_key;
564 if (
intset->num_buffered_values > 0 &&
x >=
intset->buffered_values[0])
568 intset->num_buffered_values,
570 if (itemno >=
intset->num_buffered_values)
573 return (
intset->buffered_values[itemno] ==
x);
583 for (level =
intset->num_levels - 1; level > 0; level--)
603 item = &leaf->
items[itemno - 1];
626 intset->iter_active =
true;
630 intset->iter_num_values = 0;
661 item = &
intset->iter_node->items[
intset->iter_itemno++];
665 &
intset->iter_values_buf[1],
667 intset->iter_num_values = num_decoded + 1;
696 intset->iter_active =
false;
723 mid = low + (high - low) / 2;
727 if (item >= arr[mid])
756 mid = low + (high - low) / 2;
760 if (item >= arr[mid].first)
767 if (item > arr[mid].first)
856#define EMPTY_CODEWORD UINT64CONST(0x0FFFFFFFFFFFFFFF)
902 diff = ints[0] - base - 1;
925 diff = ints[
i] - last_val - 1;
952 for (
i = nints - 1;
i > 0;
i--)
954 diff = ints[
i] - ints[
i - 1] - 1;
958 diff = ints[0] - base - 1;
963 codeword |= (
uint64) selector << 60;
965 *num_encoded = nints;
976 int selector = (codeword >> 60);
986 for (
int i = 0;
i < nints;
i++)
988 uint64 diff = codeword & mask;
990 curr_value += 1 + diff;
991 decoded[
i] = curr_value;
1005 int selector = (codeword >> 60);
1015 return (
key - base) <= nints;
1023 for (
int i = 0;
i < nints;
i++)
1025 uint64 diff = codeword & mask;
1027 curr_value += 1 + diff;
1029 if (curr_value >=
key)
1031 if (curr_value ==
key)
Datum intset(PG_FUNCTION_ARGS)
static Datum values[MAXATTR]
#define Assert(condition)
#define MAX_VALUES_PER_LEAF_ITEM
uint64 intset_memory_usage(IntegerSet *intset)
uint64 intset_num_entries(IntegerSet *intset)
static void intset_update_upper(IntegerSet *intset, int level, intset_node *child, uint64 child_key)
bool intset_is_member(IntegerSet *intset, uint64 x)
#define MAX_INTERNAL_ITEMS
#define MAX_BUFFERED_VALUES
static intset_internal_node * intset_new_internal_node(IntegerSet *intset)
void intset_begin_iterate(IntegerSet *intset)
static int intset_binsrch_uint64(uint64 item, uint64 *arr, int arr_elems, bool nextkey)
static void intset_flush_buffered_values(IntegerSet *intset)
static uint64 simple8b_encode(const uint64 *ints, int *num_encoded, uint64 base)
bool intset_iterate_next(IntegerSet *intset, uint64 *next)
static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)
IntegerSet * intset_create(void)
void intset_add_member(IntegerSet *intset, uint64 x)
static const struct simple8b_mode simple8b_modes[17]
static int intset_binsrch_leaf(uint64 item, leaf_item *arr, int arr_elems, bool nextkey)
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
static intset_leaf_node * intset_new_leaf_node(IntegerSet *intset)
if(TABLE==NULL||TABLE_index==NULL)
void * MemoryContextAlloc(MemoryContext context, Size size)
Size GetMemoryChunkSpace(void *pointer)
MemoryContext CurrentMemoryContext
intset_node * rightmost_nodes[MAX_TREE_LEVELS]
uint64 iter_values_buf[MAX_VALUES_PER_LEAF_ITEM]
intset_leaf_node * leftmost_leaf
const uint64 * iter_values
uint64 buffered_values[MAX_BUFFERED_VALUES]
intset_leaf_node * iter_node
intset_node * downlinks[MAX_INTERNAL_ITEMS]
uint64 values[MAX_INTERNAL_ITEMS]
leaf_item items[MAX_LEAF_ITEMS]