41 return *(
reinterpret_cast<Slice*
>(
value));
43 return Slice(key_data, key_length);
56 ~HandleTable() {
delete[]
list_; }
59 return *FindPointer(key, hash);
62 LRUHandle* Insert(LRUHandle* h) {
63 LRUHandle** ptr = FindPointer(h->key(), h->hash);
64 LRUHandle* old = *ptr;
65 h->next_hash = (old == NULL ? NULL : old->next_hash);
79 LRUHandle** ptr = FindPointer(key, hash);
80 LRUHandle* result = *ptr;
82 *ptr = result->next_hash;
98 LRUHandle** FindPointer(
const Slice& key,
uint32_t hash) {
99 LRUHandle** ptr = &list_[hash & (length_ - 1)];
100 while (*ptr != NULL &&
101 ((*ptr)->hash != hash || key != (*ptr)->key())) {
102 ptr = &(*ptr)->next_hash;
109 while (new_length < elems_) {
112 LRUHandle** new_list =
new LRUHandle*[new_length];
113 memset(new_list, 0,
sizeof(new_list[0]) * new_length);
116 LRUHandle* h = list_[i];
118 LRUHandle*
next = h->next_hash;
120 LRUHandle** ptr = &new_list[hash & (new_length - 1)];
127 assert(elems_ == count);
130 length_ = new_length;
141 void SetCapacity(
size_t capacity) {
capacity_ = capacity; }
144 Cache::Handle* Insert(
const Slice& key,
uint32_t hash,
146 void (*
deleter)(
const Slice& key,
void* value));
148 void Release(Cache::Handle* handle);
149 void Erase(
const Slice& key,
uint32_t hash);
152 void LRU_Remove(LRUHandle* e);
153 void LRU_Append(LRUHandle* e);
154 void Unref(LRUHandle* e);
177 LRUCache::~LRUCache() {
178 for (LRUHandle* e =
lru_.next; e != &
lru_; ) {
179 LRUHandle*
next = e->next;
180 assert(e->refs == 1);
186 void LRUCache::Unref(LRUHandle* e) {
191 (*e->deleter)(e->key(), e->value);
196 void LRUCache::LRU_Remove(LRUHandle* e) {
197 e->next->prev = e->prev;
198 e->prev->next = e->next;
201 void LRUCache::LRU_Append(LRUHandle* e) {
211 LRUHandle* e =
table_.Lookup(key, hash);
217 return reinterpret_cast<Cache::Handle*
>(e);
220 void LRUCache::Release(Cache::Handle* handle) {
222 Unref(reinterpret_cast<LRUHandle*>(handle));
225 Cache::Handle* LRUCache::Insert(
226 const Slice& key,
uint32_t hash,
void* value,
size_t charge,
227 void (*
deleter)(
const Slice& key,
void* value)) {
230 LRUHandle* e =
reinterpret_cast<LRUHandle*
>(
231 malloc(
sizeof(LRUHandle)-1 + key.size()));
235 e->key_length = key.size();
238 memcpy(e->key_data, key.data(), key.size());
242 LRUHandle* old =
table_.Insert(e);
249 LRUHandle* old =
lru_.next;
251 table_.Remove(old->key(), old->hash);
255 return reinterpret_cast<Cache::Handle*
>(e);
258 void LRUCache::Erase(
const Slice& key,
uint32_t hash) {
260 LRUHandle* e =
table_.Remove(key, hash);
267 static const int kNumShardBits = 4;
268 static const int kNumShards = 1 << kNumShardBits;
270 class ShardedLRUCache :
public Cache {
276 static inline uint32_t HashSlice(
const Slice& s) {
277 return Hash(s.data(), s.size(), 0);
281 return hash >> (32 - kNumShardBits);
285 explicit ShardedLRUCache(
size_t capacity)
287 const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
288 for (
int s = 0; s < kNumShards; s++) {
289 shard_[s].SetCapacity(per_shard);
292 virtual ~ShardedLRUCache() { }
293 virtual Handle* Insert(
const Slice& key,
void* value,
size_t charge,
294 void (*
deleter)(
const Slice& key,
void* value)) {
295 const uint32_t hash = HashSlice(key);
296 return shard_[Shard(hash)].Insert(key, hash, value, charge,
deleter);
298 virtual Handle*
Lookup(
const Slice& key) {
299 const uint32_t hash = HashSlice(key);
300 return shard_[Shard(hash)].Lookup(key, hash);
302 virtual void Release(Handle* handle) {
303 LRUHandle* h =
reinterpret_cast<LRUHandle*
>(handle);
304 shard_[Shard(h->hash)].Release(handle);
306 virtual void Erase(
const Slice& key) {
307 const uint32_t hash = HashSlice(key);
308 shard_[Shard(hash)].Erase(key, hash);
310 virtual void*
Value(Handle* handle) {
311 return reinterpret_cast<LRUHandle*
>(handle)->value;
314 MutexLock l(&id_mutex_);
322 return new ShardedLRUCache(capacity);
void(* deleter)(const Slice &, void *value)
LRUCache shard_[kNumShards]
unsigned long long uint64_t
uint256 Hash(const T1 pbegin, const T1 pend)
Cache * NewLRUCache(size_t capacity)
bool Lookup(const char *pszName, std::vector< CService > &vAddr, int portDefault, bool fAllowLookup, unsigned int nMaxSolutions)