| 905 | }; |
| 906 | |
| 907 | fl::size find_index(const Key &key) const { |
| 908 | const fl::size cap = _buckets.size(); |
| 909 | const fl::size mask = cap - 1; |
| 910 | const fl::size h = _hash(key) & mask; |
| 911 | |
| 912 | if (cap <= kLinearProbingOnlySize) { |
| 913 | // linear probing |
| 914 | for (fl::size i = 0; i < cap; ++i) { |
| 915 | const fl::size idx = (h + i) & mask; |
| 916 | if (is_empty(idx)) |
| 917 | return npos(); |
| 918 | if (is_occupied(idx) && _equal(_buckets[idx].key, key)) |
| 919 | return idx; |
| 920 | } |
| 921 | } else { |
| 922 | // quadratic probing up to 8 tries |
| 923 | fl::size i = 0; |
| 924 | for (; i < kQuadraticProbingTries; ++i) { |
| 925 | const fl::size idx = (h + i + i * i) & mask; |
| 926 | if (is_empty(idx)) |
| 927 | return npos(); |
| 928 | if (is_occupied(idx) && _equal(_buckets[idx].key, key)) |
| 929 | return idx; |
| 930 | } |
| 931 | // fallback to linear for the rest |
| 932 | for (; i < cap; ++i) { |
| 933 | const fl::size idx = (h + i) & mask; |
| 934 | if (is_empty(idx)) |
| 935 | return npos(); |
| 936 | if (is_occupied(idx) && _equal(_buckets[idx].key, key)) |
| 937 | return idx; |
| 938 | } |
| 939 | } |
| 940 | |
| 941 | return npos(); |
| 942 | } |
| 943 | |
| 944 | fl::size find_unoccupied_index_using_bitset( |
| 945 | const Key &key, const fl::bitset<1024> &occupied_set) const { |
no test coverage detected