sortedset.h

filter: Statementstmt 76.5% 733 / 958 Branchbran 55.0% 468 / 850 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 66.4% 1201 / 1808 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Data/SortedSet/Shared.pm ↑ Summary Shared.xs »
1 /*
2 * sortedset.h -- Shared-memory sorted set (ZSET) for Linux
3 *
4 * int64 members ordered by a double score on an order-statistics B+tree (keyed
5 * by the total order (score, member); per-child subtree counts give O(log n)
6 * rank; doubly-linked leaves give sequential range scans), plus a member->score
7 * open-addressed hash index for O(1) lookup by member. Nodes and index slots
8 * live in fixed pools. A write-preferring futex rwlock with reader-slot
9 * dead-process recovery guards mutations.
10 *
11 * Layout: Header -> reader_slots[1024] -> member_index -> node_pool
12 */
13  
14 #ifndef SORTEDSET_H
15 #define SORTEDSET_H
16  
17 #include <stddef.h>
18 #include <stdint.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <unistd.h>
22 #include <fcntl.h>
23 #include <errno.h>
24 #include <time.h>
25 #include <limits.h>
26 #include <signal.h>
27 #include <sys/mman.h>
28 #include <sys/stat.h>
29 #include <sys/file.h>
30 #include <sys/syscall.h>
31 #include <linux/futex.h>
32 #include <sys/eventfd.h>
33 #include <pthread.h>
34  
35 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
36 #error "sortedset.h: requires little-endian architecture"
37 #endif
38  
39  
40 /* ================================================================
41 * Constants
42 * ================================================================ */
43  
44 #define SS_MAGIC 0x53534554U /* "SSET" */
45 #define SS_VERSION 2 /* 2: added the occupancy bitmap region (layout change) */
46 #define SS_NONE UINT32_MAX
47 #define SS_ERR_BUFLEN (PATH_MAX + 256)
48 #ifndef SS_READER_SLOTS
49 #define SS_READER_SLOTS 1024 /* max concurrent reader processes for dead-process recovery */
50 #endif
51  
52 /* Occupancy bitmap: one bit per reader slot, set when a process claims a slot and
53 * cleared on clean release. A writer scans these SS_OCC_WORDS words to visit
54 * only OCCUPIED slots (O(words + live readers)) instead of all SS_READER_SLOTS. */
55 #define SS_OCC_WORDS (((SS_READER_SLOTS) + 63) / 64) /* 16 for 1024 slots */
56 #define SS_OCC_BYTES ((uint64_t)SS_OCC_WORDS * 8) /* 128 bytes */
57  
58 #define SS_ORDER 16 /* B+tree fanout: max children / max leaf entries */
59 #define SS_MIN (SS_ORDER / 2) /* min children/entries except the root */
60  
61 /* SsHeader.wphase: which structure a write is changing. While the tree
62 * changes, the index still holds the set as before the write; while the index
63 * changes, the tree holds it as after. */
64 #define SS_WP_NONE 0
65 #define SS_WP_TREE 1
66 #define SS_WP_INDEX 2
67  
68 #define SS_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, SS_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while (0)
69  
70 /* ================================================================
71 * Structs
72 * ================================================================ */
73  
74 /* B+tree node (one pool, one size). Leaf (is_leaf=1): up to SS_ORDER
75 (score,member) entries in key order, doubly-linked via next/prev. Internal:
76 up to SS_ORDER children with SS_ORDER-1 separators (scores/members) and
77 per-child subtree entry counts (order-statistics, for rank). Parallel arrays
78 so the in-node binary search scans packed scores. Free nodes thread the
79 free-list through `parent`. */
80 /* arrays are SS_ORDER+1 to hold the transient overflow during a split */
81 typedef struct {
82 uint16_t num; /* leaf: #entries; internal: #children */
83 uint8_t is_leaf;
84 uint8_t mark; /* stale-lock rebuild scratch; 0 outside it */
85 uint32_t parent; /* SS_NONE for root; free-list link when free */
86 uint32_t next, prev; /* leaf sibling links (SS_NONE at the ends) */
87 double scores[SS_ORDER + 1]; /* leaf entries / internal separators (num-1 used) */
88 int64_t members[SS_ORDER + 1];
89 uint32_t children[SS_ORDER + 1]; /* internal child node idx */
90 uint32_t counts[SS_ORDER + 1]; /* internal per-child subtree entry counts */
91 } SsNode;
92  
93 /* member -> score open-addressed hash index slot (backward-shift delete) */
94 typedef struct {
95 int64_t member;
96 double score;
97 uint8_t state; /* 0 empty, 1 occupied */
98 } SsIdxSlot;
99  
100 /* Per-process slot for dead-process recovery. In the reader-slots-only rwlock a
101 * reader's ENTIRE contribution to the shared lock is `rdepth` in its OWN slot --
102 * there is no separate shared reader counter to fall out of sync with it -- so a
103 * dead reader's contribution is exactly this one word, which a draining writer
104 * neutralises by clearing the slot's pid (the scan then ignores the slot). No
105 * orphaned counter can exist, so there is no quiescent force-reset and sustained
106 * readers cannot starve a writer. _rsv1/_rsv2 are kept only to preserve the
107 * 16-byte slot size across the already-released builds. */
108 typedef struct {
109 uint32_t pid; /* 0 = unclaimed */
110 uint32_t rdepth; /* read-locks THIS process currently holds (recursion-safe) */
111 uint32_t _rsv1; /* reserved (was waiters_parked); unused, kept for layout size */
112 uint32_t _rsv2; /* reserved (was writers_parked); unused, kept for layout size */
113 } SsReaderSlot;
114  
115 struct SsHeader {
116 uint32_t magic, version; /* 0,4 */
117 uint32_t max_entries; /* 8 entry capacity */
118 uint32_t node_capacity; /* 12 node-pool size */
119 uint32_t index_slots; /* 16 member-index slots (power of two) */
120 uint32_t count; /* 20 live entries */
121 uint64_t total_size; /* 24 */
122 uint64_t reader_slots_off; /* 32 */
123 uint64_t index_off; /* 40 */
124 uint64_t nodes_off; /* 48 */
125 uint32_t root; /* 56 root node idx (SS_NONE if empty) */
126 uint32_t height; /* 60 tree height (0 = empty) */
127 uint32_t leftmost; /* 64 leftmost leaf idx */
128 uint32_t rightmost; /* 68 rightmost leaf idx */
129 uint32_t node_free_head; /* 72 */
130 uint32_t wlock; /* 76 WRITER word ONLY: 0 (free) or WRITER_BIT|pid. NOT a reader count. */
131 uint32_t rwait; /* 80 parked-waiter hint (readers+writers blocked on wlock); over-count-safe */
132 uint32_t drain_seq; /* 84 futex bumped by a reader releasing under a draining writer (wakes it) */
133 uint64_t stat_ops; /* 88 */
134 uint32_t slotless_rdepth; /* 96: readers holding with no reader-slot (documented residual) */
135 uint8_t sealed; /* 100 0 = mutable, 1 = frozen (read-only; lock-free reads) */
136 uint8_t wphase; /* 101 SS_WP_*; carved from the pad, so older files read 0 */
137 uint8_t _pad[154]; /* 102..255 */
138 };
139 typedef struct SsHeader SsHeader;
140  
141 _Static_assert(sizeof(SsHeader) == 256, "SsHeader must be 256 bytes");
142  
143 /* ---- Process-local handle ---- */
144  
145 typedef struct SsHandle {
146 SsHeader *hdr;
147 SsReaderSlot *reader_slots; /* SS_READER_SLOTS entries */
148 uint64_t *occ; /* SS_OCC_WORDS-word slot-occupancy bitmap (trusted layout offset) */
149 SsIdxSlot *index; /* member -> score */
150 SsNode *nodes; /* B+tree node pool */
151 size_t mmap_size;
152 char *path; /* backing file path (strdup'd) */
153 int notify_fd;
154 int backing_fd; /* memfd fd to close on destroy, -1 otherwise */
155 uint32_t node_capacity; /* cached-at-attach node-pool size (trusted geometry; validated) */
156 uint32_t index_slots; /* cached-at-attach member-index slot count (trusted, pow2) */
157 uint32_t my_slot_idx; /* UINT32_MAX if all slots taken (no recovery for this handle) */
158 uint32_t cached_pid; /* getpid() cached at last slot claim */
159 uint32_t cached_fork_gen; /* ss_fork_gen value at last slot claim */
160 uint32_t slotless_held; /* rwlock read-locks held with no reader-slot */
161 int readonly; /* 1 = frozen O_RDONLY/PROT_READ view: lock-free reads, mutation croaks */
162 } SsHandle;
163  
164 /* ================================================================
165 * Helpers
166 * ================================================================ */
167  
168 49 static inline uint32_t ss_next_pow2(uint32_t v) {
169 49 ▶ if (v < 2) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (v < 2) return 1; 0 49 49
170 49 return 1u << (32 - __builtin_clz(v - 1));
171 }
172  
173 /* member hash: splitmix64 finalizer (good avalanche for int64 keys) */
174 368147 static inline uint64_t ss_hash_member(int64_t m) {
175 368147 uint64_t x = (uint64_t)m + 0x9E3779B97F4A7C15ULL;
176 368147 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
177 368147 x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
178 368147 return x ^ (x >> 31);
179 }
180  
181 /* total order on (score, member): -1 / 0 / +1 */
182 3316592 static inline int ss_key_cmp(double sa, int64_t ma, double sb, int64_t mb) {
183 3316592 ▶ if (sa < sb) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa < sb) return -1; 788640 2527952 3316592
184 2527952 ▶ if (sa > sb) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa > sb) return 1; 372547 2155405 2527952
185 2155405 ▶ return (ma < mb) ? -1 : (ma > mb) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
return (ma < mb) ? -1 : (ma > mb) ? 1 : 0; 407434 1747971 2155405
186 }
187  
188 /* ================================================================
189 * Futex-based write-preferring read-write lock (reader-slots-only)
190 * with dead-process recovery
191 *
192 * The reader count is NOT stored in a shared counter. It is DISTRIBUTED across
193 * per-process reader slots: each slot's `rdepth` is that process's entire
194 * contribution to the lock. A reader publishes its presence in its own slot and
195 * then re-checks the writer word; a writer publishes the writer word and then
196 * scans every slot until all live readers' rdepth reach 0. Sequentially-
197 * consistent store+load on each side (a Dekker handshake) gives mutual exclusion.
198 *
199 * Because a reader's whole contribution is ONE atomic word owned by ONE process,
200 * a crashed reader is recovered by clearing that one slot (CAS its pid to 0) --
201 * there is no second counter to strand, no orphaned +1, and therefore no
202 * quiescent force-reset. A reader killed anywhere in rdlock/rdunlock leaves at
203 * most `rdepth>0` in its dead slot, which the draining writer clears directly, so
204 * sustained read traffic can never starve a writer. Write-preference is inherent
205 * in the gate (new readers see wlock!=0 and yield), so there is no reader-count
206 * yield hack.
207 * ================================================================ */
208  
209 #define SS_RWLOCK_SPIN_LIMIT 32
210 #define SS_LOCK_TIMEOUT_SEC 2 /* FUTEX_WAIT timeout for stale lock detection */
211  
212 0 static inline void ss_rwlock_spin_pause(void) {
213 #if defined(__x86_64__) || defined(__i386__)
214 0 __asm__ volatile("pause" ::: "memory");
215 #elif defined(__aarch64__)
216 __asm__ volatile("yield" ::: "memory");
217 #else
218 __asm__ volatile("" ::: "memory");
219 #endif
220 0 }
221  
222 /* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
223 #define SS_RWLOCK_WRITER_BIT 0x80000000U
224 #define SS_RWLOCK_PID_MASK 0x7FFFFFFFU
225 #define SS_RWLOCK_WR(pid) (SS_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & SS_RWLOCK_PID_MASK))
226  
227 /* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
228 * process that crashed while holding the lock and lingers unreaped would never
229 * be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
230 * this module); if /proc is unreadable we fall back to "alive" (safe: we never
231 * force-recover a possibly-live holder). */
232 0 static inline int ss_pid_is_zombie(uint32_t pid) {
233 char path[32], buf[256];
234 0 snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
235 0 int fd = open(path, O_RDONLY | O_CLOEXEC);
236 0 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 0 0
237 0 ssize_t n = read(fd, buf, sizeof(buf) - 1);
238 0 close(fd);
239 0 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 0 0
240 0 buf[n] = '\0';
241 /* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
242 0 char *rp = strrchr(buf, ')');
243 0 ▶ if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */
Branch: 2 branches
BranchTrueFalseTotal
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 0 0
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */ 0 0 0
244 0 ▶ return rp[1] == ' ' && rp[2] == 'Z';
Branch: 2 branches
BranchTrueFalseTotal
return rp[1] == ' ' && rp[2] == 'Z'; 0 0 0
return rp[1] == ' ' && rp[2] == 'Z'; 0 0 0
245 }
246 /* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
247 * recycled PID reports "alive" and the slot is not reclaimed until that
248 * process exits. See "Crash Safety" in the POD. */
249 0 static inline int ss_pid_alive(uint32_t pid) {
250 0 ▶ if (pid == 0) return 0; /* no owner recorded, treat as dead */
Branch: 1 branch
BranchTrueFalseTotal
if (pid == 0) return 0; /* no owner recorded, treat as dead */ 0 0 0
251 0 ▶ if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */
Branch: 2 branches
BranchTrueFalseTotal
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 0 0 0
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */ 0 0 0
252 0 return !ss_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
253 }
254  
255 static const struct timespec ss_lock_timeout = { SS_LOCK_TIMEOUT_SEC, 0 };
256  
257 /* Process-global fork-generation counter. Incremented in the pthread_atfork
258 * child callback so every open handle detects a fork transition on the next
259 * lock call without paying a getpid() syscall on the hot path. */
260 static uint32_t ss_fork_gen = 1;
261 static pthread_once_t ss_atfork_once = PTHREAD_ONCE_INIT;
262 0 static void ss_on_fork_child(void) {
263 0 __atomic_add_fetch(&ss_fork_gen, 1, __ATOMIC_RELAXED);
264 0 }
265 10 static void ss_atfork_init(void) {
266 10 pthread_atfork(NULL, NULL, ss_on_fork_child);
267 10 }
268  
269 /* Occupancy bitmap: set a slot's bit when it is claimed, clear it on clean
270 * release. SEQ_CST so a set bit is ordered before the slot's rdepth can go
271 * non-zero (bit set in claim, which precedes any rdlock), letting a writer's
272 * SEQ_CST bitmap scan never miss a slot a committed reader holds. */
273 37 static inline void ss_occ_set(SsHandle *h, uint32_t s) {
274 37 __atomic_fetch_or(&h->occ[s >> 6], (uint64_t)1 << (s & 63), __ATOMIC_SEQ_CST);
275 37 }
276 37 static inline void ss_occ_clear(SsHandle *h, uint32_t s) {
277 37 __atomic_fetch_and(&h->occ[s >> 6], ~((uint64_t)1 << (s & 63)), __ATOMIC_SEQ_CST);
278 37 }
279  
280 /* Ensure this process owns a reader slot. Called from the lock helpers so
281 * that fork()'d children pick up their own slot lazily instead of sharing
282 * the parent's. Hot-path is a single relaxed load + compare; only on a
283 * fork-generation mismatch do we touch getpid() and scan slots. */
284 235428 static inline void ss_claim_reader_slot(SsHandle *h) {
285 235428 uint32_t cur_gen = __atomic_load_n(&ss_fork_gen, __ATOMIC_RELAXED);
286 235428 ▶ if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1))
Branch: 2 branches
BranchTrueFalseTotal
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 235391 37 235428
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) 235391 0 235391
287 235391 return;
288 /* Cold path -- register the atfork hook once per process, then claim. */
289 37 pthread_once(&ss_atfork_once, ss_atfork_init);
290 /* Re-read after pthread_once: ss_on_fork_child may have bumped it. */
291 37 cur_gen = __atomic_load_n(&ss_fork_gen, __ATOMIC_RELAXED);
292 37 uint32_t now_pid = (uint32_t)getpid();
293 37 h->cached_pid = now_pid;
294 37 ▶ if (cur_gen != h->cached_fork_gen) h->slotless_held = 0; /* fork: child holds none of the parent's slotless read locks */
Branch: 1 branch
BranchTrueFalseTotal
if (cur_gen != h->cached_fork_gen) h->slotless_held = 0; /* fork: child holds none of the parent's slotless read locks */ 37 0 37
295 37 h->cached_fork_gen = cur_gen;
296 37 h->my_slot_idx = UINT32_MAX;
297 37 uint32_t start = now_pid % SS_READER_SLOTS;
298 /* Pass 1: take a free slot. */
299 37 ▶ for (uint32_t i = 0; i < SS_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < SS_READER_SLOTS; i++) { 37 0 37
300 37 uint32_t s = (start + i) % SS_READER_SLOTS;
301 37 uint32_t expected = 0;
302 37 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[s].pid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, 37 0 37
303 &expected, now_pid, 0,
304 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
305 /* Fresh owner holds no read locks yet; clear any stale rdepth left by
306 * a dead predecessor (its contribution is dropped as we take over). */
307 37 __atomic_store_n(&h->reader_slots[s].rdepth, 0, __ATOMIC_RELAXED);
308 37 ss_occ_set(h, s); /* mark occupied BEFORE any rdlock can bump rdepth */
309 37 h->my_slot_idx = s;
310 37 return;
311 }
312 }
313 /* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
314 * if its rdepth>0: clearing pid drops the dead reader's entire contribution
315 * (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
316 * claim it. */
317 0 ▶ for (uint32_t i = 0; i < SS_READER_SLOTS; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < SS_READER_SLOTS; i++) { 0 0 0
318 0 uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
319 0 ▶ if (dpid == 0 || dpid == now_pid || ss_pid_alive(dpid)) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (dpid == 0 || dpid == now_pid || ss_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || ss_pid_alive(dpid)) continue; 0 0 0
if (dpid == 0 || dpid == now_pid || ss_pid_alive(dpid)) continue; 0 0 0
320 0 uint32_t expected = dpid;
321 0 ▶ if (__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, now_pid, 0,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, now_pid, 0, 0 0 0
322 __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
323 0 __atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
324 0 ss_occ_set(h, i);
325 0 h->my_slot_idx = i;
326 0 return;
327 }
328 }
329 /* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
330 * slotless path (lock still works; recovery of THIS reader's death is the
331 * documented slotless limitation). */
332 }
333  
334 /* Wait until no live reader holds the lock; the caller owns wlock, so no NEW
335 * reader can join (they see wlock!=0 and yield). The SEQ_CST wlock CAS + the
336 * SEQ_CST rdepth loads below are the writer side of the Dekker handshake. */
337 158980 static inline void ss_rwlock_drain(SsHandle *h) {
338 158980 SsHeader *hdr = h->hdr;
339 0 for (;;) {
340 158980 uint32_t v = __atomic_load_n(&hdr->drain_seq, __ATOMIC_ACQUIRE); /* snapshot BEFORE scan */
341 158980 int busy = 0;
342 /* Visit only OCCUPIED slots via the occupancy bitmap (SEQ_CST: a committed
343 * reader's bit -- set in claim, before its rdepth++ -- is ordered before
344 * this scan, so no held slot is skipped). O(SS_OCC_WORDS + live readers)
345 * instead of O(SS_READER_SLOTS). */
346 2702660 ▶ for (uint32_t w = 0; w < SS_OCC_WORDS; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t w = 0; w < SS_OCC_WORDS; w++) { 2543680 158980 2702660
347 2543680 uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
348 2702660 ▶ while (word) {
Branch: 1 branch
BranchTrueFalseTotal
while (word) { 158980 2543680 2702660
349 158980 uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
350 158980 word &= word - 1; /* consume this bit (local copy) */
351 158980 uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
352 158980 ▶ if (rd == 0) continue; /* occupied but not read-locking now */
Branch: 1 branch
BranchTrueFalseTotal
if (rd == 0) continue; /* occupied but not read-locking now */ 158980 0 158980
353 0 uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
354 0 ▶ if (pid == 0) continue; /* stale rdepth on a freed slot */
Branch: 1 branch
BranchTrueFalseTotal
if (pid == 0) continue; /* stale rdepth on a freed slot */ 0 0 0
355 0 ▶ if (!ss_pid_alive(pid)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_pid_alive(pid)) { 0 0 0
356 /* Dead reader: drop its pid so the slot no longer counts. Leave
357 * the occ bit set (harmless -- a later scan hits pid==0 and skips,
358 * a re-claim re-sets it) to avoid racing a concurrent claimant. */
359 0 uint32_t ep = pid;
360 0 __atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
361 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
362 0 continue;
363 }
364 0 busy = 1; /* live reader still holding */
365 }
366 }
367 /* A live slotless reader keeps us waiting; a crashed slotless reader that
368 * cannot be attributed to a pid is the documented slotless limitation. */
369 158980 ▶ if (__atomic_load_n(&hdr->slotless_rdepth, __ATOMIC_SEQ_CST) != 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->slotless_rdepth, __ATOMIC_SEQ_CST) != 0) 0 158980 158980
370 0 busy = 1;
371 158980 ▶ if (!busy)
Branch: 1 branch
BranchTrueFalseTotal
if (!busy) 158980 0 158980
372 158980 return; /* exclusive: wlock held + every rdepth 0 */
373 /* Wait for a reader to release (drain_seq bump) or time out to re-scan
374 * (which reclaims any newly-dead slotted reader). */
375 0 syscall(SYS_futex, &hdr->drain_seq, FUTEX_WAIT, v, &ss_lock_timeout, NULL, 0);
376 }
377 }
378  
379 /* 1 if this process holds a read lock on the segment (through any handle). Such a
380 * lock predates the current wlock holder, whose drain could then never have
381 * finished: it died before mutating anything. */
382 0 static int ss_self_reading(SsHandle *h) {
383 0 ▶ if (h->slotless_held) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held) return 1; 0 0 0
384 0 uint32_t me = (uint32_t)getpid();
385 0 ▶ for (uint32_t i = 0; i < SS_READER_SLOTS; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < SS_READER_SLOTS; i++) 0 0 0
386 0 ▶ if (__atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE) == me &&
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE) == me && 0 0 0
387 0 ▶ __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_ACQUIRE) != 0)
Branch: 1 branch
BranchTrueFalseTotal
__atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_ACQUIRE) != 0) 0 0 0
388 0 return 1;
389 0 return 0;
390 }
391  
392 static void ss_rebuild_locked(SsHandle *h);
393  
394 /* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
395 * CAS to OUR pid to hold the lock while repairing shared state, then release.
396 * Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
397 * process can detect and re-recover if we crash mid-recovery. */
398 0 static inline void ss_recover_stale_lock(SsHandle *h, uint32_t observed_wlock) {
399 0 SsHeader *hdr = h->hdr;
400 0 uint32_t mypid = SS_RWLOCK_WR((uint32_t)getpid());
401 0 ▶ if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock,
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_compare_exchange_n(&hdr->wlock, &observed_wlock, 0 0 0
402 mypid, 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
403 0 return;
404 0 ▶ if (!ss_self_reading(h)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_self_reading(h)) { 0 0 0
405 0 ss_rwlock_drain(h);
406 0 ▶ if (!__atomic_load_n(&hdr->sealed, __ATOMIC_ACQUIRE))
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&hdr->sealed, __ATOMIC_ACQUIRE)) 0 0 0
407 0 ss_rebuild_locked(h);
408 }
409 0 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
410 0 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 0 0
411 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
412 }
413  
414 /* Inspect the writer word after a futex-wait timeout. If a dead writer holds
415 * it, force-recover. Dead READERS need no action here: only a writer that owns
416 * wlock drains readers, and it clears dead readers inline in its own scan. */
417 0 static inline void ss_recover_after_timeout(SsHandle *h) {
418 0 uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
419 0 ▶ if (val >= SS_RWLOCK_WRITER_BIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (val >= SS_RWLOCK_WRITER_BIT) { 0 0 0
420 0 uint32_t pid = val & SS_RWLOCK_PID_MASK;
421 0 ▶ if (!ss_pid_alive(pid))
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_pid_alive(pid)) 0 0 0
422 0 ss_recover_stale_lock(h, val);
423 }
424 0 }
425  
426 /* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
427 * writers (blocked acquiring wlock) wait on the wlock futex and use this, so
428 * wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
429 * SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
430 * (harmless); it can never under-count, so no wakeup is lost. */
431 0 static inline void ss_park(SsHandle *h) {
432 0 __atomic_add_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
433 0 }
434 0 static inline void ss_unpark(SsHandle *h) {
435 0 __atomic_sub_fetch(&h->hdr->rwait, 1, __ATOMIC_RELAXED);
436 0 }
437  
438 /* Publish (inc) / retract (dec) this reader's presence -- its ENTIRE
439 * contribution to the lock. A slotted reader uses its slot's rdepth; a reader
440 * that could not claim a slot uses the global slotless_rdepth. inc() is SEQ_CST
441 * so the wlock re-check that follows it in rdlock forms a Dekker handshake with
442 * the writer's SEQ_CST wlock-store + rdepth-scan. leave() peels slotless first
443 * so a slot claimed mid-hold cannot misattribute the decrement. */
444 76448 static inline void ss_rdepth_inc(SsHandle *h) {
445 76448 ▶ if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->my_slot_idx != UINT32_MAX) { 76448 0 76448
446 76448 __atomic_add_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_SEQ_CST);
447 } else {
448 0 __atomic_add_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_SEQ_CST);
449 0 h->slotless_held++;
450 }
451 76448 }
452 76448 static inline void ss_rdepth_dec(SsHandle *h) {
453 76448 ▶ if (h->slotless_held > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (h->slotless_held > 0) { 0 76448 76448
454 0 h->slotless_held--;
455 0 __atomic_sub_fetch(&h->hdr->slotless_rdepth, 1, __ATOMIC_RELEASE);
456 76448 ▶ } else if (h->my_slot_idx != UINT32_MAX) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (h->my_slot_idx != UINT32_MAX) { 76448 0 76448
457 76448 __atomic_sub_fetch(&h->reader_slots[h->my_slot_idx].rdepth, 1, __ATOMIC_RELEASE);
458 }
459 76448 }
460  
461 /* Wake a writer that may be draining readers (it waits on drain_seq). Called
462 * after every rdepth decrement so a released read lock lets the writer re-scan
463 * promptly instead of waiting out its timeout. */
464 76448 static inline void ss_reader_wake_drain(SsHandle *h) {
465 76448 ▶ if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&h->hdr->wlock, __ATOMIC_ACQUIRE) != 0) { 0 76448 76448
466 0 __atomic_add_fetch(&h->hdr->drain_seq, 1, __ATOMIC_RELEASE);
467 0 syscall(SYS_futex, &h->hdr->drain_seq, FUTEX_WAKE, 1, NULL, NULL, 0);
468 }
469 76448 }
470  
471 76448 static inline void ss_rwlock_rdlock(SsHandle *h) {
472 76448 ss_claim_reader_slot(h);
473 76448 SsHeader *hdr = h->hdr;
474 76448 for (int spin = 0; ; spin++) {
475 76448 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_ACQUIRE);
476 76448 ▶ if (cur == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur == 0) { 76448 0 76448
477 /* Optimistically take the read: publish rdepth, then re-check wlock.
478 * SEQ_CST inc + SEQ_CST load vs the writer's SEQ_CST wlock CAS +
479 * SEQ_CST rdepth scan: by the single total order of SEQ_CST ops the
480 * two sides cannot both miss each other, so we never hold
481 * concurrently with a writer. */
482 76448 ss_rdepth_inc(h);
483 76448 ▶ if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0) 76448 0 76448
484 76448 return; /* no writer after our publish -> we hold the read lock */
485 /* A writer appeared during our publish -- yield to it (write-preferring). */
486 0 ss_rdepth_dec(h);
487 0 ss_reader_wake_drain(h); /* let the draining writer see rdepth drop */
488 0 spin = 0;
489 0 continue;
490 }
491 /* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
492 0 if (cur >= SS_RWLOCK_WRITER_BIT &&
493 0 !ss_pid_alive(cur & SS_RWLOCK_PID_MASK)) {
494 0 ss_recover_stale_lock(h, cur);
495 0 spin = 0;
496 0 continue;
497 }
498 0 ▶ if (__builtin_expect(spin < SS_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < SS_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
499 0 ss_rwlock_spin_pause();
500 0 continue;
501 }
502 0 ss_park(h);
503 0 cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
504 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
505 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
506 &ss_lock_timeout, NULL, 0);
507 0 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
508 0 ss_unpark(h);
509 0 ss_recover_after_timeout(h);
510 0 spin = 0;
511 0 continue;
512 }
513 }
514 0 ss_unpark(h);
515 0 spin = 0;
516 }
517 }
518  
519 76448 static inline void ss_rwlock_rdunlock(SsHandle *h) {
520 76448 ss_rdepth_dec(h); /* RELEASE: drop our entire contribution */
521 76448 ss_reader_wake_drain(h); /* if a writer is draining, wake it to re-scan */
522 76448 }
523  
524 158980 static inline void ss_rwlock_wrlock(SsHandle *h) {
525 158980 ss_claim_reader_slot(h); /* refresh cached_pid across fork */
526 158980 SsHeader *hdr = h->hdr;
527 /* Encode PID in the wlock word itself (0x80000000 | pid) to eliminate any
528 * crash window between acquiring the lock and storing the owner. */
529 158980 uint32_t mypid = SS_RWLOCK_WR(h->cached_pid);
530 /* Phase 1: acquire the writer word (mutual exclusion among writers). */
531 158980 for (int spin = 0; ; spin++) {
532 158980 uint32_t expected = 0;
533 158980 ▶ if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid, 158980 0 158980
534 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
535 158980 break;
536 /* Contended: expected now holds the current wlock value. */
537 0 if (expected >= SS_RWLOCK_WRITER_BIT &&
538 0 !ss_pid_alive(expected & SS_RWLOCK_PID_MASK)) {
539 0 ss_recover_stale_lock(h, expected);
540 0 spin = 0;
541 0 continue;
542 }
543 0 ▶ if (__builtin_expect(spin < SS_RWLOCK_SPIN_LIMIT, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (__builtin_expect(spin < SS_RWLOCK_SPIN_LIMIT, 1)) { 0 0 0
544 0 ss_rwlock_spin_pause();
545 0 continue;
546 }
547 0 ss_park(h);
548 0 uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
549 0 ▶ if (cur != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != 0) { 0 0 0
550 0 long rc = syscall(SYS_futex, &hdr->wlock, FUTEX_WAIT, cur,
551 &ss_lock_timeout, NULL, 0);
552 0 ▶ if (rc == -1 && errno == ETIMEDOUT) {
Branch: 2 branches
BranchTrueFalseTotal
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
if (rc == -1 && errno == ETIMEDOUT) { 0 0 0
553 0 ss_unpark(h);
554 0 ss_recover_after_timeout(h);
555 0 spin = 0;
556 0 continue;
557 }
558 }
559 0 ss_unpark(h);
560 0 spin = 0;
561 }
562 /* Phase 2: drain the readers that were already holding when we won the CAS. */
563 158980 ss_rwlock_drain(h);
564 158980 }
565  
566 158980 static inline void ss_rwlock_wrunlock(SsHandle *h) {
567 158980 SsHeader *hdr = h->hdr;
568 158980 __atomic_store_n(&hdr->wlock, 0, __ATOMIC_RELEASE);
569 158980 ▶ if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (__atomic_load_n(&hdr->rwait, __ATOMIC_RELAXED) > 0) 0 158980 158980
570 0 syscall(SYS_futex, &hdr->wlock, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
571 158980 }
572  
573 /* ================================================================
574 * Layout math + create / open / destroy
575 *
576 * Layout: Header -> reader_slots[1024] -> member_index -> node_pool
577 * ================================================================ */
578  
579 /* Largest max_entries accepted at create time. 2^30 keeps the index-slot
580 * power-of-two rounding (ss_next_pow2) and every byte offset well within
581 * range, and is far beyond any realistic shared-memory map. */
582 #define SS_MAX_CAPACITY 0x40000000u
583  
584 /* Single source of truth for the mmap region layout offsets:
585 * Header -> reader_slots[] -> occ bitmap -> member_index -> node_pool. */
586 typedef struct { uint64_t reader_slots, occ, index, nodes; } SsLayout;
587  
588 161 static inline SsLayout ss_layout(uint32_t index_slots) {
589 SsLayout L;
590 161 L.reader_slots = sizeof(SsHeader);
591 161 L.occ = L.reader_slots + (uint64_t)SS_READER_SLOTS * sizeof(SsReaderSlot);
592 161 L.index = L.occ + SS_OCC_BYTES;
593 161 L.nodes = L.index + (uint64_t)index_slots * sizeof(SsIdxSlot);
594 161 L.nodes = (L.nodes + 7) & ~(uint64_t)7; /* 8-byte align the node pool */
595 161 return L;
596 }
597  
598 62 static inline uint64_t ss_total_size(uint32_t index_slots, uint32_t node_capacity) {
599 62 SsLayout L = ss_layout(index_slots);
600 62 return L.nodes + (uint64_t)node_capacity * sizeof(SsNode);
601 }
602  
603 38 static inline void ss_init_header(void *base, uint32_t max_entries, uint32_t index_slots,
604 uint32_t node_capacity, uint64_t total) {
605 38 SsLayout L = ss_layout(index_slots);
606 38 SsHeader *hdr = (SsHeader *)base;
607 38 memset(base, 0, (size_t)total);
608 38 hdr->version = SS_VERSION;
609 38 hdr->max_entries = max_entries;
610 38 hdr->node_capacity = node_capacity;
611 38 hdr->index_slots = index_slots;
612 38 hdr->count = 0;
613 38 hdr->total_size = total;
614 38 hdr->reader_slots_off = L.reader_slots;
615 38 hdr->index_off = L.index;
616 38 hdr->nodes_off = L.nodes;
617 38 hdr->root = SS_NONE; /* empty tree */
618 38 hdr->height = 0;
619 38 hdr->leftmost = SS_NONE;
620 38 hdr->rightmost = SS_NONE;
621  
622 /* Thread the node free-list through `parent`. */
623 38 SsNode *nodes = (SsNode *)((uint8_t *)base + L.nodes);
624 16351 ▶ for (uint32_t i = 0; i < node_capacity; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < node_capacity; i++) 16313 38 16351
625 16313 ▶ nodes[i].parent = (i + 1 < node_capacity) ? (i + 1) : SS_NONE;
Branch: 1 branch
BranchTrueFalseTotal
nodes[i].parent = (i + 1 < node_capacity) ? (i + 1) : SS_NONE; 16275 38 16313
626 38 hdr->node_free_head = 0;
627 /* index region left zeroed: every slot empty (state == 0). */
628 /* Publish magic LAST, as a release store: it is the commit point, so a
629 creator killed before it leaves magic==0 and never a file mistaken for
630 a valid one. A kill during the field stores leaves one to remove by
631 hand. */
632 38 __atomic_store_n(&hdr->magic, SS_MAGIC, __ATOMIC_RELEASE);
633 38 __atomic_thread_fence(__ATOMIC_SEQ_CST);
634 38 }
635  
636 48 static inline SsHandle *ss_setup(void *base, size_t map_size,
637 const char *path, int backing_fd) {
638 48 SsHeader *hdr = (SsHeader *)base;
639 48 SsHandle *h = (SsHandle *)calloc(1, sizeof(SsHandle));
640 48 ▶ if (!h) {
Branch: 1 branch
BranchTrueFalseTotal
if (!h) { 0 48 48
641 0 munmap(base, map_size);
642 0 ▶ if (backing_fd >= 0) close(backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (backing_fd >= 0) close(backing_fd); 0 0 0
643 0 return NULL;
644 }
645 48 h->hdr = hdr;
646 48 h->reader_slots = (SsReaderSlot *)((uint8_t *)base + sizeof(SsHeader)); /* trusted layout, not the peer-writable header offset */
647 48 h->occ = (uint64_t *)((uint8_t *)base + ss_layout(hdr->index_slots).occ); /* trusted layout offset */
648 48 h->index = (SsIdxSlot *)((uint8_t *)base + hdr->index_off);
649 48 h->nodes = (SsNode *)((uint8_t *)base + hdr->nodes_off);
650 /* Cache the fixed pool geometry now (validated at create/attach): a
651 * lock-violating peer that later corrupts these header fields must not be
652 * able to loosen index masks, node-index bounds, or clear/validate loops. */
653 48 h->node_capacity = hdr->node_capacity;
654 48 h->index_slots = hdr->index_slots;
655 48 h->mmap_size = map_size;
656 48 ▶ h->path = path ? strdup(path) : NULL;
Branch: 1 branch
BranchTrueFalseTotal
h->path = path ? strdup(path) : NULL; 21 27 48
657 48 h->notify_fd = -1;
658 48 h->backing_fd = backing_fd;
659 48 h->my_slot_idx = UINT32_MAX;
660 48 return h;
661 }
662  
663 /* Validate immutable geometry before setting up a handle. */
664 17 static inline int ss_validate_header(const SsHeader *hdr, uint64_t file_size) {
665 17 ▶ if (hdr->magic != SS_MAGIC) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->magic != SS_MAGIC) return 0; 4 13 17
666 13 ▶ if (hdr->version != SS_VERSION) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->version != SS_VERSION) return 0; 0 13 13
667 13 ▶ if (hdr->max_entries == 0 || hdr->max_entries >= SS_MAX_CAPACITY) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->max_entries == 0 || hdr->max_entries >= SS_MAX_CAPACITY) return 0; 13 0 13
if (hdr->max_entries == 0 || hdr->max_entries >= SS_MAX_CAPACITY) return 0; 0 13 13
668 13 ▶ if (hdr->index_slots == 0 || (hdr->index_slots & (hdr->index_slots - 1)) != 0) return 0; /* pow2 */
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->index_slots == 0 || (hdr->index_slots & (hdr->index_slots - 1)) != 0) return 0; /* pow2 */ 13 0 13
if (hdr->index_slots == 0 || (hdr->index_slots & (hdr->index_slots - 1)) != 0) return 0; /* pow2 */ 0 13 13
669 13 ▶ if (hdr->node_capacity == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->node_capacity == 0) return 0; 0 13 13
670 13 ▶ if (hdr->total_size != file_size) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != file_size) return 0; 0 13 13
671 13 ▶ if (hdr->total_size != ss_total_size(hdr->index_slots, hdr->node_capacity)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->total_size != ss_total_size(hdr->index_slots, hdr->node_capacity)) return 0; 0 13 13
672 13 SsLayout L = ss_layout(hdr->index_slots);
673 13 ▶ if (hdr->reader_slots_off != L.reader_slots) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->reader_slots_off != L.reader_slots) return 0; 0 13 13
674 13 ▶ if (hdr->index_off != L.index) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->index_off != L.index) return 0; 0 13 13
675 13 ▶ if (hdr->nodes_off != L.nodes) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->nodes_off != L.nodes) return 0; 0 13 13
676 13 return 1;
677 }
678  
679 /* Tree fields may disagree while a writer is running or awaiting recovery. */
680 10 static inline int ss_validate_state(const SsHeader *hdr) {
681 10 ▶ if (hdr->count > hdr->max_entries) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->count > hdr->max_entries) return 0; 0 10 10
682 10 ▶ if (hdr->root != SS_NONE && hdr->root >= hdr->node_capacity) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->root != SS_NONE && hdr->root >= hdr->node_capacity) return 0; 7 3 10
if (hdr->root != SS_NONE && hdr->root >= hdr->node_capacity) return 0; 0 7 7
683 10 ▶ if (hdr->root == SS_NONE && hdr->count != 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->root == SS_NONE && hdr->count != 0) return 0; 3 7 10
if (hdr->root == SS_NONE && hdr->count != 0) return 0; 0 3 3
684 10 ▶ if (hdr->root != SS_NONE && (hdr->count == 0 || hdr->height == 0)) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (hdr->root != SS_NONE && (hdr->count == 0 || hdr->height == 0)) return 0; 7 3 10
if (hdr->root != SS_NONE && (hdr->count == 0 || hdr->height == 0)) return 0; 7 0 7
if (hdr->root != SS_NONE && (hdr->count == 0 || hdr->height == 0)) return 0; 0 7 7
685 10 ▶ if (hdr->height != 0 && hdr->root == SS_NONE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->height != 0 && hdr->root == SS_NONE) return 0; 7 3 10
if (hdr->height != 0 && hdr->root == SS_NONE) return 0; 0 7 7
686 10 return 1;
687 }
688  
689 static void ss_destroy(SsHandle *h);
690  
691 7 static SsHandle *ss_attach(void *base, size_t map_size, const char *path, int fd, char *errbuf) {
692 7 SsHandle *h = ss_setup(base, map_size, path, fd);
693 7 ▶ if (!h) { SS_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { SS_ERR("out of memory"); return NULL; } 0 7 7
if (!h) { SS_ERR("out of memory"); return NULL; } 0 0 0
694 7 ss_rwlock_rdlock(h);
695 7 int valid = ss_validate_state(h->hdr), sealed = h->hdr->sealed;
696 7 ss_rwlock_rdunlock(h);
697 7 ▶ if (!valid || sealed) {
Branch: 2 branches
BranchTrueFalseTotal
if (!valid || sealed) { 7 0 7
if (!valid || sealed) { 0 7 7
698 0 ▶ SS_ERR("%s", sealed ? "this sorted set is frozen (read-only); open it with new_readonly" : "invalid sorted-set file");
Branch: 2 branches
BranchTrueFalseTotal
SS_ERR("%s", sealed ? "this sorted set is frozen (read-only); open it with new_readonly" : "invalid sorted-set file"); 0 0 0
SS_ERR("%s", sealed ? "this sorted set is frozen (read-only); open it with new_readonly" : "invalid sorted-set file"); 0 0 0
699 0 ss_destroy(h);
700 0 return NULL;
701 }
702 7 return h;
703 }
704  
705  
706 /* validate max_entries and compute the index-slot count + node-pool capacity
707 (shared by ss_create + ss_create_memfd) */
708 50 static int ss_validate_create_args(uint32_t max_entries, uint32_t *index_slots,
709 uint32_t *node_capacity, char *errbuf) {
710 50 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 50 0 50
711 50 ▶ if (max_entries == 0) { SS_ERR("max_entries must be > 0"); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (max_entries == 0) { SS_ERR("max_entries must be > 0"); return 0; } 1 49 50
if (max_entries == 0) { SS_ERR("max_entries must be > 0"); return 0; } 1 0 1
712 /* must be strictly < SS_MAX_CAPACITY: at exactly 2^30 the index cap below makes
713 index_slots == max_entries (load factor 1.0), so ss_idx_find never finds an
714 empty slot on an absent lookup when full and spins forever under the lock. */
715 49 ▶ if (max_entries >= SS_MAX_CAPACITY) { SS_ERR("max_entries too large (max %u)", SS_MAX_CAPACITY - 1); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (max_entries >= SS_MAX_CAPACITY) { SS_ERR("max_entries too large (max %u)", SS_MAX_CAPACITY - 1); return 0; } 0 49 49
if (max_entries >= SS_MAX_CAPACITY) { SS_ERR("max_entries too large (max %u)", SS_MAX_CAPACITY - 1); return 0; } 0 0 0
716 49 uint64_t want = (uint64_t)max_entries * 10 / 7 + 1; /* index load factor ~0.7 */
717 49 ▶ if (want > SS_MAX_CAPACITY) want = SS_MAX_CAPACITY;
Branch: 1 branch
BranchTrueFalseTotal
if (want > SS_MAX_CAPACITY) want = SS_MAX_CAPACITY; 0 49 49
718 49 *index_slots = ss_next_pow2((uint32_t)want);
719 49 *node_capacity = (uint32_t)((uint64_t)max_entries / (SS_MIN - 1) + 64); /* worst-case fill + slack */
720 49 return 1;
721 }
722  
723 /* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at mode,
724 * default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no O_CREAT). */
725 23 static int ss_secure_open(const char *path, mode_t mode, char *errbuf) {
726 23 ▶ for (int attempt = 0; attempt < 100; attempt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int attempt = 0; attempt < 100; attempt++) { 23 0 23
727 23 int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
728 23 ▶ if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ 11 12 23
729 12 ▶ if (errno != EEXIST) { SS_ERR("create %s: %s", path, strerror(errno)); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (errno != EEXIST) { SS_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 12 12
if (errno != EEXIST) { SS_ERR("create %s: %s", path, strerror(errno)); return -1; } 0 0 0
730 12 fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
731 12 ▶ if (fd >= 0) return fd;
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) return fd; 12 0 12
732 0 ▶ if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */
Branch: 1 branch
BranchTrueFalseTotal
if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */ 0 0 0
733 0 ▶ SS_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ 0 0 0
734 0 return -1;
735 }
736 0 ▶ SS_ERR("open %s: create/attach kept racing", path);
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("open %s: create/attach kept racing", path); 0 0 0
737 0 return -1;
738 }
739  
740 /* True iff the whole file is zero -- what an abandoned mid-init
741 creator leaves. Lets recovery re-init only a provably-empty file, never
742 one that merely starts with a zero word. Cold path, so a byte scan is
743 fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */
744 2 static int ss_file_is_zero(int fd, uint64_t size) {
745 char buf[16384];
746 9 ▶ for (uint64_t off = 0; off < size; ) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint64_t off = 0; off < size; ) { 8 1 9
747 8 ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off);
748 8 ▶ if (n <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return 0; 0 8 8
749 111975 ▶ for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0;
Branch: 2 branches
BranchTrueFalseTotal
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 1 111967 111968
for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; 111968 7 111975
750 7 off += (uint64_t)n;
751 }
752 1 return 1;
753 }
754  
755 /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */
756 13 static int ss_reserve(int fd, uint64_t size) {
757 13 const char *sp = getenv("DATA_SORTEDSET_SHARED_SPARSE");
758 13 ▶ if (sp && *sp && strcmp(sp, "0")) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (sp && *sp && strcmp(sp, "0")) return 0; 0 13 13
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
if (sp && *sp && strcmp(sp, "0")) return 0; 0 0 0
759 /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a
760 * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */
761 sigset_t all, old;
762 13 sigfillset(&all);
763 13 sigprocmask(SIG_BLOCK, &all, &old);
764 int e;
765 13 ▶ do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR);
Branch: 1 branch
BranchTrueFalseTotal
do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); 0 13 13
766 13 sigprocmask(SIG_SETMASK, &old, NULL);
767 13 ▶ if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 13 13
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; 0 0 0
768 0 errno = e;
769 0 return -1;
770 }
771  
772 49 static SsHandle *ss_create(const char *path, uint32_t max_entries, mode_t mode, char *errbuf) {
773 uint32_t index_slots, node_capacity;
774 49 ▶ if (!ss_validate_create_args(max_entries, &index_slots, &node_capacity, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_validate_create_args(max_entries, &index_slots, &node_capacity, errbuf)) return NULL; 1 48 49
775  
776 48 uint64_t total = ss_total_size(index_slots, node_capacity);
777 48 int anonymous = (path == NULL);
778 48 int fd = -1;
779 size_t map_size;
780 void *base;
781  
782 48 ▶ if (anonymous) {
Branch: 1 branch
BranchTrueFalseTotal
if (anonymous) { 25 23 48
783 25 map_size = (size_t)total;
784 25 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
785 25 ▶ if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 25 25
if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
786 } else {
787 23 fd = ss_secure_open(path, mode, errbuf);
788 35 ▶ if (fd < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return NULL; 0 23 23
789 23 ▶ if (flock(fd, LOCK_EX) < 0) { SS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (flock(fd, LOCK_EX) < 0) { SS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 23 23
if (flock(fd, LOCK_EX) < 0) { SS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
790 struct stat st;
791 23 ▶ if (fstat(fd, &st) < 0) { SS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { SS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 23 23
if (fstat(fd, &st) < 0) { SS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } 0 0 0
792 23 int is_new = (st.st_size == 0);
793 23 ▶ if (!is_new && (uint64_t)st.st_size < sizeof(SsHeader)) {
Branch: 2 branches
BranchTrueFalseTotal
if (!is_new && (uint64_t)st.st_size < sizeof(SsHeader)) { 12 11 23
if (!is_new && (uint64_t)st.st_size < sizeof(SsHeader)) { 1 11 12
794 1 ▶ SS_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: file too small (%lld)", path, (long long)st.st_size); 1 0 1
795 1 flock(fd, LOCK_UN); close(fd); return NULL;
796 }
797 22 ▶ if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) {
Branch: 3 branches
BranchTrueFalseTotal
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 11 11 22
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 11 0 11
if (is_new && (st.st_uid != geteuid() || fchmod(fd, mode) < 0)) { 0 11 11
798 0 ▶ SS_ERR("%s: refusing to initialize file not owned by us", path);
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: refusing to initialize file not owned by us", path); 0 0 0
799 0 flock(fd, LOCK_UN); close(fd); return NULL;
800 }
801 22 ▶ if (is_new && ftruncate(fd, (off_t)total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ftruncate(fd, (off_t)total) < 0) { 11 11 22
if (is_new && ftruncate(fd, (off_t)total) < 0) { 0 11 11
802 0 ▶ SS_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; 0 0 0
803 }
804 22 ▶ if (is_new && ss_reserve(fd, total) < 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (is_new && ss_reserve(fd, total) < 0) { 11 11 22
if (is_new && ss_reserve(fd, total) < 0) { 0 11 11
805 0 ▶ SS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
806 0 if (ftruncate(fd, 0) < 0) { /* best effort */ }
807 0 flock(fd, LOCK_UN); close(fd); return NULL;
808 }
809 22 ▶ map_size = is_new ? (size_t)total : (size_t)st.st_size;
Branch: 1 branch
BranchTrueFalseTotal
map_size = is_new ? (size_t)total : (size_t)st.st_size; 11 11 22
810 22 base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
811 22 ▶ if (base == MAP_FAILED) {
Branch: 1 branch
BranchTrueFalseTotal
if (base == MAP_FAILED) { 0 22 22
812 0 ▶ SS_ERR("mmap: %s", strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("mmap: %s", strerror(errno)); 0 0 0
813 0 ▶ if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ }
Branch: 1 branch
BranchTrueFalseTotal
if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } 0 0 0
814 0 flock(fd, LOCK_UN); close(fd); return NULL;
815 }
816 22 ▶ if (!is_new) {
Branch: 1 branch
BranchTrueFalseTotal
if (!is_new) { 11 11 22
817 11 ▶ if (!ss_validate_header((SsHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_validate_header((SsHeader *)base, (uint64_t)st.st_size)) { 4 7 11
818 /* Recover an abandoned mid-init file: a creator killed
819 * between the ftruncate and the header init leaves a
820 * full-size, all-zero (magic==0) file that would brick every
821 * future open of this path. Re-initialize ONLY when it is
822 * exactly our size, still uninitialized, and owned by us;
823 * anything else still errors. */
824 4 ▶ if (((SsHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((SsHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 3 1 4
if (((SsHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
825 2 ▶ && st.st_uid == geteuid() && ss_file_is_zero(fd, map_size)) {
Branch: 2 branches
BranchTrueFalseTotal
&& st.st_uid == geteuid() && ss_file_is_zero(fd, map_size)) { 2 0 2
&& st.st_uid == geteuid() && ss_file_is_zero(fd, map_size)) { 1 1 2
826 1 ▶ if (fchmod(fd, mode) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fchmod(fd, mode) < 0) { 0 1 1
827 0 ▶ SS_ERR("%s: fchmod: %s", path, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: fchmod: %s", path, strerror(errno)); 0 0 0
828 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
829 }
830 1 ▶ if (ss_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ss_reserve(fd, total) < 0) { 0 1 1
831 0 ▶ SS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); 0 0 0
832 0 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
833 }
834 1 ss_init_header(base, max_entries, index_slots, node_capacity, total);
835 1 flock(fd, LOCK_UN); close(fd);
836 1 return ss_setup(base, map_size, path, -1);
837 }
838 3 ▶ if (((SsHeader *)base)->magic == 0 && (uint64_t)st.st_size == total
Branch: 2 branches
BranchTrueFalseTotal
if (((SsHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 2 1 3
if (((SsHeader *)base)->magic == 0 && (uint64_t)st.st_size == total 1 1 2
839 1 ▶ && st.st_uid == geteuid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& st.st_uid == geteuid()) { 1 0 1
840 1 ▶ SS_ERR("%s: incomplete sorted-set file left by an interrupted create; remove it and retry", path);
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: incomplete sorted-set file left by an interrupted create; remove it and retry", path); 1 0 1
841 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
842 }
843 2 ▶ SS_ERR("invalid sorted-set file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("invalid sorted-set file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; 2 0 2
844 }
845 7 ▶ if (((SsHeader *)base)->sealed) { /* a frozen file must never be reopened read-write */
Branch: 1 branch
BranchTrueFalseTotal
if (((SsHeader *)base)->sealed) { /* a frozen file must never be reopened read-write */ 1 6 7
846 1 ▶ SS_ERR("%s is frozen (read-only); open it with new_readonly", path);
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s is frozen (read-only); open it with new_readonly", path); 1 0 1
847 1 munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
848 }
849 6 flock(fd, LOCK_UN); close(fd);
850 6 return ss_attach(base, map_size, path, -1, errbuf);
851 }
852 }
853 36 ss_init_header(base, max_entries, index_slots, node_capacity, total);
854 36 ▶ if (fd >= 0) { flock(fd, LOCK_UN); close(fd); }
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } 11 25 36
855 36 return ss_setup(base, map_size, path, -1);
856 }
857  
858 1 static SsHandle *ss_create_memfd(const char *name, uint32_t max_entries, char *errbuf) {
859 uint32_t index_slots, node_capacity;
860 1 ▶ if (!ss_validate_create_args(max_entries, &index_slots, &node_capacity, errbuf)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_validate_create_args(max_entries, &index_slots, &node_capacity, errbuf)) return NULL; 0 1 1
861  
862 1 uint64_t total = ss_total_size(index_slots, node_capacity);
863 1 ▶ int fd = memfd_create(name ? name : "sortedset", MFD_CLOEXEC | MFD_ALLOW_SEALING);
Branch: 1 branch
BranchTrueFalseTotal
int fd = memfd_create(name ? name : "sortedset", MFD_CLOEXEC | MFD_ALLOW_SEALING); 1 0 1
864 1 ▶ if (fd < 0) { SS_ERR("memfd_create: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { SS_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 1 1
if (fd < 0) { SS_ERR("memfd_create: %s", strerror(errno)); return NULL; } 0 0 0
865 1 ▶ if (ftruncate(fd, (off_t)total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ftruncate(fd, (off_t)total) < 0) { 0 1 1
866 0 ▶ SS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; 0 0 0
867 }
868 1 ▶ if (ss_reserve(fd, total) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ss_reserve(fd, total) < 0) { 0 1 1
869 0 ▶ SS_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno));
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); 0 0 0
870 0 close(fd); return NULL;
871 }
872 1 (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW);
873 1 void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
874 1 ▶ if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 1 1
if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } 0 0 0
875 1 ss_init_header(base, max_entries, index_slots, node_capacity, total);
876 1 return ss_setup(base, (size_t)total, NULL, fd);
877 }
878  
879 2 static SsHandle *ss_open_fd(int fd, char *errbuf) {
880 2 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 2 0 2
881 struct stat st;
882 2 ▶ if (fstat(fd, &st) < 0) { SS_ERR("fstat: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { SS_ERR("fstat: %s", strerror(errno)); return NULL; } 0 2 2
if (fstat(fd, &st) < 0) { SS_ERR("fstat: %s", strerror(errno)); return NULL; } 0 0 0
883 2 ▶ if ((uint64_t)st.st_size < sizeof(SsHeader)) { SS_ERR("too small"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(SsHeader)) { SS_ERR("too small"); return NULL; } 0 2 2
if ((uint64_t)st.st_size < sizeof(SsHeader)) { SS_ERR("too small"); return NULL; } 0 0 0
884 /* before mmap: a creator may truncate the file until it has set magic */
885 uint32_t magic;
886 2 ▶ if (pread(fd, &magic, sizeof magic, offsetof(SsHeader, magic)) != (ssize_t)sizeof magic || magic != SS_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(SsHeader, magic)) != (ssize_t)sizeof magic || magic != SS_MAGIC) { 2 0 2
if (pread(fd, &magic, sizeof magic, offsetof(SsHeader, magic)) != (ssize_t)sizeof magic || magic != SS_MAGIC) { 0 2 2
887 0 ▶ SS_ERR("invalid sorted-set"); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("invalid sorted-set"); return NULL; 0 0 0
888 }
889 2 size_t ms = (size_t)st.st_size;
890 2 void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
891 2 ▶ if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 2 2
if (base == MAP_FAILED) { SS_ERR("mmap: %s", strerror(errno)); return NULL; } 0 0 0
892 2 ▶ if (!ss_validate_header((SsHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_validate_header((SsHeader *)base, (uint64_t)st.st_size)) { 0 2 2
893 0 ▶ SS_ERR("invalid sorted-set"); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("invalid sorted-set"); munmap(base, ms); return NULL; 0 0 0
894 }
895 2 ▶ if (((SsHeader *)base)->sealed) { /* a frozen file must never be reopened read-write */
Branch: 1 branch
BranchTrueFalseTotal
if (((SsHeader *)base)->sealed) { /* a frozen file must never be reopened read-write */ 1 1 2
896 1 ▶ SS_ERR("this sorted set is frozen (read-only); open it with new_readonly");
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("this sorted set is frozen (read-only); open it with new_readonly"); 1 0 1
897 1 munmap(base, ms); return NULL;
898 }
899 1 int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0);
900 1 ▶ if (myfd < 0) { SS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (myfd < 0) { SS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 1 1
if (myfd < 0) { SS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } 0 0 0
901 1 return ss_attach(base, ms, NULL, myfd, errbuf);
902 }
903  
904 48 static void ss_destroy(SsHandle *h) {
905 48 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 48 48
906 /* Release our reader slot on clean teardown (else short-lived-reader churn
907 * exhausts the slot table); skip if a read lock is still held (rdepth>0). */
908 48 ▶ if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid &&
Branch: 3 branches
BranchTrueFalseTotal
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 48 0 48
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 37 11 48
if (h->reader_slots && h->my_slot_idx != UINT32_MAX && h->cached_pid && 37 0 37
909 37 ▶ h->cached_fork_gen == __atomic_load_n(&ss_fork_gen, __ATOMIC_RELAXED) &&
Branch: 1 branch
BranchTrueFalseTotal
h->cached_fork_gen == __atomic_load_n(&ss_fork_gen, __ATOMIC_RELAXED) && 37 0 37
910 37 ▶ __atomic_load_n(&h->reader_slots[h->my_slot_idx].rdepth, __ATOMIC_ACQUIRE) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
__atomic_load_n(&h->reader_slots[h->my_slot_idx].rdepth, __ATOMIC_ACQUIRE) == 0) { 37 0 37
911 /* Clear our occ bit BEFORE freeing the slot: we still own the pid so no
912 * claimant can take the slot mid-clear, and rdepth==0 so no writer needs
913 * to see us. (A crash skips this -> the bit is reclaimed lazily by a
914 * writer scan / re-claim, same as the pid.) */
915 37 ss_occ_clear(h, h->my_slot_idx);
916 37 uint32_t expected = h->cached_pid;
917 37 __atomic_compare_exchange_n(&h->reader_slots[h->my_slot_idx].pid,
918 &expected, 0, 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
919 }
920 48 ▶ if (h->notify_fd >= 0) close(h->notify_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd >= 0) close(h->notify_fd); 1 47 48
921 48 ▶ if (h->backing_fd >= 0) close(h->backing_fd);
Branch: 1 branch
BranchTrueFalseTotal
if (h->backing_fd >= 0) close(h->backing_fd); 2 46 48
922 48 ▶ if (h->hdr) munmap(h->hdr, h->mmap_size);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr) munmap(h->hdr, h->mmap_size); 48 0 48
923 48 free(h->path);
924 48 free(h);
925 }
926  
927 6 static inline int ss_msync(SsHandle *h) {
928 6 ▶ if (!h || !h->hdr) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !h->hdr) return 0; 6 0 6
if (!h || !h->hdr) return 0; 0 6 6
929 6 return msync(h->hdr, h->mmap_size, MS_SYNC);
930 }
931  
932 /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever.
933 * A sealed file is immutable and no read path writes the mapping, so queries
934 * take no reader-slot / rwlock traffic and any number of processes can share
935 * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian
936 * file). */
937 5 static SsHandle *ss_open_readonly(const char *path, char *errbuf) {
938 5 ▶ if (errbuf) errbuf[0] = '\0';
Branch: 1 branch
BranchTrueFalseTotal
if (errbuf) errbuf[0] = '\0'; 5 0 5
939 5 int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC);
940 5 ▶ if (fd < 0) { SS_ERR("open %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0) { SS_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 4 5
if (fd < 0) { SS_ERR("open %s: %s", path, strerror(errno)); return NULL; } 1 0 1
941 struct stat st;
942 4 ▶ if (fstat(fd, &st) < 0) { SS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (fstat(fd, &st) < 0) { SS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 4 4
if (fstat(fd, &st) < 0) { SS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } 0 0 0
943 4 ▶ if ((uint64_t)st.st_size < sizeof(SsHeader)) { SS_ERR("%s: file too small", path); close(fd); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(SsHeader)) { SS_ERR("%s: file too small", path); close(fd); return NULL; } 0 4 4
if ((uint64_t)st.st_size < sizeof(SsHeader)) { SS_ERR("%s: file too small", path); close(fd); return NULL; } 0 0 0
944 /* before mmap: a creator may truncate the file until it has set magic */
945 uint32_t magic;
946 4 ▶ if (pread(fd, &magic, sizeof magic, offsetof(SsHeader, magic)) != (ssize_t)sizeof magic || magic != SS_MAGIC) {
Branch: 2 branches
BranchTrueFalseTotal
if (pread(fd, &magic, sizeof magic, offsetof(SsHeader, magic)) != (ssize_t)sizeof magic || magic != SS_MAGIC) { 4 0 4
if (pread(fd, &magic, sizeof magic, offsetof(SsHeader, magic)) != (ssize_t)sizeof magic || magic != SS_MAGIC) { 0 4 4
947 0 ▶ SS_ERR("%s: invalid sorted-set file", path); close(fd); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: invalid sorted-set file", path); close(fd); return NULL; 0 0 0
948 }
949 4 size_t ms = (size_t)st.st_size;
950 4 void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0);
951 4 close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */
952 4 ▶ if (base == MAP_FAILED) { SS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (base == MAP_FAILED) { SS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 4 4
if (base == MAP_FAILED) { SS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } 0 0 0
953 4 ▶ if (!ss_validate_header((SsHeader *)base, (uint64_t)st.st_size)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_validate_header((SsHeader *)base, (uint64_t)st.st_size)) { 0 4 4
954 0 ▶ SS_ERR("%s: invalid sorted-set file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: invalid sorted-set file", path); munmap(base, ms); return NULL; 0 0 0
955 }
956 4 ▶ if (!__atomic_load_n(&((SsHeader *)base)->sealed, __ATOMIC_ACQUIRE)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!__atomic_load_n(&((SsHeader *)base)->sealed, __ATOMIC_ACQUIRE)) { 1 3 4
957 1 ▶ SS_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path);
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); 1 0 1
958 1 munmap(base, ms); return NULL;
959 }
960 3 ▶ if (!ss_validate_state((SsHeader *)base)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_validate_state((SsHeader *)base)) { 0 3 3
961 0 ▶ SS_ERR("%s: invalid sorted-set file", path); munmap(base, ms); return NULL;
Branch: 1 branch
BranchTrueFalseTotal
SS_ERR("%s: invalid sorted-set file", path); munmap(base, ms); return NULL; 0 0 0
962 }
963 3 SsHandle *h = ss_setup(base, ms, path, -1); /* munmaps on OOM */
964 3 ▶ if (!h) { SS_ERR("out of memory"); return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { SS_ERR("out of memory"); return NULL; } 0 3 3
if (!h) { SS_ERR("out of memory"); return NULL; } 0 0 0
965 3 h->readonly = 1;
966 3 return h;
967 }
968  
969 /* Seal a sorted set: make it permanently immutable so it can be shipped and
970 * opened read-only. Takes the write lock so no mutation is in flight, publishes
971 * the seal, then flushes it (file/memfd-backed). The order-statistics B+tree is
972 * maintained EAGERLY on every write (subtree counts, leaf links and separators
973 * are all kept up to date in add/remove/incr) -- there is no deferred/lazy build
974 * to force-complete, so the sealed tree is already query-ready for the lock-free
975 * read path. Afterwards every mutator croaks and a read-write reopen is refused. */
976 1 static int ss_freeze(SsHandle *h) {
977 1 ss_rwlock_wrlock(h);
978 1 __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE);
979 1 ss_rwlock_wrunlock(h);
980 1 ▶ if (h->path || h->backing_fd >= 0) return ss_msync(h); /* durability for file/memfd-backed */
Branch: 2 branches
BranchTrueFalseTotal
if (h->path || h->backing_fd >= 0) return ss_msync(h); /* durability for file/memfd-backed */ 0 1 1
if (h->path || h->backing_fd >= 0) return ss_msync(h); /* durability for file/memfd-backed */ 0 0 0
981 0 return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
982 }
983  
984 1 static int ss_create_eventfd(SsHandle *h) {
985 1 ▶ if (h->notify_fd >= 0) return h->notify_fd;
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd >= 0) return h->notify_fd; 0 1 1
986 1 int efd = eventfd(0, EFD_NONBLOCK|EFD_CLOEXEC);
987 1 ▶ if (efd < 0) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (efd < 0) return -1; 0 1 1
988 1 h->notify_fd = efd;
989 1 return efd;
990 }
991  
992 1 static int ss_notify(SsHandle *h) {
993 1 ▶ if (h->notify_fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd < 0) return 0; 0 1 1
994 1 uint64_t v = 1;
995 1 return write(h->notify_fd, &v, sizeof(v)) == sizeof(v);
996 }
997  
998 1 static int64_t ss_eventfd_consume(SsHandle *h) {
999 1 ▶ if (h->notify_fd < 0) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->notify_fd < 0) return -1; 0 1 1
1000 1 uint64_t v = 0;
1001 1 ▶ if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1; 0 1 1
1002 1 return (int64_t)v;
1003 }
1004  
1005 /* ================================================================
1006 * Sorted set: node pool, member index, B+tree (callers hold the lock)
1007 * ================================================================ */
1008  
1009 5 static inline void ss_clear_tree(SsHandle *h) {
1010 5 SsHeader *hdr = h->hdr;
1011 5 hdr->count = 0;
1012 5 hdr->root = SS_NONE;
1013 5 hdr->height = 0;
1014 5 hdr->leftmost = SS_NONE;
1015 5 hdr->rightmost = SS_NONE;
1016 625 ▶ for (uint32_t i = 0; i < h->node_capacity; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < h->node_capacity; i++) 620 5 625
1017 620 ▶ h->nodes[i].parent = (i + 1 < h->node_capacity) ? (i + 1) : SS_NONE;
Branch: 1 branch
BranchTrueFalseTotal
h->nodes[i].parent = (i + 1 < h->node_capacity) ? (i + 1) : SS_NONE; 615 5 620
1018 5 hdr->node_free_head = 0;
1019 5 }
1020  
1021 /* reset to the empty set (caller holds the write lock) */
1022 5 static inline void ss_clear_locked(SsHandle *h) {
1023 5 ss_clear_tree(h);
1024 5 memset(h->index, 0, (size_t)h->index_slots * sizeof(SsIdxSlot));
1025 5 }
1026  
1027 /* ---- node pool ---- */
1028 6812 static inline uint32_t ss_node_alloc(SsHandle *h) {
1029 6812 uint32_t idx = h->hdr->node_free_head;
1030 6812 ▶ if (idx == SS_NONE || idx >= h->node_capacity) return SS_NONE; /* Layer B: empty or corrupt free-list head */
Branch: 2 branches
BranchTrueFalseTotal
if (idx == SS_NONE || idx >= h->node_capacity) return SS_NONE; /* Layer B: empty or corrupt free-list head */ 6812 0 6812
if (idx == SS_NONE || idx >= h->node_capacity) return SS_NONE; /* Layer B: empty or corrupt free-list head */ 0 6812 6812
1031 6812 h->hdr->node_free_head = h->nodes[idx].parent;
1032 6812 return idx;
1033 }
1034 /* Layer B: the free list head and links live in peer-writable shared memory, so
1035 * ss_node_alloc can legitimately return SS_NONE (exhausted OR corrupt). The
1036 * write paths cannot unwind a half-done split, so callers must confirm the
1037 * worst case is available BEFORE mutating anything -- otherwise a split would
1038 * write through &h->nodes[SS_NONE], far outside the mapping.
1039 * Walks at most `need` links, so a corrupt free list containing a cycle is
1040 * bounded here too. */
1041 112327 static inline int ss_nodes_available(const SsHandle *h, uint32_t need) {
1042 112327 uint32_t idx = h->hdr->node_free_head;
1043 712470 ▶ for (uint32_t i = 0; i < need; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < need; i++) { 600143 112327 712470
1044 600143 ▶ if (idx == SS_NONE || idx >= h->node_capacity) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (idx == SS_NONE || idx >= h->node_capacity) return 0; 600143 0 600143
if (idx == SS_NONE || idx >= h->node_capacity) return 0; 0 600143 600143
1045 600143 idx = h->nodes[idx].parent;
1046 }
1047 112327 return 1;
1048 }
1049  
1050 /* An insert splits at most once per level and may add a new root. */
1051 112327 static inline int ss_add_has_headroom(const SsHandle *h) {
1052 112327 return ss_nodes_available(h, h->hdr->height + 2);
1053 }
1054  
1055 2338 static inline void ss_node_free(SsHandle *h, uint32_t idx) {
1056 2338 h->nodes[idx].parent = h->hdr->node_free_head;
1057 2338 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1058 2338 h->hdr->node_free_head = idx;
1059 2338 }
1060  
1061 /* node indices stored in the mmap (children[], leftmost,
1062 * rightmost, leaf next/prev, free-list links) are attacker-controlled -- a
1063 * local peer can write the backing file. Bound every such index against the
1064 * node pool before using it to dereference h->nodes[]. A predictable
1065 * never-taken branch for valid data; on a bad index the caller stops/skips
1066 * instead of trapping. */
1067 711088 static inline int ss_node_ok(const SsHandle *h, uint32_t idx) {
1068 711088 return idx < h->node_capacity; /* cached geometry, not peer-writable header */
1069 }
1070  
1071 /* ---- member -> score index (open addressing, linear probe) ---- */
1072 /* returns the slot of `member` (if present) or the first empty slot for it;
1073 *found (optional, may be NULL) says which. Returns SS_NONE with *found == 0
1074 when every slot reads occupied and `member` is absent. Create-time sizing
1075 keeps the load factor <= 0.7, so an all-occupied table means a lock-violating
1076 peer has scribbled over the state bytes -- but the probe must still be
1077 bounded by the table size: an unbounded one spins forever while holding the
1078 lock, hanging every process that shares the segment. */
1079 362040 static inline uint32_t ss_idx_find(SsHandle *h, int64_t member, int *found) {
1080 362040 uint32_t mask = h->index_slots - 1; /* cached geometry, not peer-writable header */
1081 362040 uint32_t i = (uint32_t)(ss_hash_member(member) & mask);
1082 401859 ▶ for (uint32_t probe = 0; probe < h->index_slots; probe++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t probe = 0; probe < h->index_slots; probe++) { 401859 0 401859
1083 401859 ▶ if (!h->index[i].state) { if (found) *found = 0; return i; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h->index[i].state) { if (found) *found = 0; return i; } 170911 230948 401859
if (!h->index[i].state) { if (found) *found = 0; return i; } 91358 79553 170911
1084 230948 ▶ if (h->index[i].member == member) { if (found) *found = 1; return i; }
Branch: 2 branches
BranchTrueFalseTotal
if (h->index[i].member == member) { if (found) *found = 1; return i; } 191129 39819 230948
if (h->index[i].member == member) { if (found) *found = 1; return i; } 158355 32774 191129
1085 39819 i = (i + 1) & mask;
1086 }
1087 0 ▶ if (found) *found = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (found) *found = 0; 0 0 0
1088 0 return SS_NONE; /* corrupt full table */
1089 }
1090 214184 static inline int ss_idx_get(SsHandle *h, int64_t member, double *score) {
1091 214184 int f; uint32_t i = ss_idx_find(h, member, &f);
1092 214184 ▶ if (f) { *score = h->index[i].score; return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (f) { *score = h->index[i].score; return 1; } 122826 91358 214184
1093 91358 return 0;
1094 }
1095 /* returns 0 when the (corrupt) index has no free slot for an absent member --
1096 the caller must fail the operation instead of clobbering an arbitrary slot */
1097 112327 static inline int ss_idx_set(SsHandle *h, int64_t member, double score) {
1098 112327 uint32_t i = ss_idx_find(h, member, NULL);
1099 112327 ▶ if (i == SS_NONE) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (i == SS_NONE) return 0; 0 112327 112327
1100 112327 h->index[i].member = member;
1101 112327 h->index[i].score = score;
1102 112327 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1103 112327 h->index[i].state = 1;
1104 112327 return 1;
1105 }
1106  
1107 /* ---- B+tree ---- */
1108 13520 static inline uint32_t ss_node_total(const SsNode *nd) {
1109 13520 ▶ if (nd->is_leaf) return nd->num;
Branch: 1 branch
BranchTrueFalseTotal
if (nd->is_leaf) return nd->num; 12698 822 13520
1110 822 uint32_t t = 0;
1111 7809 ▶ for (int i = 0; i < nd->num; i++) t += nd->counts[i];
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < nd->num; i++) t += nd->counts[i]; 6987 822 7809
1112 822 return t;
1113 }
1114  
1115 /* child index in an internal node whose subtree would hold (score,member) */
1116 428564 static inline int ss_child_index(const SsNode *nd, double score, int64_t member) {
1117 428564 int lo = 0, hi = nd->num - 1;
1118 1836587 ▶ while (lo < hi) {
Branch: 1 branch
BranchTrueFalseTotal
while (lo < hi) { 1408023 428564 1836587
1119 1408023 int mid = (lo + hi) / 2;
1120 1408023 ▶ if (ss_key_cmp(score, member, nd->scores[mid], nd->members[mid]) < 0) hi = mid;
Branch: 1 branch
BranchTrueFalseTotal
if (ss_key_cmp(score, member, nd->scores[mid], nd->members[mid]) < 0) hi = mid; 804610 603413 1408023
1121 603413 else lo = mid + 1;
1122 }
1123 428564 return lo;
1124 }
1125  
1126 typedef struct { int split; uint32_t rnode; double rscore; int64_t rmember; } SsSplit;
1127  
1128 /* insert (score,member) into subtree nidx (member known absent); on overflow
1129 split and return the new right node + separator to promote; maintains counts */
1130 375487 static SsSplit ss_insert_rec(SsHandle *h, uint32_t nidx, double score, int64_t member) {
1131 375487 SsNode *nd = &h->nodes[nidx];
1132 375487 SsSplit r = { 0, SS_NONE, 0.0, 0 };
1133 375487 ▶ if (nd->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (nd->is_leaf) { 112294 263193 375487
1134 112294 int pos = 0;
1135 776780 ▶ while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) < 0) pos++;
Branch: 2 branches
BranchTrueFalseTotal
while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) < 0) pos++; 762427 14353 776780
while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) < 0) pos++; 664486 97941 762427
1136 716617 ▶ for (int i = nd->num; i > pos; i--) { nd->scores[i] = nd->scores[i-1]; nd->members[i] = nd->members[i-1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = nd->num; i > pos; i--) { nd->scores[i] = nd->scores[i-1]; nd->members[i] = nd->members[i-1]; } 604323 112294 716617
1137 112294 nd->scores[pos] = score; nd->members[pos] = member; nd->num++;
1138 112294 ▶ if (nd->num <= SS_ORDER) return r;
Branch: 1 branch
BranchTrueFalseTotal
if (nd->num <= SS_ORDER) return r; 105945 6349 112294
1139 6349 uint32_t ridx = ss_node_alloc(h);
1140 6349 SsNode *rn = &h->nodes[ridx];
1141 6349 rn->is_leaf = 1; rn->parent = nd->parent;
1142 6349 int mid = nd->num / 2, rc = nd->num - mid;
1143 63490 ▶ for (int i = 0; i < rc; i++) { rn->scores[i] = nd->scores[mid+i]; rn->members[i] = nd->members[mid+i]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < rc; i++) { rn->scores[i] = nd->scores[mid+i]; rn->members[i] = nd->members[mid+i]; } 57141 6349 63490
1144 6349 rn->num = (uint16_t)rc; nd->num = (uint16_t)mid;
1145 6349 rn->next = nd->next; rn->prev = nidx;
1146 6349 ▶ if (nd->next == SS_NONE) h->hdr->rightmost = ridx;
Branch: 1 branch
BranchTrueFalseTotal
if (nd->next == SS_NONE) h->hdr->rightmost = ridx; 663 5686 6349
1147 5686 ▶ else if (ss_node_ok(h, nd->next)) h->nodes[nd->next].prev = ridx;
Branch: 1 branch
BranchTrueFalseTotal
else if (ss_node_ok(h, nd->next)) h->nodes[nd->next].prev = ridx; 5686 0 5686
1148 /* corrupt next link: skip the backlink fix rather than a wild write */
1149 6349 nd->next = ridx;
1150 6349 r.split = 1; r.rnode = ridx; r.rscore = rn->scores[0]; r.rmember = rn->members[0];
1151 6349 return r;
1152 }
1153 263193 int c = ss_child_index(nd, score, member);
1154 263193 uint32_t cidx = nd->children[c];
1155 263193 ▶ if (!ss_node_ok(h, cidx)) return r; /* Layer B: corrupt child index -- stop instead of a wild descent */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, cidx)) return r; /* Layer B: corrupt child index -- stop instead of a wild descent */ 0 263193 263193
1156 263193 SsSplit cr = ss_insert_rec(h, cidx, score, member);
1157 263193 ▶ if (!cr.split) { nd->counts[c]++; return r; }
Branch: 1 branch
BranchTrueFalseTotal
if (!cr.split) { nd->counts[c]++; return r; } 256452 6741 263193
1158 42475 ▶ for (int i = nd->num; i > c + 1; i--) { nd->children[i] = nd->children[i-1]; nd->counts[i] = nd->counts[i-1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = nd->num; i > c + 1; i--) { nd->children[i] = nd->children[i-1]; nd->counts[i] = nd->counts[i-1]; } 35734 6741 42475
1159 42475 ▶ for (int i = nd->num - 1; i > c; i--) { nd->scores[i] = nd->scores[i-1]; nd->members[i] = nd->members[i-1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = nd->num - 1; i > c; i--) { nd->scores[i] = nd->scores[i-1]; nd->members[i] = nd->members[i-1]; } 35734 6741 42475
1160 6741 nd->scores[c] = cr.rscore; nd->members[c] = cr.rmember;
1161 6741 nd->children[c+1] = cr.rnode; h->nodes[cr.rnode].parent = nidx;
1162 6741 nd->num++;
1163 6741 nd->counts[c] = ss_node_total(&h->nodes[cidx]);
1164 6741 nd->counts[c+1] = ss_node_total(&h->nodes[cr.rnode]);
1165 6741 ▶ if (nd->num <= SS_ORDER) return r;
Branch: 1 branch
BranchTrueFalseTotal
if (nd->num <= SS_ORDER) return r; 6330 411 6741
1166 411 uint32_t ridx = ss_node_alloc(h);
1167 411 SsNode *rn = &h->nodes[ridx];
1168 411 rn->is_leaf = 0; rn->parent = nd->parent;
1169 411 int midc = nd->num / 2, rch = nd->num - midc;
1170 4110 ▶ for (int i = 0; i < rch; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < rch; i++) { 3699 411 4110
1171 3699 rn->children[i] = nd->children[midc+i];
1172 3699 rn->counts[i] = nd->counts[midc+i];
1173 3699 ▶ if (ss_node_ok(h, rn->children[i])) h->nodes[rn->children[i]].parent = ridx; /* skip a corrupt child index */
Branch: 1 branch
BranchTrueFalseTotal
if (ss_node_ok(h, rn->children[i])) h->nodes[rn->children[i]].parent = ridx; /* skip a corrupt child index */ 3699 0 3699
1174 }
1175 3699 ▶ for (int i = 0; i < rch - 1; i++) { rn->scores[i] = nd->scores[midc+i]; rn->members[i] = nd->members[midc+i]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < rch - 1; i++) { rn->scores[i] = nd->scores[midc+i]; rn->members[i] = nd->members[midc+i]; } 3288 411 3699
1176 411 rn->num = (uint16_t)rch;
1177 411 double up_s = nd->scores[midc-1]; int64_t up_m = nd->members[midc-1];
1178 411 nd->num = (uint16_t)midc;
1179 411 r.split = 1; r.rnode = ridx; r.rscore = up_s; r.rmember = up_m;
1180 411 return r;
1181 }
1182  
1183 112327 static void ss_tree_add(SsHandle *h, double score, int64_t member) {
1184 112327 SsHeader *hdr = h->hdr;
1185 112327 ▶ if (hdr->root == SS_NONE) {
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->root == SS_NONE) { 33 112294 112327
1186 33 uint32_t l = ss_node_alloc(h);
1187 33 SsNode *nd = &h->nodes[l];
1188 33 nd->is_leaf = 1; nd->parent = SS_NONE; nd->next = SS_NONE; nd->prev = SS_NONE;
1189 33 nd->num = 1; nd->scores[0] = score; nd->members[0] = member;
1190 33 hdr->root = l; hdr->leftmost = l; hdr->rightmost = l; hdr->height = 1;
1191 33 hdr->count++;
1192 33 return;
1193 }
1194 112294 ▶ if (!ss_node_ok(h, hdr->root)) return; /* Layer B: corrupt root index -- refuse the descent */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, hdr->root)) return; /* Layer B: corrupt root index -- refuse the descent */ 0 112294 112294
1195 112294 SsSplit r = ss_insert_rec(h, hdr->root, score, member);
1196 112294 ▶ if (r.split) {
Branch: 1 branch
BranchTrueFalseTotal
if (r.split) { 19 112275 112294
1197 19 uint32_t nr = ss_node_alloc(h);
1198 19 SsNode *root = &h->nodes[nr];
1199 19 root->is_leaf = 0; root->parent = SS_NONE; root->num = 2;
1200 19 root->children[0] = hdr->root; root->children[1] = r.rnode;
1201 19 root->scores[0] = r.rscore; root->members[0] = r.rmember;
1202 19 root->counts[0] = ss_node_total(&h->nodes[hdr->root]);
1203 19 root->counts[1] = ss_node_total(&h->nodes[r.rnode]);
1204 19 h->nodes[hdr->root].parent = nr;
1205 19 h->nodes[r.rnode].parent = nr;
1206 19 hdr->root = nr; hdr->height++;
1207 }
1208 112294 hdr->count++;
1209 }
1210  
1211 /* index backward-shift deletion (keeps probe sequences contiguous) */
1212 35529 static void ss_idx_del(SsHandle *h, int64_t member) {
1213 35529 uint32_t mask = h->index_slots - 1; /* cached geometry, not peer-writable header */
1214 35529 int f; uint32_t i = ss_idx_find(h, member, &f);
1215 35529 ▶ if (!f) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!f) return; 0 35529 35529
1216 35529 uint32_t j = i;
1217 /* bounded by the table size: the shift scan stops at the first empty slot,
1218 but a corrupt all-occupied table has none and must not spin forever
1219 under the lock */
1220 41636 ▶ for (uint32_t probe = 0; probe < h->index_slots; probe++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t probe = 0; probe < h->index_slots; probe++) { 41636 0 41636
1221 41636 j = (j + 1) & mask;
1222 41636 ▶ if (!h->index[j].state) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!h->index[j].state) break; 35529 6107 41636
1223 6107 uint32_t k = (uint32_t)(ss_hash_member(h->index[j].member) & mask);
1224 6107 ▶ int in = (i < j) ? (i < k && k <= j) : (k > i || k <= j); /* k in (i, j] ? */
Branch: 5 branches
BranchTrueFalseTotal
int in = (i < j) ? (i < k && k <= j) : (k > i || k <= j); /* k in (i, j] ? */ 6107 0 6107
int in = (i < j) ? (i < k && k <= j) : (k > i || k <= j); /* k in (i, j] ? */ 4665 1442 6107
int in = (i < j) ? (i < k && k <= j) : (k > i || k <= j); /* k in (i, j] ? */ 4665 0 4665
int in = (i < j) ? (i < k && k <= j) : (k > i || k <= j); /* k in (i, j] ? */ 0 0 0
int in = (i < j) ? (i < k && k <= j) : (k > i || k <= j); /* k in (i, j] ? */ 0 0 0
1225 6107 ▶ if (!in) { h->index[i] = h->index[j]; i = j; }
Branch: 1 branch
BranchTrueFalseTotal
if (!in) { h->index[i] = h->index[j]; i = j; } 1442 4665 6107
1226 }
1227 35529 h->index[i].state = 0;
1228 }
1229  
1230 /* merge children[c] and children[c+1] of pidx into children[c]; frees the right
1231 node and pulls separator c down (for internal nodes) */
1232 2334 static void ss_merge(SsHandle *h, uint32_t pidx, int c) {
1233 2334 SsNode *p = &h->nodes[pidx];
1234 2334 uint32_t lidx = p->children[c], ridx = p->children[c+1];
1235 2334 ▶ if (!ss_node_ok(h, lidx) || !ss_node_ok(h, ridx)) return; /* Layer B: corrupt child index */
Branch: 2 branches
BranchTrueFalseTotal
if (!ss_node_ok(h, lidx) || !ss_node_ok(h, ridx)) return; /* Layer B: corrupt child index */ 2334 0 2334
if (!ss_node_ok(h, lidx) || !ss_node_ok(h, ridx)) return; /* Layer B: corrupt child index */ 0 2334 2334
1236 2334 SsNode *ln = &h->nodes[lidx], *rn = &h->nodes[ridx];
1237 2334 ▶ if (ln->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (ln->is_leaf) { 2307 27 2334
1238 19462 ▶ for (int i = 0; i < rn->num; i++) { ln->scores[ln->num+i] = rn->scores[i]; ln->members[ln->num+i] = rn->members[i]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < rn->num; i++) { ln->scores[ln->num+i] = rn->scores[i]; ln->members[ln->num+i] = rn->members[i]; } 17155 2307 19462
1239 2307 ln->next = rn->next;
1240 2307 ▶ if (rn->next == SS_NONE) h->hdr->rightmost = lidx;
Branch: 1 branch
BranchTrueFalseTotal
if (rn->next == SS_NONE) h->hdr->rightmost = lidx; 473 1834 2307
1241 1834 ▶ else if (ss_node_ok(h, rn->next)) h->nodes[rn->next].prev = lidx;
Branch: 1 branch
BranchTrueFalseTotal
else if (ss_node_ok(h, rn->next)) h->nodes[rn->next].prev = lidx; 1834 0 1834
1242 /* corrupt next link: skip the backlink fix rather than a wild write */
1243 2307 ln->num = (uint16_t)(ln->num + rn->num);
1244 } else {
1245 27 ln->scores[ln->num-1] = p->scores[c]; ln->members[ln->num-1] = p->members[c]; /* pull separator down */
1246 234 ▶ for (int i = 0; i < rn->num; i++) { ln->children[ln->num+i] = rn->children[i]; ln->counts[ln->num+i] = rn->counts[i]; if (ss_node_ok(h, rn->children[i])) h->nodes[rn->children[i]].parent = lidx; }
Branch: 2 branches
BranchTrueFalseTotal
for (int i = 0; i < rn->num; i++) { ln->children[ln->num+i] = rn->children[i]; ln->counts[ln->num+i] = rn->counts[i]; if (ss_node_ok(h, rn->children[i])) h->nodes[rn->children[i]].parent = lidx; } 207 0 207
for (int i = 0; i < rn->num; i++) { ln->children[ln->num+i] = rn->children[i]; ln->counts[ln->num+i] = rn->counts[i]; if (ss_node_ok(h, rn->children[i])) h->nodes[rn->children[i]].parent = lidx; } 207 27 234
1247 207 ▶ for (int i = 0; i < rn->num - 1; i++) { ln->scores[ln->num+i] = rn->scores[i]; ln->members[ln->num+i] = rn->members[i]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < rn->num - 1; i++) { ln->scores[ln->num+i] = rn->scores[i]; ln->members[ln->num+i] = rn->members[i]; } 180 27 207
1248 27 ln->num = (uint16_t)(ln->num + rn->num);
1249 }
1250 2334 p->counts[c] += p->counts[c+1];
1251 15567 ▶ for (int i = c+1; i+1 < p->num; i++) { p->children[i] = p->children[i+1]; p->counts[i] = p->counts[i+1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = c+1; i+1 < p->num; i++) { p->children[i] = p->children[i+1]; p->counts[i] = p->counts[i+1]; } 13233 2334 15567
1252 15567 ▶ for (int i = c; i+1 < p->num-1; i++) { p->scores[i] = p->scores[i+1]; p->members[i] = p->members[i+1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = c; i+1 < p->num-1; i++) { p->scores[i] = p->scores[i+1]; p->members[i] = p->members[i+1]; } 13233 2334 15567
1253 2334 p->num--;
1254 2334 ss_node_free(h, ridx);
1255 }
1256  
1257 /* fix an underflow in children[c] of pidx by borrowing from a sibling or merging */
1258 11908 static void ss_fix_underflow(SsHandle *h, uint32_t pidx, int c) {
1259 11908 SsNode *p = &h->nodes[pidx];
1260 11908 uint32_t cidx = p->children[c];
1261 11908 ▶ if (!ss_node_ok(h, cidx)) return; /* Layer B: corrupt child index */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, cidx)) return; /* Layer B: corrupt child index */ 0 11908 11908
1262 11908 SsNode *cn = &h->nodes[cidx];
1263 11908 ▶ if (c > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (c > 0) { 9105 2803 11908
1264 9105 uint32_t lidx = p->children[c-1];
1265 9105 ▶ if (!ss_node_ok(h, lidx)) return; /* Layer B: corrupt sibling index */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, lidx)) return; /* Layer B: corrupt sibling index */ 0 9105 9105
1266 9105 SsNode *ln = &h->nodes[lidx];
1267 9105 ▶ if (ln->num > SS_MIN) { /* borrow from left */
Branch: 1 branch
BranchTrueFalseTotal
if (ln->num > SS_MIN) { /* borrow from left */ 6195 2910 9105
1268 6195 ▶ if (cn->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (cn->is_leaf) { 6143 52 6195
1269 49144 ▶ for (int i = cn->num; i > 0; i--) { cn->scores[i] = cn->scores[i-1]; cn->members[i] = cn->members[i-1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = cn->num; i > 0; i--) { cn->scores[i] = cn->scores[i-1]; cn->members[i] = cn->members[i-1]; } 43001 6143 49144
1270 6143 cn->scores[0] = ln->scores[ln->num-1]; cn->members[0] = ln->members[ln->num-1];
1271 6143 cn->num++; ln->num--;
1272 6143 p->scores[c-1] = cn->scores[0]; p->members[c-1] = cn->members[0];
1273 6143 p->counts[c-1]--; p->counts[c]++;
1274 } else {
1275 52 uint32_t moved = ln->counts[ln->num-1];
1276 416 ▶ for (int i = cn->num; i > 0; i--) { cn->children[i] = cn->children[i-1]; cn->counts[i] = cn->counts[i-1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = cn->num; i > 0; i--) { cn->children[i] = cn->children[i-1]; cn->counts[i] = cn->counts[i-1]; } 364 52 416
1277 364 ▶ for (int i = cn->num-1; i > 0; i--) { cn->scores[i] = cn->scores[i-1]; cn->members[i] = cn->members[i-1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = cn->num-1; i > 0; i--) { cn->scores[i] = cn->scores[i-1]; cn->members[i] = cn->members[i-1]; } 312 52 364
1278 52 cn->scores[0] = p->scores[c-1]; cn->members[0] = p->members[c-1];
1279 52 cn->children[0] = ln->children[ln->num-1]; cn->counts[0] = moved;
1280 52 ▶ if (ss_node_ok(h, cn->children[0])) h->nodes[cn->children[0]].parent = cidx; /* skip a corrupt borrowed child */
Branch: 1 branch
BranchTrueFalseTotal
if (ss_node_ok(h, cn->children[0])) h->nodes[cn->children[0]].parent = cidx; /* skip a corrupt borrowed child */ 52 0 52
1281 52 cn->num++;
1282 52 p->scores[c-1] = ln->scores[ln->num-2]; p->members[c-1] = ln->members[ln->num-2];
1283 52 ln->num--;
1284 52 p->counts[c-1] -= moved; p->counts[c] += moved;
1285 }
1286 6195 return;
1287 }
1288 }
1289 5713 ▶ if (c < p->num - 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (c < p->num - 1) { 5091 622 5713
1290 5091 uint32_t ridx = p->children[c+1];
1291 5091 ▶ if (!ss_node_ok(h, ridx)) return; /* Layer B: corrupt sibling index */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, ridx)) return; /* Layer B: corrupt sibling index */ 0 5091 5091
1292 5091 SsNode *rn = &h->nodes[ridx];
1293 5091 ▶ if (rn->num > SS_MIN) { /* borrow from right */
Branch: 1 branch
BranchTrueFalseTotal
if (rn->num > SS_MIN) { /* borrow from right */ 3379 1712 5091
1294 3379 ▶ if (cn->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (cn->is_leaf) { 3327 52 3379
1295 3327 cn->scores[cn->num] = rn->scores[0]; cn->members[cn->num] = rn->members[0]; cn->num++;
1296 34314 ▶ for (int i = 0; i+1 < rn->num; i++) { rn->scores[i] = rn->scores[i+1]; rn->members[i] = rn->members[i+1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i+1 < rn->num; i++) { rn->scores[i] = rn->scores[i+1]; rn->members[i] = rn->members[i+1]; } 30987 3327 34314
1297 3327 rn->num--;
1298 3327 p->scores[c] = rn->scores[0]; p->members[c] = rn->members[0];
1299 3327 p->counts[c]++; p->counts[c+1]--;
1300 } else {
1301 52 uint32_t moved = rn->counts[0];
1302 52 cn->scores[cn->num-1] = p->scores[c]; cn->members[cn->num-1] = p->members[c];
1303 52 cn->children[cn->num] = rn->children[0]; cn->counts[cn->num] = moved;
1304 52 ▶ if (ss_node_ok(h, cn->children[cn->num])) h->nodes[cn->children[cn->num]].parent = cidx; /* skip a corrupt borrowed child */
Branch: 1 branch
BranchTrueFalseTotal
if (ss_node_ok(h, cn->children[cn->num])) h->nodes[cn->children[cn->num]].parent = cidx; /* skip a corrupt borrowed child */ 52 0 52
1305 52 cn->num++;
1306 52 p->scores[c] = rn->scores[0]; p->members[c] = rn->members[0];
1307 526 ▶ for (int i = 0; i+1 < rn->num; i++) { rn->children[i] = rn->children[i+1]; rn->counts[i] = rn->counts[i+1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i+1 < rn->num; i++) { rn->children[i] = rn->children[i+1]; rn->counts[i] = rn->counts[i+1]; } 474 52 526
1308 474 ▶ for (int i = 0; i+1 < rn->num-1; i++) { rn->scores[i] = rn->scores[i+1]; rn->members[i] = rn->members[i+1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i+1 < rn->num-1; i++) { rn->scores[i] = rn->scores[i+1]; rn->members[i] = rn->members[i+1]; } 422 52 474
1309 52 rn->num--;
1310 52 p->counts[c] += moved; p->counts[c+1] -= moved;
1311 }
1312 3379 return;
1313 }
1314 }
1315 2334 ▶ ss_merge(h, pidx, (c > 0) ? c - 1 : c); /* merge with a sibling */
Branch: 1 branch
BranchTrueFalseTotal
ss_merge(h, pidx, (c > 0) ? c - 1 : c); /* merge with a sibling */ 1310 1024 2334
1316 }
1317  
1318 /* delete (score,member) from subtree nidx (known present); decrement counts;
1319 return 1 if nidx now underflows (num < SS_MIN) */
1320 204597 static int ss_delete_rec(SsHandle *h, uint32_t nidx, double score, int64_t member) {
1321 204597 SsNode *nd = &h->nodes[nidx];
1322 204597 ▶ if (nd->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (nd->is_leaf) { 68303 136294 204597
1323 68303 int pos = 0;
1324 380161 ▶ while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) != 0) pos++;
Branch: 2 branches
BranchTrueFalseTotal
while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) != 0) pos++; 380161 0 380161
while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) != 0) pos++; 311858 68303 380161
1325 441891 ▶ for (int i = pos; i+1 < nd->num; i++) { nd->scores[i] = nd->scores[i+1]; nd->members[i] = nd->members[i+1]; }
Branch: 1 branch
BranchTrueFalseTotal
for (int i = pos; i+1 < nd->num; i++) { nd->scores[i] = nd->scores[i+1]; nd->members[i] = nd->members[i+1]; } 373588 68303 441891
1326 68303 nd->num--;
1327 68303 return nd->num < SS_MIN;
1328 }
1329 136294 int c = ss_child_index(nd, score, member);
1330 136294 uint32_t cidx = nd->children[c];
1331 136294 ▶ if (!ss_node_ok(h, cidx)) return 0; /* Layer B: corrupt child index -- stop, report no underflow */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, cidx)) return 0; /* Layer B: corrupt child index -- stop, report no underflow */ 0 136294 136294
1332 136294 int under = ss_delete_rec(h, cidx, score, member);
1333 136294 nd->counts[c]--;
1334 136294 ▶ if (under) ss_fix_underflow(h, nidx, c);
Branch: 1 branch
BranchTrueFalseTotal
if (under) ss_fix_underflow(h, nidx, c); 11908 124386 136294
1335 136294 return nd->num < SS_MIN;
1336 }
1337  
1338 68303 static void ss_tree_del(SsHandle *h, double score, int64_t member) {
1339 68303 SsHeader *hdr = h->hdr;
1340 68303 ▶ if (hdr->root == SS_NONE || hdr->root >= h->node_capacity) return; /* Layer B: empty or corrupt root -> no-op */
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->root == SS_NONE || hdr->root >= h->node_capacity) return; /* Layer B: empty or corrupt root -> no-op */ 68303 0 68303
if (hdr->root == SS_NONE || hdr->root >= h->node_capacity) return; /* Layer B: empty or corrupt root -> no-op */ 0 68303 68303
1341 68303 ss_delete_rec(h, hdr->root, score, member);
1342 68303 SsNode *root = &h->nodes[hdr->root];
1343 68303 ▶ if (root->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (root->is_leaf) { 23 68280 68303
1344 23 ▶ if (root->num == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (root->num == 0) { 3 20 23
1345 3 ss_node_free(h, hdr->root);
1346 3 hdr->root = SS_NONE; hdr->leftmost = SS_NONE; hdr->rightmost = SS_NONE; hdr->height = 0;
1347 }
1348 68280 ▶ } else if (root->num == 1) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (root->num == 1) { 1 68279 68280
1349 1 uint32_t child = root->children[0];
1350 1 ss_node_free(h, hdr->root);
1351 1 ▶ if (ss_node_ok(h, child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ss_node_ok(h, child)) { 1 0 1
1352 1 hdr->root = child; h->nodes[child].parent = SS_NONE; hdr->height--;
1353 } else {
1354 /* Layer B: corrupt child index -- drop the tree rather than point
1355 the root outside the node pool */
1356 0 hdr->root = SS_NONE; hdr->leftmost = SS_NONE; hdr->rightmost = SS_NONE; hdr->height = 0;
1357 }
1358 }
1359 68303 hdr->count--;
1360 }
1361  
1362 443568 static inline void ss_wphase(SsHandle *h, uint8_t p) {
1363 443568 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1364 443568 __atomic_store_n(&h->hdr->wphase, p, __ATOMIC_RELAXED);
1365 443568 __atomic_signal_fence(__ATOMIC_SEQ_CST);
1366 443568 }
1367  
1368 /* Give member the score, moving it from old when had. 0 on a corrupt full index. */
1369 112327 static int ss_put_locked(SsHandle *h, int64_t member, int had, double old, double score) {
1370 112327 ss_wphase(h, SS_WP_TREE);
1371 112327 ▶ if (had) ss_tree_del(h, old, member);
Branch: 1 branch
BranchTrueFalseTotal
if (had) ss_tree_del(h, old, member); 32774 79553 112327
1372 112327 ss_tree_add(h, score, member);
1373 112327 ss_wphase(h, SS_WP_INDEX);
1374 112327 int ok = ss_idx_set(h, member, score);
1375 112327 ss_wphase(h, SS_WP_NONE);
1376 112327 return ok;
1377 }
1378  
1379 35529 static void ss_drop_locked(SsHandle *h, int64_t member, double old) {
1380 35529 ss_wphase(h, SS_WP_TREE);
1381 35529 ss_tree_del(h, old, member);
1382 35529 ss_wphase(h, SS_WP_INDEX);
1383 35529 ss_idx_del(h, member);
1384 35529 ss_wphase(h, SS_WP_NONE);
1385 35529 }
1386  
1387 /* add: 1 (new), 0 (existing -- score updated if changed), -1 (full) */
1388 98371 static int ss_add_locked(SsHandle *h, int64_t member, double score) {
1389 double old;
1390 98371 ▶ if (ss_idx_get(h, member, &old)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ss_idx_get(h, member, &old)) { 27138 71233 98371
1391 27138 ▶ if (old != score) {
Branch: 1 branch
BranchTrueFalseTotal
if (old != score) { 26051 1087 27138
1392 /* re-insert: check headroom BEFORE the delete, so a refusal leaves
1393 the set untouched rather than dropping the member */
1394 26051 ▶ if (!ss_add_has_headroom(h)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_add_has_headroom(h)) return -1; 0 26051 26051
1395 26051 ss_put_locked(h, member, 1, old, score);
1396 }
1397 27138 return 0;
1398 }
1399 71233 ▶ if (h->hdr->count >= h->hdr->max_entries) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->count >= h->hdr->max_entries) return -1; 3 71230 71233
1400 71230 ▶ if (!ss_add_has_headroom(h)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_add_has_headroom(h)) return -1; 0 71230 71230
1401 71230 ▶ if (!ss_put_locked(h, member, 0, 0, score)) return -1; /* corrupt full index: fail the add */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_put_locked(h, member, 0, 0, score)) return -1; /* corrupt full index: fail the add */ 0 71230 71230
1402 71230 return 1;
1403 }
1404  
1405 /* remove: 1 if removed, 0 if absent */
1406 23436 static int ss_remove_locked(SsHandle *h, int64_t member) {
1407 double old;
1408 23436 ▶ if (!ss_idx_get(h, member, &old)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_idx_get(h, member, &old)) return 0; 11689 11747 23436
1409 11747 ss_drop_locked(h, member, old);
1410 11747 return 1;
1411 }
1412  
1413 /* incr by delta. *out = new score. returns 1 (created), 0 (updated), -1 (full),
1414 -2 (result is NaN) */
1415 16395 static int ss_incr_locked(SsHandle *h, int64_t member, double delta, double *out) {
1416 double old;
1417 16395 ▶ if (ss_idx_get(h, member, &old)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ss_idx_get(h, member, &old)) { 8072 8323 16395
1418 8072 double ns = old + delta; *out = ns;
1419 8072 ▶ if (ns != ns) return -2;
Branch: 1 branch
BranchTrueFalseTotal
if (ns != ns) return -2; 1 8071 8072
1420 8071 ▶ if (ns != old) {
Branch: 1 branch
BranchTrueFalseTotal
if (ns != old) { 6723 1348 8071
1421 6723 ▶ if (!ss_add_has_headroom(h)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_add_has_headroom(h)) return -1; 0 6723 6723
1422 6723 ss_put_locked(h, member, 1, old, ns);
1423 }
1424 8071 return 0;
1425 }
1426 8323 ▶ if (h->hdr->count >= h->hdr->max_entries) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->count >= h->hdr->max_entries) return -1; 0 8323 8323
1427 8323 *out = delta;
1428 8323 ▶ if (delta != delta) return -2;
Branch: 1 branch
BranchTrueFalseTotal
if (delta != delta) return -2; 0 8323 8323
1429 8323 ▶ if (!ss_add_has_headroom(h)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_add_has_headroom(h)) return -1; 0 8323 8323
1430 8323 ▶ if (!ss_put_locked(h, member, 0, 0, delta)) return -1; /* corrupt full index: fail the incr */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_put_locked(h, member, 0, 0, delta)) return -1; /* corrupt full index: fail the incr */ 0 8323 8323
1431 8323 return 1;
1432 }
1433  
1434 /* pop the min (max=0) or max (max=1): 0 if empty, else 1 with *m,*s */
1435 23784 static int ss_pop_locked(SsHandle *h, int max, int64_t *m, double *s) {
1436 23784 ▶ if (h->hdr->root == SS_NONE) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hdr->root == SS_NONE) return 0; 2 23782 23784
1437 23782 ▶ uint32_t li = max ? h->hdr->rightmost : h->hdr->leftmost;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t li = max ? h->hdr->rightmost : h->hdr->leftmost; 8833 14949 23782
1438 23782 ▶ if (!ss_node_ok(h, li)) return 0; /* corrupt leftmost/rightmost */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, li)) return 0; /* corrupt leftmost/rightmost */ 0 23782 23782
1439 23782 SsNode *nd = &h->nodes[li];
1440 23782 ▶ int pos = max ? nd->num - 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
int pos = max ? nd->num - 1 : 0; 8833 14949 23782
1441 23782 *m = nd->members[pos]; *s = nd->scores[pos];
1442 23782 ss_drop_locked(h, *m, *s);
1443 23782 return 1;
1444 }
1445  
1446 /* ---- structural validator (debug / tests) ---- */
1447 35168 static long ss_check_rec(SsHandle *h, uint32_t nidx, int depth, int is_root,
1448 double *ps, int64_t *pm, int *hp, int *leaf_depth) {
1449 35168 ▶ if (!ss_node_ok(h, nidx)) return -1; /* corrupt child index */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, nidx)) return -1; /* corrupt child index */ 0 35168 35168
1450 35168 SsNode *nd = &h->nodes[nidx];
1451 35168 ▶ if (nd->num < 1 || nd->num > SS_ORDER) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (nd->num < 1 || nd->num > SS_ORDER) return -1; 35168 0 35168
if (nd->num < 1 || nd->num > SS_ORDER) return -1; 0 35168 35168
1452 35168 ▶ if (!is_root && nd->num < SS_MIN) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (!is_root && nd->num < SS_MIN) return -1; 35062 106 35168
if (!is_root && nd->num < SS_MIN) return -1; 0 35062 35062
1453 35168 ▶ if (nd->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (nd->is_leaf) { 31958 3210 35168
1454 31958 ▶ if (*leaf_depth < 0) *leaf_depth = depth;
Branch: 1 branch
BranchTrueFalseTotal
if (*leaf_depth < 0) *leaf_depth = depth; 106 31852 31958
1455 31852 ▶ else if (*leaf_depth != depth) return -1;
Branch: 1 branch
BranchTrueFalseTotal
else if (*leaf_depth != depth) return -1; 0 31852 31852
1456 382954 ▶ for (int i = 0; i < nd->num; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < nd->num; i++) { 350996 31958 382954
1457 350996 ▶ if (*hp && ss_key_cmp(*ps, *pm, nd->scores[i], nd->members[i]) >= 0) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (*hp && ss_key_cmp(*ps, *pm, nd->scores[i], nd->members[i]) >= 0) return -1; 350890 106 350996
if (*hp && ss_key_cmp(*ps, *pm, nd->scores[i], nd->members[i]) >= 0) return -1; 0 350890 350890
1458 350996 *ps = nd->scores[i]; *pm = nd->members[i]; *hp = 1;
1459 }
1460 31958 return nd->num;
1461 }
1462 3210 long total = 0;
1463 38272 ▶ for (int i = 0; i < nd->num; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < nd->num; i++) { 35062 3210 38272
1464 35062 long c = ss_check_rec(h, nd->children[i], depth + 1, 0, ps, pm, hp, leaf_depth);
1465 35062 ▶ if (c < 0 || (uint32_t)c != nd->counts[i]) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (c < 0 || (uint32_t)c != nd->counts[i]) return -1; 35062 0 35062
if (c < 0 || (uint32_t)c != nd->counts[i]) return -1; 0 35062 35062
1466 35062 total += c;
1467 }
1468 3210 return total;
1469 }
1470 107 static int ss_validate_tree(SsHandle *h) {
1471 107 SsHeader *hdr = h->hdr;
1472 107 ▶ if (hdr->root == SS_NONE) return hdr->count == 0 && hdr->leftmost == SS_NONE;
Branch: 3 branches
BranchTrueFalseTotal
if (hdr->root == SS_NONE) return hdr->count == 0 && hdr->leftmost == SS_NONE; 1 106 107
if (hdr->root == SS_NONE) return hdr->count == 0 && hdr->leftmost == SS_NONE; 1 0 1
if (hdr->root == SS_NONE) return hdr->count == 0 && hdr->leftmost == SS_NONE; 1 0 1
1473 106 double ps = 0; int64_t pm = 0; int hp = 0, ld = -1;
1474 106 long total = ss_check_rec(h, hdr->root, 0, 1, &ps, &pm, &hp, &ld);
1475 106 ▶ if (total < 0 || (uint32_t)total != hdr->count) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (total < 0 || (uint32_t)total != hdr->count) return 0; 106 0 106
if (total < 0 || (uint32_t)total != hdr->count) return 0; 0 106 106
1476 /* leaf links == in-order, and reach rightmost */
1477 106 uint32_t leaf = hdr->leftmost; double ls = 0; int64_t lm = 0; int lh = 0; uint32_t seen = 0;
1478 32064 ▶ while (leaf != SS_NONE) {
Branch: 1 branch
BranchTrueFalseTotal
while (leaf != SS_NONE) { 31958 106 32064
1479 31958 ▶ if (!ss_node_ok(h, leaf)) return 0; /* corrupt leaf-link index */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, leaf)) return 0; /* corrupt leaf-link index */ 0 31958 31958
1480 31958 SsNode *nd = &h->nodes[leaf];
1481 31958 ▶ if (!nd->is_leaf) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!nd->is_leaf) return 0; 0 31958 31958
1482 382954 ▶ for (int i = 0; i < nd->num; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < nd->num; i++) { 350996 31958 382954
1483 350996 ▶ if (lh && ss_key_cmp(ls, lm, nd->scores[i], nd->members[i]) >= 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (lh && ss_key_cmp(ls, lm, nd->scores[i], nd->members[i]) >= 0) return 0; 350890 106 350996
if (lh && ss_key_cmp(ls, lm, nd->scores[i], nd->members[i]) >= 0) return 0; 0 350890 350890
1484 350996 ls = nd->scores[i]; lm = nd->members[i]; lh = 1; seen++;
1485 }
1486 31958 ▶ if (nd->next == SS_NONE && leaf != hdr->rightmost) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (nd->next == SS_NONE && leaf != hdr->rightmost) return 0; 106 31852 31958
if (nd->next == SS_NONE && leaf != hdr->rightmost) return 0; 0 106 106
1487 31958 leaf = nd->next;
1488 }
1489 106 ▶ if (seen != hdr->count) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (seen != hdr->count) return 0; 0 106 106
1490 /* index population == count */
1491 106 uint32_t icount = 0;
1492 2804354 ▶ for (uint32_t i = 0; i < h->index_slots; i++) if (h->index[i].state) icount++; /* cached geometry */
Branch: 2 branches
BranchTrueFalseTotal
for (uint32_t i = 0; i < h->index_slots; i++) if (h->index[i].state) icount++; /* cached geometry */ 350996 2453252 2804248
for (uint32_t i = 0; i < h->index_slots; i++) if (h->index[i].state) icount++; /* cached geometry */ 2804248 106 2804354
1493 106 return icount == hdr->count;
1494 }
1495  
1496 /* ---- stale-lock repair ---- */
1497 typedef struct { uint32_t prev_leaf, leaf_depth; } SsRebuild;
1498  
1499 0 static uint32_t ss_rebuild_rec(SsHandle *h, SsRebuild *rb, uint32_t nidx, uint32_t parent, uint32_t depth) {
1500 0 SsNode *nd = &h->nodes[nidx];
1501 0 nd->parent = parent;
1502 0 ▶ if (nd->num > SS_ORDER) nd->num = SS_ORDER; /* killed mid-split: keep later inserts in bounds */
Branch: 1 branch
BranchTrueFalseTotal
if (nd->num > SS_ORDER) nd->num = SS_ORDER; /* killed mid-split: keep later inserts in bounds */ 0 0 0
1503 0 ▶ if (depth >= 64) { nd->is_leaf = 1; nd->num = 0; } /* only a corrupt file nests this deep */
Branch: 1 branch
BranchTrueFalseTotal
if (depth >= 64) { nd->is_leaf = 1; nd->num = 0; } /* only a corrupt file nests this deep */ 0 0 0
1504 0 int k = 0;
1505 0 ▶ if (nd->is_leaf) {
Branch: 1 branch
BranchTrueFalseTotal
if (nd->is_leaf) { 0 0 0
1506 0 ▶ for (int i = 0; i < nd->num; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < nd->num; i++) { 0 0 0
1507 int f;
1508 0 ss_idx_find(h, nd->members[i], &f);
1509 0 ▶ if (f || !ss_idx_set(h, nd->members[i], nd->scores[i])) continue; /* a torn shift's duplicate */
Branch: 2 branches
BranchTrueFalseTotal
if (f || !ss_idx_set(h, nd->members[i], nd->scores[i])) continue; /* a torn shift's duplicate */ 0 0 0
if (f || !ss_idx_set(h, nd->members[i], nd->scores[i])) continue; /* a torn shift's duplicate */ 0 0 0
1510 0 nd->scores[k] = nd->scores[i]; nd->members[k] = nd->members[i]; k++;
1511 }
1512 0 nd->num = (uint16_t)k;
1513 0 ▶ if (k) {
Branch: 1 branch
BranchTrueFalseTotal
if (k) { 0 0 0
1514 0 ▶ if (rb->leaf_depth == UINT32_MAX) rb->leaf_depth = depth;
Branch: 1 branch
BranchTrueFalseTotal
if (rb->leaf_depth == UINT32_MAX) rb->leaf_depth = depth; 0 0 0
1515 0 nd->prev = rb->prev_leaf;
1516 0 nd->next = SS_NONE;
1517 0 ▶ if (rb->prev_leaf == SS_NONE) h->hdr->leftmost = nidx;
Branch: 1 branch
BranchTrueFalseTotal
if (rb->prev_leaf == SS_NONE) h->hdr->leftmost = nidx; 0 0 0
1518 0 else h->nodes[rb->prev_leaf].next = nidx;
1519 0 rb->prev_leaf = nidx;
1520 }
1521 0 return (uint32_t)k;
1522 }
1523 0 uint32_t total = 0;
1524 0 ▶ for (int i = 0; i < nd->num; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < nd->num; i++) { 0 0 0
1525 0 uint32_t c = nd->children[i];
1526 0 ▶ if (!ss_node_ok(h, c) || h->nodes[c].mark) continue; /* a corrupt or duplicate child link */
Branch: 2 branches
BranchTrueFalseTotal
if (!ss_node_ok(h, c) || h->nodes[c].mark) continue; /* a corrupt or duplicate child link */ 0 0 0
if (!ss_node_ok(h, c) || h->nodes[c].mark) continue; /* a corrupt or duplicate child link */ 0 0 0
1527 0 h->nodes[c].mark = 1;
1528 0 uint32_t t = ss_rebuild_rec(h, rb, c, nidx, depth + 1);
1529 0 ▶ if (!t) { h->nodes[c].mark = 0; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (!t) { h->nodes[c].mark = 0; continue; } 0 0 0
1530 0 ▶ if (k > 0 && k != i) { nd->scores[k-1] = nd->scores[i-1]; nd->members[k-1] = nd->members[i-1]; }
Branch: 2 branches
BranchTrueFalseTotal
if (k > 0 && k != i) { nd->scores[k-1] = nd->scores[i-1]; nd->members[k-1] = nd->members[i-1]; } 0 0 0
if (k > 0 && k != i) { nd->scores[k-1] = nd->scores[i-1]; nd->members[k-1] = nd->members[i-1]; } 0 0 0
1531 0 nd->children[k] = c;
1532 0 nd->counts[k++] = t;
1533 0 total += t;
1534 }
1535 0 nd->num = (uint16_t)k;
1536 0 return total;
1537 }
1538  
1539 /* From what the root reaches, re-derive the subtree counts, parent and leaf
1540 * links, leftmost/rightmost, height, count, the free list and the member index.
1541 * A node left mid-shift or mid-split is only bounded (duplicates and empty
1542 * nodes dropped), not repaired. Idempotent. */
1543 0 static void ss_rebuild_from_tree(SsHandle *h) {
1544 0 SsHeader *hdr = h->hdr;
1545 0 uint32_t cap = h->node_capacity, root = hdr->root;
1546 0 SsRebuild rb = { SS_NONE, UINT32_MAX };
1547 0 ▶ if (root == SS_NONE || !ss_node_ok(h, root)) { ss_clear_locked(h); return; }
Branch: 2 branches
BranchTrueFalseTotal
if (root == SS_NONE || !ss_node_ok(h, root)) { ss_clear_locked(h); return; } 0 0 0
if (root == SS_NONE || !ss_node_ok(h, root)) { ss_clear_locked(h); return; } 0 0 0
1548 0 ▶ for (uint32_t i = 0; i < cap; i++) h->nodes[i].mark = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < cap; i++) h->nodes[i].mark = 0; 0 0 0
1549 0 memset(h->index, 0, (size_t)h->index_slots * sizeof(SsIdxSlot));
1550 0 h->nodes[root].mark = 1;
1551 0 hdr->leftmost = SS_NONE;
1552 0 uint32_t n = ss_rebuild_rec(h, &rb, root, SS_NONE, 0);
1553 0 ▶ if (n == 0) { ss_clear_locked(h); return; }
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { ss_clear_locked(h); return; } 0 0 0
1554 0 hdr->rightmost = rb.prev_leaf;
1555 0 hdr->height = rb.leaf_depth + 1;
1556 0 hdr->count = n;
1557 0 uint32_t head = SS_NONE;
1558 0 ▶ for (uint32_t i = cap; i-- > 0; )
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = cap; i-- > 0; ) 0 0 0
1559 0 ▶ if (h->nodes[i].mark) h->nodes[i].mark = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (h->nodes[i].mark) h->nodes[i].mark = 0; 0 0 0
1560 0 else { h->nodes[i].parent = head; head = i; }
1561 0 hdr->node_free_head = head;
1562 }
1563  
1564 /* Repair what a dead writer left half done. Mid-tree, the index still holds
1565 * the set from before the write: replant the tree from it, undoing the write.
1566 * Otherwise the tree is whole and the index is rebuilt from it; the tree check
1567 * also bounds a file whose writer predates wphase. */
1568 0 static void ss_rebuild_locked(SsHandle *h) {
1569 0 SsHeader *hdr = h->hdr;
1570 0 ▶ if (hdr->wphase == SS_WP_TREE) {
Branch: 1 branch
BranchTrueFalseTotal
if (hdr->wphase == SS_WP_TREE) { 0 0 0
1571 0 ss_clear_tree(h);
1572 0 ▶ for (uint32_t i = 0; i < h->index_slots; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < h->index_slots; i++) { 0 0 0
1573 0 SsIdxSlot *s = &h->index[i];
1574 0 ▶ if (!s->state) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!s->state) continue; 0 0 0
1575 0 ▶ if (hdr->count >= hdr->max_entries || !ss_add_has_headroom(h)) break; /* corrupt index */
Branch: 2 branches
BranchTrueFalseTotal
if (hdr->count >= hdr->max_entries || !ss_add_has_headroom(h)) break; /* corrupt index */ 0 0 0
if (hdr->count >= hdr->max_entries || !ss_add_has_headroom(h)) break; /* corrupt index */ 0 0 0
1576 0 ss_tree_add(h, s->score, s->member);
1577 }
1578 0 ss_wphase(h, SS_WP_INDEX);
1579 }
1580 0 ss_rebuild_from_tree(h);
1581 0 ss_wphase(h, SS_WP_NONE);
1582 0 }
1583  
1584 /* ---- order-statistics queries (read paths; caller holds the read lock) ---- */
1585  
1586 /* number of entries strictly less than (score, member) -- the rank of the key */
1587 10354 static uint32_t ss_rank_of(SsHandle *h, double score, int64_t member) {
1588 10354 uint32_t n = h->hdr->root, rank = 0;
1589 39431 ▶ while (ss_node_ok(h, n) && !h->nodes[n].is_leaf) {
Branch: 2 branches
BranchTrueFalseTotal
while (ss_node_ok(h, n) && !h->nodes[n].is_leaf) { 39431 0 39431
while (ss_node_ok(h, n) && !h->nodes[n].is_leaf) { 29077 10354 39431
1590 29077 SsNode *nd = &h->nodes[n];
1591 29077 int c = ss_child_index(nd, score, member);
1592 165486 ▶ for (int i = 0; i < c; i++) rank += nd->counts[i];
Branch: 1 branch
BranchTrueFalseTotal
for (int i = 0; i < c; i++) rank += nd->counts[i]; 136409 29077 165486
1593 29077 n = nd->children[c];
1594 }
1595 10354 ▶ if (!ss_node_ok(h, n)) return rank; /* corrupt child index: stop */
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_node_ok(h, n)) return rank; /* corrupt child index: stop */ 0 10354 10354
1596 10354 SsNode *nd = &h->nodes[n];
1597 10354 int pos = 0;
1598 64231 ▶ while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) < 0) pos++;
Branch: 2 branches
BranchTrueFalseTotal
while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) < 0) pos++; 64201 30 64231
while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) < 0) pos++; 53877 10324 64201
1599 10354 return rank + (uint32_t)pos;
1600 }
1601  
1602 /* entry at 0-based rank r (r < count); returns leaf idx and sets *pos */
1603 394 static uint32_t ss_at_rank(SsHandle *h, uint32_t r, int *pos) {
1604 394 uint32_t n = h->hdr->root;
1605 1497 ▶ while (ss_node_ok(h, n) && !h->nodes[n].is_leaf) {
Branch: 2 branches
BranchTrueFalseTotal
while (ss_node_ok(h, n) && !h->nodes[n].is_leaf) { 1497 0 1497
while (ss_node_ok(h, n) && !h->nodes[n].is_leaf) { 1103 394 1497
1606 1103 SsNode *nd = &h->nodes[n];
1607 1103 int c = 0;
1608 3490 ▶ while (c < nd->num && r >= nd->counts[c]) { r -= nd->counts[c]; c++; }
Branch: 2 branches
BranchTrueFalseTotal
while (c < nd->num && r >= nd->counts[c]) { r -= nd->counts[c]; c++; } 3490 0 3490
while (c < nd->num && r >= nd->counts[c]) { r -= nd->counts[c]; c++; } 2387 1103 3490
1609 1103 n = nd->children[c];
1610 }
1611 394 *pos = (int)r;
1612 394 ▶ return ss_node_ok(h, n) ? n : SS_NONE; /* corrupt child index -> SS_NONE */
Branch: 1 branch
BranchTrueFalseTotal
return ss_node_ok(h, n) ? n : SS_NONE; /* corrupt child index -> SS_NONE */ 394 0 394
1613 }
1614  
1615 /* number of entries with score in [min, max] (inclusive). *lo_out (optional, may
1616 be NULL) receives #{score < min} -- the rank of the first in-range entry -- so
1617 range_by_score can reuse it instead of recomputing ss_rank_of(min, ...). */
1618 109 static uint32_t ss_count_in_score(SsHandle *h, double min, double max, uint32_t *lo_out) {
1619 109 ▶ if (h->hdr->root == SS_NONE || !(min <= max)) { if (lo_out) *lo_out = 0; return 0; }
Branch: 3 branches
BranchTrueFalseTotal
if (h->hdr->root == SS_NONE || !(min <= max)) { if (lo_out) *lo_out = 0; return 0; } 108 1 109
if (h->hdr->root == SS_NONE || !(min <= max)) { if (lo_out) *lo_out = 0; return 0; } 0 108 108
if (h->hdr->root == SS_NONE || !(min <= max)) { if (lo_out) *lo_out = 0; return 0; } 0 1 1
1620 108 uint32_t lo = ss_rank_of(h, min, INT64_MIN); /* #{score < min} */
1621 108 ▶ if (lo_out) *lo_out = lo;
Branch: 1 branch
BranchTrueFalseTotal
if (lo_out) *lo_out = lo; 67 41 108
1622 108 uint32_t hi = ss_rank_of(h, max, INT64_MAX); /* #{key < (max, INT64_MAX)} */
1623 double sc;
1624 108 ▶ if (ss_idx_get(h, INT64_MAX, &sc) && sc == max) hi++; /* + the (max, INT64_MAX) entry itself */
Branch: 2 branches
BranchTrueFalseTotal
if (ss_idx_get(h, INT64_MAX, &sc) && sc == max) hi++; /* + the (max, INT64_MAX) entry itself */ 4 104 108
if (ss_idx_get(h, INT64_MAX, &sc) && sc == max) hi++; /* + the (max, INT64_MAX) entry itself */ 2 2 4
1625 108 return hi - lo;
1626 }
1627  
1628 /* result collector: parallel member/score arrays */
1629 typedef struct { int64_t *members; double *scores; size_t n, cap; } ss_rcollect_t;
1630 99838 static int ss_rcollect_push(ss_rcollect_t *c, int64_t m, double s) {
1631 99838 ▶ if (c->n == c->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (c->n == c->cap) { 350 99488 99838
1632 350 ▶ size_t nc = c->cap ? c->cap * 2 : 64;
Branch: 1 branch
BranchTrueFalseTotal
size_t nc = c->cap ? c->cap * 2 : 64; 263 87 350
1633 350 int64_t *nm = (int64_t *)realloc(c->members, nc * sizeof(int64_t));
1634 350 ▶ if (!nm) return 0; c->members = nm;
Branch: 1 branch
BranchTrueFalseTotal
if (!nm) return 0; c->members = nm; 0 350 350
1635 350 double *ns = (double *)realloc(c->scores, nc * sizeof(double));
1636 350 ▶ if (!ns) return 0; c->scores = ns;
Branch: 1 branch
BranchTrueFalseTotal
if (!ns) return 0; c->scores = ns; 0 350 350
1637 350 c->cap = nc;
1638 }
1639 99838 c->members[c->n] = m; c->scores[c->n] = s; c->n++;
1640 99838 return 1;
1641 }
1642  
1643 /* collect `len` entries starting at rank `start` (in order, or reversed). The
1644 caller has clamped [start, start+len) within [0, count]. Returns 0 on OOM. */
1645 93 static int ss_collect_range(SsHandle *h, uint32_t start, uint32_t len, int reverse, ss_rcollect_t *c) {
1646 93 ▶ if (len == 0 || h->hdr->root == SS_NONE) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (len == 0 || h->hdr->root == SS_NONE) return 1; 87 6 93
if (len == 0 || h->hdr->root == SS_NONE) return 1; 0 87 87
1647 int pos;
1648 87 ▶ uint32_t leaf = ss_at_rank(h, reverse ? (start + len - 1) : start, &pos);
Branch: 1 branch
BranchTrueFalseTotal
uint32_t leaf = ss_at_rank(h, reverse ? (start + len - 1) : start, &pos); 28 59 87
1649 87 uint32_t got = 0;
1650 87 ▶ if (!reverse) {
Branch: 1 branch
BranchTrueFalseTotal
if (!reverse) { 59 28 87
1651 6109 ▶ while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) {
Branch: 3 branches
BranchTrueFalseTotal
while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) { 6078 31 6109
while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) { 6078 0 6078
while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) { 6050 28 6078
1652 6050 SsNode *nd = &h->nodes[leaf];
1653 70541 ▶ for (; pos < nd->num && got < len; pos++, got++)
Branch: 2 branches
BranchTrueFalseTotal
for (; pos < nd->num && got < len; pos++, got++) 64526 6015 70541
for (; pos < nd->num && got < len; pos++, got++) 64491 35 64526
1654 64491 ▶ if (!ss_rcollect_push(c, nd->members[pos], nd->scores[pos])) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_rcollect_push(c, nd->members[pos], nd->scores[pos])) return 0; 0 64491 64491
1655 6050 leaf = nd->next; pos = 0;
1656 }
1657 } else {
1658 3320 ▶ while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) {
Branch: 3 branches
BranchTrueFalseTotal
while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) { 3314 6 3320
while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) { 3314 0 3314
while (leaf != SS_NONE && ss_node_ok(h, leaf) && got < len) { 3292 22 3314
1659 3292 SsNode *nd = &h->nodes[leaf];
1660 38639 ▶ for (; pos >= 0 && got < len; pos--, got++)
Branch: 2 branches
BranchTrueFalseTotal
for (; pos >= 0 && got < len; pos--, got++) 35370 3269 38639
for (; pos >= 0 && got < len; pos--, got++) 35347 23 35370
1661 35347 ▶ if (!ss_rcollect_push(c, nd->members[pos], nd->scores[pos])) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ss_rcollect_push(c, nd->members[pos], nd->scores[pos])) return 0; 0 35347 35347
1662 3292 leaf = nd->prev;
1663 3292 ▶ if (leaf != SS_NONE && ss_node_ok(h, leaf)) pos = h->nodes[leaf].num - 1;
Branch: 2 branches
BranchTrueFalseTotal
if (leaf != SS_NONE && ss_node_ok(h, leaf)) pos = h->nodes[leaf].num - 1; 3286 6 3292
if (leaf != SS_NONE && ss_node_ok(h, leaf)) pos = h->nodes[leaf].num - 1; 3286 0 3286
1664 }
1665 }
1666 87 return 1;
1667 }
1668  
1669 #endif /* SORTEDSET_H */
1670  
« blib/lib/Data/SortedSet/Shared.pm ↑ Summary Shared.xs »