GCC Code Coverage Report

ernie/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
133 / 159
83.6%
Branches:
93 / 154
60.4%
Functions:
15 / 15, 1 excl
100.0%
util/hash_index.h
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 /// @file hash_index.h
3 /// @brief An open-addressed index of 32-bit ids whose keys live with their owner.
4 #pragma once
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <cstdint>
9 #include <limits>
10 #include <optional>
11 #include <vector>
12
13 namespace ernie {
14
15 /// @brief Finds ids by hash, testing candidates with the owner's own equality, so the index holds
16 /// no keys and a lookup touches one flat array (linear probing, at most half full).
17
2/4
✗ Branch 2 not taken.
✓ Branch 3 taken 1 time.
✓ Branch 3 taken 272 times.
✗ Branch 4 not taken.
 547 class HashIndex {
18 public:
19 /// @return The id `equal` accepts among those with `hash`, if any.
20 template <typename Equal>
21 34166 std::optional<std::uint32_t> Find(std::uint64_t hash, const Equal& equal) const {
22
7/14
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5} const&) const:
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1000 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 5370 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 27792 times.
 34166 if (slots_.empty()) {
23 1 return std::nullopt;
24 }
25 34165 const std::uint32_t tag = Tag(hash);
26 41276 for (std::size_t i = tag & Mask();; i = (i + 1) & Mask()) {
27
7/14
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5} const&) const:
✗ Branch 0 not taken.
✗ Branch 1 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1504 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 7281 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✓ Branch 0 taken 393 times.
✓ Branch 1 taken 32094 times.
 41276 const Slot& slot = slots_[i];
28
7/14
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5} const&) const:
✗ Branch 0 not taken.
✗ Branch 1 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 1504 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 7281 times.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✓ Branch 0 taken 393 times.
✓ Branch 1 taken 32094 times.
 41276 if (slot.id == kEmpty) {
29 394 return std::nullopt;
30 }
31
14/26
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#3} const&) const:
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 1 time.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5}>(unsigned long, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#5} const&) const:
✗ Branch 0 not taken.
✗ Branch 1 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#2} const&) const:
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 504 times.
✓ Branch 2 taken 1000 times.
✗ Branch 3 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4}>(unsigned long, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#4} const&) const:
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}::operator()(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✓ Branch 0 taken 5370 times.
✓ Branch 1 taken 1911 times.
✓ Branch 2 taken 5370 times.
✗ Branch 3 not taken.
std::optional<unsigned int> ernie::HashIndex::Find<ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1}>(unsigned long, ernie::TokenTable::Find(std::basic_string_view<char, std::char_traits<char> >) const::{lambda(unsigned int)#1} const&) const:
✓ Branch 0 taken 27399 times.
✓ Branch 1 taken 4695 times.
✓ Branch 3 taken 27399 times.
✗ Branch 4 not taken.
 40882 if (slot.tag == tag && equal(slot.id)) {
32 33771 return slot.id;
33 }
34 }
35 }
36
37 /// @return The id `equal` accepts among those with `hash`, or `id` once added.
38 template <typename Equal>
39 33028 std::uint32_t Insert(std::uint64_t hash, std::uint32_t id, const Equal& equal) {
40
9/12
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1} const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2} const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 992 times.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3} const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 318 times.
✓ Branch 1 taken 3904 times.
unsigned int ernie::HashIndex::Insert<ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 868 times.
✓ Branch 1 taken 26935 times.
 33028 if (2 * (size_ + 1) > slots_.size()) {
41
6/12
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1} const&):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2} const&):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3} const&):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
unsigned int ernie::HashIndex::Insert<ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 257 times.
unsigned int ernie::HashIndex::Insert<ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 596 times.
✓ Branch 1 taken 272 times.
 1858 Rehash(std::max<std::size_t>(16, 2 * slots_.size()));
42 }
43 33028 const std::uint32_t tag = Tag(hash);
44 43978 for (std::size_t i = tag & Mask();; i = (i + 1) & Mask()) {
45
10/12
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2} const&):
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 902 times.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3} const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 3263 times.
✓ Branch 1 taken 2897 times.
unsigned int ernie::HashIndex::Insert<ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 10818 times.
✓ Branch 1 taken 25094 times.
 43978 Slot& slot = slots_[i];
46
10/12
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2} const&):
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 902 times.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3} const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 3263 times.
✓ Branch 1 taken 2897 times.
unsigned int ernie::HashIndex::Insert<ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 10818 times.
✓ Branch 1 taken 25094 times.
 43978 if (slot.id == kEmpty) {
47 15083 slot = {tag, id};
48 15083 ++size_;
49 15082 return id;
50 }
51
11/20
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_CollidingHashesAreToldApartByTheOwner_Test::TestBody()::{lambda(unsigned int)#2} const&):
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#1} const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 902 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
unsigned int ernie::HashIndex::Insert<ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3}>(unsigned long, unsigned int, ernie::(anonymous namespace)::HashIndex_FindsIdsThroughTheOwnersKeysAcrossRehashes_Test::TestBody()::{lambda(unsigned int)#3} const&):
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 time.
unsigned int ernie::HashIndex::Insert<ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::PathTable::Child(unsigned int, unsigned int)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 959 times.
✓ Branch 1 taken 1938 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 959 times.
unsigned int ernie::HashIndex::Insert<ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1}>(unsigned long, unsigned int, ernie::TokenTable::Intern(std::basic_string_view<char, std::char_traits<char> >)::{lambda(unsigned int)#1} const&):
✓ Branch 0 taken 16985 times.
✓ Branch 1 taken 8109 times.
✓ Branch 3 taken 16985 times.
✗ Branch 4 not taken.
 28895 if (slot.tag == tag && equal(slot.id)) {
52 16985 return slot.id;
53 }
54 }
55 }
56
57 /// Makes room for `count` ids without rehashing.
58 1 void Reserve(std::size_t count) {
59 1 std::size_t slots = 16;
60
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
 1 while (slots < 2 * count) {
61 ✗ slots *= 2;
62 }
63
1/2
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
 1 if (slots > slots_.size()) {
64 1 Rehash(slots);
65 }
66 1 }
67
68 2 std::size_t Size() const {
69
2/4
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
 2 return size_;
70 }
71
72 private:
73 static constexpr std::uint32_t kEmpty = std::numeric_limits<std::uint32_t>::max();
74 struct Slot {
75 std::uint32_t tag = 0;
76 std::uint32_t id = kEmpty;
77 };
78
79 67193 static std::uint32_t Tag(std::uint64_t hash) {
80 67193 return static_cast<std::uint32_t>(hash ^ (hash >> 32));
81 }
82 96893 std::size_t Mask() const {
83 85254 return slots_.size() - 1;
84 }
85 1195 void Rehash(std::size_t slots) {
86 1195 std::vector<Slot> old(slots, Slot{});
87 1195 old.swap(slots_);
88
2/2
✓ Branch 0 taken 33792 times.
✓ Branch 1 taken 1195 times.
 34987 for (const Slot& slot : old) {
89
2/2
✓ Branch 0 taken 16896 times.
✓ Branch 1 taken 16896 times.
 33792 if (slot.id != kEmpty) {
90 16896 std::size_t i = slot.tag & Mask();
91
2/2
✓ Branch 0 taken 2167 times.
✓ Branch 1 taken 16896 times.
 19063 while (slots_[i].id != kEmpty) {
92 2167 i = (i + 1) & Mask();
93 }
94 16896 slots_[i] = slot;
95 }
96 }
97 1195 }
98
99 std::vector<Slot> slots_;
100 std::size_t size_ = 0;
101 };
102
103 } // namespace ernie
104