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 12 using base::StringPiece; 13 14 namespace content { 15 16 LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db) 17 : db_(db), snapshot_(db), comparator_(db->Comparator()), finished_(false) { 18 tree_.abstractor().comparator_ = comparator_; 19 } 20 21 LevelDBTransaction::AVLTreeNode::AVLTreeNode() {} 22 LevelDBTransaction::AVLTreeNode::~AVLTreeNode() {} 23 24 void 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 40 LevelDBTransaction::~LevelDBTransaction() { ClearTree(); } 41 42 void 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 62 void LevelDBTransaction::Put(const StringPiece& key, std::string* value) { 63 Set(key, value, false); 64 } 65 66 void LevelDBTransaction::Remove(const StringPiece& key) { 67 std::string empty; 68 Set(key, &empty, true); 69 } 70 71 bool 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 95 bool 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 125 void LevelDBTransaction::Rollback() { 126 DCHECK(!finished_); 127 finished_ = true; 128 ClearTree(); 129 } 130 131 scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() { 132 return TransactionIterator::Create(this).PassAs<LevelDBIterator>(); 133 } 134 135 scoped_ptr<LevelDBTransaction::TreeIterator> 136 LevelDBTransaction::TreeIterator::Create(LevelDBTransaction* transaction) { 137 return make_scoped_ptr(new TreeIterator(transaction)); 138 } 139 140 bool LevelDBTransaction::TreeIterator::IsValid() const { return !!*iterator_; } 141 142 void LevelDBTransaction::TreeIterator::SeekToLast() { 143 iterator_.StartIterGreatest(tree_); 144 if (IsValid()) 145 key_ = (*iterator_)->key; 146 } 147 148 void 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 157 void 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 166 void 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 176 StringPiece LevelDBTransaction::TreeIterator::Key() const { 177 DCHECK(IsValid()); 178 return key_; 179 } 180 181 StringPiece LevelDBTransaction::TreeIterator::Value() const { 182 DCHECK(IsValid()); 183 DCHECK(!IsDeleted()); 184 return (*iterator_)->value; 185 } 186 187 bool LevelDBTransaction::TreeIterator::IsDeleted() const { 188 DCHECK(IsValid()); 189 return (*iterator_)->deleted; 190 } 191 192 void LevelDBTransaction::TreeIterator::Reset() { 193 DCHECK(IsValid()); 194 iterator_.StartIter(tree_, key_, TreeType::EQUAL); 195 DCHECK(IsValid()); 196 } 197 198 LevelDBTransaction::TreeIterator::~TreeIterator() {} 199 200 LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction) 201 : tree_(&transaction->tree_), transaction_(transaction) {} 202 203 scoped_ptr<LevelDBTransaction::TransactionIterator> 204 LevelDBTransaction::TransactionIterator::Create( 205 scoped_refptr<LevelDBTransaction> transaction) { 206 return make_scoped_ptr(new TransactionIterator(transaction)); 207 } 208 209 LevelDBTransaction::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 221 LevelDBTransaction::TransactionIterator::~TransactionIterator() { 222 transaction_->UnregisterIterator(this); 223 } 224 225 bool LevelDBTransaction::TransactionIterator::IsValid() const { 226 return !!current_; 227 } 228 229 void LevelDBTransaction::TransactionIterator::SeekToLast() { 230 tree_iterator_->SeekToLast(); 231 db_iterator_->SeekToLast(); 232 direction_ = REVERSE; 233 234 HandleConflictsAndDeletes(); 235 SetCurrentIteratorToLargestKey(); 236 } 237 238 void 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 247 void 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 276 void 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 310 StringPiece LevelDBTransaction::TransactionIterator::Key() const { 311 DCHECK(IsValid()); 312 if (tree_changed_) 313 RefreshTreeIterator(); 314 return current_->Key(); 315 } 316 317 StringPiece LevelDBTransaction::TransactionIterator::Value() const { 318 DCHECK(IsValid()); 319 if (tree_changed_) 320 RefreshTreeIterator(); 321 return current_->Value(); 322 } 323 324 void LevelDBTransaction::TransactionIterator::TreeChanged() { 325 tree_changed_ = true; 326 } 327 328 void 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 358 bool LevelDBTransaction::TransactionIterator::TreeIteratorIsLower() const { 359 return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) < 0; 360 } 361 362 bool LevelDBTransaction::TransactionIterator::TreeIteratorIsHigher() const { 363 return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) > 0; 364 } 365 366 void 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 398 void 399 LevelDBTransaction::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 414 void 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 429 void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) { 430 DCHECK(iterators_.find(iterator) == iterators_.end()); 431 iterators_.insert(iterator); 432 } 433 434 void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) { 435 DCHECK(iterators_.find(iterator) != iterators_.end()); 436 iterators_.erase(iterator); 437 } 438 439 void 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 448 scoped_ptr<LevelDBWriteOnlyTransaction> LevelDBWriteOnlyTransaction::Create( 449 LevelDBDatabase* db) { 450 return make_scoped_ptr(new LevelDBWriteOnlyTransaction(db)); 451 } 452 453 LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db) 454 : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {} 455 456 LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction() { 457 write_batch_->Clear(); 458 } 459 460 void LevelDBWriteOnlyTransaction::Remove(const StringPiece& key) { 461 DCHECK(!finished_); 462 write_batch_->Remove(key); 463 } 464 465 bool 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