IndexedDB: Replace transaction's AVLTree with std::map

content/browser/indexed_db/leveldb/leveldb_transaction.cc

Index: content/browser/indexed_db/leveldb/leveldb_transaction.cc
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.cc b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
index 5388d44c6f5ad13fbe09a8d0aa825446fe4a4f26..f52c03d685f1c6046e5d64d10104d488197aec58 100644
--- a/content/browser/indexed_db/leveldb/leveldb_transaction.cc
+++ b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
@@ -14,27 +14,21 @@ using base::StringPiece;
 namespace content {
 
 LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
-    : db_(db), snapshot_(db), comparator_(db->Comparator()), finished_(false) {
-  tree_.abstractor().comparator_ = comparator_;
-}
+    : db_(db),
+      snapshot_(db),
+      comparator_(db->Comparator()),
+      tree_comparator_(comparator_),
+      tree_(tree_comparator_),
+      finished_(false) {}
 
-LevelDBTransaction::AVLTreeNode::AVLTreeNode() {}
-LevelDBTransaction::AVLTreeNode::~AVLTreeNode() {}
+LevelDBTransaction::TreeNode::TreeNode() : deleted(false) {}
+LevelDBTransaction::TreeNode::~TreeNode() {}
 
 void LevelDBTransaction::ClearTree() {
-  TreeType::Iterator iterator;
-  iterator.StartIterLeast(&tree_);
-
-  std::vector<AVLTreeNode*> nodes;
-
-  while (*iterator) {
-    nodes.push_back(*iterator);
-    ++iterator;
+  for (TreeType::iterator it = tree_.begin(); it != tree_.end(); ++it) {
+    delete it->second;
   }
-  tree_.Purge();
-
-  for (size_t i = 0; i < nodes.size(); ++i)
-    delete nodes[i];
+  tree_.clear();
 }
 
 LevelDBTransaction::~LevelDBTransaction() { ClearTree(); }
@@ -43,20 +37,20 @@ void LevelDBTransaction::Set(const StringPiece& key,
                              std::string* value,
                              bool deleted) {
   DCHECK(!finished_);
-  bool new_node = false;
-  AVLTreeNode* node = tree_.Search(key);
-
-  if (!node) {
-    node = new AVLTreeNode;
-    node->key = key.as_string();
-    tree_.Insert(node);
-    new_node = true;
+  std::string string_key(key.begin(), key.end() - key.begin());
+  TreeType::iterator it = tree_.find(string_key);
+
+  if (it == tree_.end()) {
+    TreeNode* node = new TreeNode();
+    node->value.swap(*value);
+    node->deleted = deleted;
+    tree_[string_key] = node;
+    NotifyIteratorsOfTreeChange();
+    return;
   }
-  node->value.swap(*value);
-  node->deleted = deleted;
 
-  if (new_node)
-    NotifyIteratorsOfTreeChange();
+  it->second->value.swap(*value);
+  it->second->deleted = deleted;
 }
 
 void LevelDBTransaction::Put(const StringPiece& key, std::string* value) {
@@ -73,13 +67,14 @@ bool LevelDBTransaction::Get(const StringPiece& key,
                              bool* found) {
   *found = false;
   DCHECK(!finished_);
-  AVLTreeNode* node = tree_.Search(key);
+  std::string string_key(key.begin(), key.end() - key.begin());

[alecflett, 2013/09/10 16:46:40]

Not that this is particularly expensive, but can you use StringPiece here?

[jsbell, 2013/09/10 17:00:06]

StringPiece doesn't own its storage, and map::find() takes const key_type& - it
wasn't apparent to me how to avoid key copies.

A more intrusive change would be change this method to take a const string&,
since that probably exists on the stack already.

[jsbell, 2013/09/10 21:29:36]

That turned out to be tricky due to upstream callers that only had slices
themselves, so I went a different direction. 

The map record now holds both the key and value as std::strings, and the map
keys are changed to StringPieces. A record's key is always a StringPiece
pointing at the record's own key property.

Pulling at this thread reveals that key_ is held on to by iterators so they can
be reset if the tree changes. But std::map iterators aren't invalidated by tree
changes (except deletes, which aren't used here) so further simplification is
possible.

+  TreeType::const_iterator it = tree_.find(string_key);
 
-  if (node) {
-    if (node->deleted)
+  if (it != tree_.end()) {
+    if (it->second->deleted)
       return true;
 
-    *value = node->value;
+    *value = it->second->value;

[alecflett, 2013/09/10 16:46:40]

it's too bad there's no way to swap or something here, as the value is going to
probably be the expensive option. Is it kosher for Get() to "return" a
StringPiece* here?

[jsbell, 2013/09/10 17:00:06]

Nope, since the the storage is owned by the tree and could go away at any time.
(Note that there was a copy here in the old code.)

     *found = true;
     return true;
   }
@@ -95,23 +90,19 @@ bool LevelDBTransaction::Get(const StringPiece& key,
 bool LevelDBTransaction::Commit() {
   DCHECK(!finished_);
 
-  if (tree_.IsEmpty()) {
+  if (tree_.empty()) {
     finished_ = true;
     return true;
   }
 
   scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();
 
-  TreeType::Iterator iterator;
-  iterator.StartIterLeast(&tree_);
-
-  while (*iterator) {
-    AVLTreeNode* node = *iterator;
-    if (!node->deleted)
-      write_batch->Put(node->key, node->value);
+  for (TreeType::iterator iterator = tree_.begin(); iterator != tree_.end();
+       ++iterator) {
+    if (!iterator->second->deleted)
+      write_batch->Put(iterator->first, iterator->second->value);
     else
-      write_batch->Remove(node->key);
-    ++iterator;
+      write_batch->Remove(iterator->first);
   }
 
   if (!db_->Write(*write_batch))
@@ -137,39 +128,54 @@ LevelDBTransaction::TreeIterator::Create(LevelDBTransaction* transaction) {
   return make_scoped_ptr(new TreeIterator(transaction));
 }
 
-bool LevelDBTransaction::TreeIterator::IsValid() const { return !!*iterator_; }
+bool LevelDBTransaction::TreeIterator::IsValid() const {
+  return iterator_ != tree_->end();
+}
 
 void LevelDBTransaction::TreeIterator::SeekToLast() {
-  iterator_.StartIterGreatest(tree_);
+  iterator_ = tree_->end();
+  if (iterator_ != tree_->begin())
+    --iterator_;
+
   if (IsValid())
-    key_ = (*iterator_)->key;
+    key_ = iterator_->first;
 }
 
 void LevelDBTransaction::TreeIterator::Seek(const StringPiece& target) {
-  iterator_.StartIter(tree_, target, TreeType::EQUAL);
-  if (!IsValid())
-    iterator_.StartIter(tree_, target, TreeType::GREATER);
+  std::string key(target.begin(), target.end() - target.begin());

[alecflett, 2013/09/10 16:46:40]

copying on a seek seems bad?

[jsbell, 2013/09/10 17:00:06]

I'll look at changing this API here to take a const string& instead, too.

+
+  iterator_ = tree_->find(key);
+  if (!IsValid()) {
+    TreeNode dummy;

[ericu, 2013/09/10 01:00:41]

How about map::lower_bound or map::equal_range?

[jsbell, 2013/09/10 17:00:06]

lower_bound should work - it looks like exactly what I needed, and definitely
better than modifying the tree! I must have missed that when reviewing the
std::map interface. (Or I'll rediscover soon why it won't work here, once I page
everything back into my brain.) 

+    std::pair<TreeType::iterator, bool> position =
+        tree_->insert(make_pair(key, &dummy));
+    iterator_ = position.first;
+    ++iterator_;
+    tree_->erase(position.first);
+  }
 
   if (IsValid())
-    key_ = (*iterator_)->key;
+    key_ = iterator_->first;
 }
 
 void LevelDBTransaction::TreeIterator::Next() {
   DCHECK(IsValid());
   ++iterator_;
   if (IsValid()) {
-    DCHECK_GE(transaction_->comparator_->Compare((*iterator_)->key, key_), 0);
-    key_ = (*iterator_)->key;
+    DCHECK_GE(transaction_->comparator_->Compare(iterator_->first, key_), 0);
+    key_ = iterator_->first;
   }
 }
 
 void LevelDBTransaction::TreeIterator::Prev() {
   DCHECK(IsValid());
-  --iterator_;
+  if (iterator_ != tree_->begin())
+    --iterator_;
+  else
+    iterator_ = tree_->end();
   if (IsValid()) {
-    DCHECK_LT(tree_->abstractor().comparator_->Compare((*iterator_)->key, key_),
-              0);
-    key_ = (*iterator_)->key;
+    DCHECK_LT(transaction_->comparator_->Compare(iterator_->first, key_), 0);
+    key_ = iterator_->first;
   }
 }
 
@@ -181,24 +187,26 @@ StringPiece LevelDBTransaction::TreeIterator::Key() const {
 StringPiece LevelDBTransaction::TreeIterator::Value() const {
   DCHECK(IsValid());
   DCHECK(!IsDeleted());
-  return (*iterator_)->value;
+  return iterator_->second->value;
 }
 
 bool LevelDBTransaction::TreeIterator::IsDeleted() const {
   DCHECK(IsValid());
-  return (*iterator_)->deleted;
+  return iterator_->second->deleted;
 }
 
 void LevelDBTransaction::TreeIterator::Reset() {
   DCHECK(IsValid());
-  iterator_.StartIter(tree_, key_, TreeType::EQUAL);
+  iterator_ = tree_->find(key_);
   DCHECK(IsValid());
 }
 
 LevelDBTransaction::TreeIterator::~TreeIterator() {}
 
 LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction)
-    : tree_(&transaction->tree_), transaction_(transaction) {}
+    : tree_(&transaction->tree_),
+      iterator_(tree_->end()),
+      transaction_(transaction) {}
 
 scoped_ptr<LevelDBTransaction::TransactionIterator>
 LevelDBTransaction::TransactionIterator::Create(