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