leveldb::ConcurrentTest Class Reference

Collaboration diagram for leveldb::ConcurrentTest:

Classes
struct	State

Public Member Functions
	ConcurrentTest ()
void	WriteStep (Random *rnd)
void	ReadStep (Random *rnd)

Static Private Member Functions
static uint64_t	key (Key key)
static uint64_t	gen (Key key)
static uint64_t	hash (Key key)
static uint64_t	HashNumbers (uint64_t k, uint64_t g)
static Key	MakeKey (uint64_t k, uint64_t g)
static bool	IsValidKey (Key k)
static Key	RandomTarget (Random *rnd)

Private Attributes
State	current_
Arena	arena_
SkipList< Key, Comparator >	list_

Static Private Attributes
static const uint32_t	K = 4

Detailed Description

Definition at line 149 of file skiplist_test.cc.

Constructor & Destructor Documentation

ConcurrentTest()

leveldb::ConcurrentTest::ConcurrentTest ( )

inline

Definition at line 214 of file skiplist_test.cc.

: list_(Comparator(), &arena_) { }

Member Function Documentation

gen()

static uint64_t leveldb::ConcurrentTest::gen ( Key  key )

inlinestaticprivate

Definition at line 154 of file skiplist_test.cc.

{ return (key >> 8) & 0xffffffffu; }

hash()

static uint64_t leveldb::ConcurrentTest::hash ( Key  key )

inlinestaticprivate

Definition at line 155 of file skiplist_test.cc.

{ return key & 0xff; }

HashNumbers()

static uint64_t leveldb::ConcurrentTest::HashNumbers ( uint64_t  k, uint64_t  g  )

inlinestaticprivate

Definition at line 157 of file skiplist_test.cc.

                                                      {
    uint64_t data[2] = { k, g };
    return Hash(reinterpret_cast<char*>(data), sizeof(data), 0);
  }

Here is the call graph for this function:

IsValidKey()

static bool leveldb::ConcurrentTest::IsValidKey ( Key  k )

inlinestaticprivate

Definition at line 169 of file skiplist_test.cc.

                                {
    return hash(k) == (HashNumbers(key(k), gen(k)) & 0xff);
  }

key()

static uint64_t leveldb::ConcurrentTest::key ( Key  key )

inlinestaticprivate

Definition at line 153 of file skiplist_test.cc.

{ return (key >> 40); }

MakeKey()

static Key leveldb::ConcurrentTest::MakeKey ( uint64_t  k, uint64_t  g  )

inlinestaticprivate

Definition at line 162 of file skiplist_test.cc.

                                             {
    assert(sizeof(Key) == sizeof(uint64_t));
    assert(k <= K);  // We sometimes pass K to seek to the end of the skiplist
    assert(g <= 0xffffffffu);
    return ((k << 40) | (g << 8) | (HashNumbers(k, g) & 0xff));
  }

RandomTarget()

static Key leveldb::ConcurrentTest::RandomTarget ( Random *  rnd )

inlinestaticprivate

Definition at line 173 of file skiplist_test.cc.

                                       {
    switch (rnd->Next() % 10) {
      case 0:
        // Seek to beginning
        return MakeKey(0, 0);
      case 1:
        // Seek to end
        return MakeKey(K, 0);
      default:
        // Seek to middle
        return MakeKey(rnd->Next() % K, 0);
    }
  }

Here is the call graph for this function:

ReadStep()

void leveldb::ConcurrentTest::ReadStep ( Random *  rnd )

inline

Definition at line 225 of file skiplist_test.cc.

                             {
    // Remember the initial committed state of the skiplist.
    State initial_state;
    for (int k = 0; k < K; k++) {
      initial_state.Set(k, current_.Get(k));
    }

    Key pos = RandomTarget(rnd);
    SkipList<Key, Comparator>::Iterator iter(&list_);
    iter.Seek(pos);
    while (true) {
      Key current;
      if (!iter.Valid()) {
        current = MakeKey(K, 0);
      } else {
        current = iter.key();
        ASSERT_TRUE(IsValidKey(current)) << current;
      }
      ASSERT_LE(pos, current) << "should not go backwards";

      // Verify that everything in [pos,current) was not present in
      // initial_state.
      while (pos < current) {
        ASSERT_LT(key(pos), K) << pos;

        // Note that generation 0 is never inserted, so it is ok if
        // <*,0,*> is missing.
        ASSERT_TRUE((gen(pos) == 0) ||
                    (gen(pos) > static_cast<Key>(initial_state.Get(key(pos))))
                    ) << "key: " << key(pos)
                      << "; gen: " << gen(pos)
                      << "; initgen: "
                      << initial_state.Get(key(pos));

        // Advance to next key in the valid key space
        if (key(pos) < key(current)) {
          pos = MakeKey(key(pos) + 1, 0);
        } else {
          pos = MakeKey(key(pos), gen(pos) + 1);
        }
      }

      if (!iter.Valid()) {
        break;
      }

      if (rnd->Next() % 2) {
        iter.Next();
        pos = MakeKey(key(pos), gen(pos) + 1);
      } else {
        Key new_target = RandomTarget(rnd);
        if (new_target > pos) {
          pos = new_target;
          iter.Seek(new_target);
        }
      }
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

WriteStep()

void leveldb::ConcurrentTest::WriteStep ( Random *  rnd )

inline

Definition at line 217 of file skiplist_test.cc.

                              {
    const uint32_t k = rnd->Next() % K;
    const intptr_t g = current_.Get(k) + 1;
    const Key key = MakeKey(k, g);
    list_.Insert(key);
    current_.Set(k, g);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

arena_

Arena leveldb::ConcurrentTest::arena_

private

Definition at line 207 of file skiplist_test.cc.

current_

State leveldb::ConcurrentTest::current_

private

Definition at line 205 of file skiplist_test.cc.

K

const uint32_t leveldb::ConcurrentTest::K = 4

staticprivate

Definition at line 151 of file skiplist_test.cc.

list_

SkipList<Key, Comparator> leveldb::ConcurrentTest::list_

private

Definition at line 211 of file skiplist_test.cc.

---

The documentation for this class was generated from the following file:

• db/skiplist_test.cc