| 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, which the mask then folds onto the slot | ||
| 32 | * range (Fibonacci hashing). | ||
| 33 | */ | ||
| 34 | #define VS_HASH_GOLDEN_GAMMA 0x9E3779B97F4A7C15ULL | ||
| 35 | |||
| 36 | typedef struct VsIdSet | ||
| 37 | { | ||
| 38 | uint64_t *slots; | ||
| 39 | uint32_t mask; /* nslots - 1; nslots is a power of two */ | ||
| 40 | bool has_zero; | ||
| 41 | } VsIdSet; | ||
| 42 | |||
| 43 | /* | ||
| 44 | * Size for up to `expected` distinct ids at a load factor of at most | ||
| 45 | * one half. The set neither resizes nor tracks its population: | ||
| 46 | * inserting more than nslots distinct ids would probe forever, so the | ||
| 47 | * caller's bound must hold. Populations needing more than the 2^31 | ||
| 48 | * slot ceiling (2^30 ids -- a 24+ GB candidate buffer upstream) are | ||
| 49 | * rejected outright rather than proceeding undersized. | ||
| 50 | */ | ||
| 51 | static inline void | ||
| 52 | 4239 | vs_idset_init(VsIdSet *set, uint32_t expected) | |
| 53 | { | ||
| 54 | 4239 | uint64_t want = (uint64_t)expected * 2; | |
| 55 | 4239 | uint32_t nslots = 2; | |
| 56 | |||
| 57 |
2/2✓ Branch 0 taken 276 times.
✓ Branch 1 taken 3963 times.
|
4239 | if (expected > (1u << 30)) |
| 58 | ✗ | vs_error("id set population %u exceeds the slot ceiling", expected); | |
| 59 | |||
| 60 |
2/2✓ Branch 0 taken 23931 times.
✓ Branch 1 taken 4239 times.
|
28170 | while ((uint64_t)nslots < want) |
| 61 | 23931 | nslots <<= 1; | |
| 62 | 4239 | set->slots = vs_alloc0(nslots * sizeof(uint64_t)); | |
| 63 | 4239 | set->mask = nslots - 1; | |
| 64 | 4239 | set->has_zero = false; | |
| 65 | 4239 | } | |
| 66 | |||
| 67 | /* | ||
| 68 | * Insert `id` if absent. Returns true when the id was newly added, | ||
| 69 | * false when it was already a member. | ||
| 70 | */ | ||
| 71 | static inline bool | ||
| 72 | 105032 | vs_idset_test_add(VsIdSet *set, uint64_t id) | |
| 73 | { | ||
| 74 |
2/2✓ Branch 0 taken 146 times.
✓ Branch 1 taken 104886 times.
|
105032 | if (id == 0) |
| 75 | { | ||
| 76 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 144 times.
|
146 | if (set->has_zero) |
| 77 | 2 | return false; | |
| 78 | 144 | set->has_zero = true; | |
| 79 | 144 | return true; | |
| 80 | } | ||
| 81 | |||
| 82 | 104886 | uint32_t slot = (uint32_t)(id * VS_HASH_GOLDEN_GAMMA) & set->mask; | |
| 83 |
4/4✓ Branch 0 taken 3404294 times.
✓ Branch 1 taken 96981 times.
✓ Branch 2 taken 3396389 times.
✓ Branch 3 taken 7905 times.
|
3501275 | while (set->slots[slot] != 0 && set->slots[slot] != id) |
| 84 | 3396389 | slot = (slot + 1) & set->mask; | |
| 85 |
2/2✓ Branch 0 taken 19250 times.
✓ Branch 1 taken 85636 times.
|
104886 | if (set->slots[slot] == id) |
| 86 | 7268 | return false; | |
| 87 | 96981 | set->slots[slot] = id; | |
| 88 | 96981 | return true; | |
| 89 | } | ||
| 90 | |||
| 91 | static inline void | ||
| 92 | 4239 | vs_idset_cleanup(VsIdSet *set) | |
| 93 | { | ||
| 94 |
1/2✓ Branch 0 taken 4239 times.
✗ Branch 1 not taken.
|
4239 | if (set->slots != NULL) |
| 95 | { | ||
| 96 | 4239 | vs_free(set->slots); | |
| 97 | 4239 | set->slots = NULL; | |
| 98 | } | ||
| 99 | 3963 | } | |
| 100 | |||
| 101 | #endif /* VS_CORE_IDSET_H */ | ||
| 102 |