chrome/browser/sync_file_system/drive_backend/leveldb_wrapper.cc

   1 // Copyright 2014 The Chromium 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.
   4
   5 #include "chrome/browser/sync_file_system/drive_backend/leveldb_wrapper.h"
   6
   7 #include <map>
   8 #include <set>
   9 #include <string>
  10
  11 #include "base/logging.h"
  12 #include "third_party/leveldatabase/src/include/leveldb/db.h"
  13 #include "third_party/leveldatabase/src/include/leveldb/iterator.h"
  14 #include "third_party/leveldatabase/src/include/leveldb/slice.h"
  15 #include "third_party/leveldatabase/src/include/leveldb/status.h"
  16 #include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
  17
  18 namespace sync_file_system {
  19 namespace drive_backend {
  20
  21 LevelDBWrapper::Iterator::Iterator(LevelDBWrapper* db)
  22     : db_(db),
  23       db_iterator_(db->db_->NewIterator(leveldb::ReadOptions())),
  24       map_iterator_(db->pending_.end()) {}
  25
  26 LevelDBWrapper::Iterator::~Iterator() {}
  27
  28 bool LevelDBWrapper::Iterator::Valid() {
  29   return map_iterator_ != db_->pending_.end() ||
  30       db_iterator_->Valid();
  31 }
  32
  33 void LevelDBWrapper::Iterator::SeekToFirst() {
  34   map_iterator_ = db_->pending_.begin();
  35   db_iterator_->SeekToFirst();
  36   AdvanceIterators();
  37 }
  38
  39 void LevelDBWrapper::Iterator::SeekToLast() {
  40   map_iterator_ = db_->pending_.end();
  41   db_iterator_->SeekToLast();
  42 }
  43
  44 void LevelDBWrapper::Iterator::Seek(const std::string& target) {
  45   map_iterator_ = db_->pending_.lower_bound(target);
  46   db_iterator_->Seek(target);
  47   AdvanceIterators();
  48 }
  49
  50 void LevelDBWrapper::Iterator::Next() {
  51   if (map_iterator_ == db_->pending_.end()) {
  52     if (db_iterator_->Valid())
  53       db_iterator_->Next();
  54     return;
  55   }
  56
  57   if (db_iterator_->Valid()) {
  58     int comp = db_iterator_->key().compare(map_iterator_->first);
  59     if (comp <= 0)
  60       db_iterator_->Next();
  61     if (comp >= 0)
  62       ++map_iterator_;
  63   } else {
  64     ++map_iterator_;
  65   }
  66
  67   AdvanceIterators();
  68 }
  69
  70 void LevelDBWrapper::Iterator::Delete() {
  71   DCHECK(Valid());
  72
  73   const std::string key_str = key().ToString();
  74   Transaction deletion(DELETE_OPERATION, std::string());
  75   map_iterator_ = db_->pending_.insert(map_iterator_,
  76                                        std::make_pair(key_str, deletion));
  77   // In case that |db_->pending_| already had an entry for the key, we have to
  78   // update the value.
  79   map_iterator_->second = deletion;
  80
  81   ++(db_->num_deletes_);
  82
  83   AdvanceIterators();
  84 }
  85
  86 leveldb::Slice LevelDBWrapper::Iterator::key() {
  87   DCHECK(Valid());
  88
  89   if (!db_iterator_->Valid())
  90     return map_iterator_->first;
  91   if (map_iterator_ == db_->pending_.end())
  92     return db_iterator_->key();
  93
  94   const leveldb::Slice db_key = db_iterator_->key();
  95   const leveldb::Slice map_key = map_iterator_->first;
  96   return (db_key.compare(map_key) < 0) ? db_key : map_key;
  97 }
  98
  99 leveldb::Slice LevelDBWrapper::Iterator::value() {
 100   DCHECK(Valid());
 101
 102   if (!db_iterator_->Valid())
 103     return map_iterator_->second.second;
 104   if (map_iterator_ == db_->pending_.end())
 105     return db_iterator_->value();
 106
 107   const leveldb::Slice db_key = db_iterator_->key();
 108   const leveldb::Slice map_key = map_iterator_->first;
 109   if (db_key.compare(map_key) < 0)
 110     return db_iterator_->value();
 111
 112   DCHECK(map_iterator_->second.first == PUT_OPERATION);
 113   return map_iterator_->second.second;
 114 }
 115
 116 void LevelDBWrapper::Iterator::AdvanceIterators() {
 117   // Iterator is valid iff any of below holds:
 118   // - |db_itr.key| < |map_itr.key| OR |map_itr| == end()
 119   // - (|db_itr.key| >= |map_itr.key| OR !|db_itr|->IsValid())
 120   //   AND |map_itr.operation| == PUT_OPERATION
 121
 122   if (map_iterator_ == db_->pending_.end())
 123     return;
 124
 125   while (map_iterator_ != db_->pending_.end() && db_iterator_->Valid()) {
 126     int cmp_key = db_iterator_->key().compare(map_iterator_->first);
 127     if (cmp_key < 0 || map_iterator_->second.first == PUT_OPERATION)
 128       return;
 129     // |db_itr.key| >= |map_itr.key| && |map_itr.operation| != PUT_OPERATION
 130     if (cmp_key == 0)
 131       db_iterator_->Next();
 132     ++map_iterator_;
 133   }
 134
 135   if (db_iterator_->Valid())
 136     return;
 137
 138   while (map_iterator_ != db_->pending_.end() &&
 139          map_iterator_->second.first == DELETE_OPERATION)
 140     ++map_iterator_;
 141 }
 142
 143 // ---------------------------------------------------------------------------
 144 // LevelDBWrapper class
 145 // ---------------------------------------------------------------------------
 146 LevelDBWrapper::LevelDBWrapper(scoped_ptr<leveldb::DB> db)
 147     : db_(db.Pass()), num_puts_(0), num_deletes_(0) {
 148   DCHECK(db_);
 149 }
 150
 151 LevelDBWrapper::~LevelDBWrapper() {}
 152
 153 void LevelDBWrapper::Put(const std::string& key, const std::string& value) {
 154   pending_[key] = Transaction(PUT_OPERATION, value);
 155   ++num_puts_;
 156 }
 157
 158 void LevelDBWrapper::Delete(const std::string& key) {
 159   pending_[key] = Transaction(DELETE_OPERATION, std::string());
 160   ++num_deletes_;
 161 }
 162
 163 leveldb::Status LevelDBWrapper::Get(const std::string& key,
 164                                     std::string* value) {
 165   PendingOperationMap::iterator itr = pending_.find(key);
 166   if (itr == pending_.end())
 167     return db_->Get(leveldb::ReadOptions(), key, value);
 168
 169   const Transaction& transaction = itr->second;
 170   switch (transaction.first) {
 171     case PUT_OPERATION:
 172       *value = transaction.second;
 173       return leveldb::Status();
 174     case DELETE_OPERATION:
 175       return leveldb::Status::NotFound(leveldb::Slice());
 176   }
 177   NOTREACHED();
 178   return leveldb::Status::NotSupported("Not supported operation.");
 179 }
 180
 181 scoped_ptr<LevelDBWrapper::Iterator> LevelDBWrapper::NewIterator() {
 182   return make_scoped_ptr(new Iterator(this));
 183 }
 184
 185 leveldb::Status LevelDBWrapper::Commit() {
 186   leveldb::WriteBatch batch;
 187   for (PendingOperationMap::iterator itr = pending_.begin();
 188        itr != pending_.end(); ++itr) {
 189     const leveldb::Slice key(itr->first);
 190     const Transaction& transaction = itr->second;
 191     switch (transaction.first) {
 192       case PUT_OPERATION:
 193         batch.Put(key, transaction.second);
 194         break;
 195       case DELETE_OPERATION:
 196         batch.Delete(key);
 197         break;
 198     }
 199   }
 200
 201   leveldb::Status status = db_->Write(leveldb::WriteOptions(), &batch);
 202   // TODO(peria): Decide what to do depending on |status|.
 203   if (status.ok())
 204     Clear();
 205
 206   return status;
 207 }
 208
 209 void LevelDBWrapper::Clear() {
 210   pending_.clear();
 211   num_puts_ = 0;
 212   num_deletes_ = 0;
 213 }
 214
 215 leveldb::DB* LevelDBWrapper::GetLevelDB() {
 216   return db_.get();
 217 }
 218
 219 }  // namespace drive_backend
 220 }  // namespace sync_file_system