leveldb_transaction.cc revision a1401311d1ab56c4ed0a474bd38c108f75cb0cd9 
1// Copyright (c) 2013 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 "content/browser/indexed_db/leveldb/leveldb_transaction.h"
6
7#include "base/logging.h"
8#include "content/browser/indexed_db/leveldb/leveldb_database.h"
9#include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
10#include "third_party/leveldatabase/src/include/leveldb/db.h"
11
12using base::StringPiece;
13
14namespace content {
15
16LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
17    : db_(db),
18      snapshot_(db),
19      comparator_(db->Comparator()),
20      data_comparator_(comparator_),
21      data_(data_comparator_),
22      finished_(false) {}
23
24LevelDBTransaction::Record::Record() : deleted(false) {}
25LevelDBTransaction::Record::~Record() {}
26
27void LevelDBTransaction::Clear() {
28  for (DataType::iterator it = data_.begin(); it != data_.end(); ++it) {
29    delete it->second;
30  }
31  data_.clear();
32}
33
34LevelDBTransaction::~LevelDBTransaction() { Clear(); }
35
36void LevelDBTransaction::Set(const StringPiece& key,
37                             std::string* value,
38                             bool deleted) {
39  DCHECK(!finished_);
40  DataType::iterator it = data_.find(key);
41
42  if (it == data_.end()) {
43    Record* record = new Record();
44    record->key.assign(key.begin(), key.end() - key.begin());
45    record->value.swap(*value);
46    record->deleted = deleted;
47    data_[record->key] = record;
48    NotifyIterators();
49    return;
50  }
51
52  it->second->value.swap(*value);
53  it->second->deleted = deleted;
54}
55
56void LevelDBTransaction::Put(const StringPiece& key, std::string* value) {
57  Set(key, value, false);
58}
59
60void LevelDBTransaction::Remove(const StringPiece& key) {
61  std::string empty;
62  Set(key, &empty, true);
63}
64
65leveldb::Status LevelDBTransaction::Get(const StringPiece& key,
66                                        std::string* value,
67                                        bool* found) {
68  *found = false;
69  DCHECK(!finished_);
70  std::string string_key(key.begin(), key.end() - key.begin());
71  DataType::const_iterator it = data_.find(string_key);
72
73  if (it != data_.end()) {
74    if (it->second->deleted)
75      return leveldb::Status::OK();
76
77    *value = it->second->value;
78    *found = true;
79    return leveldb::Status::OK();
80  }
81
82  leveldb::Status s = db_->Get(key, value, found, &snapshot_);
83  if (!s.ok())
84    DCHECK(!*found);
85  return s;
86}
87
88leveldb::Status LevelDBTransaction::Commit() {
89  DCHECK(!finished_);
90
91  if (data_.empty()) {
92    finished_ = true;
93    return leveldb::Status::OK();
94  }
95
96  scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();
97
98  for (DataType::iterator iterator = data_.begin(); iterator != data_.end();
99       ++iterator) {
100    if (!iterator->second->deleted)
101      write_batch->Put(iterator->first, iterator->second->value);
102    else
103      write_batch->Remove(iterator->first);
104  }
105
106  leveldb::Status s = db_->Write(*write_batch);
107  if (s.ok()) {
108    Clear();
109    finished_ = true;
110  }
111  return s;
112}
113
114void LevelDBTransaction::Rollback() {
115  DCHECK(!finished_);
116  finished_ = true;
117  Clear();
118}
119
120scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() {
121  return TransactionIterator::Create(this).PassAs<LevelDBIterator>();
122}
123
124scoped_ptr<LevelDBTransaction::DataIterator>
125LevelDBTransaction::DataIterator::Create(LevelDBTransaction* transaction) {
126  return make_scoped_ptr(new DataIterator(transaction));
127}
128
129bool LevelDBTransaction::DataIterator::IsValid() const {
130  return iterator_ != data_->end();
131}
132
133void LevelDBTransaction::DataIterator::SeekToLast() {
134  iterator_ = data_->end();
135  if (iterator_ != data_->begin())
136    --iterator_;
137}
138
139void LevelDBTransaction::DataIterator::Seek(const StringPiece& target) {
140  iterator_ = data_->lower_bound(target);
141}
142
143void LevelDBTransaction::DataIterator::Next() {
144  DCHECK(IsValid());
145  ++iterator_;
146}
147
148void LevelDBTransaction::DataIterator::Prev() {
149  DCHECK(IsValid());
150  if (iterator_ != data_->begin())
151    --iterator_;
152  else
153    iterator_ = data_->end();
154}
155
156StringPiece LevelDBTransaction::DataIterator::Key() const {
157  DCHECK(IsValid());
158  return iterator_->first;
159}
160
161StringPiece LevelDBTransaction::DataIterator::Value() const {
162  DCHECK(IsValid());
163  DCHECK(!IsDeleted());
164  return iterator_->second->value;
165}
166
167bool LevelDBTransaction::DataIterator::IsDeleted() const {
168  DCHECK(IsValid());
169  return iterator_->second->deleted;
170}
171
172LevelDBTransaction::DataIterator::~DataIterator() {}
173
174LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
175    : data_(&transaction->data_),
176      iterator_(data_->end()) {}
177
178scoped_ptr<LevelDBTransaction::TransactionIterator>
179LevelDBTransaction::TransactionIterator::Create(
180    scoped_refptr<LevelDBTransaction> transaction) {
181  return make_scoped_ptr(new TransactionIterator(transaction));
182}
183
184LevelDBTransaction::TransactionIterator::TransactionIterator(
185    scoped_refptr<LevelDBTransaction> transaction)
186    : transaction_(transaction),
187      comparator_(transaction_->comparator_),
188      data_iterator_(DataIterator::Create(transaction_.get())),
189      db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
190      current_(0),
191      direction_(FORWARD),
192      data_changed_(false) {
193  transaction_->RegisterIterator(this);
194}
195
196LevelDBTransaction::TransactionIterator::~TransactionIterator() {
197  transaction_->UnregisterIterator(this);
198}
199
200bool LevelDBTransaction::TransactionIterator::IsValid() const {
201  return !!current_;
202}
203
204void LevelDBTransaction::TransactionIterator::SeekToLast() {
205  data_iterator_->SeekToLast();
206  db_iterator_->SeekToLast();
207  direction_ = REVERSE;
208
209  HandleConflictsAndDeletes();
210  SetCurrentIteratorToLargestKey();
211}
212
213void LevelDBTransaction::TransactionIterator::Seek(const StringPiece& target) {
214  data_iterator_->Seek(target);
215  db_iterator_->Seek(target);
216  direction_ = FORWARD;
217
218  HandleConflictsAndDeletes();
219  SetCurrentIteratorToSmallestKey();
220}
221
222void LevelDBTransaction::TransactionIterator::Next() {
223  DCHECK(IsValid());
224  if (data_changed_)
225    RefreshDataIterator();
226
227  if (direction_ != FORWARD) {
228    // Ensure the non-current iterator is positioned after Key().
229
230    LevelDBIterator* non_current = (current_ == db_iterator_.get())
231                                       ? data_iterator_.get()
232                                       : db_iterator_.get();
233
234    non_current->Seek(Key());
235    if (non_current->IsValid() &&
236        !comparator_->Compare(non_current->Key(), Key())) {
237      // Take an extra step so the non-current key is
238      // strictly greater than Key().
239      non_current->Next();
240    }
241    DCHECK(!non_current->IsValid() ||
242           comparator_->Compare(non_current->Key(), Key()) > 0);
243
244    direction_ = FORWARD;
245  }
246
247  current_->Next();
248  HandleConflictsAndDeletes();
249  SetCurrentIteratorToSmallestKey();
250}
251
252void LevelDBTransaction::TransactionIterator::Prev() {
253  DCHECK(IsValid());
254  if (data_changed_)
255    RefreshDataIterator();
256
257  if (direction_ != REVERSE) {
258    // Ensure the non-current iterator is positioned before Key().
259
260    LevelDBIterator* non_current = (current_ == db_iterator_.get())
261                                       ? data_iterator_.get()
262                                       : db_iterator_.get();
263
264    non_current->Seek(Key());
265    if (non_current->IsValid()) {
266      // Iterator is at first entry >= Key().
267      // Step back once to entry < key.
268      // This is why we don't check for the keys being the same before
269      // stepping, like we do in Next() above.
270      non_current->Prev();
271    } else {
272      // Iterator has no entries >= Key(). Position at last entry.
273      non_current->SeekToLast();
274    }
275    DCHECK(!non_current->IsValid() ||
276           comparator_->Compare(non_current->Key(), Key()) < 0);
277
278    direction_ = REVERSE;
279  }
280
281  current_->Prev();
282  HandleConflictsAndDeletes();
283  SetCurrentIteratorToLargestKey();
284}
285
286StringPiece LevelDBTransaction::TransactionIterator::Key() const {
287  DCHECK(IsValid());
288  if (data_changed_)
289    RefreshDataIterator();
290  return current_->Key();
291}
292
293StringPiece LevelDBTransaction::TransactionIterator::Value() const {
294  DCHECK(IsValid());
295  if (data_changed_)
296    RefreshDataIterator();
297  return current_->Value();
298}
299
300void LevelDBTransaction::TransactionIterator::DataChanged() {
301  data_changed_ = true;
302}
303
304void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const {
305  DCHECK(data_changed_);
306
307  data_changed_ = false;
308
309  if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
310    return;
311  }
312
313  if (db_iterator_->IsValid()) {
314    // There could be new records in data that we should iterate over.
315
316    if (direction_ == FORWARD) {
317      // Try to seek data iterator to something greater than the db iterator.
318      data_iterator_->Seek(db_iterator_->Key());
319      if (data_iterator_->IsValid() &&
320          !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
321        // If equal, take another step so the data iterator is strictly greater.
322        data_iterator_->Next();
323      }
324    } else {
325      // If going backward, seek to a key less than the db iterator.
326      DCHECK_EQ(REVERSE, direction_);
327      data_iterator_->Seek(db_iterator_->Key());
328      if (data_iterator_->IsValid())
329        data_iterator_->Prev();
330    }
331  }
332}
333
334bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const {
335  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0;
336}
337
338bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const {
339  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0;
340}
341
342void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
343  bool loop = true;
344
345  while (loop) {
346    loop = false;
347
348    if (data_iterator_->IsValid() && db_iterator_->IsValid() &&
349        !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
350      // For equal keys, the data iterator takes precedence, so move the
351      // database iterator another step.
352      if (direction_ == FORWARD)
353        db_iterator_->Next();
354      else
355        db_iterator_->Prev();
356    }
357
358    // Skip over delete markers in the data iterator until it catches up with
359    // the db iterator.
360    if (data_iterator_->IsValid() && data_iterator_->IsDeleted()) {
361      if (direction_ == FORWARD &&
362          (!db_iterator_->IsValid() || DataIteratorIsLower())) {
363        data_iterator_->Next();
364        loop = true;
365      } else if (direction_ == REVERSE &&
366                 (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
367        data_iterator_->Prev();
368        loop = true;
369      }
370    }
371  }
372}
373
374void
375LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
376  LevelDBIterator* smallest = 0;
377
378  if (data_iterator_->IsValid())
379    smallest = data_iterator_.get();
380
381  if (db_iterator_->IsValid()) {
382    if (!smallest ||
383        comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
384      smallest = db_iterator_.get();
385  }
386
387  current_ = smallest;
388}
389
390void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
391  LevelDBIterator* largest = 0;
392
393  if (data_iterator_->IsValid())
394    largest = data_iterator_.get();
395
396  if (db_iterator_->IsValid()) {
397    if (!largest ||
398        comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
399      largest = db_iterator_.get();
400  }
401
402  current_ = largest;
403}
404
405void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) {
406  DCHECK(iterators_.find(iterator) == iterators_.end());
407  iterators_.insert(iterator);
408}
409
410void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
411  DCHECK(iterators_.find(iterator) != iterators_.end());
412  iterators_.erase(iterator);
413}
414
415void LevelDBTransaction::NotifyIterators() {
416  for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
417       i != iterators_.end();
418       ++i) {
419    TransactionIterator* transaction_iterator = *i;
420    transaction_iterator->DataChanged();
421  }
422}
423
424scoped_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create(
425    LevelDBDatabase* db) {
426  return make_scoped_ptr(new LevelDBDirectTransaction(db));
427}
428
429LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db)
430    : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
431
432LevelDBDirectTransaction::~LevelDBDirectTransaction() {
433  write_batch_->Clear();
434}
435
436void LevelDBDirectTransaction::Put(const StringPiece& key,
437                                   const std::string* value) {
438  DCHECK(!finished_);
439  write_batch_->Put(key, *value);
440}
441
442leveldb::Status LevelDBDirectTransaction::Get(const StringPiece& key,
443                                              std::string* value,
444                                              bool* found) {
445  *found = false;
446  DCHECK(!finished_);
447
448  leveldb::Status s = db_->Get(key, value, found);
449  DCHECK(s.ok() || !*found);
450  return s;
451}
452
453void LevelDBDirectTransaction::Remove(const StringPiece& key) {
454  DCHECK(!finished_);
455  write_batch_->Remove(key);
456}
457
458leveldb::Status LevelDBDirectTransaction::Commit() {
459  DCHECK(!finished_);
460
461  leveldb::Status s = db_->Write(*write_batch_);
462  if (s.ok()) {
463    finished_ = true;
464    write_batch_->Clear();
465  }
466  return s;
467}
468
469}  // namespace content
470