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