src/storage/lru_cache.h

// Copyright 2010-2014, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef MOZC_STORAGE_LRU_CACHE_H_
#define MOZC_STORAGE_LRU_CACHE_H_

#include <cstring>
#include <map>
#include <string>

#include "base/logging.h"
#include "base/port.h"

namespace mozc {
namespace storage {

// Note: this class keeps some resources inside of the Key/Value, even if
// such a entry is erased. Be careful to use for such classes.
// TODO(yukawa): Make this class final once we stop supporting GCC 4.6.
template<typename Key, typename Value>
class LRUCache {
 public:
  // Constructs a new LRUCache that can hold at most max_elements
  explicit LRUCache(size_t max_elements);

  // Cleans up all allocated resources.
  ~LRUCache();

  // Every Element is either on the free list or the lru list.  The
  // free list is singly-linked and only uses the next pointer, while
  // the LRU list is doubly-linked and uses both next and prev.
  struct Element {
    Element* next;
    Element* prev;
    Key key;
    Value value;
  };

  // Adds the specified key/value pair into the cache, putting it at the head
  // of the LRU list.
  void Insert(const Key &key, const Value& value);

  // Adds the specified key and return the Element added to the cache.
  // Caller needs to set the value
  Element* Insert(const Key &key);

  // Returns the cached value associated with the key, or NULL if the cache
  // does not contain an entry for that key.  The caller does not assume
  // ownership of the returned value.  The reference returned by Lookup() could
  // be invalidated by a call to Insert(), so the caller must take care to not
  // access the value if Insert() could have been called after Lookup().
  const Value* Lookup(const Key &key);

  // return non-const Value
  Value *MutableLookup(const Key &key);

  // Lookup/MutableLookup don't change the LRU order.
  const Value *LookupWithoutInsert(const Key &key) const;
  Value *MutableLookupWithoutInsert(const Key &key) const;

  // Removes the cache entry specified by key.  Returns true if the entry was
  // in the cache, otherwise returns false.
  bool Erase(const Key &key);

  // Removes all entries from the cache.  Note that this does not release the
  // memory associates with the blocks, but just pushes all the elements onto
  // the free list.
  void Clear();

  // Returns the number of entries currently in the cache.
  size_t Size() const;

  bool HasKey(const Key &key) const;

  // Returns the head of LRU list
  const Element *Head() const { return lru_head_; }
  Element *MutableHead() const { return lru_head_; }

  // Returns the tail of LRU list
  const Element *Tail() const { return lru_tail_; }

 private:
  // Allocates a new block containing next_block_size_ elements, updates
  // next_block_size_ appropriately, and pushes the elements in the new block
  // onto the free list.
  void AddBlock();

  // Pushes an element onto the head of the free list.
  void PushFreeList(Element* element);

  // Pops an element from the head of the free list.
  Element* PopFreeList();

  // Returns a free element, popping from the free list if possible, or
  // allocating a new element if the free list is empty.  If there are already
  // max_elements_ in use this will return NULL.
  Element* NextFreeElement();

  // Returns the Element* associated with key, or NULL if no element with this
  // key is found.
  Element* LookupInternal(const Key &key) const;

  // Removes the specified element from the LRU list.
  void RemoveFromLRU(Element* element);

  // Adds the specified element to the head of the LRU list.
  void PushLRUHead(Element* element);

  // Evict is similar to Erase, except that it adds the eviction callback and
  // element to a list of eviction calls, and takes an element so that another
  // lookup is not necessary.
  bool Evict(Element* element);

  typedef map<Key, Element*> Table;

  Table* table_;
  Element* free_list_;     // singly linked list of Element
  Element* lru_head_;      // head of doubly linked list of Element
  Element* lru_tail_;      // tail of doubly linked list of Element
  Element* blocks_[10];    // blocks of Element, with each block being twice
  //   as big as the previous block.  This allows the
  //   cache to use a small amount of memory when it
  //   contains few items, but still have low malloc
  //   overhead per insert.  The number of blocks is
  //   arbitrary, but 10 blocks allows the largest
  //   block to be 2^10 times as large as the smallest
  //   block, which seems like more than enough.
  size_t block_count_;      // how many entries in blocks_ have been used
  size_t block_capacity_;   // how many Elements can be stored in current blocks
  size_t next_block_size_;  // size of the next block to allocate
  size_t max_elements_;     // maximum elements to hold

  DISALLOW_COPY_AND_ASSIGN(LRUCache);
};


template<typename Key, typename Value>
void LRUCache<Key, Value>::AddBlock() {
  const size_t max_blocks = sizeof(blocks_) / sizeof(blocks_[0]);
  if (block_count_ < max_blocks && block_capacity_ < max_elements_) {
    blocks_[block_count_] = new Element[next_block_size_];
    block_capacity_ += next_block_size_;
    // Add new elements to free list
    for (size_t i = 0; i < next_block_size_; ++i) {
      Element* e = &((blocks_[block_count_])[i]);
      e->prev = NULL;  // free list is not doubly linked
      e->next = free_list_;
      free_list_ = e;
    }
    block_count_++;
    size_t blocks_remaining = max_blocks - block_count_;
    if (blocks_remaining > 0) {
      next_block_size_ = (next_block_size_ << 1);
      size_t elements_remaining = max_elements_ - block_capacity_;
      if (next_block_size_ > (elements_remaining / blocks_remaining)) {
        next_block_size_ = elements_remaining / blocks_remaining;
      }
      if (block_capacity_ + next_block_size_ > max_elements_) {
        next_block_size_ = max_elements_ - block_capacity_;
      }
    }
  }
}

template<typename Key, typename Value>
void LRUCache<Key, Value>::PushFreeList(Element* element) {
  element->prev = NULL;
  element->next = free_list_;
  free_list_ = element;
}

template<typename Key, typename Value>
typename LRUCache<Key, Value>::Element*
LRUCache<Key, Value>::PopFreeList() {
  Element* r = free_list_;
  if (r != NULL) {
    CHECK(r->prev == NULL);
    free_list_ = r->next;
    if (free_list_ != NULL) {
      free_list_->prev = NULL;
    }
    r->next = NULL;
  }
  return r;
}

template<typename Key, typename Value>
typename LRUCache<Key, Value>::Element*
LRUCache<Key, Value>::NextFreeElement() {
  Element* r = PopFreeList();
  if (r == NULL) {
    AddBlock();
    r = PopFreeList();
  }
  return r;
}

template<typename Key, typename Value>
typename LRUCache<Key, Value>::Element*
LRUCache<Key, Value>::LookupInternal(const Key &key) const {
  typename Table::iterator iter = table_->find(key);
  if (iter != table_->end()) {
    return iter->second;
  }
  return NULL;
}

template<typename Key, typename Value>
void LRUCache<Key, Value>::RemoveFromLRU(Element* element) {
  if (lru_head_ == element) {
    lru_head_ = element->next;
  }
  if (lru_tail_ == element) {
    lru_tail_ = element->prev;
  }
  if (element->prev != NULL) {
    element->prev->next = element->next;
  }
  if (element->next != NULL) {
    element->next->prev = element->prev;
  }
  element->prev = NULL;
  element->next = NULL;
}

template<typename Key, typename Value>
void LRUCache<Key, Value>::PushLRUHead(Element* element) {
  if (lru_head_ == element) {
    // element is already at head, so do nothing.
    return;
  }
  RemoveFromLRU(element);
  element->next = lru_head_;
  lru_head_ = element;
  if (element->next != NULL) {
    element->next->prev = element;
  }
  if (lru_tail_ == NULL) {
    lru_tail_ = element;
  }
}

template<typename Key, typename Value>
bool LRUCache<Key, Value>::Evict(Element* e) {
  if (e != NULL) {
    int erased = table_->erase(e->key);
    CHECK_EQ(erased, 1);
    RemoveFromLRU(e);
    PushFreeList(e);
    return true;
  }
  return false;
}

template<typename Key, typename Value>
LRUCache<Key, Value>::LRUCache(size_t max_elements)
  : free_list_(NULL),
    lru_head_(NULL),
    lru_tail_(NULL),
    block_count_(0),
    block_capacity_(0),
    max_elements_(max_elements) {
  ::memset(blocks_, 0, sizeof(blocks_));
  table_ = new Table;
  CHECK(table_);
  if (max_elements_ <= 128) {
    next_block_size_ = max_elements_;
  } else {
    next_block_size_ = 64;
    size_t num_blocks = sizeof(blocks_) / sizeof(blocks_[0]);
    // The default starting block size is 64, which is 2^6.  Every block is
    // twice as big as the previous (see AddBlock()), so the size of the last
    // block would be 2^(6 + num_blocks) if the first block was of size 64.  If
    // max_elements is large enough that 64 is too low of a starting size,
    // figure that out here.
    while ((next_block_size_ << num_blocks) < max_elements) {
      next_block_size_ = (next_block_size_ << 1);
    }
  }
}

template<typename Key, typename Value>
LRUCache<Key, Value>::~LRUCache() {
  // To free all the memory that I have allocated I need to delete table_ and
  // any used entries in blocks_.
  delete table_;
  for (size_t i = 0; i < block_count_; ++i) {
    delete [] blocks_[i];
  }
}

template<typename Key, typename Value>
void LRUCache<Key, Value>::Insert(const Key& key,
                                  const Value& value) {
  Element *e = Insert(key);
  if (e != NULL) {
    e->value = value;
  }
}

template<typename Key, typename Value>
typename LRUCache<Key, Value>::Element *
LRUCache<Key, Value>::Insert(const Key& key) {
  bool erased = false;
  Element* e = LookupInternal(key);
  if (e != NULL) {
    erased = Evict(e);
    CHECK(erased);
  }

  e = NextFreeElement();
  if (e == NULL) {
    // no free elements, I have to replace an existing element
    e = lru_tail_;
    erased = Evict(e);
    CHECK(erased);
    e = NextFreeElement();
    CHECK(e != NULL);
  }
  e->key = key;
  (*table_)[key] = e;
  PushLRUHead(e);

  return e;
}

template<typename Key, typename Value>
Value* LRUCache<Key, Value>::MutableLookup(const Key& key) {
  Element* e = LookupInternal(key);
  if (e != NULL) {
    PushLRUHead(e);
    return &(e->value);
  }
  return NULL;
}

template<typename Key, typename Value>
const Value* LRUCache<Key, Value>::Lookup(const Key& key) {
  return MutableLookup(key);
}

template<typename Key, typename Value>
Value* LRUCache<Key, Value>::MutableLookupWithoutInsert(const Key& key) const {
  Element *e = LookupInternal(key);
  if (e != NULL) {
    return &(e->value);
  }
  return NULL;
}

template<typename Key, typename Value>
const Value* LRUCache<Key, Value>::LookupWithoutInsert(const Key& key) const {
  return MutableLookupWithoutInsert(key);
}

template<typename Key, typename Value>
bool LRUCache<Key, Value>::Erase(const Key& key) {
  Element* e = LookupInternal(key);
  return Evict(e);
}

template<typename Key, typename Value>
void LRUCache<Key, Value>::Clear() {
  table_->clear();
  Element* e = lru_head_;
  while (e != NULL) {
    Element* next = e->next;
    PushFreeList(e);
    e = next;
  }
  lru_head_ = lru_tail_ = NULL;
}

template<typename Key, typename Value>
bool LRUCache<Key, Value>::HasKey(const Key& key) const {
  return (table_->find(key) != table_->end());
}

template<typename Key, typename Value>
size_t LRUCache<Key, Value>::Size() const {
  return table_->size();
}

}  // namespace storage
}  // namespace mozc
#endif  // MOZC_STORAGE_LRU_CACHE_H_