BPStudy と並カンと LRU

　金曜の BPStudy で「TDD なペアプロで 30 分で課題を解きましょう」っていうイベントがあって、初対面の方 (@uranojpさん) と「C 言語にしますかね」とか言ってたら、お題が LRU で、C 言語だと辛いなと思いながら、二人でがんばってなんとか時間内に実装完了 (成果物は bpstudy で出会い系ペアプロがまさかの LRU だったという話 · GitHub)。

　ネタとしては「C 言語で書くことになったので、まずテストフレームワークを作りました」というところでウケを取れたから良かったとして、課題を解くためが目的の無難な実装になっていることが不満と言えば不満だった。特に k.inaba さんの

shinhさんにもらった宿題ですが、やっぱりシングルリンクで十分ですね。

d.y.d.

ていうのが記憶の片隅に残っていたので。で、今日、並カンで↑のお題を出した id:shinh さんにお目にかかったりしたこともあって、ちょっと逃避がてら実装してみたら出来た。30分以上はかかったと思うけど。実装は↓。とかやってたらパストラックが落ちてたので会社に来て対策。リバースプロキシの DomU がハングしてましたorz

#include <iostream>
#include <map>
#include <string>

using namespace std;

template <typename KeyType, typename ValueType> class lru_t {
public:
  struct entry_t {
    entry_t* next_; // points to the next item (or garbage if this == last_)
    KeyType key_;
    ValueType value_;
    entry_t(const KeyType& key, const ValueType& value) : next_(NULL), key_(key), value_(value) {}
  };
  typedef map<KeyType /* FIXME should be pointer to key_ */, entry_t*> hash_t;
protected:
  hash_t hash_;
  entry_t first_; // dummy, next_ points to least recently used item
  entry_t* last_; // most recently used
  size_t capacity_;
public:
  lru_t(size_t capacity) : hash_(), first_(KeyType(), ValueType()), last_(NULL), capacity_(capacity) {
    assert(capacity >= 2);
  }
  ~lru_t() {
    // FIXME
  }
  void put(const KeyType& key, const ValueType& value) {
    typename hash_t::iterator hi = hash_.find(key);
    if (hi != hash_.end()) {
      _move_to_last(hi);
      last_->value_ = value;
    } else {
      if (hash_.size() == capacity_) {
	entry_t* evict = first_.next_;
	hash_.erase(evict->key_);
	hash_[evict->next_->key_] = &first_;
	first_.next_ = evict->next_;
	delete evict;
      }
      entry_t* e = new entry_t(key, value);
      if (last_ == NULL) {
	last_ = &first_;
      }
      hash_[key] = last_;
      last_->next_ = e;
      last_ = e;
    }
  }
  const ValueType* get(const KeyType& key) {
    typename hash_t::iterator hi = hash_.find(key);
    if (hi != hash_.end()) {
      _move_to_last(hi);
      return &last_->value_;
    }
    return NULL;
  }
protected:
  void _move_to_last(const typename hash_t::iterator& hi) {
    if (hi->second->next_ != last_) {
      entry_t* e = hi->second->next_;
      hash_[e->next_->key_] = hi->second;
      hi->second->next_ = e->next_;
      hash_[hi->first] = last_;
      last_->next_ = e;
      last_ = e;
    }
  }
  
#ifdef TEST
public:
  struct test_t {
    int status;
    test_t() : status(0) {}
    template <typename X, typename Y> void _is(int line, const X& x, const Y& y) {
      if (x == y) {
	cout << "ok at line " << line << endl;
      } else {
	cout << "not ok at line " << line << ", " << x << " != " << y << endl;
	status = 1;
      }
    }
    int doit() {
#define is(x, y) _is(__LINE__, (x), (y))  
#define ok(x) _is(__LINE__, ! ! (x), true)
      lru_t<string, string> lru(2);
      
      lru.put("a", "danA");
      is(lru.first_.next_, lru.last_);
      is(lru.last_->key_, "a");
      is(lru.last_->value_, "danA");
      is(lru.hash_["a"], &lru.first_);
      
      lru.put("b", "danB");
      is(lru.first_.next_->key_, "a");
      is(lru.first_.next_->value_, "danA");
      is(lru.first_.next_->next_, lru.last_);
      is(lru.last_->key_, "b");
      is(lru.last_->value_, "danB");
      is(lru.hash_["a"], &lru.first_);
      is(lru.hash_["b"], lru.first_.next_);
      
      lru.put("c", "danC");
      is(lru.first_.next_->key_, "b");
      is(lru.first_.next_->value_, "danB");
      is(lru.first_.next_->next_, lru.last_);
      is(lru.last_->key_, "c");
      is(lru.last_->value_, "danC");
      ok(lru.hash_.find("a") == lru.hash_.end());
      is(lru.hash_["b"], &lru.first_);
      is(lru.hash_["c"], lru.first_.next_);
      
      ok(lru.get("a") == NULL);
      is(lru.first_.next_->key_, "b");
      is(lru.first_.next_->next_, lru.last_);
      is(lru.last_->key_, "c");
      
      const string* v = lru.get("c");
      ok(v != NULL);
      is(*v, "danC");
      is(lru.first_.next_->key_, "b");
      is(lru.first_.next_->next_, lru.last_);
      is(lru.last_->key_, "c");

      v = lru.get("b");
      ok(v != NULL);
      is(*v, "danB");
      is(lru.first_.next_->key_, "c");
      is(lru.first_.next_->next_, lru.last_);
      is(lru.last_->key_, "b");
      
      return status;
#undef is
#undef ok
    }
  };
#endif TEST
};

#ifdef TEST
int main(int argc, char** argv)
{
  return lru_t<string, string>::test_t().doit();
}
#endif