← Back to branch summary

~ubuntu-branches/ubuntu/quantal/ceph/quantal

« back to all changes in this revision

Viewing changes to src/leveldb/util/cache_test.cc

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-07-16 09:56:24 UTC
  • mfrom: (0.3.11)
  • mto: This revision was merged to the branch mainline in revision 17.
  • Revision ID: package-import@ubuntu.com-20120716095624-azr2w4hbhei1rxmx
Tags: upstream-0.48
Import upstream version 0.48

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/leveldb/util/cache_test.cc
1
 
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2
 
// Use of this source code is governed by a BSD-style license that can be
3
 
// found in the LICENSE file. See the AUTHORS file for names of contributors.
4
 
 
5
 
#include "leveldb/cache.h"
6
 
 
7
 
#include <vector>
8
 
#include "util/coding.h"
9
 
#include "util/testharness.h"
10
 
 
11
 
namespace leveldb {
12
 
 
13
 
// Conversions between numeric keys/values and the types expected by Cache.
14
 
static std::string EncodeKey(int k) {
15
 
  std::string result;
16
 
  PutFixed32(&result, k);
17
 
  return result;
18
 
}
19
 
static int DecodeKey(const Slice& k) {
20
 
  assert(k.size() == 4);
21
 
  return DecodeFixed32(k.data());
22
 
}
23
 
static void* EncodeValue(uintptr_t v) { return reinterpret_cast<void*>(v); }
24
 
static int DecodeValue(void* v) { return reinterpret_cast<uintptr_t>(v); }
25
 
 
26
 
class CacheTest {
27
 
 public:
28
 
  static CacheTest* current_;
29
 
 
30
 
  static void Deleter(const Slice& key, void* v) {
31
 
    current_->deleted_keys_.push_back(DecodeKey(key));
32
 
    current_->deleted_values_.push_back(DecodeValue(v));
33
 
  }
34
 
 
35
 
  static const int kCacheSize = 1000;
36
 
  std::vector<int> deleted_keys_;
37
 
  std::vector<int> deleted_values_;
38
 
  Cache* cache_;
39
 
 
40
 
  CacheTest() : cache_(NewLRUCache(kCacheSize)) {
41
 
    current_ = this;
42
 
  }
43
 
 
44
 
  ~CacheTest() {
45
 
    delete cache_;
46
 
  }
47
 
 
48
 
  int Lookup(int key) {
49
 
    Cache::Handle* handle = cache_->Lookup(EncodeKey(key));
50
 
    const int r = (handle == NULL) ? -1 : DecodeValue(cache_->Value(handle));
51
 
    if (handle != NULL) {
52
 
      cache_->Release(handle);
53
 
    }
54
 
    return r;
55
 
  }
56
 
 
57
 
  void Insert(int key, int value, int charge = 1) {
58
 
    cache_->Release(cache_->Insert(EncodeKey(key), EncodeValue(value), charge,
59
 
                                   &CacheTest::Deleter));
60
 
  }
61
 
 
62
 
  void Erase(int key) {
63
 
    cache_->Erase(EncodeKey(key));
64
 
  }
65
 
};
66
 
CacheTest* CacheTest::current_;
67
 
 
68
 
TEST(CacheTest, HitAndMiss) {
69
 
  ASSERT_EQ(-1, Lookup(100));
70
 
 
71
 
  Insert(100, 101);
72
 
  ASSERT_EQ(101, Lookup(100));
73
 
  ASSERT_EQ(-1,  Lookup(200));
74
 
  ASSERT_EQ(-1,  Lookup(300));
75
 
 
76
 
  Insert(200, 201);
77
 
  ASSERT_EQ(101, Lookup(100));
78
 
  ASSERT_EQ(201, Lookup(200));
79
 
  ASSERT_EQ(-1,  Lookup(300));
80
 
 
81
 
  Insert(100, 102);
82
 
  ASSERT_EQ(102, Lookup(100));
83
 
  ASSERT_EQ(201, Lookup(200));
84
 
  ASSERT_EQ(-1,  Lookup(300));
85
 
 
86
 
  ASSERT_EQ(1, deleted_keys_.size());
87
 
  ASSERT_EQ(100, deleted_keys_[0]);
88
 
  ASSERT_EQ(101, deleted_values_[0]);
89
 
}
90
 
 
91
 
TEST(CacheTest, Erase) {
92
 
  Erase(200);
93
 
  ASSERT_EQ(0, deleted_keys_.size());
94
 
 
95
 
  Insert(100, 101);
96
 
  Insert(200, 201);
97
 
  Erase(100);
98
 
  ASSERT_EQ(-1,  Lookup(100));
99
 
  ASSERT_EQ(201, Lookup(200));
100
 
  ASSERT_EQ(1, deleted_keys_.size());
101
 
  ASSERT_EQ(100, deleted_keys_[0]);
102
 
  ASSERT_EQ(101, deleted_values_[0]);
103
 
 
104
 
  Erase(100);
105
 
  ASSERT_EQ(-1,  Lookup(100));
106
 
  ASSERT_EQ(201, Lookup(200));
107
 
  ASSERT_EQ(1, deleted_keys_.size());
108
 
}
109
 
 
110
 
TEST(CacheTest, EntriesArePinned) {
111
 
  Insert(100, 101);
112
 
  Cache::Handle* h1 = cache_->Lookup(EncodeKey(100));
113
 
  ASSERT_EQ(101, DecodeValue(cache_->Value(h1)));
114
 
 
115
 
  Insert(100, 102);
116
 
  Cache::Handle* h2 = cache_->Lookup(EncodeKey(100));
117
 
  ASSERT_EQ(102, DecodeValue(cache_->Value(h2)));
118
 
  ASSERT_EQ(0, deleted_keys_.size());
119
 
 
120
 
  cache_->Release(h1);
121
 
  ASSERT_EQ(1, deleted_keys_.size());
122
 
  ASSERT_EQ(100, deleted_keys_[0]);
123
 
  ASSERT_EQ(101, deleted_values_[0]);
124
 
 
125
 
  Erase(100);
126
 
  ASSERT_EQ(-1, Lookup(100));
127
 
  ASSERT_EQ(1, deleted_keys_.size());
128
 
 
129
 
  cache_->Release(h2);
130
 
  ASSERT_EQ(2, deleted_keys_.size());
131
 
  ASSERT_EQ(100, deleted_keys_[1]);
132
 
  ASSERT_EQ(102, deleted_values_[1]);
133
 
}
134
 
 
135
 
TEST(CacheTest, EvictionPolicy) {
136
 
  Insert(100, 101);
137
 
  Insert(200, 201);
138
 
 
139
 
  // Frequently used entry must be kept around
140
 
  for (int i = 0; i < kCacheSize + 100; i++) {
141
 
    Insert(1000+i, 2000+i);
142
 
    ASSERT_EQ(2000+i, Lookup(1000+i));
143
 
    ASSERT_EQ(101, Lookup(100));
144
 
  }
145
 
  ASSERT_EQ(101, Lookup(100));
146
 
  ASSERT_EQ(-1, Lookup(200));
147
 
}
148
 
 
149
 
TEST(CacheTest, HeavyEntries) {
150
 
  // Add a bunch of light and heavy entries and then count the combined
151
 
  // size of items still in the cache, which must be approximately the
152
 
  // same as the total capacity.
153
 
  const int kLight = 1;
154
 
  const int kHeavy = 10;
155
 
  int added = 0;
156
 
  int index = 0;
157
 
  while (added < 2*kCacheSize) {
158
 
    const int weight = (index & 1) ? kLight : kHeavy;
159
 
    Insert(index, 1000+index, weight);
160
 
    added += weight;
161
 
    index++;
162
 
  }
163
 
 
164
 
  int cached_weight = 0;
165
 
  for (int i = 0; i < index; i++) {
166
 
    const int weight = (i & 1 ? kLight : kHeavy);
167
 
    int r = Lookup(i);
168
 
    if (r >= 0) {
169
 
      cached_weight += weight;
170
 
      ASSERT_EQ(1000+i, r);
171
 
    }
172
 
  }
173
 
  ASSERT_LE(cached_weight, kCacheSize + kCacheSize/10);
174
 
}
175
 
 
176
 
TEST(CacheTest, NewId) {
177
 
  uint64_t a = cache_->NewId();
178
 
  uint64_t b = cache_->NewId();
179
 
  ASSERT_NE(a, b);
180
 
}
181
 
 
182
 
}  // namespace leveldb
183
 
 
184
 
int main(int argc, char** argv) {
185
 
  return leveldb::test::RunAllTests();
186
 
}