85 #define SIMPLE8B_MAX_VALUES_PER_CODEWORD 240
96 #define MAX_INTERNAL_ITEMS 64
97 #define MAX_LEAF_ITEMS 64
111 #define MAX_TREE_LEVELS 11
168 #define MAX_VALUES_PER_LEAF_ITEM (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)
188 #define MAX_BUFFERED_VALUES (MAX_VALUES_PER_LEAF_ITEM * 2)
272 static uint64
simple8b_encode(
const uint64 *ints,
int *num_encoded, uint64 base);
273 static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base);
294 intset->highest_value = 0;
298 memset(
intset->rightmost_nodes, 0,
sizeof(
intset->rightmost_nodes));
299 intset->leftmost_leaf = NULL;
301 intset->num_buffered_values = 0;
303 intset->iter_active =
false;
307 intset->iter_num_values = 0;
308 intset->iter_values = NULL;
353 return intset->num_entries;
374 elog(
ERROR,
"cannot add new values to integer set while iteration is in progress");
376 if (x <= intset->highest_value &&
intset->num_entries > 0)
377 elog(
ERROR,
"cannot add value to integer set out of order");
388 intset->num_buffered_values++;
400 uint64 num_values =
intset->num_buffered_values;
420 intset->leftmost_leaf = leaf;
455 old_leaf->
next = leaf;
461 num_packed += 1 + num_encoded;
467 if (num_packed < intset->num_buffered_values)
469 memmove(&
intset->buffered_values[0],
470 &
intset->buffered_values[num_packed],
471 (
intset->num_buffered_values - num_packed) *
sizeof(uint64));
473 intset->num_buffered_values -= num_packed;
492 if (level >=
intset->num_levels)
499 elog(
ERROR,
"could not expand integer set, maximum number of levels reached");
506 if (
intset->root->level == 0)
512 parent->
level = level;
513 parent->
values[0] = downlink_key;
540 parent->
level = level;
541 parent->
values[0] = child_key;
566 if (
intset->num_buffered_values > 0 &&
x >=
intset->buffered_values[0])
572 intset->num_buffered_values,
574 if (itemno >=
intset->num_buffered_values)
577 return (
intset->buffered_values[itemno] ==
x);
587 for (level =
intset->num_levels - 1; level > 0; level--)
607 item = &leaf->
items[itemno - 1];
630 intset->iter_active =
true;
634 intset->iter_num_values = 0;
665 item = &
intset->iter_node->items[
intset->iter_itemno++];
669 &
intset->iter_values_buf[1],
671 intset->iter_num_values = num_decoded + 1;
688 if (
intset->iter_values == (
const uint64 *)
intset->iter_values_buf)
700 intset->iter_active =
false;
727 mid = low + (high - low) / 2;
731 if (item >= arr[mid])
760 mid = low + (high - low) / 2;
764 if (item >= arr[mid].first)
771 if (item > arr[mid].first)
860 #define EMPTY_CODEWORD UINT64CONST(0x0FFFFFFFFFFFFFFF)
906 diff = ints[0] - base - 1;
911 if (diff >= (UINT64CONST(1) << bits))
929 diff = ints[
i] - last_val - 1;
956 for (
i = nints - 1;
i > 0;
i--)
958 diff = ints[
i] - ints[
i - 1] - 1;
962 diff = ints[0] - base - 1;
967 codeword |= (uint64) selector << 60;
969 *num_encoded = nints;
980 int selector = (codeword >> 60);
983 uint64 mask = (UINT64CONST(1) << bits) - 1;
990 for (
int i = 0;
i < nints;
i++)
992 uint64 diff = codeword & mask;
994 curr_value += 1 + diff;
995 decoded[
i] = curr_value;
1009 int selector = (codeword >> 60);
1019 return (
key - base) <= nints;
1023 uint64 mask = (UINT64CONST(1) << bits) - 1;
1027 for (
int i = 0;
i < nints;
i++)
1029 uint64 diff = codeword & mask;
1031 curr_value += 1 + diff;
1033 if (curr_value >=
key)
1035 if (curr_value ==
key)
Datum intset(PG_FUNCTION_ARGS)
static Datum values[MAXATTR]
#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
IntegerSet * intset_create(void)
#define MAX_BUFFERED_VALUES
static intset_leaf_node * intset_new_leaf_node(IntegerSet *intset)
void intset_begin_iterate(IntegerSet *intset)
static void intset_flush_buffered_values(IntegerSet *intset)
static uint64 simple8b_encode(const uint64 *ints, int *num_encoded, uint64 base)
static int intset_binsrch_uint64(uint64 value, uint64 *arr, int arr_elems, bool nextkey)
bool intset_iterate_next(IntegerSet *intset, uint64 *next)
static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)
void intset_add_member(IntegerSet *intset, uint64 x)
static const struct simple8b_mode simple8b_modes[17]
static intset_internal_node * intset_new_internal_node(IntegerSet *intset)
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
static int intset_binsrch_leaf(uint64 value, leaf_item *arr, int arr_elems, bool nextkey)
Assert(fmt[strlen(fmt) - 1] !='\n')
Size GetMemoryChunkSpace(void *pointer)
MemoryContext CurrentMemoryContext
void * MemoryContextAlloc(MemoryContext context, Size size)
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]