84 #define SIMPLE8B_MAX_VALUES_PER_CODEWORD 240
95 #define MAX_INTERNAL_ITEMS 64
96 #define MAX_LEAF_ITEMS 64
110 #define MAX_TREE_LEVELS 11
167 #define MAX_VALUES_PER_LEAF_ITEM (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)
187 #define MAX_BUFFERED_VALUES (MAX_VALUES_PER_LEAF_ITEM * 2)
271 static uint64
simple8b_encode(
const uint64 *ints,
int *num_encoded, uint64 base);
272 static int simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base);
293 intset->highest_value = 0;
297 memset(
intset->rightmost_nodes, 0,
sizeof(
intset->rightmost_nodes));
298 intset->leftmost_leaf = NULL;
300 intset->num_buffered_values = 0;
302 intset->iter_active =
false;
306 intset->iter_num_values = 0;
307 intset->iter_values = NULL;
352 return intset->num_entries;
373 elog(
ERROR,
"cannot add new values to integer set while iteration is in progress");
375 if (x <= intset->highest_value &&
intset->num_entries > 0)
376 elog(
ERROR,
"cannot add value to integer set out of order");
387 intset->num_buffered_values++;
399 uint64 num_values =
intset->num_buffered_values;
419 intset->leftmost_leaf = leaf;
454 old_leaf->
next = leaf;
460 num_packed += 1 + num_encoded;
466 if (num_packed < intset->num_buffered_values)
468 memmove(&
intset->buffered_values[0],
469 &
intset->buffered_values[num_packed],
470 (
intset->num_buffered_values - num_packed) *
sizeof(uint64));
472 intset->num_buffered_values -= num_packed;
491 if (level >=
intset->num_levels)
498 elog(
ERROR,
"could not expand integer set, maximum number of levels reached");
505 if (
intset->root->level == 0)
511 parent->
level = level;
512 parent->
values[0] = downlink_key;
539 parent->
level = level;
540 parent->
values[0] = child_key;
565 if (
intset->num_buffered_values > 0 &&
x >=
intset->buffered_values[0])
569 intset->num_buffered_values,
571 if (itemno >=
intset->num_buffered_values)
574 return (
intset->buffered_values[itemno] ==
x);
584 for (level =
intset->num_levels - 1; level > 0; level--)
604 item = &leaf->
items[itemno - 1];
627 intset->iter_active =
true;
631 intset->iter_num_values = 0;
662 item = &
intset->iter_node->items[
intset->iter_itemno++];
666 &
intset->iter_values_buf[1],
668 intset->iter_num_values = num_decoded + 1;
685 if (
intset->iter_values == (
const uint64 *)
intset->iter_values_buf)
697 intset->iter_active =
false;
724 mid = low + (high - low) / 2;
728 if (item >= arr[mid])
757 mid = low + (high - low) / 2;
761 if (item >= arr[mid].first)
768 if (item > arr[mid].first)
857 #define EMPTY_CODEWORD UINT64CONST(0x0FFFFFFFFFFFFFFF)
903 diff = ints[0] - base - 1;
908 if (diff >= (UINT64CONST(1) << bits))
926 diff = ints[
i] - last_val - 1;
953 for (
i = nints - 1;
i > 0;
i--)
955 diff = ints[
i] - ints[
i - 1] - 1;
959 diff = ints[0] - base - 1;
964 codeword |= (uint64) selector << 60;
966 *num_encoded = nints;
977 int selector = (codeword >> 60);
980 uint64 mask = (UINT64CONST(1) << bits) - 1;
987 for (
int i = 0;
i < nints;
i++)
989 uint64 diff = codeword & mask;
991 curr_value += 1 + diff;
992 decoded[
i] = curr_value;
1006 int selector = (codeword >> 60);
1016 return (
key - base) <= nints;
1020 uint64 mask = (UINT64CONST(1) << bits) - 1;
1024 for (
int i = 0;
i < nints;
i++)
1026 uint64 diff = codeword & mask;
1028 curr_value += 1 + diff;
1030 if (curr_value >=
key)
1032 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
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 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)
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 intset_internal_node * intset_new_internal_node(IntegerSet *intset)
static bool simple8b_contains(uint64 codeword, uint64 key, uint64 base)
if(TABLE==NULL||TABLE_index==NULL)
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]