55 for (
int i = 0; i < N; i++) {
56 Key key = rnd.
Next() % R;
57 if (keys.insert(key).second) {
62 for (
int i = 0; i < R; i++) {
89 for (
int i = 0; i < R; i++) {
94 std::set<Key>::iterator model_iter = keys.lower_bound(i);
95 for (
int j = 0; j < 3; j++) {
96 if (model_iter == keys.end()) {
114 for (std::set<Key>::reverse_iterator model_iter = keys.rbegin();
115 model_iter != keys.rend();
159 return Hash(reinterpret_cast<char*>(data),
sizeof(data), 0);
163 assert(
sizeof(Key) ==
sizeof(
uint64_t));
165 assert(g <= 0xffffffffu);
166 return ((k << 40) | (g << 8) | (
HashNumbers(k, g) & 0xff));
174 switch (rnd->
Next() % 10) {
190 void Set(
int k, intptr_t v) {
194 return reinterpret_cast<intptr_t
>(generation[k].
Acquire_Load());
198 for (
int k = 0; k <
K; k++) {
219 const intptr_t g = current_.
Get(k) + 1;
228 for (
int k = 0; k <
K; k++) {
229 initial_state.
Set(k, current_.
Get(k));
240 current = iter.
key();
243 ASSERT_LE(pos, current) <<
"should not go backwards";
247 while (pos < current) {
254 ) <<
"key: " <<
key(pos)
255 <<
"; gen: " <<
gen(pos)
257 << initial_state.
Get(
key(pos));
260 if (
key(pos) <
key(current)) {
271 if (rnd->
Next() % 2) {
276 if (new_target > pos) {
278 iter.
Seek(new_target);
291 for (
int i = 0; i < 10000; i++) {
336 static void ConcurrentReader(
void*
arg) {
348 static void RunConcurrent(
int run) {
352 const int kSize = 1000;
353 for (
int i = 0; i < N; i++) {
354 if ((i % 100) == 0) {
355 fprintf(stderr,
"Run %d of %d\n", i, N);
357 TestState
state(seed + 1);
360 for (
int i = 0; i < kSize; i++) {
376 int main(
int argc,
char** argv) {
void Seek(const Key &target)
static bool IsValidKey(Key k)
static uint64_t hash(Key key)
void * Acquire_Load() const
uint32_t Hash(const char *data, size_t n, uint32_t seed)
void ReadStep(Random *rnd)
port::AtomicPointer quit_flag_
void Release_Store(void *v)
static Key RandomTarget(Random *rnd)
int operator()(const Key &a, const Key &b) const
static uint64_t HashNumbers(uint64_t k, uint64_t g)
int main(int argc, char **argv)
void Insert(const Key &key)
unsigned long long uint64_t
TEST(CorruptionTest, Recovery)
static uint64_t key(Key key)
bool Contains(const Key &key) const
virtual void Schedule(void(*function)(void *arg), void *arg)=0
port::AtomicPointer generation[K]
void Set(int k, intptr_t v)
void Change(ReaderState s)
SkipList< Key, Comparator > list_
void WriteStep(Random *rnd)
static Key MakeKey(uint64_t k, uint64_t g)
static uint64_t gen(Key key)