leveldb_transaction.cc revision 0529e5d033099cbfc42635f6f6183833b09dff6e 
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
133leveldb::Status LevelDBTransaction::DataIterator::SeekToLast() {
134  iterator_ = data_->end();
135  if (iterator_ != data_->begin())
136    --iterator_;
137  return leveldb::Status::OK();
138}
139
140leveldb::Status LevelDBTransaction::DataIterator::Seek(
141    const StringPiece& target) {
142  iterator_ = data_->lower_bound(target);
143  return leveldb::Status::OK();
144}
145
146leveldb::Status LevelDBTransaction::DataIterator::Next() {
147  DCHECK(IsValid());
148  ++iterator_;
149  return leveldb::Status::OK();
150}
151
152leveldb::Status LevelDBTransaction::DataIterator::Prev() {
153  DCHECK(IsValid());
154  if (iterator_ != data_->begin())
155    --iterator_;
156  else
157    iterator_ = data_->end();
158  return leveldb::Status::OK();
159}
160
161StringPiece LevelDBTransaction::DataIterator::Key() const {
162  DCHECK(IsValid());
163  return iterator_->first;
164}
165
166StringPiece LevelDBTransaction::DataIterator::Value() const {
167  DCHECK(IsValid());
168  DCHECK(!IsDeleted());
169  return iterator_->second->value;
170}
171
172bool LevelDBTransaction::DataIterator::IsDeleted() const {
173  DCHECK(IsValid());
174  return iterator_->second->deleted;
175}
176
177LevelDBTransaction::DataIterator::~DataIterator() {}
178
179LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
180    : data_(&transaction->data_),
181      iterator_(data_->end()) {}
182
183scoped_ptr<LevelDBTransaction::TransactionIterator>
184LevelDBTransaction::TransactionIterator::Create(
185    scoped_refptr<LevelDBTransaction> transaction) {
186  return make_scoped_ptr(new TransactionIterator(transaction));
187}
188
189LevelDBTransaction::TransactionIterator::TransactionIterator(
190    scoped_refptr<LevelDBTransaction> transaction)
191    : transaction_(transaction),
192      comparator_(transaction_->comparator_),
193      data_iterator_(DataIterator::Create(transaction_.get())),
194      db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
195      current_(0),
196      direction_(FORWARD),
197      data_changed_(false) {
198  transaction_->RegisterIterator(this);
199}
200
201LevelDBTransaction::TransactionIterator::~TransactionIterator() {
202  transaction_->UnregisterIterator(this);
203}
204
205bool LevelDBTransaction::TransactionIterator::IsValid() const {
206  return !!current_;
207}
208
209leveldb::Status LevelDBTransaction::TransactionIterator::SeekToLast() {
210  leveldb::Status s = data_iterator_->SeekToLast();
211  DCHECK(s.ok());
212  s = db_iterator_->SeekToLast();
213  if (!s.ok())
214    return s;
215  direction_ = REVERSE;
216
217  HandleConflictsAndDeletes();
218  SetCurrentIteratorToLargestKey();
219  return s;
220}
221
222leveldb::Status LevelDBTransaction::TransactionIterator::Seek(
223    const StringPiece& target) {
224  leveldb::Status s = data_iterator_->Seek(target);
225  DCHECK(s.ok());
226  s = db_iterator_->Seek(target);
227  if (!s.ok())
228    return s;
229  direction_ = FORWARD;
230
231  HandleConflictsAndDeletes();
232  SetCurrentIteratorToSmallestKey();
233  return s;
234}
235
236leveldb::Status LevelDBTransaction::TransactionIterator::Next() {
237  DCHECK(IsValid());
238  if (data_changed_)
239    RefreshDataIterator();
240
241  leveldb::Status s;
242  if (direction_ != FORWARD) {
243    // Ensure the non-current iterator is positioned after Key().
244
245    LevelDBIterator* non_current = (current_ == db_iterator_.get())
246                                       ? data_iterator_.get()
247                                       : db_iterator_.get();
248
249    non_current->Seek(Key());
250    if (non_current->IsValid() &&
251        !comparator_->Compare(non_current->Key(), Key())) {
252      // Take an extra step so the non-current key is
253      // strictly greater than Key().
254      s = non_current->Next();
255      if (!s.ok())
256        return s;
257    }
258    DCHECK(!non_current->IsValid() ||
259           comparator_->Compare(non_current->Key(), Key()) > 0);
260
261    direction_ = FORWARD;
262  }
263
264  s = current_->Next();
265  if (!s.ok())
266    return s;
267  HandleConflictsAndDeletes();
268  SetCurrentIteratorToSmallestKey();
269  return leveldb::Status::OK();
270}
271
272leveldb::Status LevelDBTransaction::TransactionIterator::Prev() {
273  DCHECK(IsValid());
274  leveldb::Status s;
275  if (data_changed_)
276    RefreshDataIterator();
277
278  if (direction_ != REVERSE) {
279    // Ensure the non-current iterator is positioned before Key().
280
281    LevelDBIterator* non_current = (current_ == db_iterator_.get())
282                                       ? data_iterator_.get()
283                                       : db_iterator_.get();
284
285    s = non_current->Seek(Key());
286    if (!s.ok())
287      return s;
288    if (non_current->IsValid()) {
289      // Iterator is at first entry >= Key().
290      // Step back once to entry < key.
291      // This is why we don't check for the keys being the same before
292      // stepping, like we do in Next() above.
293      non_current->Prev();
294    } else {
295      // Iterator has no entries >= Key(). Position at last entry.
296      non_current->SeekToLast();
297    }
298    DCHECK(!non_current->IsValid() ||
299           comparator_->Compare(non_current->Key(), Key()) < 0);
300
301    direction_ = REVERSE;
302  }
303
304  s = current_->Prev();
305  if (!s.ok())
306    return s;
307  HandleConflictsAndDeletes();
308  SetCurrentIteratorToLargestKey();
309  return leveldb::Status::OK();
310}
311
312StringPiece LevelDBTransaction::TransactionIterator::Key() const {
313  DCHECK(IsValid());
314  if (data_changed_)
315    RefreshDataIterator();
316  return current_->Key();
317}
318
319StringPiece LevelDBTransaction::TransactionIterator::Value() const {
320  DCHECK(IsValid());
321  if (data_changed_)
322    RefreshDataIterator();
323  return current_->Value();
324}
325
326void LevelDBTransaction::TransactionIterator::DataChanged() {
327  data_changed_ = true;
328}
329
330void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const {
331  DCHECK(data_changed_);
332
333  data_changed_ = false;
334
335  if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
336    return;
337  }
338
339  if (db_iterator_->IsValid()) {
340    // There could be new records in data that we should iterate over.
341
342    if (direction_ == FORWARD) {
343      // Try to seek data iterator to something greater than the db iterator.
344      data_iterator_->Seek(db_iterator_->Key());
345      if (data_iterator_->IsValid() &&
346          !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
347        // If equal, take another step so the data iterator is strictly greater.
348        data_iterator_->Next();
349      }
350    } else {
351      // If going backward, seek to a key less than the db iterator.
352      DCHECK_EQ(REVERSE, direction_);
353      data_iterator_->Seek(db_iterator_->Key());
354      if (data_iterator_->IsValid())
355        data_iterator_->Prev();
356    }
357  }
358}
359
360bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const {
361  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0;
362}
363
364bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const {
365  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0;
366}
367
368void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
369  bool loop = true;
370
371  while (loop) {
372    loop = false;
373
374    if (data_iterator_->IsValid() && db_iterator_->IsValid() &&
375        !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
376      // For equal keys, the data iterator takes precedence, so move the
377      // database iterator another step.
378      if (direction_ == FORWARD)
379        db_iterator_->Next();
380      else
381        db_iterator_->Prev();
382    }
383
384    // Skip over delete markers in the data iterator until it catches up with
385    // the db iterator.
386    if (data_iterator_->IsValid() && data_iterator_->IsDeleted()) {
387      if (direction_ == FORWARD &&
388          (!db_iterator_->IsValid() || DataIteratorIsLower())) {
389        data_iterator_->Next();
390        loop = true;
391      } else if (direction_ == REVERSE &&
392                 (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
393        data_iterator_->Prev();
394        loop = true;
395      }
396    }
397  }
398}
399
400void
401LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
402  LevelDBIterator* smallest = 0;
403
404  if (data_iterator_->IsValid())
405    smallest = data_iterator_.get();
406
407  if (db_iterator_->IsValid()) {
408    if (!smallest ||
409        comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
410      smallest = db_iterator_.get();
411  }
412
413  current_ = smallest;
414}
415
416void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
417  LevelDBIterator* largest = 0;
418
419  if (data_iterator_->IsValid())
420    largest = data_iterator_.get();
421
422  if (db_iterator_->IsValid()) {
423    if (!largest ||
424        comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
425      largest = db_iterator_.get();
426  }
427
428  current_ = largest;
429}
430
431void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) {
432  DCHECK(iterators_.find(iterator) == iterators_.end());
433  iterators_.insert(iterator);
434}
435
436void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
437  DCHECK(iterators_.find(iterator) != iterators_.end());
438  iterators_.erase(iterator);
439}
440
441void LevelDBTransaction::NotifyIterators() {
442  for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
443       i != iterators_.end();
444       ++i) {
445    TransactionIterator* transaction_iterator = *i;
446    transaction_iterator->DataChanged();
447  }
448}
449
450scoped_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create(
451    LevelDBDatabase* db) {
452  return make_scoped_ptr(new LevelDBDirectTransaction(db));
453}
454
455LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db)
456    : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
457
458LevelDBDirectTransaction::~LevelDBDirectTransaction() {
459  write_batch_->Clear();
460}
461
462void LevelDBDirectTransaction::Put(const StringPiece& key,
463                                   const std::string* value) {
464  DCHECK(!finished_);
465  write_batch_->Put(key, *value);
466}
467
468leveldb::Status LevelDBDirectTransaction::Get(const StringPiece& key,
469                                              std::string* value,
470                                              bool* found) {
471  *found = false;
472  DCHECK(!finished_);
473
474  leveldb::Status s = db_->Get(key, value, found);
475  DCHECK(s.ok() || !*found);
476  return s;
477}
478
479void LevelDBDirectTransaction::Remove(const StringPiece& key) {
480  DCHECK(!finished_);
481  write_batch_->Remove(key);
482}
483
484leveldb::Status LevelDBDirectTransaction::Commit() {
485  DCHECK(!finished_);
486
487  leveldb::Status s = db_->Write(*write_batch_);
488  if (s.ok()) {
489    finished_ = true;
490    write_batch_->Clear();
491  }
492  return s;
493}
494
495}  // namespace content
496