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