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 221