leveldb_wrapper.cc revision 6e8cce623b6e4fe0c9e4af605d675dd9d0338c38 
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
18namespace sync_file_system {
19namespace drive_backend {
20
21LevelDBWrapper::Iterator::Iterator(LevelDBWrapper* db)
22    : db_(db),
23      db_iterator_(db->db_->NewIterator(leveldb::ReadOptions())),
24      map_iterator_(db->pending_.end()) {}
25
26LevelDBWrapper::Iterator::~Iterator() {}
27
28bool LevelDBWrapper::Iterator::Valid() {
29  return map_iterator_ != db_->pending_.end() ||
30      db_iterator_->Valid();
31}
32
33void LevelDBWrapper::Iterator::SeekToFirst() {
34  map_iterator_ = db_->pending_.begin();
35  db_iterator_->SeekToFirst();
36  AdvanceIterators();
37}
38
39void LevelDBWrapper::Iterator::SeekToLast() {
40  map_iterator_ = db_->pending_.end();
41  db_iterator_->SeekToLast();
42}
43
44void LevelDBWrapper::Iterator::Seek(const std::string& target) {
45  map_iterator_ = db_->pending_.lower_bound(target);
46  db_iterator_->Seek(target);
47  AdvanceIterators();
48}
49
50void 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
70void 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
86leveldb::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
99leveldb::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
116void 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// ---------------------------------------------------------------------------
146LevelDBWrapper::LevelDBWrapper(scoped_ptr<leveldb::DB> db)
147    : db_(db.Pass()), num_puts_(0), num_deletes_(0) {
148  DCHECK(db_);
149}
150
151LevelDBWrapper::~LevelDBWrapper() {}
152
153void LevelDBWrapper::Put(const std::string& key, const std::string& value) {
154  pending_[key] = Transaction(PUT_OPERATION, value);
155  ++num_puts_;
156}
157
158void LevelDBWrapper::Delete(const std::string& key) {
159  pending_[key] = Transaction(DELETE_OPERATION, std::string());
160  ++num_deletes_;
161}
162
163leveldb::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
181scoped_ptr<LevelDBWrapper::Iterator> LevelDBWrapper::NewIterator() {
182  return make_scoped_ptr(new Iterator(this));
183}
184
185leveldb::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
209void LevelDBWrapper::Clear() {
210  pending_.clear();
211  num_puts_ = 0;
212  num_deletes_ = 0;
213}
214
215leveldb::DB* LevelDBWrapper::GetLevelDB() {
216  return db_.get();
217}
218
219}  // namespace drive_backend
220}  // namespace sync_file_system
221