| 847 | } |
| 848 | |
| 849 | pair<fl::size, bool> find_slot(const Key &key) const { |
| 850 | const fl::size cap = _buckets.size(); |
| 851 | const fl::size mask = cap - 1; |
| 852 | const fl::size h = _hash(key) & mask; |
| 853 | fl::size first_tomb = npos(); |
| 854 | |
| 855 | if (cap <= 8) { |
| 856 | // linear probing |
| 857 | for (fl::size i = 0; i < cap; ++i) { |
| 858 | const fl::size idx = (h + i) & mask; |
| 859 | |
| 860 | if (is_empty(idx)) |
| 861 | return {first_tomb != npos() ? first_tomb : idx, true}; |
| 862 | if (is_deleted(idx)) { |
| 863 | if (first_tomb == npos()) |
| 864 | first_tomb = idx; |
| 865 | } else if (is_occupied(idx) && _equal(_buckets[idx].key, key)) { |
| 866 | return {idx, false}; |
| 867 | } |
| 868 | } |
| 869 | } else { |
| 870 | // quadratic probing up to 8 tries |
| 871 | fl::size i = 0; |
| 872 | for (; i < 8; ++i) { |
| 873 | const fl::size idx = (h + i + i * i) & mask; |
| 874 | |
| 875 | if (is_empty(idx)) |
| 876 | return {first_tomb != npos() ? first_tomb : idx, true}; |
| 877 | if (is_deleted(idx)) { |
| 878 | if (first_tomb == npos()) |
| 879 | first_tomb = idx; |
| 880 | } else if (is_occupied(idx) && _equal(_buckets[idx].key, key)) { |
| 881 | return {idx, false}; |
| 882 | } |
| 883 | } |
| 884 | // fallback to linear for the rest |
| 885 | for (; i < cap; ++i) { |
| 886 | const fl::size idx = (h + i) & mask; |
| 887 | |
| 888 | if (is_empty(idx)) |
| 889 | return {first_tomb != npos() ? first_tomb : idx, true}; |
| 890 | if (is_deleted(idx)) { |
| 891 | if (first_tomb == npos()) |
| 892 | first_tomb = idx; |
| 893 | } else if (is_occupied(idx) && _equal(_buckets[idx].key, key)) { |
| 894 | return {idx, false}; |
| 895 | } |
| 896 | } |
| 897 | } |
| 898 | |
| 899 | return {npos(), false}; |
| 900 | } |
| 901 | |
| 902 | enum { |
| 903 | kLinearProbingOnlySize = 8, |
no test coverage detected