Find bucket/index for key k.
| 141 | |
| 142 | // Find bucket/index for key k. |
| 143 | SearchResult Find(const Key& k) const { |
| 144 | size_t h = hash_(k); |
| 145 | const uint32 marker = Marker(h & 0xff); |
| 146 | size_t index = (h >> 8) & mask_; // Holds bucket num and index-in-bucket |
| 147 | uint32 num_probes = 1; // Needed for quadratic probing |
| 148 | while (true) { |
| 149 | uint32 bi = index & (kWidth - 1); |
| 150 | Bucket* b = &array_[index >> kBase]; |
| 151 | const uint32 x = b->marker[bi]; |
| 152 | if (x == marker && equal_(b->key(bi), k)) { |
| 153 | return {true, b, bi}; |
| 154 | } else if (x == kEmpty) { |
| 155 | return {false, nullptr, 0}; |
| 156 | } |
| 157 | index = NextIndex(index, num_probes); |
| 158 | num_probes++; |
| 159 | } |
| 160 | } |
| 161 | |
| 162 | // Find bucket/index for key k, creating a new one if necessary. |
| 163 | // |