| line |
true |
false |
branch |
|
171
|
0 |
0 |
if (pid == 0) return 1; /* no owner recorded, assume alive */ |
|
172
|
0 |
0 |
return !(kill((pid_t)pid, 0) == -1 && errno == ESRCH); |
|
|
0 |
0 |
return !(kill((pid_t)pid, 0) == -1 && errno == ESRCH); |
|
182
|
0 |
0 |
if (!__atomic_compare_exchange_n(&hdr->rwlock, &observed_rwlock, |
|
188
|
0 |
0 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
212
|
62530 |
39 |
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) |
|
|
62530 |
0 |
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) |
|
223
|
42 |
0 |
for (uint32_t i = 0; i < RB_READER_SLOTS; i++) { |
|
226
|
39 |
3 |
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, |
|
246
|
0 |
0 |
if (!sub) return; |
|
249
|
0 |
0 |
uint32_t want = (cur > sub) ? cur - sub : 0; |
|
250
|
0 |
0 |
if (__atomic_compare_exchange_n(p, &cur, want, |
|
268
|
0 |
0 |
if (!__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, 0, |
|
273
|
0 |
0 |
if (wp) rb_atomic_sub_cap(&hdr->rwlock_waiters, wp); |
|
274
|
0 |
0 |
if (writp) rb_atomic_sub_cap(&hdr->rwlock_writers_waiting, writp); |
|
284
|
0 |
0 |
if (!h->reader_slots) return; |
|
294
|
0 |
0 |
for (uint32_t i = 0; i < RB_READER_SLOTS; i++) { |
|
296
|
0 |
0 |
if (pid == 0) continue; |
|
298
|
0 |
0 |
if (rb_pid_alive(pid)) { |
|
299
|
0 |
0 |
if (sc > 0) any_live_reader = 1; |
|
302
|
0 |
0 |
if (sc > 0) { found_dead_reader = 1; continue; } |
|
309
|
0 |
0 |
if (found_dead_reader && !any_live_reader) { |
|
|
0 |
0 |
if (found_dead_reader && !any_live_reader) { |
|
311
|
0 |
0 |
if (cur > 0 && cur < RB_RWLOCK_WRITER_BIT) { |
|
|
0 |
0 |
if (cur > 0 && cur < RB_RWLOCK_WRITER_BIT) { |
|
312
|
0 |
0 |
if (__atomic_compare_exchange_n(&hdr->rwlock, &cur, 0, |
|
314
|
0 |
0 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
318
|
0 |
0 |
for (uint32_t i = 0; i < RB_READER_SLOTS; i++) { |
|
320
|
0 |
0 |
if (pid == 0 || rb_pid_alive(pid)) continue; |
|
|
0 |
0 |
if (pid == 0 || rb_pid_alive(pid)) continue; |
|
332
|
0 |
0 |
if (val >= RB_RWLOCK_WRITER_BIT) { |
|
334
|
0 |
0 |
if (!rb_pid_alive(pid)) |
|
345
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
351
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
355
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) { |
|
365
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) { |
|
379
|
12904 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
385
|
0 |
12904 |
if (cur > 0 && cur < RB_RWLOCK_WRITER_BIT) { |
|
|
0 |
0 |
if (cur > 0 && cur < RB_RWLOCK_WRITER_BIT) { |
|
386
|
0 |
0 |
if (__atomic_compare_exchange_n(lock, &cur, cur + 1, |
|
389
|
12904 |
0 |
} else if (cur == 0 && !__atomic_load_n(writers_waiting, __ATOMIC_RELAXED)) { |
|
|
12904 |
0 |
} else if (cur == 0 && !__atomic_load_n(writers_waiting, __ATOMIC_RELAXED)) { |
|
390
|
12904 |
0 |
if (__atomic_compare_exchange_n(lock, &cur, 1, |
|
394
|
0 |
0 |
if (__builtin_expect(spin < RB_RWLOCK_SPIN_LIMIT, 1)) { |
|
400
|
0 |
0 |
if (cur >= RB_RWLOCK_WRITER_BIT || cur == 0) { |
|
|
0 |
0 |
if (cur >= RB_RWLOCK_WRITER_BIT || cur == 0) { |
|
403
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
420
|
12904 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
422
|
12904 |
0 |
if (after == 0 && __atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
|
0 |
12904 |
if (after == 0 && __atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
435
|
49665 |
0 |
if (__atomic_compare_exchange_n(lock, &expected, mypid, |
|
438
|
0 |
0 |
if (__builtin_expect(spin < RB_RWLOCK_SPIN_LIMIT, 1)) { |
|
444
|
0 |
0 |
if (cur != 0) { |
|
447
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
462
|
0 |
49665 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
525
|
1 |
453 |
if (hdr->free_head) { |
|
529
|
453 |
0 |
} else if (hdr->container_used < hdr->container_cap) { |
|
552
|
6144 |
6 |
for (uint32_t w = 0; w < 1024; w++) c += (uint64_t)__builtin_popcountll(bits[w]); |
|
561
|
765144 |
76689 |
while (lo_i < hi_i) { |
|
563
|
562729 |
202415 |
if (vals[mid] < lo) lo_i = mid + 1; |
|
567
|
37731 |
38958 |
return (lo_i < card && vals[lo_i] == lo); |
|
|
1692 |
36039 |
return (lo_i < card && vals[lo_i] == lo); |
|
586
|
53248 |
13 |
for (uint32_t i = 0; i < card; i++) { |
|
601
|
454 |
83244 |
if (bt->type == RB_TYPE_NONE) { |
|
610
|
71969 |
11275 |
if (bt->type == RB_TYPE_ARRAY) { |
|
613
|
13 |
71956 |
if (rb_array_search(vals, bt->cardinality, lo, &pos)) return 0; |
|
618
|
13 |
71943 |
if (bt->cardinality >= RB_ARRAY_MAX) { |
|
637
|
0 |
11275 |
if (bits[w] & b) return 0; |
|
650
|
38 |
12746 |
if (bt->type == RB_TYPE_NONE) return 0; |
|
651
|
4718 |
8028 |
if (bt->type == RB_TYPE_ARRAY) { |
|
668
|
1 |
5003 |
if (bt->type == RB_TYPE_NONE) return 0; |
|
669
|
2 |
5001 |
if (bt->type == RB_TYPE_ARRAY) { |
|
672
|
0 |
2 |
if (!rb_array_search(vals, bt->cardinality, lo, &pos)) return 0; |
|
676
|
1 |
1 |
if (bt->cardinality == 0) { |
|
687
|
1 |
5000 |
if (!(bits[w] & b)) return 0; |
|
691
|
1 |
4999 |
if (bt->cardinality == 0) { |
|
715
|
65543 |
1 |
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { |
|
716
|
65536 |
7 |
if (bt[hi].type == RB_TYPE_NONE) continue; |
|
717
|
4 |
3 |
if (bt[hi].type == RB_TYPE_ARRAY) { |
|
723
|
3 |
0 |
for (uint32_t w = 0; w < 1024; w++) { |
|
724
|
3 |
0 |
if (bits[w]) { |
|
738
|
458525 |
1 |
for (uint32_t hi = RB_NUM_BUCKETS; hi-- > 0; ) { |
|
739
|
458518 |
7 |
if (bt[hi].type == RB_TYPE_NONE) continue; |
|
740
|
5 |
2 |
if (bt[hi].type == RB_TYPE_ARRAY) { |
|
746
|
1892 |
0 |
for (uint32_t w = 1024; w-- > 0; ) { |
|
747
|
2 |
1890 |
if (bits[w]) { |
|
762
|
786432 |
12 |
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) |
|
763
|
228 |
786204 |
if (bt[hi].type != RB_TYPE_NONE) n++; |
|
778
|
3 |
1 |
if (bbt->type == RB_TYPE_ARRAY) { |
|
780
|
4022 |
3 |
for (uint32_t i = 0; i < bbt->cardinality; i++) { |
|
786
|
1024 |
1 |
for (uint32_t w = 0; w < 1024; w++) abits[w] |= bb[w]; |
|
797
|
458752 |
7 |
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { |
|
798
|
130 |
458622 |
if (bbt[hi].type != RB_TYPE_NONE && abt[hi].type == RB_TYPE_NONE) need++; |
|
|
2 |
128 |
if (bbt[hi].type != RB_TYPE_NONE && abt[hi].type == RB_TYPE_NONE) need++; |
|
806
|
720896 |
11 |
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) |
|
807
|
194 |
720702 |
if (abt[hi].type != RB_TYPE_NONE) total += abt[hi].cardinality; |
|
816
|
393216 |
6 |
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { |
|
817
|
393089 |
127 |
if (bbt[hi].type == RB_TYPE_NONE) continue; |
|
819
|
0 |
127 |
if (abt[hi].type == RB_TYPE_NONE) { |
|
829
|
123 |
4 |
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) { |
|
|
122 |
1 |
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) { |
|
836
|
10462 |
122 |
while (ai < ac && bi < bc) { |
|
|
10462 |
0 |
while (ai < ac && bi < bc) { |
|
838
|
3787 |
6675 |
if (x < y) { tmp[n++] = x; ai++; } |
|
839
|
3666 |
3009 |
else if (x > y) { tmp[n++] = y; bi++; } |
|
842
|
0 |
122 |
while (ai < ac) tmp[n++] = av[ai++]; |
|
843
|
124 |
122 |
while (bi < bc) tmp[n++] = bv[bi++]; |
|
844
|
120 |
2 |
if (n <= RB_ARRAY_MAX) { |
|
850
|
9026 |
2 |
for (uint32_t i = 0; i < n; i++) bits[tmp[i] >> 6] |= (uint64_t)1 << (tmp[i] & 63); |
|
857
|
1 |
4 |
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) { |
|
|
1 |
0 |
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) { |
|
866
|
1 |
1 |
for (uint32_t i = 0; i < ac; i++) abits[tmp[i] >> 6] |= (uint64_t)1 << (tmp[i] & 63); |
|
887
|
327680 |
5 |
for (uint32_t hi = 0; hi < RB_NUM_BUCKETS; hi++) { |
|
888
|
327554 |
126 |
if (abt[hi].type == RB_TYPE_NONE) continue; |
|
890
|
0 |
126 |
if (bbt[hi].type == RB_TYPE_NONE) { |
|
898
|
122 |
4 |
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) { |
|
|
121 |
1 |
if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_ARRAY) { |
|
905
|
6007 |
62 |
while (ai < ac && bi < bc) { |
|
|
5948 |
59 |
while (ai < ac && bi < bc) { |
|
907
|
2222 |
3726 |
if (x < y) ai++; |
|
908
|
1833 |
1893 |
else if (x > y) bi++; |
|
914
|
1 |
4 |
else if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) { |
|
|
1 |
0 |
else if (abt[hi].type == RB_TYPE_ARRAY && bbt[hi].type == RB_TYPE_BITMAP) { |
|
919
|
1 |
1 |
for (uint32_t i = 0; i < abt[hi].cardinality; i++) { |
|
921
|
1 |
0 |
if ((bb[lo >> 6] >> (lo & 63)) & 1) av[n++] = lo; |
|
925
|
4 |
0 |
else if (abt[hi].type == RB_TYPE_BITMAP && bbt[hi].type == RB_TYPE_ARRAY) { |
|
|
3 |
1 |
else if (abt[hi].type == RB_TYPE_BITMAP && bbt[hi].type == RB_TYPE_ARRAY) { |
|
933
|
5020 |
3 |
for (uint32_t i = 0; i < bbt[hi].cardinality; i++) { |
|
935
|
4011 |
1009 |
if ((abits[lo >> 6] >> (lo & 63)) & 1) tmp[n++] = lo; |
|
945
|
1024 |
1 |
for (uint32_t w = 0; w < 1024; w++) abits[w] &= bb[w]; |
|
950
|
59 |
67 |
if (abt[hi].cardinality == 0) { |
|
967
|
46 |
0 |
if (errbuf) errbuf[0] = '\0'; |
|
968
|
2 |
44 |
if (container_cap < 1) { RB_ERR("container_capacity must be >= 1"); return 0; } |
|
|
2 |
0 |
if (container_cap < 1) { RB_ERR("container_capacity must be >= 1"); return 0; } |
|
969
|
1 |
43 |
if (container_cap > RB_MAX_CONTAINERS) { RB_ERR("container_capacity must be <= %u", (unsigned)RB_MAX_CONTAINERS); return 0; } |
|
|
1 |
0 |
if (container_cap > RB_MAX_CONTAINERS) { RB_ERR("container_capacity must be <= %u", (unsigned)RB_MAX_CONTAINERS); return 0; } |
|
985
|
0 |
40 |
if (r != (ssize_t)sizeof id) { |
|
991
|
0 |
40 |
if (id == 0) id = 0x9E3779B97F4A7C15ull; /* never 0 */ |
|
1020
|
0 |
43 |
if (!h) { |
|
1022
|
0 |
0 |
if (backing_fd >= 0) close(backing_fd); |
|
1029
|
6 |
37 |
h->path = path ? strdup(path) : NULL; |
|
1038
|
0 |
3 |
if (hdr->magic != RB_MAGIC) return 0; |
|
1039
|
0 |
3 |
if (hdr->version != RB_VERSION) return 0; |
|
1040
|
0 |
3 |
if (hdr->bitmap_id == 0) return 0; /* identity must have been set at create */ |
|
1041
|
3 |
0 |
if (hdr->container_cap < 1 || hdr->container_cap > RB_MAX_CONTAINERS) return 0; |
|
|
0 |
3 |
if (hdr->container_cap < 1 || hdr->container_cap > RB_MAX_CONTAINERS) return 0; |
|
1042
|
0 |
3 |
if (hdr->total_size != file_size) return 0; |
|
1043
|
0 |
3 |
if (hdr->total_size != rb_total_size(hdr->container_cap)) return 0; |
|
1045
|
0 |
3 |
if (hdr->reader_slots_off != L.reader_slots) return 0; |
|
1046
|
0 |
3 |
if (hdr->bucket_table_off != L.bucket_table) return 0; |
|
1047
|
0 |
3 |
if (hdr->container_pool_off != L.container_pool) return 0; |
|
1048
|
3 |
0 |
if (hdr->container_used < 1 || hdr->container_used > hdr->container_cap) return 0; |
|
|
0 |
3 |
if (hdr->container_used < 1 || hdr->container_used > hdr->container_cap) return 0; |
|
1049
|
0 |
3 |
if (hdr->free_head >= hdr->container_cap) return 0; |
|
1050
|
0 |
3 |
if (hdr->free_count > hdr->container_cap) return 0; |
|
1055
|
2 |
41 |
if (!rb_validate_create_args(container_cap_in, errbuf)) return NULL; |
|
1064
|
34 |
7 |
if (anonymous) { |
|
1067
|
0 |
34 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
1070
|
0 |
7 |
if (fd < 0) { RB_ERR("open: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fd < 0) { RB_ERR("open: %s", strerror(errno)); return NULL; } |
|
1071
|
0 |
7 |
if (flock(fd, LOCK_EX) < 0) { RB_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
|
|
0 |
0 |
if (flock(fd, LOCK_EX) < 0) { RB_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
|
1073
|
0 |
7 |
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
|
0 |
0 |
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
1075
|
3 |
4 |
if (!is_new && (uint64_t)st.st_size < sizeof(RbHeader)) { |
|
|
1 |
2 |
if (!is_new && (uint64_t)st.st_size < sizeof(RbHeader)) { |
|
1076
|
1 |
0 |
RB_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
|
1079
|
4 |
2 |
if (is_new && ftruncate(fd, (off_t)total) < 0) { |
|
|
0 |
4 |
if (is_new && ftruncate(fd, (off_t)total) < 0) { |
|
1080
|
0 |
0 |
RB_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
|
1082
|
2 |
4 |
map_size = is_new ? (size_t)total : (size_t)st.st_size; |
|
1084
|
0 |
6 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
1085
|
2 |
4 |
if (!is_new) { |
|
1086
|
0 |
2 |
if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) { |
|
1087
|
0 |
0 |
RB_ERR("invalid roaring-bitmap file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
|
1094
|
4 |
34 |
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
|
1099
|
1 |
2 |
if (!rb_validate_create_args(container_cap_in, errbuf)) return NULL; |
|
1103
|
1 |
1 |
int fd = memfd_create(name ? name : "roaring", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
|
1104
|
0 |
2 |
if (fd < 0) { RB_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fd < 0) { RB_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
|
1105
|
0 |
2 |
if (ftruncate(fd, (off_t)total) < 0) { |
|
1106
|
0 |
0 |
RB_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; |
|
1110
|
0 |
2 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
|
1116
|
2 |
0 |
if (errbuf) errbuf[0] = '\0'; |
|
1118
|
0 |
2 |
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fstat(fd, &st) < 0) { RB_ERR("fstat: %s", strerror(errno)); return NULL; } |
|
1119
|
1 |
1 |
if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("too small"); return NULL; } |
|
|
1 |
0 |
if ((uint64_t)st.st_size < sizeof(RbHeader)) { RB_ERR("too small"); return NULL; } |
|
1122
|
0 |
1 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { RB_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
1123
|
0 |
1 |
if (!rb_validate_header((RbHeader *)base, (uint64_t)st.st_size)) { |
|
1124
|
0 |
0 |
RB_ERR("invalid roaring-bitmap file"); munmap(base, ms); return NULL; |
|
1127
|
0 |
1 |
if (myfd < 0) { RB_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
|
|
0 |
0 |
if (myfd < 0) { RB_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
|
1132
|
0 |
43 |
if (!h) return; |
|
1133
|
3 |
40 |
if (h->backing_fd >= 0) close(h->backing_fd); |
|
1134
|
43 |
0 |
if (h->base) munmap(h->base, h->mmap_size); |
|
1140
|
2 |
0 |
if (!h || !h->base) return 0; |
|
|
0 |
2 |
if (!h || !h->base) return 0; |