| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * idset.h - Minimal open-addressing set of uint64 ids | ||
| 6 | * | ||
| 7 | * Membership tracking for per-query scratch use: linear probing over a | ||
| 8 | * power-of-two slot array, no deletion, no resizing. Callers size the | ||
| 9 | * set once for the expected population; the load factor stays at or | ||
| 10 | * below one half, keeping probe chains short. | ||
| 11 | * | ||
| 12 | * Id 0 doubles as the empty-slot marker, so a literal id 0 is tracked | ||
| 13 | * in a dedicated flag instead of a slot. Posting-encoded TIDs are | ||
| 14 | * never 0 (block 0 is the metapage), so the flag is idle on the scan | ||
| 15 | * paths and exists for generic callers. | ||
| 16 | * | ||
| 17 | * Used by both standalone and PG builds. | ||
| 18 | */ | ||
| 19 | #ifndef VS_CORE_IDSET_H | ||
| 20 | #define VS_CORE_IDSET_H | ||
| 21 | |||
| 22 | #include <stdbool.h> | ||
| 23 | #include <stdint.h> | ||
| 24 | |||
| 25 | #include "core/log.h" | ||
| 26 | #include "core/memory.h" | ||
| 27 | |||
| 28 | /* | ||
| 29 | * 2^64 divided by the golden ratio, rounded to odd (the splitmix64 | ||
| 30 | * increment). Multiplying by it scatters consecutive or structured | ||
| 31 | * ids across the high bits, and the top bits of the product pick the | ||
| 32 | * slot (Fibonacci hashing). The low bits would not do: bit i of the | ||
| 33 | * product depends only on bits 0..i of the id, and a posting-encoded | ||
| 34 | * TID keeps its tuple offset in the low 16. | ||
| 35 | */ | ||
| 36 | #define VS_HASH_GOLDEN_GAMMA 0x9E3779B97F4A7C15ULL | ||
| 37 | |||
| 38 | typedef struct VsIdSet | ||
| 39 | { | ||
| 40 | uint64_t *slots; | ||
| 41 | uint32_t mask; /* nslots - 1; nslots is a power of two */ | ||
| 42 | uint32_t shift; /* 64 - log2(nslots) */ | ||
| 43 | bool has_zero; | ||
| 44 | } VsIdSet; | ||
| 45 | |||
| 46 | /* | ||
| 47 | * Size for up to `expected` distinct ids at a load factor of at most | ||
| 48 | * one half. The set neither resizes nor tracks its population: | ||
| 49 | * inserting more than nslots distinct ids would probe forever, so the | ||
| 50 | * caller's bound must hold. Populations needing more than the 2^31 | ||
| 51 | * slot ceiling (2^30 ids -- a 24+ GB candidate buffer upstream) are | ||
| 52 | * rejected outright rather than proceeding undersized. | ||
| 53 | */ | ||
| 54 | static inline void | ||
| 55 | 4254 | vs_idset_init(VsIdSet *set, uint32_t expected) | |
| 56 | { | ||
| 57 | 4254 | uint64_t want = (uint64_t)expected * 2; | |
| 58 | 4254 | uint32_t nslots = 2; | |
| 59 | 4254 | uint32_t bits = 1; | |
| 60 | |||
| 61 |
2/2✓ Branch 0 taken 276 times.
✓ Branch 1 taken 3978 times.
|
4254 | if (expected > (1u << 30)) |
| 62 | ✗ | vs_error("id set population %u exceeds the slot ceiling", expected); | |
| 63 | |||
| 64 |
2/2✓ Branch 0 taken 24092 times.
✓ Branch 1 taken 4254 times.
|
28346 | while ((uint64_t)nslots < want) |
| 65 | { | ||
| 66 | 24092 | nslots <<= 1; | |
| 67 | 24092 | bits++; | |
| 68 | } | ||
| 69 | 4254 | set->slots = vs_alloc0(nslots * sizeof(uint64_t)); | |
| 70 | 4254 | set->mask = nslots - 1; | |
| 71 | 4254 | set->shift = 64 - bits; | |
| 72 | 4254 | set->has_zero = false; | |
| 73 | 4254 | } | |
| 74 | |||
| 75 | /* | ||
| 76 | * Insert `id` if absent. Returns true when the id was newly added, | ||
| 77 | * false when it was already a member. | ||
| 78 | */ | ||
| 79 | static inline bool | ||
| 80 | 115776 | vs_idset_test_add(VsIdSet *set, uint64_t id) | |
| 81 | { | ||
| 82 |
2/2✓ Branch 0 taken 146 times.
✓ Branch 1 taken 115630 times.
|
115776 | if (id == 0) |
| 83 | { | ||
| 84 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 144 times.
|
146 | if (set->has_zero) |
| 85 | 2 | return false; | |
| 86 | 144 | set->has_zero = true; | |
| 87 | 144 | return true; | |
| 88 | } | ||
| 89 | |||
| 90 | 115630 | uint32_t slot = (uint32_t)((id * VS_HASH_GOLDEN_GAMMA) >> set->shift); | |
| 91 |
4/4✓ Branch 0 taken 18108 times.
✓ Branch 1 taken 107714 times.
✓ Branch 2 taken 10192 times.
✓ Branch 3 taken 7916 times.
|
125822 | while (set->slots[slot] != 0 && set->slots[slot] != id) |
| 92 | 10192 | slot = (slot + 1) & set->mask; | |
| 93 |
2/2✓ Branch 0 taken 19256 times.
✓ Branch 1 taken 96374 times.
|
115630 | if (set->slots[slot] == id) |
| 94 | 7268 | return false; | |
| 95 | 107714 | set->slots[slot] = id; | |
| 96 | 107714 | return true; | |
| 97 | } | ||
| 98 | |||
| 99 | static inline void | ||
| 100 | 4254 | vs_idset_cleanup(VsIdSet *set) | |
| 101 | { | ||
| 102 |
1/2✓ Branch 0 taken 4254 times.
✗ Branch 1 not taken.
|
4254 | if (set->slots != NULL) |
| 103 | { | ||
| 104 | 4254 | vs_free(set->slots); | |
| 105 | 4254 | set->slots = NULL; | |
| 106 | } | ||
| 107 | 3978 | } | |
| 108 | |||
| 109 | #endif /* VS_CORE_IDSET_H */ | ||
| 110 |