1/* 2 * Copyright (C) 2011 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#include "config.h" 27#include "LevelDBTransaction.h" 28 29#if ENABLE(INDEXED_DATABASE) 30#if USE(LEVELDB) 31 32#include "LevelDBDatabase.h" 33#include "LevelDBSlice.h" 34#include "LevelDBWriteBatch.h" 35#include <leveldb/db.h> 36 37namespace WebCore { 38 39PassRefPtr<LevelDBTransaction> LevelDBTransaction::create(LevelDBDatabase* db) 40{ 41 return adoptRef(new LevelDBTransaction(db)); 42} 43 44LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db) 45 : m_db(db) 46 , m_snapshot(db) 47 , m_comparator(db->comparator()) 48 , m_finished(false) 49{ 50 m_tree.abstractor().m_comparator = m_comparator; 51} 52 53void LevelDBTransaction::clearTree() 54{ 55 TreeType::Iterator iterator; 56 iterator.start_iter_least(m_tree); 57 58 Vector<AVLTreeNode*> nodes; 59 60 while (*iterator) { 61 nodes.append(*iterator); 62 ++iterator; 63 } 64 m_tree.purge(); 65 66 for (size_t i = 0; i < nodes.size(); ++i) 67 delete(nodes[i]); 68} 69 70LevelDBTransaction::~LevelDBTransaction() 71{ 72 clearTree(); 73} 74 75static void initVector(const LevelDBSlice& slice, Vector<char>* vector) 76{ 77 vector->clear(); 78 vector->append(slice.begin(), slice.end() - slice.begin()); 79} 80 81void LevelDBTransaction::set(const LevelDBSlice& key, const Vector<char>& value, bool deleted) 82{ 83 ASSERT(!m_finished); 84 bool newNode = false; 85 AVLTreeNode* node = m_tree.search(key); 86 87 if (!node) { 88 node = new AVLTreeNode; 89 initVector(key, &node->key); 90 m_tree.insert(node); 91 newNode = true; 92 } 93 node->value = value; 94 node->deleted = deleted; 95 96 if (newNode) 97 notifyIteratorsOfTreeChange(); 98} 99 100void LevelDBTransaction::put(const LevelDBSlice& key, const Vector<char>& value) 101{ 102 set(key, value, false); 103} 104 105void LevelDBTransaction::remove(const LevelDBSlice& key) 106{ 107 set(key, Vector<char>(), true); 108} 109 110bool LevelDBTransaction::safeGet(const LevelDBSlice& key, Vector<char>& value, bool& found) 111{ 112 found = false; 113 ASSERT(!m_finished); 114 AVLTreeNode* node = m_tree.search(key); 115 116 if (node) { 117 if (node->deleted) 118 return true; 119 120 value = node->value; 121 found = true; 122 return true; 123 } 124 125 bool ok = m_db->safeGet(key, value, found, &m_snapshot); 126 if (!ok) { 127 ASSERT(!found); 128 return false; 129 } 130 return true; 131} 132 133bool LevelDBTransaction::commit() 134{ 135 ASSERT(!m_finished); 136 137 if (m_tree.is_empty()) { 138 m_finished = true; 139 return true; 140 } 141 142 std::unique_ptr<LevelDBWriteBatch> writeBatch = std::make_unique<LevelDBWriteBatch>(); 143 144 TreeType::Iterator iterator; 145 iterator.start_iter_least(m_tree); 146 147 while (*iterator) { 148 AVLTreeNode* node = *iterator; 149 if (!node->deleted) 150 writeBatch->put(node->key, node->value); 151 else 152 writeBatch->remove(node->key); 153 ++iterator; 154 } 155 156 if (!m_db->write(*writeBatch)) 157 return false; 158 159 clearTree(); 160 m_finished = true; 161 return true; 162} 163 164void LevelDBTransaction::rollback() 165{ 166 ASSERT(!m_finished); 167 m_finished = true; 168 clearTree(); 169} 170 171std::unique_ptr<LevelDBIterator> LevelDBTransaction::createIterator() 172{ 173 return std::make_unique<TransactionIterator>(this); 174} 175 176bool LevelDBTransaction::TreeIterator::isValid() const 177{ 178 return *m_iterator; 179} 180 181void LevelDBTransaction::TreeIterator::seekToLast() 182{ 183 m_iterator.start_iter_greatest(*m_tree); 184 if (isValid()) 185 m_key = (*m_iterator)->key; 186} 187 188void LevelDBTransaction::TreeIterator::seek(const LevelDBSlice& target) 189{ 190 m_iterator.start_iter(*m_tree, target, TreeType::EQUAL); 191 if (!isValid()) 192 m_iterator.start_iter(*m_tree, target, TreeType::GREATER); 193 194 if (isValid()) 195 m_key = (*m_iterator)->key; 196} 197 198void LevelDBTransaction::TreeIterator::next() 199{ 200 ASSERT(isValid()); 201 ++m_iterator; 202 if (isValid()) { 203 ASSERT(m_transaction->m_comparator->compare((*m_iterator)->key, m_key) > 0); 204 (void)m_transaction; 205 m_key = (*m_iterator)->key; 206 } 207} 208 209void LevelDBTransaction::TreeIterator::prev() 210{ 211 ASSERT(isValid()); 212 --m_iterator; 213 if (isValid()) { 214 ASSERT(m_tree->abstractor().m_comparator->compare((*m_iterator)->key, m_key) < 0); 215 m_key = (*m_iterator)->key; 216 } 217} 218 219LevelDBSlice LevelDBTransaction::TreeIterator::key() const 220{ 221 ASSERT(isValid()); 222 return m_key; 223} 224 225LevelDBSlice LevelDBTransaction::TreeIterator::value() const 226{ 227 ASSERT(isValid()); 228 ASSERT(!isDeleted()); 229 return (*m_iterator)->value; 230} 231 232bool LevelDBTransaction::TreeIterator::isDeleted() const 233{ 234 ASSERT(isValid()); 235 return (*m_iterator)->deleted; 236} 237 238void LevelDBTransaction::TreeIterator::reset() 239{ 240 ASSERT(isValid()); 241 m_iterator.start_iter(*m_tree, m_key, TreeType::EQUAL); 242 ASSERT(isValid()); 243} 244 245LevelDBTransaction::TreeIterator::~TreeIterator() 246{ 247} 248 249LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction) 250 : m_tree(&transaction->m_tree) 251 , m_transaction(transaction) 252{ 253} 254 255LevelDBTransaction::TransactionIterator::TransactionIterator(PassRefPtr<LevelDBTransaction> transaction) 256 : m_transaction(transaction) 257 , m_comparator(m_transaction->m_comparator) 258 , m_treeIterator(std::make_unique<TreeIterator>((m_transaction.get()))) 259 , m_dbIterator(m_transaction->m_db->createIterator(&m_transaction->m_snapshot)) 260 , m_current(0) 261 , m_direction(kForward) 262 , m_treeChanged(false) 263{ 264 m_transaction->registerIterator(this); 265} 266 267LevelDBTransaction::TransactionIterator::~TransactionIterator() 268{ 269 m_transaction->unregisterIterator(this); 270} 271 272bool LevelDBTransaction::TransactionIterator::isValid() const 273{ 274 return m_current; 275} 276 277void LevelDBTransaction::TransactionIterator::seekToLast() 278{ 279 m_treeIterator->seekToLast(); 280 m_dbIterator->seekToLast(); 281 m_direction = kReverse; 282 283 handleConflictsAndDeletes(); 284 setCurrentIteratorToLargestKey(); 285} 286 287void LevelDBTransaction::TransactionIterator::seek(const LevelDBSlice& target) 288{ 289 m_treeIterator->seek(target); 290 m_dbIterator->seek(target); 291 m_direction = kForward; 292 293 handleConflictsAndDeletes(); 294 setCurrentIteratorToSmallestKey(); 295} 296 297void LevelDBTransaction::TransactionIterator::next() 298{ 299 ASSERT(isValid()); 300 if (m_treeChanged) 301 refreshTreeIterator(); 302 303 if (m_direction != kForward) { 304 // Ensure the non-current iterator is positioned after key(). 305 306 LevelDBIterator* nonCurrent = (m_current == m_dbIterator.get()) ? m_treeIterator.get() : m_dbIterator.get(); 307 308 nonCurrent->seek(key()); 309 if (nonCurrent->isValid() && !m_comparator->compare(nonCurrent->key(), key())) 310 nonCurrent->next(); // Take an extra step so the non-current key is strictly greater than key(). 311 312 ASSERT(!nonCurrent->isValid() || m_comparator->compare(nonCurrent->key(), key()) > 0); 313 314 m_direction = kForward; 315 } 316 317 m_current->next(); 318 handleConflictsAndDeletes(); 319 setCurrentIteratorToSmallestKey(); 320} 321 322void LevelDBTransaction::TransactionIterator::prev() 323{ 324 ASSERT(isValid()); 325 if (m_treeChanged) 326 refreshTreeIterator(); 327 328 if (m_direction != kReverse) { 329 // Ensure the non-current iterator is positioned before key(). 330 331 LevelDBIterator* nonCurrent = (m_current == m_dbIterator.get()) ? m_treeIterator.get() : m_dbIterator.get(); 332 333 nonCurrent->seek(key()); 334 if (nonCurrent->isValid()) { 335 // Iterator is at first entry >= key(). 336 // Step back once to entry < key. 337 // This is why we don't check for the keys being the same before 338 // stepping, like we do in next() above. 339 nonCurrent->prev(); 340 } else 341 nonCurrent->seekToLast(); // Iterator has no entries >= key(). Position at last entry. 342 343 ASSERT(!nonCurrent->isValid() || m_comparator->compare(nonCurrent->key(), key()) < 0); 344 345 m_direction = kReverse; 346 } 347 348 m_current->prev(); 349 handleConflictsAndDeletes(); 350 setCurrentIteratorToLargestKey(); 351} 352 353LevelDBSlice LevelDBTransaction::TransactionIterator::key() const 354{ 355 ASSERT(isValid()); 356 if (m_treeChanged) 357 refreshTreeIterator(); 358 return m_current->key(); 359} 360 361LevelDBSlice LevelDBTransaction::TransactionIterator::value() const 362{ 363 ASSERT(isValid()); 364 if (m_treeChanged) 365 refreshTreeIterator(); 366 return m_current->value(); 367} 368 369void LevelDBTransaction::TransactionIterator::treeChanged() 370{ 371 m_treeChanged = true; 372} 373 374void LevelDBTransaction::TransactionIterator::refreshTreeIterator() const 375{ 376 ASSERT(m_treeChanged); 377 378 m_treeChanged = false; 379 380 if (m_treeIterator->isValid() && m_treeIterator.get() == m_current) { 381 m_treeIterator->reset(); 382 return; 383 } 384 385 if (m_dbIterator->isValid()) { 386 387 // There could be new nodes in the tree that we should iterate over. 388 389 if (m_direction == kForward) { 390 // Try to seek tree iterator to something greater than the db iterator. 391 m_treeIterator->seek(m_dbIterator->key()); 392 if (m_treeIterator->isValid() && !m_comparator->compare(m_treeIterator->key(), m_dbIterator->key())) 393 m_treeIterator->next(); // If equal, take another step so the tree iterator is strictly greater. 394 } else { 395 // If going backward, seek to a key less than the db iterator. 396 ASSERT(m_direction == kReverse); 397 m_treeIterator->seek(m_dbIterator->key()); 398 if (m_treeIterator->isValid()) 399 m_treeIterator->prev(); 400 } 401 } 402} 403 404bool LevelDBTransaction::TransactionIterator::treeIteratorIsLower() const 405{ 406 return m_comparator->compare(m_treeIterator->key(), m_dbIterator->key()) < 0; 407} 408 409bool LevelDBTransaction::TransactionIterator::treeIteratorIsHigher() const 410{ 411 return m_comparator->compare(m_treeIterator->key(), m_dbIterator->key()) > 0; 412} 413 414void LevelDBTransaction::TransactionIterator::handleConflictsAndDeletes() 415{ 416 bool loop = true; 417 418 while (loop) { 419 loop = false; 420 421 if (m_treeIterator->isValid() && m_dbIterator->isValid() && !m_comparator->compare(m_treeIterator->key(), m_dbIterator->key())) { 422 // For equal keys, the tree iterator takes precedence, so move the database iterator another step. 423 if (m_direction == kForward) 424 m_dbIterator->next(); 425 else 426 m_dbIterator->prev(); 427 } 428 429 // Skip over delete markers in the tree iterator until it catches up with the db iterator. 430 if (m_treeIterator->isValid() && m_treeIterator->isDeleted()) { 431 if (m_direction == kForward && (!m_dbIterator->isValid() || treeIteratorIsLower())) { 432 m_treeIterator->next(); 433 loop = true; 434 } else if (m_direction == kReverse && (!m_dbIterator->isValid() || treeIteratorIsHigher())) { 435 m_treeIterator->prev(); 436 loop = true; 437 } 438 } 439 } 440} 441 442void LevelDBTransaction::TransactionIterator::setCurrentIteratorToSmallestKey() 443{ 444 LevelDBIterator* smallest = 0; 445 446 if (m_treeIterator->isValid()) 447 smallest = m_treeIterator.get(); 448 449 if (m_dbIterator->isValid()) { 450 if (!smallest || m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0) 451 smallest = m_dbIterator.get(); 452 } 453 454 m_current = smallest; 455} 456 457void LevelDBTransaction::TransactionIterator::setCurrentIteratorToLargestKey() 458{ 459 LevelDBIterator* largest = 0; 460 461 if (m_treeIterator->isValid()) 462 largest = m_treeIterator.get(); 463 464 if (m_dbIterator->isValid()) { 465 if (!largest || m_comparator->compare(m_dbIterator->key(), largest->key()) > 0) 466 largest = m_dbIterator.get(); 467 } 468 469 m_current = largest; 470} 471 472void LevelDBTransaction::registerIterator(TransactionIterator* iterator) 473{ 474 ASSERT(!m_iterators.contains(iterator)); 475 m_iterators.add(iterator); 476} 477 478void LevelDBTransaction::unregisterIterator(TransactionIterator* iterator) 479{ 480 ASSERT(m_iterators.contains(iterator)); 481 m_iterators.remove(iterator); 482} 483 484void LevelDBTransaction::notifyIteratorsOfTreeChange() 485{ 486 for (HashSet<TransactionIterator*>::iterator i = m_iterators.begin(); i != m_iterators.end(); ++i) { 487 TransactionIterator* transactionIterator = *i; 488 transactionIterator->treeChanged(); 489 } 490} 491 492LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db) 493 : m_db(db) 494 , m_writeBatch(std::make_unique<LevelDBWriteBatch>()) 495 , m_finished(false) 496{ 497} 498 499LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction() 500{ 501 m_writeBatch->clear(); 502} 503 504void LevelDBWriteOnlyTransaction::remove(const LevelDBSlice& key) 505{ 506 ASSERT(!m_finished); 507 m_writeBatch->remove(key); 508} 509 510bool LevelDBWriteOnlyTransaction::commit() 511{ 512 ASSERT(!m_finished); 513 514 if (!m_db->write(*m_writeBatch)) 515 return false; 516 517 m_finished = true; 518 m_writeBatch->clear(); 519 return true; 520} 521 522} // namespace WebCore 523 524#endif // USE(LEVELDB) 525#endif // ENABLE(INDEXED_DATABASE) 526