| line |
true |
false |
branch |
|
140
|
1 |
82 |
if (v < 2) return 1; |
|
156
|
4 |
2753840 |
if (!isfinite(d)) return 0; |
|
157
|
8 |
2753832 |
if (d >= (double)SPH_CELL_LIMIT) return SPH_CELL_LIMIT; |
|
158
|
1 |
2753831 |
if (d <= -(double)SPH_CELL_LIMIT) return -SPH_CELL_LIMIT; |
|
163
|
3326 |
30707 |
if (n <= 0) return c; |
|
165
|
752 |
29955 |
return m < 0 ? m + n : m; |
|
170
|
11899 |
44206 |
return (world > 0.0 && d > world * 0.5) ? world - d : d; |
|
|
2138 |
9761 |
return (world > 0.0 && d > world * 0.5) ? world - d : d; |
|
183
|
5287 |
910587 |
if (h->wrap) { |
|
193
|
57217 |
844613 |
return a[0] == b[0] && a[1] == b[1] && a[2] == b[2]; |
|
|
25009 |
32208 |
return a[0] == b[0] && a[1] == b[1] && a[2] == b[2]; |
|
|
24922 |
87 |
return a[0] == b[0] && a[1] == b[1] && a[2] == b[2]; |
|
227
|
0 |
0 |
if (pid == 0) return 1; /* no owner recorded, assume alive */ |
|
228
|
0 |
0 |
return !(kill((pid_t)pid, 0) == -1 && errno == ESRCH); |
|
|
0 |
0 |
return !(kill((pid_t)pid, 0) == -1 && errno == ESRCH); |
|
238
|
0 |
0 |
if (!__atomic_compare_exchange_n(&hdr->rwlock, &observed_rwlock, |
|
244
|
0 |
0 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
268
|
12114 |
59 |
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) |
|
|
12114 |
0 |
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) |
|
279
|
67 |
0 |
for (uint32_t i = 0; i < SPH_READER_SLOTS; i++) { |
|
282
|
59 |
8 |
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, |
|
302
|
0 |
0 |
if (!sub) return; |
|
305
|
0 |
0 |
uint32_t want = (cur > sub) ? cur - sub : 0; |
|
306
|
0 |
0 |
if (__atomic_compare_exchange_n(p, &cur, want, |
|
329
|
0 |
0 |
if (!__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, 0, |
|
334
|
0 |
0 |
if (wp) sph_atomic_sub_cap(&hdr->rwlock_waiters, wp); |
|
335
|
0 |
0 |
if (writp) sph_atomic_sub_cap(&hdr->rwlock_writers_waiting, writp); |
|
349
|
0 |
0 |
if (!h->reader_slots) return; |
|
362
|
0 |
0 |
for (uint32_t i = 0; i < SPH_READER_SLOTS; i++) { |
|
364
|
0 |
0 |
if (pid == 0) continue; |
|
366
|
0 |
0 |
if (sph_pid_alive(pid)) { |
|
367
|
0 |
0 |
if (sc > 0) any_live_reader = 1; |
|
370
|
0 |
0 |
if (sc > 0) { found_dead_reader = 1; continue; } |
|
387
|
0 |
0 |
if (found_dead_reader && !any_live_reader) { |
|
|
0 |
0 |
if (found_dead_reader && !any_live_reader) { |
|
389
|
0 |
0 |
if (cur > 0 && cur < SPH_RWLOCK_WRITER_BIT) { |
|
|
0 |
0 |
if (cur > 0 && cur < SPH_RWLOCK_WRITER_BIT) { |
|
390
|
0 |
0 |
if (__atomic_compare_exchange_n(&hdr->rwlock, &cur, 0, |
|
392
|
0 |
0 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
396
|
0 |
0 |
for (uint32_t i = 0; i < SPH_READER_SLOTS; i++) { |
|
398
|
0 |
0 |
if (pid == 0 || sph_pid_alive(pid)) continue; |
|
|
0 |
0 |
if (pid == 0 || sph_pid_alive(pid)) continue; |
|
411
|
0 |
0 |
if (val >= SPH_RWLOCK_WRITER_BIT) { |
|
413
|
0 |
0 |
if (!sph_pid_alive(pid)) |
|
425
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
431
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
435
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) { |
|
445
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) { |
|
463
|
685 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
470
|
0 |
685 |
if (cur > 0 && cur < SPH_RWLOCK_WRITER_BIT) { |
|
|
0 |
0 |
if (cur > 0 && cur < SPH_RWLOCK_WRITER_BIT) { |
|
471
|
0 |
0 |
if (__atomic_compare_exchange_n(lock, &cur, cur + 1, |
|
474
|
685 |
0 |
} else if (cur == 0 && !__atomic_load_n(writers_waiting, __ATOMIC_RELAXED)) { |
|
|
685 |
0 |
} else if (cur == 0 && !__atomic_load_n(writers_waiting, __ATOMIC_RELAXED)) { |
|
475
|
685 |
0 |
if (__atomic_compare_exchange_n(lock, &cur, 1, |
|
479
|
0 |
0 |
if (__builtin_expect(spin < SPH_RWLOCK_SPIN_LIMIT, 1)) { |
|
486
|
0 |
0 |
if (cur >= SPH_RWLOCK_WRITER_BIT || cur == 0) { |
|
|
0 |
0 |
if (cur >= SPH_RWLOCK_WRITER_BIT || cur == 0) { |
|
489
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
509
|
685 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
511
|
685 |
0 |
if (after == 0 && __atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
|
0 |
685 |
if (after == 0 && __atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
524
|
11488 |
0 |
if (__atomic_compare_exchange_n(lock, &expected, mypid, |
|
527
|
0 |
0 |
if (__builtin_expect(spin < SPH_RWLOCK_SPIN_LIMIT, 1)) { |
|
533
|
0 |
0 |
if (cur != 0) { |
|
536
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
551
|
0 |
11488 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
598
|
210 |
70 |
for (int i = 0; i < 3; i++) { |
|
599
|
24 |
186 |
double w = world ? world[i] : 0.0; |
|
601
|
18 |
192 |
if (w > 0.0) wrap = 1; |
|
603
|
8 |
62 |
hdr->flags = wrap ? SPH_FLAG_WRAP : 0; |
|
614
|
117977 |
70 |
for (uint32_t i = 0; i < num_buckets; i++) buckets[i] = SPH_NONE; |
|
618
|
89694 |
70 |
for (uint32_t i = 0; i < max_entries; i++) |
|
619
|
89624 |
70 |
entries[i].next = (i + 1 < max_entries) ? (i + 1) : SPH_NONE; |
|
630
|
0 |
79 |
if (!h) { |
|
632
|
0 |
0 |
if (backing_fd >= 0) close(backing_fd); |
|
642
|
18 |
61 |
h->path = path ? strdup(path) : NULL; |
|
647
|
237 |
79 |
for (int i = 0; i < 3; i++) { |
|
648
|
27 |
210 |
h->world[i] = h->wrap ? hdr->world[i] : 0.0; |
|
649
|
20 |
7 |
h->wrap_cells[i] = (h->wrap && hdr->world[i] > 0.0) |
|
650
|
27 |
210 |
? (int64_t)floor(hdr->world[i] / hdr->cell_size + 0.5) : 0; /* exact: extent is a multiple */ |
|
657
|
1 |
13 |
if (hdr->magic != SPH_MAGIC) return 0; |
|
658
|
1 |
12 |
if (hdr->version != SPH_VERSION) return 0; |
|
659
|
12 |
0 |
if (hdr->max_entries == 0 || hdr->num_buckets == 0) return 0; |
|
|
0 |
12 |
if (hdr->max_entries == 0 || hdr->num_buckets == 0) return 0; |
|
660
|
12 |
0 |
if (hdr->max_entries > SPH_MAX_CAPACITY || hdr->num_buckets > SPH_MAX_CAPACITY) return 0; |
|
|
0 |
12 |
if (hdr->max_entries > SPH_MAX_CAPACITY || hdr->num_buckets > SPH_MAX_CAPACITY) return 0; |
|
661
|
0 |
12 |
if ((hdr->num_buckets & (hdr->num_buckets - 1)) != 0) return 0; /* power of two */ |
|
662
|
12 |
0 |
if (!(hdr->cell_size > 0) || !isfinite(hdr->cell_size)) return 0; |
|
|
0 |
12 |
if (!(hdr->cell_size > 0) || !isfinite(hdr->cell_size)) return 0; |
|
663
|
2 |
10 |
if (hdr->total_size != file_size) return 0; |
|
664
|
0 |
10 |
if (hdr->total_size != sph_total_size(hdr->max_entries, hdr->num_buckets)) return 0; |
|
667
|
0 |
10 |
if (hdr->reader_slots_off != L.reader_slots) return 0; |
|
668
|
0 |
10 |
if (hdr->buckets_off != L.buckets) return 0; |
|
669
|
0 |
10 |
if (hdr->bitmap_off != L.bitmap) return 0; |
|
670
|
0 |
10 |
if (hdr->entries_off != L.entries) return 0; |
|
671
|
0 |
10 |
if (hdr->flags & ~SPH_FLAG_WRAP) return 0; /* no unknown flags */ |
|
673
|
30 |
10 |
for (int i = 0; i < 3; i++) { |
|
674
|
30 |
0 |
if (!isfinite(hdr->world[i]) || hdr->world[i] < 0.0) return 0; |
|
|
0 |
30 |
if (!isfinite(hdr->world[i]) || hdr->world[i] < 0.0) return 0; |
|
675
|
4 |
26 |
if (hdr->world[i] > 0.0) { w = 1; |
|
677
|
4 |
0 |
if (nx < 1.0 || fabs(nx * hdr->cell_size - hdr->world[i]) > 1e-9 * hdr->world[i]) return 0; |
|
|
0 |
4 |
if (nx < 1.0 || fabs(nx * hdr->cell_size - hdr->world[i]) > 1e-9 * hdr->world[i]) return 0; |
|
680
|
0 |
10 |
if (((hdr->flags & SPH_FLAG_WRAP) ? 1 : 0) != w) return 0; /* flag must match extents */ |
|
682
|
10 |
0 |
if (!isfinite(hdr->sphere_radius) || hdr->sphere_radius < 0.0) return 0; |
|
|
0 |
10 |
if (!isfinite(hdr->sphere_radius) || hdr->sphere_radius < 0.0) return 0; |
|
683
|
3 |
7 |
if (hdr->sphere_radius > 0.0 && (hdr->flags & SPH_FLAG_WRAP)) return 0; /* sphere and wrap are mutually exclusive */ |
|
|
1 |
2 |
if (hdr->sphere_radius > 0.0 && (hdr->flags & SPH_FLAG_WRAP)) return 0; /* sphere and wrap are mutually exclusive */ |
|
690
|
77 |
10 |
if (!world) return 1; |
|
691
|
28 |
9 |
for (int i = 0; i < 3; i++) { |
|
692
|
28 |
0 |
if (!(world[i] >= 0.0) || !isfinite(world[i])) { SPH_ERR("world extent must be finite and >= 0"); return 0; } |
|
|
0 |
28 |
if (!(world[i] >= 0.0) || !isfinite(world[i])) { SPH_ERR("world extent must be finite and >= 0"); return 0; } |
|
|
0 |
0 |
if (!(world[i] >= 0.0) || !isfinite(world[i])) { SPH_ERR("world extent must be finite and >= 0"); return 0; } |
|
693
|
21 |
7 |
if (world[i] > 0.0) { |
|
695
|
21 |
0 |
if (nx < 1.0 || fabs(nx * cell_size - world[i]) > 1e-9 * world[i]) { |
|
|
1 |
20 |
if (nx < 1.0 || fabs(nx * cell_size - world[i]) > 1e-9 * world[i]) { |
|
696
|
1 |
0 |
SPH_ERR("wrap extent must be a positive multiple of cell_size"); return 0; |
|
716
|
306 |
0 |
double s = (r > 0.0) ? in[2] / r : 0.0; |
|
717
|
0 |
306 |
if (s > 1.0) s = 1.0; else if (s < -1.0) s = -1.0; /* guard asin domain vs rounding */ |
|
|
0 |
306 |
if (s > 1.0) s = 1.0; else if (s < -1.0) s = -1.0; /* guard asin domain vs rounding */ |
|
738
|
5 |
99127 |
if (id >> 56) return 0; |
|
740
|
1 |
99126 |
if (level > SPH_CUBE_MAX_LEVEL) return 0; |
|
741
|
0 |
99126 |
if (sph_cube_face(id) > 5) return 0; |
|
744
|
99126 |
0 |
return (i < N && j < N); |
|
|
99126 |
0 |
return (i < N && j < N); |
|
752
|
84582 |
77505 |
if (ax >= ay && ax >= az) { mag = ax; face = (x >= 0) ? 0 : 1; s = y / mag; t = z / mag; } |
|
|
53713 |
30869 |
if (ax >= ay && ax >= az) { mag = ax; face = (x >= 0) ? 0 : 1; s = y / mag; t = z / mag; } |
|
753
|
54256 |
54118 |
else if (ay >= az) { mag = ay; face = (y >= 0) ? 2 : 3; s = x / mag; t = z / mag; } |
|
|
27490 |
26766 |
else if (ay >= az) { mag = ay; face = (y >= 0) ? 2 : 3; s = x / mag; t = z / mag; } |
|
754
|
26979 |
27139 |
else { mag = az; face = (z >= 0) ? 4 : 5; s = x / mag; t = y / mag; } |
|
757
|
1 |
162086 |
if (!isfinite(u)) u = 0.0; /* dir==0 -> s,t NaN; keep defined */ |
|
758
|
1 |
162086 |
if (!isfinite(v)) v = 0.0; |
|
762
|
0 |
162087 |
if (i < 0) i = 0; else if (i >= N) i = N - 1; |
|
|
0 |
162087 |
if (i < 0) i = 0; else if (i >= N) i = N - 1; |
|
763
|
0 |
162087 |
if (j < 0) j = 0; else if (j >= N) j = N - 1; |
|
|
0 |
162087 |
if (j < 0) j = 0; else if (j >= N) j = N - 1; |
|
799
|
1 |
8000 |
if (level == 0) return 0; |
|
807
|
1 |
2000 |
if (level >= SPH_CUBE_MAX_LEVEL) return 0; |
|
811
|
8000 |
4000 |
for (int di = 0; di < 2; di++) for (int dj = 0; dj < 2; dj++) |
|
|
4000 |
2000 |
for (int di = 0; di < 2; di++) for (int dj = 0; dj < 2; dj++) |
|
831
|
120480 |
30120 |
for (int k = 0; k < 4; k++) { |
|
845
|
89 |
0 |
if (errbuf) errbuf[0] = '\0'; |
|
846
|
88 |
1 |
if (!(cell_size > 0) || !isfinite(cell_size)) { SPH_ERR("cell_size must be a finite number > 0"); return 0; } |
|
|
0 |
88 |
if (!(cell_size > 0) || !isfinite(cell_size)) { SPH_ERR("cell_size must be a finite number > 0"); return 0; } |
|
|
1 |
0 |
if (!(cell_size > 0) || !isfinite(cell_size)) { SPH_ERR("cell_size must be a finite number > 0"); return 0; } |
|
847
|
1 |
87 |
if (max_entries == 0) { SPH_ERR("max_entries must be > 0"); return 0; } |
|
|
1 |
0 |
if (max_entries == 0) { SPH_ERR("max_entries must be > 0"); return 0; } |
|
848
|
1 |
86 |
if (!sph_validate_world(world, cell_size, errbuf)) return 0; |
|
849
|
86 |
0 |
if (!(sphere_radius >= 0.0) || !isfinite(sphere_radius)) { SPH_ERR("sphere radius must be finite and >= 0"); return 0; } |
|
|
0 |
86 |
if (!(sphere_radius >= 0.0) || !isfinite(sphere_radius)) { SPH_ERR("sphere radius must be finite and >= 0"); return 0; } |
|
|
0 |
0 |
if (!(sphere_radius >= 0.0) || !isfinite(sphere_radius)) { SPH_ERR("sphere radius must be finite and >= 0"); return 0; } |
|
850
|
6 |
80 |
if (sphere_radius > 0.0 && world && (world[0] > 0.0 || world[1] > 0.0 || world[2] > 0.0)) { SPH_ERR("sphere and wrap are mutually exclusive"); return 0; } |
|
|
1 |
5 |
if (sphere_radius > 0.0 && world && (world[0] > 0.0 || world[1] > 0.0 || world[2] > 0.0)) { SPH_ERR("sphere and wrap are mutually exclusive"); return 0; } |
|
|
0 |
1 |
if (sphere_radius > 0.0 && world && (world[0] > 0.0 || world[1] > 0.0 || world[2] > 0.0)) { SPH_ERR("sphere and wrap are mutually exclusive"); return 0; } |
|
|
0 |
0 |
if (sphere_radius > 0.0 && world && (world[0] > 0.0 || world[1] > 0.0 || world[2] > 0.0)) { SPH_ERR("sphere and wrap are mutually exclusive"); return 0; } |
|
|
0 |
0 |
if (sphere_radius > 0.0 && world && (world[0] > 0.0 || world[1] > 0.0 || world[2] > 0.0)) { SPH_ERR("sphere and wrap are mutually exclusive"); return 0; } |
|
|
1 |
0 |
if (sphere_radius > 0.0 && world && (world[0] > 0.0 || world[1] > 0.0 || world[2] > 0.0)) { SPH_ERR("sphere and wrap are mutually exclusive"); return 0; } |
|
851
|
1 |
84 |
if (max_entries > SPH_MAX_CAPACITY) { SPH_ERR("max_entries too large (max %u)", SPH_MAX_CAPACITY); return 0; } |
|
|
1 |
0 |
if (max_entries > SPH_MAX_CAPACITY) { SPH_ERR("max_entries too large (max %u)", SPH_MAX_CAPACITY); return 0; } |
|
852
|
1 |
83 |
if (*num_buckets > SPH_MAX_CAPACITY) { SPH_ERR("num_buckets too large (max %u)", SPH_MAX_CAPACITY); return 0; } |
|
|
1 |
0 |
if (*num_buckets > SPH_MAX_CAPACITY) { SPH_ERR("num_buckets too large (max %u)", SPH_MAX_CAPACITY); return 0; } |
|
853
|
4 |
79 |
*num_buckets = sph_next_pow2(*num_buckets == 0 ? max_entries : *num_buckets); |
|
860
|
6 |
81 |
if (!sph_validate_create_args(max_entries, &num_buckets, cell_size, world, sphere_radius, errbuf)) return NULL; |
|
868
|
57 |
24 |
if (anonymous) { |
|
871
|
0 |
57 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
874
|
0 |
24 |
if (fd < 0) { SPH_ERR("open: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fd < 0) { SPH_ERR("open: %s", strerror(errno)); return NULL; } |
|
875
|
0 |
24 |
if (flock(fd, LOCK_EX) < 0) { SPH_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
|
|
0 |
0 |
if (flock(fd, LOCK_EX) < 0) { SPH_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
|
877
|
0 |
24 |
if (fstat(fd, &st) < 0) { SPH_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
|
0 |
0 |
if (fstat(fd, &st) < 0) { SPH_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
879
|
13 |
11 |
if (!is_new && (uint64_t)st.st_size < sizeof(SphHeader)) { |
|
|
1 |
12 |
if (!is_new && (uint64_t)st.st_size < sizeof(SphHeader)) { |
|
880
|
1 |
0 |
SPH_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
|
883
|
11 |
12 |
if (is_new && ftruncate(fd, (off_t)total) < 0) { |
|
|
0 |
11 |
if (is_new && ftruncate(fd, (off_t)total) < 0) { |
|
884
|
0 |
0 |
SPH_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
|
886
|
12 |
11 |
map_size = is_new ? (size_t)total : (size_t)st.st_size; |
|
888
|
0 |
23 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
889
|
12 |
11 |
if (!is_new) { |
|
890
|
5 |
7 |
if (!sph_validate_header((SphHeader *)base, (uint64_t)st.st_size)) { |
|
891
|
5 |
0 |
SPH_ERR("invalid spatial hash file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
|
898
|
11 |
57 |
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
|
905
|
0 |
2 |
if (!sph_validate_create_args(max_entries, &num_buckets, cell_size, world, sphere_radius, errbuf)) return NULL; |
|
908
|
2 |
0 |
int fd = memfd_create(name ? name : "sphash", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
|
909
|
0 |
2 |
if (fd < 0) { SPH_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fd < 0) { SPH_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
|
910
|
0 |
2 |
if (ftruncate(fd, (off_t)total) < 0) { |
|
911
|
0 |
0 |
SPH_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; |
|
915
|
0 |
2 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
|
921
|
2 |
0 |
if (errbuf) errbuf[0] = '\0'; |
|
923
|
0 |
2 |
if (fstat(fd, &st) < 0) { SPH_ERR("fstat: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fstat(fd, &st) < 0) { SPH_ERR("fstat: %s", strerror(errno)); return NULL; } |
|
924
|
0 |
2 |
if ((uint64_t)st.st_size < sizeof(SphHeader)) { SPH_ERR("too small"); return NULL; } |
|
|
0 |
0 |
if ((uint64_t)st.st_size < sizeof(SphHeader)) { SPH_ERR("too small"); return NULL; } |
|
927
|
0 |
2 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { SPH_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
928
|
0 |
2 |
if (!sph_validate_header((SphHeader *)base, (uint64_t)st.st_size)) { |
|
929
|
0 |
0 |
SPH_ERR("invalid spatial hash"); munmap(base, ms); return NULL; |
|
932
|
0 |
2 |
if (myfd < 0) { SPH_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
|
|
0 |
0 |
if (myfd < 0) { SPH_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
|
937
|
0 |
79 |
if (!h) return; |
|
938
|
1 |
78 |
if (h->notify_fd >= 0) close(h->notify_fd); |
|
939
|
4 |
75 |
if (h->backing_fd >= 0) close(h->backing_fd); |
|
940
|
79 |
0 |
if (h->hdr) munmap(h->hdr, h->mmap_size); |
|
946
|
9 |
0 |
if (!h || !h->hdr) return 0; |
|
|
0 |
9 |
if (!h || !h->hdr) return 0; |
|
951
|
1 |
1 |
if (h->notify_fd >= 0) return h->notify_fd; |
|
953
|
0 |
1 |
if (efd < 0) return -1; |
|
959
|
0 |
2 |
if (h->notify_fd < 0) return 0; |
|
965
|
1 |
2 |
if (h->notify_fd < 0) return -1; |
|
967
|
1 |
1 |
if (read(h->notify_fd, &v, sizeof(v)) != sizeof(v)) return -1; |
|
976
|
4 |
34435 |
if (idx >= h->hdr->max_entries) return 0; |
|
983
|
4 |
9902 |
if (idx == SPH_NONE) return SPH_NONE; |
|
1007
|
1978 |
8587 |
if (head != SPH_NONE) h->entries[head].prev = idx; |
|
1015
|
39 |
1086 |
if (p != SPH_NONE) h->entries[p].next = n; else h->buckets[b] = n; |
|
1016
|
31 |
1094 |
if (n != SPH_NONE) h->entries[n].prev = p; |
|
1026
|
4 |
9902 |
if (idx == SPH_NONE) return SPH_NONE; |
|
1036
|
1 |
462 |
if (!sph_is_live(h, idx)) return 0; |
|
1044
|
3 |
664 |
if (!sph_is_live(h, idx)) return 0; |
|
1048
|
1 |
663 |
if (sph_cell_eq(oc, nc)) { /* same cell: just rewrite pos */ |
|
1065
|
341 |
13439 |
if (c->n == c->cap) { |
|
1066
|
27 |
314 |
size_t nc = c->cap ? c->cap * 2 : 64; |
|
1068
|
0 |
341 |
if (!nv) return 0; |
|
1080
|
7013 |
17533 |
if (dims == 3) { double dz = sph_axis_delta(a[2], b[2], world[2]); d += dz*dz; } |
|
1092
|
188585 |
587347 |
for (uint32_t idx = h->buckets[b]; idx != SPH_NONE; idx = h->entries[idx].next) { |
|
1094
|
182603 |
5982 |
if (!sph_cell_eq(ec, C)) continue; /* collision / dedup guard */ |
|
1095
|
5958 |
24 |
if (accept && !accept(h->entries[idx].pos, ctx)) continue; |
|
|
1791 |
4167 |
if (accept && !accept(h->entries[idx].pos, ctx)) continue; |
|
1096
|
0 |
4191 |
if (!sph_collect_push(out, h->entries[idx].value)) return 0; |
|
1102
|
1 |
16 |
double pp[3] = { p[0], p[1], dims == 3 ? p[2] : 0.0 }; |
|
1112
|
201 |
0 |
if (pos[0] < q->lo[0] || pos[0] > q->hi[0]) return 0; |
|
|
29 |
172 |
if (pos[0] < q->lo[0] || pos[0] > q->hi[0]) return 0; |
|
1113
|
172 |
0 |
if (pos[1] < q->lo[1] || pos[1] > q->hi[1]) return 0; |
|
|
23 |
149 |
if (pos[1] < q->lo[1] || pos[1] > q->hi[1]) return 0; |
|
1114
|
81 |
68 |
if (q->dims == 3 && (pos[2] < q->lo[2] || pos[2] > q->hi[2])) return 0; |
|
|
81 |
0 |
if (q->dims == 3 && (pos[2] < q->lo[2] || pos[2] > q->hi[2])) return 0; |
|
|
16 |
65 |
if (q->dims == 3 && (pos[2] < q->lo[2] || pos[2] > q->hi[2])) return 0; |
|
1131
|
812 |
332 |
for (int i = 0; i < dims; i++) { |
|
1132
|
0 |
812 |
if (ch[i] < cl[i]) return SPH_Q_OK; /* empty box */ |
|
1134
|
32 |
780 |
if (h->wrap_cells[i] > 0 && span > (uint64_t)h->wrap_cells[i]) |
|
|
0 |
32 |
if (h->wrap_cells[i] > 0 && span > (uint64_t)h->wrap_cells[i]) |
|
1136
|
3 |
809 |
if (span >= (uint64_t)SPH_MAX_QUERY_CELLS) return SPH_Q_TOOBIG; |
|
1137
|
0 |
809 |
if (cells > (uint64_t)SPH_MAX_QUERY_CELLS / span) return SPH_Q_TOOBIG; |
|
1141
|
6253 |
332 |
for (int64_t i0 = 0; i0 < cnt[0]; i0++) { |
|
1142
|
61 |
6192 |
C[0] = h->wrap ? sph_wrap_cell(cl[0] + i0, h->wrap_cells[0]) : cl[0] + i0; |
|
1143
|
336377 |
6253 |
for (int64_t i1 = 0; i1 < cnt[1]; i1++) { |
|
1144
|
283 |
336094 |
C[1] = h->wrap ? sph_wrap_cell(cl[1] + i1, h->wrap_cells[1]) : cl[1] + i1; |
|
1145
|
18850 |
317527 |
if (dims == 3) { |
|
1146
|
269803 |
18850 |
for (int64_t i2 = 0; i2 < cnt[2]; i2++) { |
|
1147
|
128 |
269675 |
C[2] = h->wrap ? sph_wrap_cell(cl[2] + i2, h->wrap_cells[2]) : cl[2] + i2; |
|
1148
|
0 |
269803 |
if (!sph_walk_cell(h, C, out, accept, ctx)) return SPH_Q_OOM; |
|
1152
|
0 |
317527 |
if (!sph_walk_cell(h, C, out, accept, ctx)) return SPH_Q_OOM; |
|
1161
|
3 |
9 |
struct sph_box q = { { lo[0], lo[1], dims==3?lo[2]:0 }, { hi[0], hi[1], dims==3?hi[2]:0 }, dims }; |
|
|
3 |
9 |
struct sph_box q = { { lo[0], lo[1], dims==3?lo[2]:0 }, { hi[0], hi[1], dims==3?hi[2]:0 }, dims }; |
|
1166
|
142 |
181 |
struct sph_disk q = { { c[0], c[1], dims==3?c[2]:0 }, r*r, dims, h->world }; |
|
1167
|
142 |
181 |
double lo[3] = { c[0]-r, c[1]-r, (dims==3?c[2]-r:0) }; |
|
1168
|
142 |
181 |
double hi[3] = { c[0]+r, c[1]+r, (dims==3?c[2]+r:0) }; |
|
1182
|
293 |
2078 |
if (*n < k) { |
|
1185
|
123 |
234 |
while (i) { uint32_t p = (i-1)/2; if (heap[p].d2 >= heap[i].d2) break; |
|
|
357 |
170 |
while (i) { uint32_t p = (i-1)/2; if (heap[p].d2 >= heap[i].d2) break; |
|
1187
|
2078 |
0 |
} else if (k && d2 < heap[0].d2) { |
|
|
177 |
1901 |
} else if (k && d2 < heap[0].d2) { |
|
1191
|
314 |
65 |
if (lheap[m].d2) m=l; |
|
|
163 |
151 |
if (lheap[m].d2) m=l; |
|
1192
|
267 |
112 |
if (rheap[m].d2) m=r; |
|
|
79 |
188 |
if (rheap[m].d2) m=r; |
|
1193
|
177 |
202 |
if (m==i) break; sph_cand_t t=heap[m]; heap[m]=heap[i]; heap[i]=t; i=m; } |
|
1198
|
86 |
353 |
return (x < y) ? -1 : (x > y) ? 1 : 0; |
|
1208
|
185108 |
1086357 |
for (uint32_t idx = h->buckets[b]; idx != SPH_NONE; idx = h->entries[idx].next) { |
|
1210
|
184237 |
871 |
if (!sph_cell_eq(ec, C)) continue; |
|
1217
|
25 |
31 |
double cc[3] = { c[0], c[1], dims==3 ? c[2] : 0 }; |
|
1219
|
2 |
54 |
if (k > total) k = total; /* can never return more than exist */ |
|
1220
|
1 |
55 |
if (k == 0) return 1; /* empty hash (or k clamped to 0): empty result */ |
|
1222
|
0 |
55 |
if (!heap) return 0; |
|
1225
|
4 |
51 |
if (h->wrap) { |
|
1230
|
15000 |
4 |
for (uint32_t idx = 0; idx < me; idx++) |
|
1231
|
1500 |
13500 |
if (sph_is_live(h, idx)) |
|
1245
|
522 |
0 |
for (int64_t g = 0; g < INT32_MAX; g++) { |
|
1257
|
51 |
471 |
if (g == 0) { |
|
1258
|
0 |
51 |
SPH_KNN_PROCESS(cx, cy, cz); |
|
1259
|
122 |
349 |
} else if (dims == 2) { |
|
1260
|
3024 |
122 |
for (int64_t dx = -g; dx <= g; dx++) { /* top + bottom rows */ |
|
1261
|
0 |
3024 |
SPH_KNN_PROCESS(cx + dx, cy - g, cz); |
|
1262
|
0 |
3024 |
SPH_KNN_PROCESS(cx + dx, cy + g, cz); |
|
1264
|
2780 |
122 |
for (int64_t dy = -g + 1; dy <= g - 1; dy++) { /* left + right cols */ |
|
1265
|
0 |
2780 |
SPH_KNN_PROCESS(cx - g, cy + dy, cz); |
|
1266
|
0 |
2780 |
SPH_KNN_PROCESS(cx + g, cy + dy, cz); |
|
1269
|
698 |
349 |
for (int64_t dz = -g; dz <= g; dz += 2 * g) { /* two z caps (full faces) */ |
|
1270
|
14098 |
698 |
for (int64_t dx = -g; dx <= g; dx++) |
|
1271
|
385498 |
14098 |
for (int64_t dy = -g; dy <= g; dy++) |
|
1272
|
0 |
385498 |
SPH_KNN_PROCESS(cx + dx, cy + dy, cz + dz); |
|
1274
|
6351 |
349 |
for (int64_t dz = -g + 1; dz <= g - 1; dz++) { /* middle layers: xy perimeter */ |
|
1275
|
178651 |
6351 |
for (int64_t dx = -g; dx <= g; dx++) { |
|
1276
|
0 |
178651 |
SPH_KNN_PROCESS(cx + dx, cy - g, cz + dz); |
|
1277
|
0 |
178651 |
SPH_KNN_PROCESS(cx + dx, cy + g, cz + dz); |
|
1279
|
165949 |
6351 |
for (int64_t dy = -g + 1; dy <= g - 1; dy++) { |
|
1280
|
0 |
165949 |
SPH_KNN_PROCESS(cx - g, cy + dy, cz + dz); |
|
1281
|
0 |
165949 |
SPH_KNN_PROCESS(cx + g, cy + dy, cz + dz); |
|
1288
|
143 |
379 |
if (n >= k) { double bound = (double)g * cs; if (bound*bound >= heap[0].d2) break; } |
|
|
49 |
94 |
if (n >= k) { double bound = (double)g * cs; if (bound*bound >= heap[0].d2) break; } |
|
1290
|
2 |
471 |
if (seen >= total) break; |
|
1294
|
293 |
55 |
for (uint32_t i = 0; i < n; i++) |
|
1295
|
0 |
293 |
if (!sph_collect_push(out, heap[i].val)) { free(heap); return 0; } |
|
1309
|
4648 |
0 |
return sph_collect_push(c, va) && sph_collect_push(c, vb); |
|
|
4648 |
0 |
return sph_collect_push(c, va) && sph_collect_push(c, vb); |
|
1324
|
9300 |
10 |
for (uint32_t i = 0; i < me; i++) { |
|
1325
|
7644 |
1656 |
if (!sph_is_live(h, i)) continue; |
|
1326
|
454 |
1202 |
if (collide && h->entries[i].radius > maxr) maxr = h->entries[i].radius; |
|
|
13 |
441 |
if (collide && h->entries[i].radius > maxr) maxr = h->entries[i].radius; |
|
1327
|
700 |
956 |
if (h->entries[i].pos[2] != 0.0) has3d = 1; |
|
1329
|
4 |
6 |
if (collide) { if (maxr <= 0.0) return SPH_Q_OK; } /* no radii -> points never collide */ |
|
|
1 |
3 |
if (collide) { if (maxr <= 0.0) return SPH_Q_OK; } /* no radii -> points never collide */ |
|
1330
|
1 |
5 |
else if (!(fixed_r > 0.0)) return SPH_Q_OK; /* non-positive radius -> nothing */ |
|
1331
|
7 |
1 |
int dims = (h->world[2] > 0.0 || has3d) ? 3 : 2; |
|
|
2 |
5 |
int dims = (h->world[2] > 0.0 || has3d) ? 3 : 2; |
|
1332
|
8200 |
8 |
for (uint32_t a = 0; a < me; a++) { |
|
1333
|
6796 |
1404 |
if (!sph_is_live(h, a)) continue; |
|
1336
|
452 |
952 |
double reach_d = ceil((collide ? (ra + maxr) : fixed_r) / cs); |
|
1339
|
0 |
1404 |
if (!(reach_d >= 0)) reach_d = 0; |
|
1340
|
0 |
1404 |
if (reach_d >= (double)SPH_MAX_QUERY_CELLS) return SPH_Q_TOOBIG; /* avoid int64 overflow */ |
|
1345
|
3508 |
1404 |
for (int i = 0; i < dims; i++) { |
|
1347
|
1300 |
2208 |
if (h->wrap_cells[i] > 0 && span > (uint64_t)h->wrap_cells[i]) span = (uint64_t)h->wrap_cells[i]; |
|
|
0 |
1300 |
if (h->wrap_cells[i] > 0 && span > (uint64_t)h->wrap_cells[i]) span = (uint64_t)h->wrap_cells[i]; |
|
1348
|
0 |
3508 |
if (span >= (uint64_t)SPH_MAX_QUERY_CELLS) return SPH_Q_TOOBIG; |
|
1349
|
0 |
3508 |
if (cells > (uint64_t)SPH_MAX_QUERY_CELLS / span) return SPH_Q_TOOBIG; |
|
1353
|
9800 |
1404 |
for (int64_t i0 = 0; i0 < cnt[0]; i0++) { |
|
1354
|
1900 |
7900 |
int64_t C0 = h->wrap ? sph_wrap_cell(b0+i0, h->wrap_cells[0]) : b0+i0; |
|
1355
|
85124 |
9800 |
for (int64_t i1 = 0; i1 < cnt[1]; i1++) { |
|
1356
|
7700 |
77424 |
int64_t C1 = h->wrap ? sph_wrap_cell(b1+i1, h->wrap_cells[1]) : b1+i1; |
|
1357
|
329146 |
85124 |
for (int64_t i2 = 0; i2 < cnt[2]; i2++) { /* cnt[2]==1 when dims==2 */ |
|
1358
|
273914 |
55232 |
int64_t C2 = (dims == 3) ? (h->wrap ? sph_wrap_cell(b2+i2, h->wrap_cells[2]) : b2+i2) : 0; |
|
|
8100 |
265814 |
int64_t C2 = (dims == 3) ? (h->wrap ? sph_wrap_cell(b2+i2, h->wrap_cells[2]) : b2+i2) : 0; |
|
1361
|
95944 |
329146 |
for (uint32_t idx = h->buckets[bkt]; idx != SPH_NONE; idx = h->entries[idx].next) { |
|
1362
|
48923 |
47021 |
if (idx <= a) continue; /* unordered: emit each pair once */ |
|
1364
|
30603 |
16418 |
if (!sph_cell_eq(ec, C)) continue; /* hash-collision guard */ |
|
1365
|
11501 |
4917 |
double thr = collide ? (ra + h->entries[idx].radius) : fixed_r; |
|
1366
|
4648 |
11770 |
if (sph_dist2(h, pa, h->entries[idx].pos, dims) < thr*thr) |
|
1367
|
0 |
4648 |
if (!emit(h->entries[a].value, h->entries[idx].value, ctx)) return SPH_Q_OOM; |
|
1382
|
1024 |
1 |
for (uint32_t b = 0; b < nb; b++) h->buckets[b] = SPH_NONE; |
|
1384
|
999 |
1 |
for (uint32_t i = 0; i < me; i++) h->entries[i].next = (i+1 < me) ? i+1 : SPH_NONE; |
|
|
1000 |
1 |
for (uint32_t i = 0; i < me; i++) h->entries[i].next = (i+1 < me) ? i+1 : SPH_NONE; |
|
1391
|
1286 |
7 |
for (uint32_t b = 0; b < nb; b++) { |
|
1393
|
1622 |
1286 |
for (uint32_t idx = h->buckets[b]; idx != SPH_NONE; idx = h->entries[idx].next) { |
|
1399
|
480452 |
1622 |
for (uint32_t j = h->buckets[b]; j != SPH_NONE; j = h->entries[j].next) { |
|
1401
|
1650 |
478802 |
if (sph_cell_eq(ci, cj)) cc++; |
|
1403
|
7 |
1615 |
if (cc > mxc) mxc = cc; |
|
1405
|
19 |
1267 |
if (len) { occ++; if (len > mx) mx = len; } |
|
|
7 |
12 |
if (len) { occ++; if (len > mx) mx = len; } |