| 241 | } |
| 242 | |
| 243 | void ReadStep(Random* rnd) { |
| 244 | // Remember the initial committed state of the skiplist. |
| 245 | State initial_state; |
| 246 | for (uint32_t k = 0; k < K; k++) { |
| 247 | initial_state.Set(k, current_.Get(k)); |
| 248 | } |
| 249 | |
| 250 | Key pos = RandomTarget(rnd); |
| 251 | SkipList<Key, Comparator>::Iterator iter(&list_); |
| 252 | iter.Seek(pos); |
| 253 | while (true) { |
| 254 | Key current; |
| 255 | if (!iter.Valid()) { |
| 256 | current = MakeKey(K, 0); |
| 257 | } else { |
| 258 | current = iter.key(); |
| 259 | ASSERT_TRUE(IsValidKey(current))<< current; |
| 260 | } |
| 261 | ASSERT_LE(pos, current)<< "should not go backwards"; |
| 262 | |
| 263 | // Verify that everything in [pos,current) was not present in |
| 264 | // initial_state. |
| 265 | while (pos < current) { |
| 266 | ASSERT_LT(key(pos), K)<< pos; |
| 267 | |
| 268 | // Note that generation 0 is never inserted, so it is ok if |
| 269 | // <*,0,*> is missing. |
| 270 | ASSERT_TRUE((gen(pos) == static_cast<uint64_t>(0)) || |
| 271 | (gen(pos) > static_cast<uint64_t>(initial_state.Get(key(pos)))) |
| 272 | ) << "key: " << key(pos) |
| 273 | << "; gen: " << gen(pos) |
| 274 | << "; initgen: " |
| 275 | << initial_state.Get(key(pos)); |
| 276 | |
| 277 | // Advance to next key in the valid key space |
| 278 | if (key(pos) < key(current)) { |
| 279 | pos = MakeKey(key(pos) + 1, 0); |
| 280 | } else { |
| 281 | pos = MakeKey(key(pos), gen(pos) + 1); |
| 282 | } |
| 283 | } |
| 284 | |
| 285 | if (!iter.Valid()) { |
| 286 | break; |
| 287 | } |
| 288 | |
| 289 | if (rnd->Next() % 2) { |
| 290 | iter.Next(); |
| 291 | pos = MakeKey(key(pos), gen(pos) + 1); |
| 292 | } else { |
| 293 | Key new_target = RandomTarget(rnd); |
| 294 | if (new_target > pos) { |
| 295 | pos = new_target; |
| 296 | iter.Seek(new_target); |
| 297 | } |
| 298 | } |
| 299 | } |
| 300 | } |