diff options
Diffstat (limited to 'content/browser/indexed_db/leveldb/leveldb_transaction.cc')
| -rw-r--r-- | content/browser/indexed_db/leveldb/leveldb_transaction.cc | 490 |
1 files changed, 490 insertions, 0 deletions
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.cc b/content/browser/indexed_db/leveldb/leveldb_transaction.cc new file mode 100644 index 0000000..a8b3a3d --- /dev/null +++ b/content/browser/indexed_db/leveldb/leveldb_transaction.cc @@ -0,0 +1,490 @@ +// Copyright (c) 2013 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "content/browser/indexed_db/leveldb/leveldb_transaction.h" + +#include "base/logging.h" +#include "content/browser/indexed_db/leveldb/leveldb_database.h" +#include "content/browser/indexed_db/leveldb/leveldb_slice.h" +#include "content/browser/indexed_db/leveldb/leveldb_write_batch.h" +#include "third_party/leveldatabase/src/include/leveldb/db.h" + +namespace content { + +scoped_refptr<LevelDBTransaction> LevelDBTransaction::Create( + LevelDBDatabase* db) { + return make_scoped_refptr(new LevelDBTransaction(db)); +} + +LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db) + : db_(db), snapshot_(db), comparator_(db->Comparator()), finished_(false) { + tree_.abstractor().comparator_ = comparator_; +} + +LevelDBTransaction::AVLTreeNode::AVLTreeNode() {} +LevelDBTransaction::AVLTreeNode::~AVLTreeNode() {} + +void LevelDBTransaction::ClearTree() { + TreeType::Iterator iterator; + iterator.start_iter_least(tree_); + + std::vector<AVLTreeNode*> nodes; + + while (*iterator) { + nodes.push_back(*iterator); + ++iterator; + } + tree_.purge(); + + for (size_t i = 0; i < nodes.size(); ++i) + delete nodes[i]; +} + +LevelDBTransaction::~LevelDBTransaction() { ClearTree(); } + +static void InitVector(const LevelDBSlice& slice, std::vector<char>* vector) { + vector->clear(); + vector->insert(vector->end(), slice.begin(), slice.end()); +} + +void LevelDBTransaction::Set(const LevelDBSlice& key, + const std::vector<char>& value, + bool deleted) { + DCHECK(!finished_); + bool new_node = false; + AVLTreeNode* node = tree_.search(key); + + if (!node) { + node = new AVLTreeNode; + InitVector(key, &node->key); + tree_.insert(node); + new_node = true; + } + node->value = value; + node->deleted = deleted; + + if (new_node) + NotifyIteratorsOfTreeChange(); +} + +void LevelDBTransaction::Put(const LevelDBSlice& key, + const std::vector<char>& value) { + Set(key, value, false); +} + +void LevelDBTransaction::Remove(const LevelDBSlice& key) { + Set(key, std::vector<char>(), true); +} + +bool LevelDBTransaction::Get(const LevelDBSlice& key, + std::vector<char>& value, + bool& found) { + found = false; + DCHECK(!finished_); + AVLTreeNode* node = tree_.search(key); + + if (node) { + if (node->deleted) + return true; + + value = node->value; + found = true; + return true; + } + + bool ok = db_->Get(key, value, found, &snapshot_); + if (!ok) { + DCHECK(!found); + return false; + } + return true; +} + +bool LevelDBTransaction::Commit() { + DCHECK(!finished_); + + if (tree_.is_empty()) { + finished_ = true; + return true; + } + + scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create(); + + TreeType::Iterator iterator; + iterator.start_iter_least(tree_); + + while (*iterator) { + AVLTreeNode* node = *iterator; + if (!node->deleted) + write_batch->Put(LevelDBSlice(node->key), LevelDBSlice(node->value)); + else + write_batch->Remove(LevelDBSlice(node->key)); + ++iterator; + } + + if (!db_->Write(*write_batch)) + return false; + + ClearTree(); + finished_ = true; + return true; +} + +void LevelDBTransaction::Rollback() { + DCHECK(!finished_); + finished_ = true; + ClearTree(); +} + +scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() { + return TransactionIterator::Create(this).PassAs<LevelDBIterator>(); +} + +scoped_ptr<LevelDBTransaction::TreeIterator> +LevelDBTransaction::TreeIterator::Create(LevelDBTransaction* transaction) { + return make_scoped_ptr(new TreeIterator(transaction)); +} + +bool LevelDBTransaction::TreeIterator::IsValid() const { return !!*iterator_; } + +void LevelDBTransaction::TreeIterator::SeekToLast() { + iterator_.start_iter_greatest(*tree_); + if (IsValid()) + key_ = (*iterator_)->key; +} + +void LevelDBTransaction::TreeIterator::Seek(const LevelDBSlice& target) { + iterator_.start_iter(*tree_, target, TreeType::EQUAL); + if (!IsValid()) + iterator_.start_iter(*tree_, target, TreeType::GREATER); + + if (IsValid()) + key_ = (*iterator_)->key; +} + +void LevelDBTransaction::TreeIterator::Next() { + DCHECK(IsValid()); + ++iterator_; + if (IsValid()) { + DCHECK(transaction_->comparator_->Compare(LevelDBSlice((*iterator_)->key), + LevelDBSlice(key_)) > + 0); + (void) transaction_; + key_ = (*iterator_)->key; + } +} + +void LevelDBTransaction::TreeIterator::Prev() { + DCHECK(IsValid()); + --iterator_; + if (IsValid()) { + DCHECK(tree_->abstractor().comparator_->Compare( + LevelDBSlice((*iterator_)->key), LevelDBSlice(key_)) < + 0); + key_ = (*iterator_)->key; + } +} + +LevelDBSlice LevelDBTransaction::TreeIterator::Key() const { + DCHECK(IsValid()); + return LevelDBSlice(key_); +} + +LevelDBSlice LevelDBTransaction::TreeIterator::Value() const { + DCHECK(IsValid()); + DCHECK(!IsDeleted()); + return LevelDBSlice((*iterator_)->value); +} + +bool LevelDBTransaction::TreeIterator::IsDeleted() const { + DCHECK(IsValid()); + return (*iterator_)->deleted; +} + +void LevelDBTransaction::TreeIterator::Reset() { + DCHECK(IsValid()); + iterator_.start_iter(*tree_, LevelDBSlice(key_), TreeType::EQUAL); + DCHECK(IsValid()); +} + +LevelDBTransaction::TreeIterator::~TreeIterator() {} + +LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction) + : tree_(&transaction->tree_), transaction_(transaction) {} + +scoped_ptr<LevelDBTransaction::TransactionIterator> +LevelDBTransaction::TransactionIterator::Create( + scoped_refptr<LevelDBTransaction> transaction) { + return make_scoped_ptr(new TransactionIterator(transaction)); +} + +LevelDBTransaction::TransactionIterator::TransactionIterator( + scoped_refptr<LevelDBTransaction> transaction) + : transaction_(transaction), + comparator_(transaction_->comparator_), + tree_iterator_(TreeIterator::Create(transaction_.get())), + db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)), + current_(0), + direction_(FORWARD), + tree_changed_(false) { + transaction_->RegisterIterator(this); +} + +LevelDBTransaction::TransactionIterator::~TransactionIterator() { + transaction_->UnregisterIterator(this); +} + +bool LevelDBTransaction::TransactionIterator::IsValid() const { + return !!current_; +} + +void LevelDBTransaction::TransactionIterator::SeekToLast() { + tree_iterator_->SeekToLast(); + db_iterator_->SeekToLast(); + direction_ = REVERSE; + + HandleConflictsAndDeletes(); + SetCurrentIteratorToLargestKey(); +} + +void LevelDBTransaction::TransactionIterator::Seek(const LevelDBSlice& target) { + tree_iterator_->Seek(target); + db_iterator_->Seek(target); + direction_ = FORWARD; + + HandleConflictsAndDeletes(); + SetCurrentIteratorToSmallestKey(); +} + +void LevelDBTransaction::TransactionIterator::Next() { + DCHECK(IsValid()); + if (tree_changed_) + RefreshTreeIterator(); + + if (direction_ != FORWARD) { + // Ensure the non-current iterator is positioned after Key(). + + LevelDBIterator* non_current = + (current_ == db_iterator_.get()) ? tree_iterator_.get() + : db_iterator_.get(); + + non_current->Seek(Key()); + if (non_current->IsValid() && + !comparator_->Compare(non_current->Key(), Key())) + non_current->Next(); // Take an extra step so the non-current key is + // strictly greater than Key(). + + DCHECK(!non_current->IsValid() || + comparator_->Compare(non_current->Key(), Key()) > 0); + + direction_ = FORWARD; + } + + current_->Next(); + HandleConflictsAndDeletes(); + SetCurrentIteratorToSmallestKey(); +} + +void LevelDBTransaction::TransactionIterator::Prev() { + DCHECK(IsValid()); + if (tree_changed_) + RefreshTreeIterator(); + + if (direction_ != REVERSE) { + // Ensure the non-current iterator is positioned before Key(). + + LevelDBIterator* non_current = + (current_ == db_iterator_.get()) ? tree_iterator_.get() + : db_iterator_.get(); + + non_current->Seek(Key()); + if (non_current->IsValid()) { + // Iterator is at first entry >= Key(). + // Step back once to entry < key. + // This is why we don't check for the keys being the same before + // stepping, like we do in Next() above. + non_current->Prev(); + } else { + non_current->SeekToLast(); // Iterator has no entries >= Key(). Position + // at last entry. + } + DCHECK(!non_current->IsValid() || + comparator_->Compare(non_current->Key(), Key()) < 0); + + direction_ = REVERSE; + } + + current_->Prev(); + HandleConflictsAndDeletes(); + SetCurrentIteratorToLargestKey(); +} + +LevelDBSlice LevelDBTransaction::TransactionIterator::Key() const { + DCHECK(IsValid()); + if (tree_changed_) + RefreshTreeIterator(); + return current_->Key(); +} + +LevelDBSlice LevelDBTransaction::TransactionIterator::Value() const { + DCHECK(IsValid()); + if (tree_changed_) + RefreshTreeIterator(); + return current_->Value(); +} + +void LevelDBTransaction::TransactionIterator::TreeChanged() { + tree_changed_ = true; +} + +void LevelDBTransaction::TransactionIterator::RefreshTreeIterator() const { + DCHECK(tree_changed_); + + tree_changed_ = false; + + if (tree_iterator_->IsValid() && tree_iterator_.get() == current_) { + tree_iterator_->Reset(); + return; + } + + if (db_iterator_->IsValid()) { + + // There could be new nodes in the tree that we should iterate over. + + if (direction_ == FORWARD) { + // Try to seek tree iterator to something greater than the db iterator. + tree_iterator_->Seek(db_iterator_->Key()); + if (tree_iterator_->IsValid() && + !comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key())) + tree_iterator_->Next(); // If equal, take another step so the tree + // iterator is strictly greater. + } else { + // If going backward, seek to a key less than the db iterator. + DCHECK_EQ(REVERSE, direction_); + tree_iterator_->Seek(db_iterator_->Key()); + if (tree_iterator_->IsValid()) + tree_iterator_->Prev(); + } + } +} + +bool LevelDBTransaction::TransactionIterator::TreeIteratorIsLower() const { + return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) < 0; +} + +bool LevelDBTransaction::TransactionIterator::TreeIteratorIsHigher() const { + return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) > 0; +} + +void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() { + bool loop = true; + + while (loop) { + loop = false; + + if (tree_iterator_->IsValid() && db_iterator_->IsValid() && + !comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key())) { + // For equal keys, the tree iterator takes precedence, so move the + // database iterator another step. + if (direction_ == FORWARD) + db_iterator_->Next(); + else + db_iterator_->Prev(); + } + + // Skip over delete markers in the tree iterator until it catches up with + // the db iterator. + if (tree_iterator_->IsValid() && tree_iterator_->IsDeleted()) { + if (direction_ == FORWARD && + (!db_iterator_->IsValid() || TreeIteratorIsLower())) { + tree_iterator_->Next(); + loop = true; + } else if (direction_ == REVERSE && + (!db_iterator_->IsValid() || TreeIteratorIsHigher())) { + tree_iterator_->Prev(); + loop = true; + } + } + } +} + +void +LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() { + LevelDBIterator* smallest = 0; + + if (tree_iterator_->IsValid()) + smallest = tree_iterator_.get(); + + if (db_iterator_->IsValid()) { + if (!smallest || + comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0) + smallest = db_iterator_.get(); + } + + current_ = smallest; +} + +void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() { + LevelDBIterator* largest = 0; + + if (tree_iterator_->IsValid()) + largest = tree_iterator_.get(); + + if (db_iterator_->IsValid()) { + if (!largest || + comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0) + largest = db_iterator_.get(); + } + + current_ = largest; +} + +void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) { + DCHECK(iterators_.find(iterator) == iterators_.end()); + iterators_.insert(iterator); +} + +void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) { + DCHECK(iterators_.find(iterator) != iterators_.end()); + iterators_.erase(iterator); +} + +void LevelDBTransaction::NotifyIteratorsOfTreeChange() { + for (std::set<TransactionIterator*>::iterator i = iterators_.begin(); + i != iterators_.end(); + ++i) { + TransactionIterator* transaction_iterator = *i; + transaction_iterator->TreeChanged(); + } +} + +scoped_ptr<LevelDBWriteOnlyTransaction> LevelDBWriteOnlyTransaction::Create( + LevelDBDatabase* db) { + return make_scoped_ptr(new LevelDBWriteOnlyTransaction(db)); +} + +LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db) + : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {} + +LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction() { + write_batch_->Clear(); +} + +void LevelDBWriteOnlyTransaction::Remove(const LevelDBSlice& key) { + DCHECK(!finished_); + write_batch_->Remove(key); +} + +bool LevelDBWriteOnlyTransaction::Commit() { + DCHECK(!finished_); + + if (!db_->Write(*write_batch_)) + return false; + + finished_ = true; + write_batch_->Clear(); + return true; +} + +} // namespace content |