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);
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");
440 item.
first = values[num_packed];
455 old_leaf->
next = leaf;
461 num_packed += 1 + num_encoded;
467 if (num_packed < intset->num_buffered_values)
499 elog(
ERROR,
"could not expand integer set, maximum number of levels reached");
513 parent->
values[0] = downlink_key;
541 parent->
values[0] = child_key;
587 for (level = intset->
num_levels - 1; level > 0; level--)
607 item = &leaf->
items[itemno - 1];
610 if (item->
first == x)
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))
928 Assert(ints[i] > last_val);
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 uint64 simple8b_encode(const uint64 *ints, int *num_encoded, uint64 base)
IntegerSet * intset_create(void)
uint64 intset_memory_usage(IntegerSet *intset)
bool intset_iterate_next(IntegerSet *intset, uint64 *next)
Size GetMemoryChunkSpace(void *pointer)
#define MAX_BUFFERED_VALUES
uint64 iter_values_buf[MAX_VALUES_PER_LEAF_ITEM]
const uint64 * iter_values
static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)
void intset_add_member(IntegerSet *intset, uint64 x)
intset_node * downlinks[MAX_INTERNAL_ITEMS]
#define MAX_INTERNAL_ITEMS
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
static int intset_binsrch_uint64(uint64 value, uint64 *arr, int arr_elems, bool nextkey)
intset_leaf_node * leftmost_leaf
static void intset_update_upper(IntegerSet *intset, int level, intset_node *child, uint64 child_key)
MemoryContext CurrentMemoryContext
void intset_begin_iterate(IntegerSet *intset)
intset_node * rightmost_nodes[MAX_TREE_LEVELS]
uint64 values[MAX_INTERNAL_ITEMS]
static intset_leaf_node * intset_new_leaf_node(IntegerSet *intset)
#define MAX_VALUES_PER_LEAF_ITEM
uint64 buffered_values[MAX_BUFFERED_VALUES]
intset_leaf_node * iter_node
#define Assert(condition)
static void intset_flush_buffered_values(IntegerSet *intset)
static int intset_binsrch_leaf(uint64 value, leaf_item *arr, int arr_elems, bool nextkey)
static Datum values[MAXATTR]
void * MemoryContextAlloc(MemoryContext context, Size size)
static intset_internal_node * intset_new_internal_node(IntegerSet *intset)
bool intset_is_member(IntegerSet *intset, uint64 x)
static const struct simple8b_mode simple8b_modes[17]
leaf_item items[MAX_LEAF_ITEMS]
uint64 intset_num_entries(IntegerSet *intset)