| 258 | static uint32 Marker(uint32 hb) { return hb + (hb < 2 ? 2 : 0); } |
| 259 | |
| 260 | void Init(size_t N) { |
| 261 | // Make enough room for N elements. |
| 262 | size_t lg = 0; // Smallest table is just one bucket. |
| 263 | while (N >= 0.8 * ((1 << lg) * kWidth)) { |
| 264 | lg++; |
| 265 | } |
| 266 | const size_t n = (1 << lg); |
| 267 | Bucket* array = new Bucket[n]; |
| 268 | for (size_t i = 0; i < n; i++) { |
| 269 | Bucket* b = &array[i]; |
| 270 | memset(b->marker, kEmpty, kWidth); |
| 271 | } |
| 272 | const size_t capacity = (1 << lg) * kWidth; |
| 273 | lglen_ = lg; |
| 274 | mask_ = capacity - 1; |
| 275 | array_ = array; |
| 276 | end_ = array + n; |
| 277 | not_empty_ = 0; |
| 278 | deleted_ = 0; |
| 279 | grow_ = static_cast<size_t>(capacity * 0.8); |
| 280 | if (lg == 0) { |
| 281 | // Already down to one bucket; no more shrinking. |
| 282 | shrink_ = 0; |
| 283 | } else { |
| 284 | shrink_ = static_cast<size_t>(grow_ * 0.4); // Must be less than 0.5 |
| 285 | } |
| 286 | } |
| 287 | |
| 288 | // Used by FreshInsert when we should copy from source. |
| 289 | struct CopyEntry { |