GCC Code Coverage Report

Directory: src/
File: src/algo/topk.c
Date: 2026-09-30 11:11:31
Exec Total Coverage
Lines: 252 259 97.3%
Functions: 17 17 100.0%
Branches: 134 143 93.7%
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 *
11 * Used by both standalone and PG builds.
12 */
13
14 #include <stdlib.h>
15 #include <string.h>
16
17 #include "algo/topk.h"
18 #include "core/idset.h"
19 #include "core/memory.h"
20 #include "core/platform.h"
21
22 #define VS_TOPK_INITIAL_CAP_MIN 32
23
24 /* ----------------------------------------------------------------
25 * Threshold heap (max-heap of Distance values)
26 * ---------------------------------------------------------------- */
27
28 static void
29 15461431 ub_sift_up(Distance *heap, uint64_t *ids, uint32_t i)
30 {
31
2/2
✓ Branch 0 taken 28706518 times.
✓ Branch 1 taken 3041803 times.
 31748321 while (i > 0)
32 {
33 28706518 uint32_t parent = (i - 1) / 2;
34
2/2
✓ Branch 0 taken 15636225 times.
✓ Branch 1 taken 13070293 times.
 28706518 if (heap[i] <= heap[parent])
35 2131044 break;
36 16286890 Distance tmp = heap[i];
37 16286890 heap[i] = heap[parent];
38 16286890 heap[parent] = tmp;
39 16286890 uint64_t tid = ids[i];
40 16286890 ids[i] = ids[parent];
41 16286890 ids[parent] = tid;
42 16286890 i = parent;
43 }
44 15461431 }
45
46 static void
47 12218097 ub_sift_down(Distance *heap, uint64_t *ids, uint32_t count)
48 {
49 12218097 uint32_t i = 0;
50 68207875 for (;;)
51 38338771 {
52 50556868 uint32_t left = 2 * i + 1;
53 50556868 uint32_t right = 2 * i + 2;
54 50556868 uint32_t largest = i;
55
56
4/4
✓ Branch 0 taken 15423939 times.
✓ Branch 1 taken 35132929 times.
✓ Branch 2 taken 15134681 times.
✓ Branch 3 taken 28886340 times.
 50556868 if (left < count && heap[left] > heap[largest])
57 46882028 largest = left;
58
4/4
✓ Branch 0 taken 15782530 times.
✓ Branch 1 taken 34774338 times.
✓ Branch 2 taken 22527105 times.
✓ Branch 3 taken 20790039 times.
 50556868 if (right < count && heap[right] > heap[largest])
59 43208864 largest = right;
60
61
2/2
✓ Branch 0 taken 32227427 times.
✓ Branch 1 taken 18329441 times.
 50556868 if (largest == i)
62 2821692 break;
63
64 38338771 Distance tmp = heap[i];
65 38338771 heap[i] = heap[largest];
66 38338771 heap[largest] = tmp;
67 38338771 uint64_t tid = ids[i];
68 38338771 ids[i] = ids[largest];
69 38338771 ids[largest] = tid;
70 38338771 i = largest;
71 }
72 12218097 }
73
74 static void
75 84 ub_sift_down_from(Distance *heap, uint64_t *ids, uint32_t count, uint32_t i)
76 {
77 252 for (;;)
78 84 {
79 168 uint32_t left = 2 * i + 1;
80 168 uint32_t right = 2 * i + 2;
81 168 uint32_t largest = i;
82
83
4/4
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 134 times.
✓ Branch 2 taken 101 times.
✓ Branch 3 taken 33 times.
 168 if (left < count && heap[left] > heap[largest])
84 168 largest = left;
85
4/4
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 133 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 69 times.
 168 if (right < count && heap[right] > heap[largest])
86 168 largest = right;
87
88
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 84 times.
 168 if (largest == i)
89 ✗ break;
90
91 84 Distance tmp = heap[i];
92 84 heap[i] = heap[largest];
93 84 heap[largest] = tmp;
94 84 uint64_t tid = ids[i];
95 84 ids[i] = ids[largest];
96 84 ids[largest] = tid;
97 84 i = largest;
98 }
99 84 }
100
101 /* ----------------------------------------------------------------
102 * Comparator for qsort (ascending by distance)
103 * ---------------------------------------------------------------- */
104
105 static int
106 68310515 cmp_by_distance(const void *a, const void *b)
107 {
108 68310515 const VsTopKEntry *ea = (const VsTopKEntry *)a;
109 68310515 const VsTopKEntry *eb = (const VsTopKEntry *)b;
110
2/2
✓ Branch 0 taken 35685117 times.
✓ Branch 1 taken 32625398 times.
 68310515 if (ea->distance < eb->distance)
111 5033273 return -1;
112
2/2
✓ Branch 0 taken 35430973 times.
✓ Branch 1 taken 30371 times.
 35461344 if (ea->distance > eb->distance)
113 35430973 return 1;
114 28012 return 0;
115 }
116
117 /* ----------------------------------------------------------------
118 * Init / cleanup / create / destroy
119 * ---------------------------------------------------------------- */
120
121 void
122 36766 vs_topk_init(VsTopK *topk, uint32_t k)
123 {
124 36766 topk->memctx = vs_memctx_create(NULL, "topk");
125 36766 topk->k = k;
126 36766 topk->k_capacity = k;
127 36766 topk->ub_heap = vs_memctx_alloc(topk->memctx, k * sizeof(Distance));
128 36766 topk->ub_ids = vs_memctx_alloc(topk->memctx, k * sizeof(uint64_t));
129 36766 topk->ub_count = 0;
130
131 36766 uint32_t cap = k * 2;
132
2/2
✓ Branch 0 taken 276 times.
✓ Branch 1 taken 274 times.
 36766 if (cap < VS_TOPK_INITIAL_CAP_MIN)
133 276 cap = VS_TOPK_INITIAL_CAP_MIN;
134 72982 topk->candidates =
135 36766 vs_memctx_alloc(topk->memctx, cap * sizeof(VsTopKEntry));
136 36766 topk->cand_count = 0;
137 36766 topk->cand_capacity = cap;
138 36766 }
139
140 void
141 36762 vs_topk_cleanup(VsTopK *topk)
142 {
143
2/2
✓ Branch 0 taken 36212 times.
✓ Branch 1 taken 550 times.
 36762 if (topk == NULL)
144 ✗ return;
145
1/2
✓ Branch 0 taken 36762 times.
✗ Branch 1 not taken.
 36762 if (topk->memctx != NULL)
146 {
147 36762 vs_memctx_delete(topk->memctx);
148 36762 topk->memctx = NULL;
149 }
150 36762 topk->ub_heap = NULL;
151 36762 topk->ub_ids = NULL;
152 36762 topk->candidates = NULL;
153 }
154
155 VsTopK *
156 2 vs_topk_create(uint32_t k)
157 {
158 2 VsMemCtx ctx = vs_memctx_create(NULL, "topk");
159 2 VsTopK *topk = vs_memctx_alloc(ctx, sizeof(VsTopK));
160 2 topk->memctx = ctx;
161 2 topk->k = k;
162 2 topk->ub_heap = vs_memctx_alloc(ctx, k * sizeof(Distance));
163 2 topk->ub_ids = vs_memctx_alloc(ctx, k * sizeof(uint64_t));
164 2 topk->ub_count = 0;
165
166 2 uint32_t cap = k * 2;
167
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (cap < VS_TOPK_INITIAL_CAP_MIN)
168 2 cap = VS_TOPK_INITIAL_CAP_MIN;
169 2 topk->candidates = vs_memctx_alloc(ctx, cap * sizeof(VsTopKEntry));
170 2 topk->cand_count = 0;
171 2 topk->cand_capacity = cap;
172 2 return topk;
173 }
174
175 void
176 2 vs_topk_destroy(VsTopK *topk)
177 {
178
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (topk == NULL)
179 ✗ return;
180 2 vs_memctx_delete(topk->memctx);
181 }
182
183 void
184 4 vs_topk_reset(VsTopK *topk)
185 {
186 4 vs_topk_reset_to_k(topk, topk->k);
187 4 }
188
189 void
190 903359 vs_topk_reset_to_k(VsTopK *topk, uint32_t k)
191 {
192 /* O(1) reset: buffers are retained across resets (grow-only), so a
193 * reused top-K reaches a steady state with zero allocator traffic.
194 * Only a k above the allocated capacity re-allocates — reset the
195 * arena first so the outgrown blocks are reclaimed rather than
196 * leaked into the context. The candidate buffer keeps its
197 * high-water capacity, avoiding the doubling-regrowth copies that
198 * a fresh buffer paid on every use. */
199
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 903353 times.
 903359 if (vs_unlikely(k > topk->k_capacity))
200 {
201 6 uint32_t cand_cap = topk->cand_capacity;
202 6 uint32_t min_cap = k * 2;
203
204
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (cand_cap < min_cap)
205 ✗ cand_cap = min_cap;
206
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (cand_cap < VS_TOPK_INITIAL_CAP_MIN)
207 ✗ cand_cap = VS_TOPK_INITIAL_CAP_MIN;
208
209 6 vs_memctx_reset(topk->memctx);
210 6 topk->ub_heap = vs_memctx_alloc(topk->memctx, k * sizeof(Distance));
211 6 topk->ub_ids = vs_memctx_alloc(topk->memctx, k * sizeof(uint64_t));
212 6 topk->candidates =
213 6 vs_memctx_alloc(topk->memctx, cand_cap * sizeof(VsTopKEntry));
214 6 topk->cand_capacity = cand_cap;
215 6 topk->k_capacity = k;
216 }
217
218 903359 topk->k = k;
219 903359 topk->ub_count = 0;
220 903359 topk->cand_count = 0;
221 903359 }
222
223 void
224 54122304 vs_topk_insert_unique(
225 VsTopK *topk, Distance distance, Distance error, uint64_t id)
226 {
227 54122304 Distance lb = distance - error;
228 54122304 Distance ub = distance + error;
229
230 /* Prune: lower bound exceeds threshold. Written NaN-safe: a NaN
231 * estimate (e.g. a zero vector normalized for cosine) fails every
232 * comparison, so the naive lb >= threshold guard would admit it --
233 * and one NaN upper bound in the heap corrupts the threshold for
234 * the rest of the scan. */
235
4/4
✓ Branch 0 taken 29222304 times.
✓ Branch 1 taken 19353071 times.
✓ Branch 2 taken 27621309 times.
✓ Branch 3 taken 19831466 times.
 83344608 if (!(lb < vs_topk_threshold(topk)))
236 6669529 return;
237
238 /* No dedup scan: caller guarantees ids are unique. */
239
2/2
✓ Branch 0 taken 15442112 times.
✓ Branch 1 taken 12179197 times.
 27621309 if (topk->ub_count < topk->k)
240 {
241 15442112 topk->ub_heap[topk->ub_count] = ub;
242 15442112 topk->ub_ids[topk->ub_count] = id;
243 15442112 topk->ub_count++;
244 15442112 ub_sift_up(topk->ub_heap, topk->ub_ids, topk->ub_count - 1);
245 }
246
1/2
✓ Branch 0 taken 12179197 times.
✗ Branch 1 not taken.
 12179197 else if (ub < topk->ub_heap[0])
247 {
248 12179197 topk->ub_heap[0] = ub;
249 12179197 topk->ub_ids[0] = id;
250 12179197 ub_sift_down(topk->ub_heap, topk->ub_ids, topk->ub_count);
251 }
252
253 /* Grow candidate buffer if needed (old buffer freed with memctx) */
254
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 27621273 times.
 27621309 if (topk->cand_count == topk->cand_capacity)
255 {
256 36 uint32_t new_cap = topk->cand_capacity * 2;
257 24 VsTopKEntry *new_buf =
258 36 vs_memctx_alloc(topk->memctx, new_cap * sizeof(VsTopKEntry));
259 36 memcpy(new_buf,
260 36 topk->candidates,
261 36 topk->cand_count * sizeof(VsTopKEntry));
262 36 topk->candidates = new_buf;
263 36 topk->cand_capacity = new_cap;
264 }
265
266 27621309 topk->candidates[topk->cand_count++] = (VsTopKEntry){
267 .distance = distance,
268 .error = error,
269 .id = id,
270 27621309 .src = topk->cur_src,
271 };
272 }
273
274 /* ----------------------------------------------------------------
275 * Insert
276 * ---------------------------------------------------------------- */
277
278 void
279 687712 vs_topk_insert(VsTopK *topk, Distance distance, Distance error, uint64_t id)
280 {
281 687712 Distance lb = distance - error;
282 687712 Distance ub = distance + error;
283
284 /* Prune: lower bound exceeds threshold. Written NaN-safe: a NaN
285 * estimate (e.g. a zero vector normalized for cosine) fails every
286 * comparison, so the naive lb >= threshold guard would admit it --
287 * and one NaN upper bound in the heap corrupts the threshold for
288 * the rest of the scan. */
289
3/4
✓ Branch 0 taken 19230 times.
✓ Branch 1 taken 76263 times.
✓ Branch 2 taken 619775 times.
✗ Branch 3 not taken.
 706942 if (!(lb < vs_topk_threshold(topk)))
290 67937 return;
291
292 /* Dedup: check if this ID is already in the heap. If so,
293 * only keep the entry with the better (smaller) upper bound.
294 * This prevents duplicates (e.g. SOAR replicas) from occupying
295 * multiple heap slots and inflating the threshold. */
296
2/2
✓ Branch 0 taken 2849614 times.
✓ Branch 1 taken 618880 times.
 3468494 for (uint32_t i = 0; i < topk->ub_count; i++)
297 {
298
2/2
✓ Branch 0 taken 895 times.
✓ Branch 1 taken 2848719 times.
 2849614 if (topk->ub_ids[i] == id)
299 {
300
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 811 times.
 895 if (ub < topk->ub_heap[i])
301 {
302 84 topk->ub_heap[i] = ub;
303 84 ub_sift_down_from(
304 topk->ub_heap, topk->ub_ids, topk->ub_count, i);
305 }
306 895 goto append;
307 }
308 }
309
310 /* Update threshold heap */
311
2/2
✓ Branch 0 taken 19319 times.
✓ Branch 1 taken 599561 times.
 618880 if (topk->ub_count < topk->k)
312 {
313 19319 topk->ub_heap[topk->ub_count] = ub;
314 19319 topk->ub_ids[topk->ub_count] = id;
315 19319 topk->ub_count++;
316 19319 ub_sift_up(topk->ub_heap, topk->ub_ids, topk->ub_count - 1);
317 }
318
2/2
✓ Branch 0 taken 560661 times.
✓ Branch 1 taken 38900 times.
 599561 else if (ub < topk->ub_heap[0])
319 {
320 38900 topk->ub_heap[0] = ub;
321 38900 topk->ub_ids[0] = id;
322 38900 ub_sift_down(topk->ub_heap, topk->ub_ids, topk->ub_count);
323 }
324
325 560661 append:
326 /* Grow candidate buffer if needed (old buffer freed with memctx) */
327
2/2
✓ Branch 0 taken 580 times.
✓ Branch 1 taken 619195 times.
 619775 if (topk->cand_count == topk->cand_capacity)
328 {
329 580 uint32_t new_cap = topk->cand_capacity * 2;
330 240 VsTopKEntry *new_buf =
331 580 vs_memctx_alloc(topk->memctx, new_cap * sizeof(VsTopKEntry));
332 580 memcpy(new_buf,
333 580 topk->candidates,
334 580 topk->cand_count * sizeof(VsTopKEntry));
335 580 topk->candidates = new_buf;
336 580 topk->cand_capacity = new_cap;
337 }
338
339 /* Append to candidate buffer */
340 619775 topk->candidates[topk->cand_count++] = (VsTopKEntry){
341 .distance = distance,
342 .error = error,
343 .id = id,
344 619775 .src = topk->cur_src,
345 };
346 }
347
348 /*
349 * Deduplicate a distance-sorted candidate prefix in place, keeping the
350 * first (best-distance) entry per ID, tracked in an id set. A rescan
351 * of prior survivors per entry would go quadratic in the survivor
352 * count; the set keeps this pass linear. Returns the deduplicated
353 * count, additionally truncated to `cap` unique entries when cap > 0.
354 */
355 static uint32_t
356 7820 dedup_sorted_prefix(VsTopKEntry *results, uint32_t n, uint32_t cap)
357 {
358
2/2
✓ Branch 0 taken 3857 times.
✓ Branch 1 taken 3963 times.
 7820 if (n <= 1)
359 3581 return n;
360
361 276 VsIdSet seen;
362 4233 vs_idset_init(&seen, n);
363
364 4233 uint32_t w = 0;
365
3/3
✓ Branch 0 taken 88399 times.
✓ Branch 1 taken 12897 times.
✓ Branch 2 taken 219 times.
 101515 for (uint32_t r = 0; r < n; r++)
366 {
367
2/2
✓ Branch 1 taken 5901 times.
✓ Branch 2 taken 95117 times.
 101018 if (!vs_idset_test_add(&seen, results[r].id))
368 5901 continue;
369 95117 results[w++] = results[r];
370
4/4
✓ Branch 0 taken 85606 times.
✓ Branch 1 taken 9511 times.
✓ Branch 2 taken 3679 times.
✓ Branch 3 taken 70002 times.
 95117 if (cap > 0 && w == cap)
371 3679 break;
372 }
373
1/2
✓ Branch 0 taken 276 times.
✗ Branch 1 not taken.
 4233 vs_idset_cleanup(&seen);
374 3957 return w;
375 }
376
377 /*
378 * Partially order `results` so the `want` smallest-distance entries
379 * occupy the front (in arbitrary order within each side). Iterative
380 * Hoare quickselect with median-of-three pivots: expected O(n), no
381 * recursion, no external randomness.
382 */
383 static void
384 2723 quickselect_by_distance(VsTopKEntry *results, uint32_t n, uint32_t want)
385 {
386 2723 uint32_t lo = 0, hi = n;
387
388
6/6
✓ Branch 0 taken 18406 times.
✓ Branch 1 taken 1435 times.
✓ Branch 2 taken 18312 times.
✓ Branch 3 taken 94 times.
✓ Branch 4 taken 16724 times.
✓ Branch 5 taken 1194 times.
 19841 while (hi - lo > 1 && want > lo && want < hi)
389 {
390 17118 uint32_t mid = lo + (hi - lo) / 2;
391 17118 Distance a = results[lo].distance;
392 17118 Distance b = results[mid].distance;
393 17118 Distance c = results[hi - 1].distance;
394 394 Distance pivot;
395
8/8
✓ Branch 0 taken 8895 times.
✓ Branch 1 taken 8223 times.
✓ Branch 2 taken 5241 times.
✓ Branch 3 taken 3654 times.
✓ Branch 4 taken 8347 times.
✓ Branch 5 taken 4797 times.
✓ Branch 6 taken 3327 times.
✓ Branch 7 taken 5020 times.
 17118 if ((a <= b && b <= c) || (c <= b && b <= a))
396 6907 pivot = b;
397
8/8
✓ Branch 0 taken 4974 times.
✓ Branch 1 taken 5062 times.
✓ Branch 2 taken 2537 times.
✓ Branch 3 taken 2437 times.
✓ Branch 4 taken 5021 times.
✓ Branch 5 taken 2492 times.
✓ Branch 6 taken 2528 times.
✓ Branch 7 taken 2493 times.
 10036 else if ((b <= a && a <= c) || (c <= a && a <= b))
398 4832 pivot = a;
399 else
400 5379 pivot = c;
401
402 /* The median-of-three pivot exists in the range, so each scan
403 * has a stopper; the explicit bounds checks make that local
404 * rather than an invariant to trust (j is unsigned, so an
405 * unchecked descent past lo would wrap). */
406 17118 uint32_t i = lo, j = hi - 1;
407
2/2
✓ Branch 0 taken 171746 times.
✓ Branch 1 taken 17118 times.
 205982 while (i <= j)
408 {
409
4/4
✓ Branch 0 taken 398459 times.
✓ Branch 1 taken 963 times.
✓ Branch 2 taken 227676 times.
✓ Branch 3 taken 170783 times.
 399422 while (i < hi - 1 && results[i].distance < pivot)
410 227676 i++;
411
4/4
✓ Branch 0 taken 407440 times.
✓ Branch 1 taken 459 times.
✓ Branch 2 taken 236153 times.
✓ Branch 3 taken 171287 times.
 407899 while (j > lo && results[j].distance > pivot)
412 236153 j--;
413
2/2
✓ Branch 0 taken 17173 times.
✓ Branch 1 taken 154573 times.
 171746 if (i <= j)
414 {
415 160405 VsTopKEntry tmp = results[i];
416 160405 results[i] = results[j];
417 160405 results[j] = tmp;
418 160405 i++;
419
2/2
✓ Branch 0 taken 6095 times.
✓ Branch 1 taken 154310 times.
 160405 if (j == 0)
420 ✗ break;
421 160405 j--;
422 }
423 }
424 /* Entries [lo, j] <= pivot <= entries [i, hi). Recurse into the
425 * side containing the selection boundary. */
426
2/2
✓ Branch 0 taken 8968 times.
✓ Branch 1 taken 8150 times.
 17118 if (want <= j + 1)
427 8783 hi = j + 1;
428
1/2
✓ Branch 0 taken 8126 times.
✗ Branch 1 not taken.
 8126 else if (want >= i)
429 7941 lo = i;
430 else
431 ✗ return; /* boundary falls in the pivot-equal middle band */
432 }
433 }
434
435 /* ----------------------------------------------------------------
436 * Extract sorted
437 * ---------------------------------------------------------------- */
438
439 /* The uncapped form of vs_topk_extract_sorted_capped. */
440 void
441 3774 vs_topk_extract_sorted(VsTopK *topk, VsTopKEntry *results, uint32_t *count_out)
442 {
443 3774 vs_topk_extract_sorted_capped(topk, results, count_out, 0);
444 3774 }
445
446 /*
447 * Extract the threshold survivors sorted by distance ascending and
448 * deduplicated (first, i.e. best-distance, entry per id), keeping at
449 * most the best `cap` unique candidates; cap == 0 keeps them all. The
450 * survivor count is unbounded when distance estimates are noisy -- a
451 * loose threshold admits most scanned entries, every SOAR replica
452 * included -- so sorting all survivors is wasted work when only a
453 * small prefix is kept. A quickselect partition narrows to the
454 * smallest 3*cap entries first: every id occurs at most twice (primary
455 * posting plus at most one SOAR replica), so the smallest 2*cap
456 * entries already contain the best cap unique ids and 3*cap leaves
457 * margin.
458 */
459 void
460 7820 vs_topk_extract_sorted_capped(
461 VsTopK *topk, VsTopKEntry *results, uint32_t *count_out, uint32_t cap)
462 {
463
2/2
✓ Branch 0 taken 270 times.
✓ Branch 1 taken 12 times.
 7820 Distance threshold = vs_topk_threshold(topk);
464
465 7820 uint32_t out = 0;
466
2/2
✓ Branch 0 taken 619293 times.
✓ Branch 1 taken 7820 times.
 627113 for (uint32_t i = 0; i < topk->cand_count; i++)
467 {
468 619293 Distance lb = topk->candidates[i].distance - topk->candidates[i].error;
469
2/2
✓ Branch 0 taken 376815 times.
✓ Branch 1 taken 242478 times.
 619293 if (lb <= threshold)
470 376815 results[out++] = topk->candidates[i];
471 }
472
473 7820 uint32_t sel = out;
474
4/4
✓ Branch 0 taken 4046 times.
✓ Branch 1 taken 3774 times.
✓ Branch 2 taken 2723 times.
✓ Branch 3 taken 1323 times.
 7820 if (cap > 0 && out > cap * 3)
475 {
476 2723 sel = cap * 3;
477 2723 quickselect_by_distance(results, out, sel);
478 }
479
480
2/2
✓ Branch 0 taken 4233 times.
✓ Branch 1 taken 3587 times.
 7820 if (sel > 1)
481 4233 qsort(results, sel, sizeof(VsTopKEntry), cmp_by_distance);
482
483 7820 *count_out = dedup_sorted_prefix(results, sel, cap);
484 7820 }
485
486 /*
487 * Same as vs_topk_extract_sorted but skips the duplicate-id pass.
488 * For callers whose ids are unique by construction (array indices,
489 * beam-search buffer positions), the dedup scan can never remove
490 * anything and is quadratic in the survivor count.
491 */
492 void
493 895895 vs_topk_extract_sorted_unique(
494 VsTopK *topk, VsTopKEntry *results, uint32_t *count_out)
495 {
496
2/2
✓ Branch 0 taken 584461 times.
✓ Branch 1 taken 108314 times.
 895895 Distance threshold = vs_topk_threshold(topk);
497
498 /* Filter stale candidates and copy survivors to results */
499 895895 uint32_t out = 0;
500
2/2
✓ Branch 0 taken 27621309 times.
✓ Branch 1 taken 895895 times.
 28517204 for (uint32_t i = 0; i < topk->cand_count; i++)
501 {
502 27621309 Distance lb = topk->candidates[i].distance - topk->candidates[i].error;
503
2/2
✓ Branch 0 taken 15442141 times.
✓ Branch 1 taken 12179168 times.
 27621309 if (lb <= threshold)
504 15442141 results[out++] = topk->candidates[i];
505 }
506
507 /* Sort by distance ascending */
508
2/2
✓ Branch 0 taken 575065 times.
✓ Branch 1 taken 320830 times.
 895895 if (out > 1)
509 575065 qsort(results, out, sizeof(VsTopKEntry), cmp_by_distance);
510
511 895895 *count_out = out;
512 895895 }
513