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