GCC Code Coverage Report


Directory: src/
File: src/algo/topk.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 299 305 98.0%
Functions: 23 23 100.0%
Branches: 164 181 90.6%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * topk.c - Top-K collection
6 *
7 * Threshold heap: max-heap of K Distance values (upper bounds).
8 * Candidate buffer: growable array of all entries that passed
9 * the threshold check.
10 * Id map: heap position of each id, for vs_topk_insert's dedup lookup.
11 *
12 * Used by both standalone and PG builds.
13 */
14
15 #include <stdlib.h>
16 #include <string.h>
17
18 #include "algo/topk.h"
19 #include "core/idset.h"
20 #include "core/memory.h"
21 #include "core/platform.h"
22
23 #define VS_TOPK_INITIAL_CAP_MIN 32
24
25 /* ----------------------------------------------------------------
26 * Id -> heap position map
27 *
28 * Linear probing over a power-of-two slot array sized for at most half
29 * load at k_capacity. Deletion shifts later entries back into the hole
30 * rather than leaving tombstones, so probe chains stay short however
31 * many evictions a scan makes.
32 * ---------------------------------------------------------------- */
33
34 #define VS_TOPK_MAP_EMPTY UINT32_MAX
35
36 static inline uint32_t
37 961724 map_home(const VsTopK *topk, uint64_t id)
38 {
39 961724 return (uint32_t)((id * VS_HASH_GOLDEN_GAMMA) >> topk->map_shift);
40 }
41
42 /* Slot holding `id`, or VS_TOPK_MAP_EMPTY if it is not in the heap. */
43 static inline uint32_t
44 821419 map_find(const VsTopK *topk, uint64_t id)
45 {
46 821419 uint32_t slot = map_home(topk, id);
47
2/2
✓ Branch 0 taken 366346 times.
✓ Branch 1 taken 815549 times.
1181895 while (topk->map_pos[slot] != VS_TOPK_MAP_EMPTY)
48 {
49
2/2
✓ Branch 0 taken 16108 times.
✓ Branch 1 taken 350238 times.
366346 if (topk->map_ids[slot] == id)
50 5394 return slot;
51 360476 slot = (slot + 1) & topk->map_mask;
52 }
53 782201 return VS_TOPK_MAP_EMPTY;
54 }
55
56 /* Record that heap position `pos` holds `id` (absent from the map). */
57 static inline void
58 124190 map_add(VsTopK *topk, uint64_t id, uint32_t pos)
59 {
60 124190 uint32_t slot = map_home(topk, id);
61
2/2
✓ Branch 0 taken 18201 times.
✓ Branch 1 taken 124190 times.
142391 while (topk->map_pos[slot] != VS_TOPK_MAP_EMPTY)
62 18201 slot = (slot + 1) & topk->map_mask;
63 124190 topk->map_ids[slot] = id;
64 124190 topk->map_pos[slot] = pos;
65 124190 topk->ub_slot[pos] = slot;
66 124190 }
67
68 static void
69 59340 map_remove(VsTopK *topk, uint32_t slot)
70 {
71 59340 uint32_t mask = topk->map_mask;
72 59340 uint32_t hole = slot;
73
74
2/2
✓ Branch 0 taken 16115 times.
✓ Branch 1 taken 59340 times.
75455 for (uint32_t j = (hole + 1) & mask; topk->map_pos[j] != VS_TOPK_MAP_EMPTY;
75 16115 j = (j + 1) & mask)
76 {
77 /* Move j into the hole unless that would put it before its
78 * home slot, where lookups would no longer reach it. */
79 16115 uint32_t home = map_home(topk, topk->map_ids[j]);
80
2/2
✓ Branch 0 taken 4181 times.
✓ Branch 1 taken 11934 times.
16115 if (((j - home) & mask) >= ((j - hole) & mask))
81 {
82 4181 topk->map_ids[hole] = topk->map_ids[j];
83 4181 topk->map_pos[hole] = topk->map_pos[j];
84 4181 topk->ub_slot[topk->map_pos[hole]] = hole;
85 4181 hole = j;
86 }
87 }
88 59340 topk->map_pos[hole] = VS_TOPK_MAP_EMPTY;
89 59340 }
90
91 /* Allocate the map on the first deduping insert, indexing whatever
92 * unique inserts already put in the heap. */
93 static void
94 798 map_build(VsTopK *topk)
95 {
96 798 uint32_t bits = 1;
97
2/2
✓ Branch 0 taken 3683 times.
✓ Branch 1 taken 798 times.
4481 while ((1ull << bits) < 2ull * topk->k_capacity)
98 3683 bits++;
99
100 798 uint32_t nslots = 1u << bits;
101 798 topk->map_ids = vs_memctx_alloc(topk->memctx, nslots * sizeof(uint64_t));
102 798 topk->map_pos = vs_memctx_alloc(topk->memctx, nslots * sizeof(uint32_t));
103 1146 topk->ub_slot =
104 798 vs_memctx_alloc(topk->memctx, topk->k_capacity * sizeof(uint32_t));
105 798 topk->map_mask = nslots - 1;
106 798 topk->map_shift = 64 - bits;
107
108 798 memset(topk->map_pos, 0xFF, nslots * sizeof(uint32_t));
109
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 798 times.
862 for (uint32_t i = 0; i < topk->ub_count; i++)
110 64 map_add(topk, topk->ub_ids[i], i);
111 798 }
112
113 /* ----------------------------------------------------------------
114 * Threshold heap (max-heap of Distance values)
115 *
116 * The sifts take the heap's arrays as locals, so stores through them
117 * don't force reloads of the pointers from VsTopK. With `track`, every
118 * move also updates the id map.
119 * ---------------------------------------------------------------- */
120
121 typedef struct HeapArrays
122 {
123 Distance *ub;
124 uint64_t *ids;
125 uint32_t *slot; /* ub_slot, used only when tracking */
126 uint32_t *pos; /* map_pos, used only when tracking */
127 } HeapArrays;
128
129 static inline HeapArrays
130 28063450 heap_arrays(const VsTopK *topk)
131 {
132 33957114 return (HeapArrays){
133 28063450 .ub = topk->ub_heap,
134 28063450 .ids = topk->ub_ids,
135 28063450 .slot = topk->ub_slot,
136 28063450 .pos = topk->map_pos,
137 };
138 }
139
140 static inline void
141 55020951 ub_swap(HeapArrays h, uint32_t a, uint32_t b, bool track)
142 {
143 55020951 Distance tmp = h.ub[a];
144 55020951 h.ub[a] = h.ub[b];
145 55020951 h.ub[b] = tmp;
146 55020951 uint64_t tid = h.ids[a];
147 55020951 h.ids[a] = h.ids[b];
148 55020951 h.ids[b] = tid;
149
150
2/2
✓ Branch 0 taken 170130 times.
✓ Branch 1 taken 54850821 times.
55020951 if (track)
151 {
152 170130 uint32_t sa = h.slot[a];
153 170130 uint32_t sb = h.slot[b];
154 170130 h.slot[a] = sb;
155 170130 h.slot[b] = sa;
156 170130 h.pos[sb] = a;
157 170130 h.pos[sa] = b;
158 }
159 55020951 }
160
161 static inline void
162 15805200 ub_sift_up(HeapArrays h, uint32_t i, bool track)
163 {
164
2/2
✓ Branch 0 taken 29348477 times.
✓ Branch 1 taken 3089077 times.
32437554 while (i > 0)
165 {
166 29348477 uint32_t parent = (i - 1) / 2;
167
2/2
✓ Branch 0 taken 16036767 times.
✓ Branch 1 taken 13311710 times.
29348477 if (h.ub[i] <= h.ub[parent])
168 2350194 break;
169 16632354 ub_swap(h, i, parent, track);
170 16632354 i = parent;
171 }
172 15805200 }
173
174 static inline void
175 12258250 ub_sift_down(HeapArrays h, uint32_t count, uint32_t i, bool track)
176 {
177 68148974 for (;;)
178 38388597 {
179 50646847 uint32_t left = 2 * i + 1;
180 50646847 uint32_t right = 2 * i + 2;
181 50646847 uint32_t largest = i;
182
183
4/4
✓ Branch 0 taken 15448469 times.
✓ Branch 1 taken 35198378 times.
✓ Branch 2 taken 15241629 times.
✓ Branch 3 taken 28934491 times.
50646847 if (left < count && h.ub[left] > h.ub[largest])
184 46920091 largest = left;
185
4/4
✓ Branch 0 taken 15825669 times.
✓ Branch 1 taken 34821178 times.
✓ Branch 2 taken 22677291 times.
✓ Branch 3 taken 20787847 times.
50646847 if (right < count && h.ub[right] > h.ub[largest])
186 43226865 largest = right;
187
188
2/2
✓ Branch 0 taken 32236289 times.
✓ Branch 1 taken 18410558 times.
50646847 if (largest == i)
189 2860618 break;
190
191 38388597 ub_swap(h, i, largest, track);
192 38388597 i = largest;
193 }
194 12258250 }
195
196 /* Add an id that isn't in the heap. It is appended while the heap holds
197 * fewer than k entries and otherwise replaces the root if ub beats it. */
198 __attribute__((always_inline)) static inline void
199 22184574 ub_insert(VsTopK *topk, Distance ub, uint64_t id, bool track)
200 {
201
6/6
✓ Branch 0 taken 53188 times.
✓ Branch 1 taken 729013 times.
✓ Branch 2 taken 2979770 times.
✓ Branch 3 taken 2806946 times.
✓ Branch 4 taken 88 times.
✓ Branch 5 taken 340 times.
28753919 if (topk->ub_count < topk->k)
202 {
203 15805200 uint32_t i = topk->ub_count++;
204 15805200 topk->ub_heap[i] = ub;
205 15805200 topk->ub_ids[i] = id;
206
3/6
✓ Branch 0 taken 53188 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2979770 times.
✓ Branch 4 taken 88 times.
✗ Branch 5 not taken.
15805200 if (track)
207 64786 map_add(topk, id, i);
208 15805200 ub_sift_up(heap_arrays(topk), i, track);
209 }
210
5/6
✓ Branch 0 taken 59182 times.
✓ Branch 1 taken 691669 times.
✓ Branch 2 taken 12197528 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 158 times.
✓ Branch 5 taken 182 times.
12948719 else if (ub < topk->ub_heap[0])
211 {
212
3/6
✓ Branch 0 taken 52240 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2806946 times.
✓ Branch 4 taken 158 times.
✗ Branch 5 not taken.
12256868 if (track)
213 59340 map_remove(topk, topk->ub_slot[0]);
214 12256868 topk->ub_heap[0] = ub;
215 12256868 topk->ub_ids[0] = id;
216
3/6
✓ Branch 0 taken 52240 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2806946 times.
✓ Branch 4 taken 158 times.
✗ Branch 5 not taken.
12256868 if (track)
217 59340 map_add(topk, id, 0);
218 12256868 ub_sift_down(heap_arrays(topk), topk->ub_count, 0, track);
219 }
220 6569345 }
221
222 /* ----------------------------------------------------------------
223 * Comparator for qsort (ascending by distance)
224 * ---------------------------------------------------------------- */
225
226 static int
227 69206673 cmp_by_distance(const void *a, const void *b)
228 {
229 69206673 const VsTopKEntry *ea = (const VsTopKEntry *)a;
230 69206673 const VsTopKEntry *eb = (const VsTopKEntry *)b;
231
2/2
✓ Branch 0 taken 36056865 times.
✓ Branch 1 taken 33149808 times.
69206673 if (ea->distance < eb->distance)
232 5568603 return -1;
233
2/2
✓ Branch 0 taken 35878627 times.
✓ Branch 1 taken 86418 times.
35965045 if (ea->distance > eb->distance)
234 35878627 return 1;
235 84571 return 0;
236 }
237
238 /* ----------------------------------------------------------------
239 * Init / cleanup / create / destroy
240 * ---------------------------------------------------------------- */
241
242 void
243 42506 vs_topk_init(VsTopK *topk, uint32_t k)
244 {
245 42506 topk->memctx = vs_memctx_create(NULL, "topk");
246 42506 topk->k = k;
247 42506 topk->k_capacity = k;
248 42506 topk->ub_heap = vs_memctx_alloc(topk->memctx, k * sizeof(Distance));
249 42506 topk->ub_ids = vs_memctx_alloc(topk->memctx, k * sizeof(uint64_t));
250 42506 topk->ub_count = 0;
251
252 42506 uint32_t cap = k * 2;
253
2/2
✓ Branch 0 taken 474 times.
✓ Branch 1 taken 466 times.
42506 if (cap < VS_TOPK_INITIAL_CAP_MIN)
254 474 cap = VS_TOPK_INITIAL_CAP_MIN;
255 84072 topk->candidates =
256 42506 vs_memctx_alloc(topk->memctx, cap * sizeof(VsTopKEntry));
257 42506 topk->cand_count = 0;
258 42506 topk->cand_capacity = cap;
259 /* Stamped onto every insert; only the query scan ever sets it. */
260 42506 topk->cur_src = 0;
261
262 42506 topk->map_ids = NULL;
263 42506 topk->map_pos = NULL;
264 42506 topk->ub_slot = NULL;
265 42506 topk->map_mask = 0;
266 42506 topk->map_shift = 0;
267 42506 }
268
269 void
270 42502 vs_topk_cleanup(VsTopK *topk)
271 {
272
2/2
✓ Branch 0 taken 41562 times.
✓ Branch 1 taken 940 times.
42502 if (topk == NULL)
273 ✗ return;
274
1/2
✓ Branch 0 taken 42502 times.
✗ Branch 1 not taken.
42502 if (topk->memctx != NULL)
275 {
276 42502 vs_memctx_delete(topk->memctx);
277 42502 topk->memctx = NULL;
278 }
279 42502 topk->ub_heap = NULL;
280 42502 topk->ub_ids = NULL;
281 42502 topk->candidates = NULL;
282 42502 topk->map_ids = NULL;
283 42502 topk->map_pos = NULL;
284 42502 topk->ub_slot = NULL;
285 }
286
287 VsTopK *
288 6 vs_topk_create(uint32_t k)
289 {
290 /* The handle comes from the caller's context rather than from the arena
291 * it owns. vs_topk_reset_to_k resets that arena when k outgrows it,
292 * which would reclaim the object being reset through. */
293 6 VsTopK *topk = vs_alloc(sizeof(VsTopK));
294 6 vs_topk_init(topk, k);
295 6 return topk;
296 }
297
298 void
299 6 vs_topk_destroy(VsTopK *topk)
300 {
301
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
6 if (topk == NULL)
302 ✗ return;
303 6 vs_topk_cleanup(topk);
304 6 vs_free(topk);
305 }
306
307 void
308 4 vs_topk_reset(VsTopK *topk)
309 {
310 4 vs_topk_reset_to_k(topk, topk->k);
311 4 }
312
313 void
314 938572 vs_topk_reset_to_k(VsTopK *topk, uint32_t k)
315 {
316 /* O(1) reset: buffers are retained across resets (grow-only), so a
317 * reused top-K reaches a steady state with zero allocator traffic.
318 * Only a k above the allocated capacity re-allocates — reset the
319 * arena first so the outgrown blocks are reclaimed rather than
320 * leaked into the context. The candidate buffer keeps its
321 * high-water capacity, avoiding the doubling-regrowth copies that
322 * a fresh buffer paid on every use. */
323
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 938554 times.
938572 if (vs_unlikely(k > topk->k_capacity))
324 {
325 18 uint32_t cand_cap = topk->cand_capacity;
326 18 uint32_t min_cap = k * 2;
327
328
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 14 times.
18 if (cand_cap < min_cap)
329 4 cand_cap = min_cap;
330
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
18 if (cand_cap < VS_TOPK_INITIAL_CAP_MIN)
331 ✗ cand_cap = VS_TOPK_INITIAL_CAP_MIN;
332
333 18 vs_memctx_reset(topk->memctx);
334 18 topk->ub_heap = vs_memctx_alloc(topk->memctx, k * sizeof(Distance));
335 18 topk->ub_ids = vs_memctx_alloc(topk->memctx, k * sizeof(uint64_t));
336 18 topk->candidates =
337 18 vs_memctx_alloc(topk->memctx, cand_cap * sizeof(VsTopKEntry));
338 18 topk->cand_capacity = cand_cap;
339 18 topk->k_capacity = k;
340 18 topk->map_ids = NULL;
341 18 topk->map_pos = NULL;
342 18 topk->ub_slot = NULL;
343 }
344
2/2
✓ Branch 0 taken 8709 times.
✓ Branch 1 taken 929845 times.
938554 else if (topk->map_pos != NULL)
345 {
346 /* Clear only the occupied slots. */
347
2/2
✓ Branch 0 taken 16012 times.
✓ Branch 1 taken 8709 times.
24721 for (uint32_t i = 0; i < topk->ub_count; i++)
348 16012 topk->map_pos[topk->ub_slot[i]] = VS_TOPK_MAP_EMPTY;
349 }
350
351 938572 topk->k = k;
352 938572 topk->ub_count = 0;
353 938572 topk->cand_count = 0;
354 938572 }
355
356 void
357 54476234 vs_topk_insert_unique(
358 VsTopK *topk, Distance distance, Distance error, uint64_t id)
359 {
360 54476234 Distance lb = distance - error;
361 54476234 Distance ub = distance + error;
362
363 /* Prune: lower bound exceeds threshold. Written NaN-safe: a NaN
364 * estimate (e.g. a zero vector normalized for cosine) fails every
365 * comparison, so the naive lb >= threshold guard would admit it --
366 * and one NaN upper bound in the heap corrupts the threshold for
367 * the rest of the scan. */
368
4/4
✓ Branch 0 taken 29226370 times.
✓ Branch 1 taken 19462720 times.
✓ Branch 2 taken 27938370 times.
✓ Branch 3 taken 19835788 times.
83702604 if (!(lb < vs_topk_threshold(topk)))
369 6702076 return;
370
371 /* No dedup lookup: caller guarantees ids are unique. A map that
372 * vs_topk_insert built is kept current. */
373
2/2
✓ Branch 0 taken 27937942 times.
✓ Branch 1 taken 428 times.
27938370 if (topk->map_pos == NULL)
374
2/2
✓ Branch 0 taken 12760644 times.
✓ Branch 1 taken 9390582 times.
22151226 ub_insert(topk, ub, id, false);
375 else
376 ✗ ub_insert(topk, ub, id, true);
377
378 /* Grow candidate buffer if needed (old buffer freed with memctx) */
379
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 27938332 times.
27938370 if (topk->cand_count == topk->cand_capacity)
380 {
381 38 uint32_t new_cap = topk->cand_capacity * 2;
382 26 VsTopKEntry *new_buf =
383 38 vs_memctx_alloc(topk->memctx, new_cap * sizeof(VsTopKEntry));
384 38 memcpy(new_buf,
385 38 topk->candidates,
386 38 topk->cand_count * sizeof(VsTopKEntry));
387 38 topk->candidates = new_buf;
388 38 topk->cand_capacity = new_cap;
389 }
390
391 27938370 topk->candidates[topk->cand_count++] = (VsTopKEntry){
392 .distance = distance,
393 .error = error,
394 .id = id,
395 27938370 .src = topk->cur_src,
396 };
397 }
398
399 /* ----------------------------------------------------------------
400 * Insert
401 * ---------------------------------------------------------------- */
402
403 void
404 1178565 vs_topk_insert(VsTopK *topk, Distance distance, Distance error, uint64_t id)
405 {
406 1178565 Distance lb = distance - error;
407 1178565 Distance ub = distance + error;
408
409 /* Prune: lower bound exceeds threshold. Written NaN-safe: a NaN
410 * estimate (e.g. a zero vector normalized for cosine) fails every
411 * comparison, so the naive lb >= threshold guard would admit it --
412 * and one NaN upper bound in the heap corrupts the threshold for
413 * the rest of the scan. */
414
4/4
✓ Branch 0 taken 22400 times.
✓ Branch 1 taken 368570 times.
✓ Branch 2 taken 821419 times.
✓ Branch 3 taken 333 times.
1200965 if (!(lb < vs_topk_threshold(topk)))
415 356813 return;
416
417 /* Dedup: if this ID is already in the heap, keep only the better
418 * (smaller) upper bound. This prevents duplicates (e.g. SOAR
419 * replicas) from occupying multiple heap slots and inflating the
420 * threshold. */
421
2/2
✓ Branch 0 taken 798 times.
✓ Branch 1 taken 820621 times.
821419 if (vs_unlikely(topk->map_pos == NULL))
422 798 map_build(topk);
423
424 821419 uint32_t slot = map_find(topk, id);
425
2/2
✓ Branch 0 taken 5870 times.
✓ Branch 1 taken 815549 times.
821419 if (slot != VS_TOPK_MAP_EMPTY)
426 {
427 5870 uint32_t i = topk->map_pos[slot];
428
2/2
✓ Branch 0 taken 1382 times.
✓ Branch 1 taken 4488 times.
5870 if (ub < topk->ub_heap[i])
429 {
430 1382 topk->ub_heap[i] = ub;
431 1382 ub_sift_down(heap_arrays(topk), topk->ub_count, i, true);
432 }
433 5870 goto append;
434 }
435
436
2/2
✓ Branch 0 taken 11510 times.
✓ Branch 1 taken 21838 times.
33348 ub_insert(topk, ub, id, true);
437
438 821419 append:
439 /* Grow candidate buffer if needed (old buffer freed with memctx) */
440
2/2
✓ Branch 0 taken 715 times.
✓ Branch 1 taken 820704 times.
821419 if (topk->cand_count == topk->cand_capacity)
441 {
442 715 uint32_t new_cap = topk->cand_capacity * 2;
443 269 VsTopKEntry *new_buf =
444 715 vs_memctx_alloc(topk->memctx, new_cap * sizeof(VsTopKEntry));
445 715 memcpy(new_buf,
446 715 topk->candidates,
447 715 topk->cand_count * sizeof(VsTopKEntry));
448 715 topk->candidates = new_buf;
449 715 topk->cand_capacity = new_cap;
450 }
451
452 /* Append to candidate buffer */
453 821419 topk->candidates[topk->cand_count++] = (VsTopKEntry){
454 .distance = distance,
455 .error = error,
456 .id = id,
457 821419 .src = topk->cur_src,
458 };
459 }
460
461 /*
462 * Deduplicate a distance-sorted candidate prefix in place, keeping the
463 * first (best-distance) entry per ID, tracked in an id set. A rescan
464 * of prior survivors per entry would go quadratic in the survivor
465 * count; the set keeps this pass linear. Returns the deduplicated
466 * count, additionally truncated to `cap` unique entries when cap > 0.
467 */
468 static uint32_t
469 9440 dedup_sorted_prefix(VsTopKEntry *results, uint32_t n, uint32_t cap)
470 {
471
2/2
✓ Branch 0 taken 4241 times.
✓ Branch 1 taken 5199 times.
9440 if (n <= 1)
472 3880 return n;
473
474 361 VsIdSet seen;
475 5553 vs_idset_init(&seen, n);
476
477 5553 uint32_t w = 0;
478
3/3
✓ Branch 0 taken 157719 times.
✓ Branch 1 taken 17115 times.
✓ Branch 2 taken 286 times.
175120 for (uint32_t r = 0; r < n; r++)
479 {
480
2/2
✓ Branch 1 taken 6015 times.
✓ Branch 2 taken 168378 times.
174393 if (!vs_idset_test_add(&seen, results[r].id))
481 6015 continue;
482 168378 results[w++] = results[r];
483
4/4
✓ Branch 0 taken 109661 times.
✓ Branch 1 taken 58717 times.
✓ Branch 2 taken 4751 times.
✓ Branch 3 taken 89062 times.
168378 if (cap > 0 && w == cap)
484 4751 break;
485 }
486
1/2
✓ Branch 0 taken 361 times.
✗ Branch 1 not taken.
5553 vs_idset_cleanup(&seen);
487 5192 return w;
488 }
489
490 /*
491 * Partially order `results` so the `want` smallest-distance entries
492 * occupy the front (in arbitrary order within each side). Iterative
493 * Hoare quickselect with median-of-three pivots: expected O(n), no
494 * recursion, no external randomness.
495 */
496 static void
497 3248 quickselect_by_distance(VsTopKEntry *results, uint32_t n, uint32_t want)
498 {
499 3248 uint32_t lo = 0, hi = n;
500
501
6/6
✓ Branch 0 taken 22432 times.
✓ Branch 1 taken 1676 times.
✓ Branch 2 taken 22350 times.
✓ Branch 3 taken 82 times.
✓ Branch 4 taken 20470 times.
✓ Branch 5 taken 1490 times.
24108 while (hi - lo > 1 && want > lo && want < hi)
502 {
503 20860 uint32_t mid = lo + (hi - lo) / 2;
504 20860 Distance a = results[lo].distance;
505 20860 Distance b = results[mid].distance;
506 20860 Distance c = results[hi - 1].distance;
507 390 Distance pivot;
508
8/8
✓ Branch 0 taken 10687 times.
✓ Branch 1 taken 10173 times.
✓ Branch 2 taken 6438 times.
✓ Branch 3 taken 4249 times.
✓ Branch 4 taken 10371 times.
✓ Branch 5 taken 5925 times.
✓ Branch 6 taken 4151 times.
✓ Branch 7 taken 6220 times.
20860 if ((a <= b && b <= c) || (c <= b && b <= a))
509 8325 pivot = b;
510
8/8
✓ Branch 0 taken 6097 times.
✓ Branch 1 taken 6264 times.
✓ Branch 2 taken 3069 times.
✓ Branch 3 taken 3028 times.
✓ Branch 4 taken 6226 times.
✓ Branch 5 taken 3024 times.
✓ Branch 6 taken 3196 times.
✓ Branch 7 taken 3030 times.
12361 else if ((b <= a && a <= c) || (c <= a && a <= b))
511 6091 pivot = a;
512 else
513 6444 pivot = c;
514
515 /* The median-of-three pivot exists in the range, so each scan
516 * has a stopper; the explicit bounds checks make that local
517 * rather than an invariant to trust (j is unsigned, so an
518 * unchecked descent past lo would wrap). */
519 20860 uint32_t i = lo, j = hi - 1;
520
2/2
✓ Branch 0 taken 222060 times.
✓ Branch 1 taken 20860 times.
263780 while (i <= j)
521 {
522
4/4
✓ Branch 0 taken 525655 times.
✓ Branch 1 taken 1014 times.
✓ Branch 2 taken 304609 times.
✓ Branch 3 taken 221046 times.
526669 while (i < hi - 1 && results[i].distance < pivot)
523 304609 i++;
524
4/4
✓ Branch 0 taken 526883 times.
✓ Branch 1 taken 534 times.
✓ Branch 2 taken 305357 times.
✓ Branch 3 taken 221526 times.
527417 while (j > lo && results[j].distance > pivot)
525 305357 j--;
526
2/2
✓ Branch 0 taken 19997 times.
✓ Branch 1 taken 202063 times.
222060 if (i <= j)
527 {
528 208112 VsTopKEntry tmp = results[i];
529 208112 results[i] = results[j];
530 208112 results[j] = tmp;
531 208112 i++;
532
2/2
✓ Branch 0 taken 6311 times.
✓ Branch 1 taken 201801 times.
208112 if (j == 0)
533 ✗ break;
534 208112 j--;
535 }
536 }
537 /* Entries [lo, j] <= pivot <= entries [i, hi). Recurse into the
538 * side containing the selection boundary. */
539
2/2
✓ Branch 0 taken 10911 times.
✓ Branch 1 taken 9949 times.
20860 if (want <= j + 1)
540 10732 hi = j + 1;
541
1/2
✓ Branch 0 taken 9917 times.
✗ Branch 1 not taken.
9917 else if (want >= i)
542 9738 lo = i;
543 else
544 ✗ return; /* boundary falls in the pivot-equal middle band */
545 }
546 }
547
548 /* ----------------------------------------------------------------
549 * Extract sorted
550 * ---------------------------------------------------------------- */
551
552 /* The uncapped form of vs_topk_extract_sorted_capped. */
553 void
554 426 vs_topk_extract_sorted(VsTopK *topk, VsTopKEntry *results, uint32_t *count_out)
555 {
556 426 vs_topk_extract_sorted_capped(topk, results, count_out, 0);
557 426 }
558
559 /*
560 * Extract the threshold survivors sorted by distance ascending and
561 * deduplicated (first, i.e. best-distance, entry per id), keeping at
562 * most the best `cap` unique candidates; cap == 0 keeps them all. The
563 * survivor count is unbounded when distance estimates are noisy -- a
564 * loose threshold admits most scanned entries, every SOAR replica
565 * included -- so sorting all survivors is wasted work when only a
566 * small prefix is kept. A quickselect partition narrows to the
567 * smallest 3*cap entries first: every id occurs at most twice (primary
568 * posting plus at most one SOAR replica), so the smallest 2*cap
569 * entries already contain the best cap unique ids and 3*cap leaves
570 * margin.
571 */
572 void
573 9440 vs_topk_extract_sorted_capped(
574 VsTopK *topk, VsTopKEntry *results, uint32_t *count_out, uint32_t cap)
575 {
576
2/2
✓ Branch 0 taken 351 times.
✓ Branch 1 taken 17 times.
9440 Distance threshold = vs_topk_threshold(topk);
577
578 9440 uint32_t out = 0;
579
2/2
✓ Branch 0 taken 803613 times.
✓ Branch 1 taken 9440 times.
813053 for (uint32_t i = 0; i < topk->cand_count; i++)
580 {
581 803613 Distance lb = topk->candidates[i].distance - topk->candidates[i].error;
582
2/2
✓ Branch 0 taken 525675 times.
✓ Branch 1 taken 277938 times.
803613 if (lb <= threshold)
583 525675 results[out++] = topk->candidates[i];
584 }
585
586 9440 uint32_t sel = out;
587
4/4
✓ Branch 0 taken 9011 times.
✓ Branch 1 taken 429 times.
✓ Branch 2 taken 3248 times.
✓ Branch 3 taken 5763 times.
9440 if (cap > 0 && out > cap * 3)
588 {
589 3248 sel = cap * 3;
590 3248 quickselect_by_distance(results, out, sel);
591 }
592
593
2/2
✓ Branch 0 taken 5553 times.
✓ Branch 1 taken 3887 times.
9440 if (sel > 1)
594 5553 qsort(results, sel, sizeof(VsTopKEntry), cmp_by_distance);
595
596 9440 *count_out = dedup_sorted_prefix(results, sel, cap);
597 9440 }
598
599 /*
600 * Same as vs_topk_extract_sorted but skips the duplicate-id pass.
601 * For callers whose ids are unique by construction (array indices,
602 * beam-search buffer positions), the dedup scan can never remove
603 * anything and is quadratic in the survivor count.
604 */
605 void
606 929752 vs_topk_extract_sorted_unique(
607 VsTopK *topk, VsTopKEntry *results, uint32_t *count_out)
608 {
609
2/2
✓ Branch 0 taken 584821 times.
✓ Branch 1 taken 122057 times.
929752 Distance threshold = vs_topk_threshold(topk);
610
611 /* Filter stale candidates and copy survivors to results */
612 929752 uint32_t out = 0;
613
2/2
✓ Branch 0 taken 27937874 times.
✓ Branch 1 taken 929752 times.
28867626 for (uint32_t i = 0; i < topk->cand_count; i++)
614 {
615 27937874 Distance lb = topk->candidates[i].distance - topk->candidates[i].error;
616
2/2
✓ Branch 0 taken 15740375 times.
✓ Branch 1 taken 12197499 times.
27937874 if (lb <= threshold)
617 15740375 results[out++] = topk->candidates[i];
618 }
619
620 /* Sort by distance ascending */
621
2/2
✓ Branch 0 taken 602341 times.
✓ Branch 1 taken 327411 times.
929752 if (out > 1)
622 602341 qsort(results, out, sizeof(VsTopKEntry), cmp_by_distance);
623
624 929752 *count_out = out;
625 929752 }
626