1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10 #ifndef ROCKSDB_LITE
11
12 #include "rocksdb/utilities/write_batch_with_index.h"
13 #include <map>
14 #include <memory>
15 #include "db/column_family.h"
16 #include "port/stack_trace.h"
17 #include "test_util/testharness.h"
18 #include "util/random.h"
19 #include "util/string_util.h"
20 #include "utilities/merge_operators.h"
21 #include "utilities/merge_operators/string_append/stringappend.h"
22
23 namespace ROCKSDB_NAMESPACE {
24
25 namespace {
26 class ColumnFamilyHandleImplDummy : public ColumnFamilyHandleImpl {
27 public:
ColumnFamilyHandleImplDummy(int id,const Comparator * comparator)28 explicit ColumnFamilyHandleImplDummy(int id, const Comparator* comparator)
29 : ColumnFamilyHandleImpl(nullptr, nullptr, nullptr),
30 id_(id),
31 comparator_(comparator) {}
GetID() const32 uint32_t GetID() const override { return id_; }
GetComparator() const33 const Comparator* GetComparator() const override { return comparator_; }
34
35 private:
36 uint32_t id_;
37 const Comparator* comparator_;
38 };
39
40 struct Entry {
41 std::string key;
42 std::string value;
43 WriteType type;
44 };
45
46 struct TestHandler : public WriteBatch::Handler {
47 std::map<uint32_t, std::vector<Entry>> seen;
PutCFROCKSDB_NAMESPACE::__anon5a6b5ba10111::TestHandler48 Status PutCF(uint32_t column_family_id, const Slice& key,
49 const Slice& value) override {
50 Entry e;
51 e.key = key.ToString();
52 e.value = value.ToString();
53 e.type = kPutRecord;
54 seen[column_family_id].push_back(e);
55 return Status::OK();
56 }
MergeCFROCKSDB_NAMESPACE::__anon5a6b5ba10111::TestHandler57 Status MergeCF(uint32_t column_family_id, const Slice& key,
58 const Slice& value) override {
59 Entry e;
60 e.key = key.ToString();
61 e.value = value.ToString();
62 e.type = kMergeRecord;
63 seen[column_family_id].push_back(e);
64 return Status::OK();
65 }
LogDataROCKSDB_NAMESPACE::__anon5a6b5ba10111::TestHandler66 void LogData(const Slice& /*blob*/) override {}
DeleteCFROCKSDB_NAMESPACE::__anon5a6b5ba10111::TestHandler67 Status DeleteCF(uint32_t column_family_id, const Slice& key) override {
68 Entry e;
69 e.key = key.ToString();
70 e.value = "";
71 e.type = kDeleteRecord;
72 seen[column_family_id].push_back(e);
73 return Status::OK();
74 }
75 };
76 } // namespace anonymous
77
78 class WriteBatchWithIndexTest : public testing::Test {};
79
TestValueAsSecondaryIndexHelper(std::vector<Entry> entries,WriteBatchWithIndex * batch)80 void TestValueAsSecondaryIndexHelper(std::vector<Entry> entries,
81 WriteBatchWithIndex* batch) {
82 // In this test, we insert <key, value> to column family `data`, and
83 // <value, key> to column family `index`. Then iterator them in order
84 // and seek them by key.
85
86 // Sort entries by key
87 std::map<std::string, std::vector<Entry*>> data_map;
88 // Sort entries by value
89 std::map<std::string, std::vector<Entry*>> index_map;
90 for (auto& e : entries) {
91 data_map[e.key].push_back(&e);
92 index_map[e.value].push_back(&e);
93 }
94
95 ColumnFamilyHandleImplDummy data(6, BytewiseComparator());
96 ColumnFamilyHandleImplDummy index(8, BytewiseComparator());
97 for (auto& e : entries) {
98 if (e.type == kPutRecord) {
99 batch->Put(&data, e.key, e.value);
100 batch->Put(&index, e.value, e.key);
101 } else if (e.type == kMergeRecord) {
102 batch->Merge(&data, e.key, e.value);
103 batch->Put(&index, e.value, e.key);
104 } else {
105 assert(e.type == kDeleteRecord);
106 std::unique_ptr<WBWIIterator> iter(batch->NewIterator(&data));
107 iter->Seek(e.key);
108 ASSERT_OK(iter->status());
109 auto write_entry = iter->Entry();
110 ASSERT_EQ(e.key, write_entry.key.ToString());
111 ASSERT_EQ(e.value, write_entry.value.ToString());
112 batch->Delete(&data, e.key);
113 batch->Put(&index, e.value, "");
114 }
115 }
116
117 // Iterator all keys
118 {
119 std::unique_ptr<WBWIIterator> iter(batch->NewIterator(&data));
120 for (int seek_to_first : {0, 1}) {
121 if (seek_to_first) {
122 iter->SeekToFirst();
123 } else {
124 iter->Seek("");
125 }
126 for (auto pair : data_map) {
127 for (auto v : pair.second) {
128 ASSERT_OK(iter->status());
129 ASSERT_TRUE(iter->Valid());
130 auto write_entry = iter->Entry();
131 ASSERT_EQ(pair.first, write_entry.key.ToString());
132 ASSERT_EQ(v->type, write_entry.type);
133 if (write_entry.type != kDeleteRecord) {
134 ASSERT_EQ(v->value, write_entry.value.ToString());
135 }
136 iter->Next();
137 }
138 }
139 ASSERT_TRUE(!iter->Valid());
140 }
141 iter->SeekToLast();
142 for (auto pair = data_map.rbegin(); pair != data_map.rend(); ++pair) {
143 for (auto v = pair->second.rbegin(); v != pair->second.rend(); v++) {
144 ASSERT_OK(iter->status());
145 ASSERT_TRUE(iter->Valid());
146 auto write_entry = iter->Entry();
147 ASSERT_EQ(pair->first, write_entry.key.ToString());
148 ASSERT_EQ((*v)->type, write_entry.type);
149 if (write_entry.type != kDeleteRecord) {
150 ASSERT_EQ((*v)->value, write_entry.value.ToString());
151 }
152 iter->Prev();
153 }
154 }
155 ASSERT_TRUE(!iter->Valid());
156 }
157
158 // Iterator all indexes
159 {
160 std::unique_ptr<WBWIIterator> iter(batch->NewIterator(&index));
161 for (int seek_to_first : {0, 1}) {
162 if (seek_to_first) {
163 iter->SeekToFirst();
164 } else {
165 iter->Seek("");
166 }
167 for (auto pair : index_map) {
168 for (auto v : pair.second) {
169 ASSERT_OK(iter->status());
170 ASSERT_TRUE(iter->Valid());
171 auto write_entry = iter->Entry();
172 ASSERT_EQ(pair.first, write_entry.key.ToString());
173 if (v->type != kDeleteRecord) {
174 ASSERT_EQ(v->key, write_entry.value.ToString());
175 ASSERT_EQ(v->value, write_entry.key.ToString());
176 }
177 iter->Next();
178 }
179 }
180 ASSERT_TRUE(!iter->Valid());
181 }
182
183 iter->SeekToLast();
184 for (auto pair = index_map.rbegin(); pair != index_map.rend(); ++pair) {
185 for (auto v = pair->second.rbegin(); v != pair->second.rend(); v++) {
186 ASSERT_OK(iter->status());
187 ASSERT_TRUE(iter->Valid());
188 auto write_entry = iter->Entry();
189 ASSERT_EQ(pair->first, write_entry.key.ToString());
190 if ((*v)->type != kDeleteRecord) {
191 ASSERT_EQ((*v)->key, write_entry.value.ToString());
192 ASSERT_EQ((*v)->value, write_entry.key.ToString());
193 }
194 iter->Prev();
195 }
196 }
197 ASSERT_TRUE(!iter->Valid());
198 }
199
200 // Seek to every key
201 {
202 std::unique_ptr<WBWIIterator> iter(batch->NewIterator(&data));
203
204 // Seek the keys one by one in reverse order
205 for (auto pair = data_map.rbegin(); pair != data_map.rend(); ++pair) {
206 iter->Seek(pair->first);
207 ASSERT_OK(iter->status());
208 for (auto v : pair->second) {
209 ASSERT_TRUE(iter->Valid());
210 auto write_entry = iter->Entry();
211 ASSERT_EQ(pair->first, write_entry.key.ToString());
212 ASSERT_EQ(v->type, write_entry.type);
213 if (write_entry.type != kDeleteRecord) {
214 ASSERT_EQ(v->value, write_entry.value.ToString());
215 }
216 iter->Next();
217 ASSERT_OK(iter->status());
218 }
219 }
220 }
221
222 // Seek to every index
223 {
224 std::unique_ptr<WBWIIterator> iter(batch->NewIterator(&index));
225
226 // Seek the keys one by one in reverse order
227 for (auto pair = index_map.rbegin(); pair != index_map.rend(); ++pair) {
228 iter->Seek(pair->first);
229 ASSERT_OK(iter->status());
230 for (auto v : pair->second) {
231 ASSERT_TRUE(iter->Valid());
232 auto write_entry = iter->Entry();
233 ASSERT_EQ(pair->first, write_entry.key.ToString());
234 ASSERT_EQ(v->value, write_entry.key.ToString());
235 if (v->type != kDeleteRecord) {
236 ASSERT_EQ(v->key, write_entry.value.ToString());
237 }
238 iter->Next();
239 ASSERT_OK(iter->status());
240 }
241 }
242 }
243
244 // Verify WriteBatch can be iterated
245 TestHandler handler;
246 batch->GetWriteBatch()->Iterate(&handler);
247
248 // Verify data column family
249 {
250 ASSERT_EQ(entries.size(), handler.seen[data.GetID()].size());
251 size_t i = 0;
252 for (auto e : handler.seen[data.GetID()]) {
253 auto write_entry = entries[i++];
254 ASSERT_EQ(e.type, write_entry.type);
255 ASSERT_EQ(e.key, write_entry.key);
256 if (e.type != kDeleteRecord) {
257 ASSERT_EQ(e.value, write_entry.value);
258 }
259 }
260 }
261
262 // Verify index column family
263 {
264 ASSERT_EQ(entries.size(), handler.seen[index.GetID()].size());
265 size_t i = 0;
266 for (auto e : handler.seen[index.GetID()]) {
267 auto write_entry = entries[i++];
268 ASSERT_EQ(e.key, write_entry.value);
269 if (write_entry.type != kDeleteRecord) {
270 ASSERT_EQ(e.value, write_entry.key);
271 }
272 }
273 }
274 }
275
TEST_F(WriteBatchWithIndexTest,TestValueAsSecondaryIndex)276 TEST_F(WriteBatchWithIndexTest, TestValueAsSecondaryIndex) {
277 Entry entries[] = {
278 {"aaa", "0005", kPutRecord},
279 {"b", "0002", kPutRecord},
280 {"cdd", "0002", kMergeRecord},
281 {"aab", "00001", kPutRecord},
282 {"cc", "00005", kPutRecord},
283 {"cdd", "0002", kPutRecord},
284 {"aab", "0003", kPutRecord},
285 {"cc", "00005", kDeleteRecord},
286 };
287 std::vector<Entry> entries_list(entries, entries + 8);
288
289 WriteBatchWithIndex batch(nullptr, 20);
290
291 TestValueAsSecondaryIndexHelper(entries_list, &batch);
292
293 // Clear batch and re-run test with new values
294 batch.Clear();
295
296 Entry new_entries[] = {
297 {"aaa", "0005", kPutRecord},
298 {"e", "0002", kPutRecord},
299 {"add", "0002", kMergeRecord},
300 {"aab", "00001", kPutRecord},
301 {"zz", "00005", kPutRecord},
302 {"add", "0002", kPutRecord},
303 {"aab", "0003", kPutRecord},
304 {"zz", "00005", kDeleteRecord},
305 };
306
307 entries_list = std::vector<Entry>(new_entries, new_entries + 8);
308
309 TestValueAsSecondaryIndexHelper(entries_list, &batch);
310 }
311
TEST_F(WriteBatchWithIndexTest,TestComparatorForCF)312 TEST_F(WriteBatchWithIndexTest, TestComparatorForCF) {
313 ColumnFamilyHandleImplDummy cf1(6, nullptr);
314 ColumnFamilyHandleImplDummy reverse_cf(66, ReverseBytewiseComparator());
315 ColumnFamilyHandleImplDummy cf2(88, BytewiseComparator());
316 WriteBatchWithIndex batch(BytewiseComparator(), 20);
317
318 batch.Put(&cf1, "ddd", "");
319 batch.Put(&cf2, "aaa", "");
320 batch.Put(&cf2, "eee", "");
321 batch.Put(&cf1, "ccc", "");
322 batch.Put(&reverse_cf, "a11", "");
323 batch.Put(&cf1, "bbb", "");
324
325 Slice key_slices[] = {"a", "3", "3"};
326 Slice value_slice = "";
327 batch.Put(&reverse_cf, SliceParts(key_slices, 3),
328 SliceParts(&value_slice, 1));
329 batch.Put(&reverse_cf, "a22", "");
330
331 {
332 std::unique_ptr<WBWIIterator> iter(batch.NewIterator(&cf1));
333 iter->Seek("");
334 ASSERT_OK(iter->status());
335 ASSERT_TRUE(iter->Valid());
336 ASSERT_EQ("bbb", iter->Entry().key.ToString());
337 iter->Next();
338 ASSERT_OK(iter->status());
339 ASSERT_TRUE(iter->Valid());
340 ASSERT_EQ("ccc", iter->Entry().key.ToString());
341 iter->Next();
342 ASSERT_OK(iter->status());
343 ASSERT_TRUE(iter->Valid());
344 ASSERT_EQ("ddd", iter->Entry().key.ToString());
345 iter->Next();
346 ASSERT_OK(iter->status());
347 ASSERT_TRUE(!iter->Valid());
348 }
349
350 {
351 std::unique_ptr<WBWIIterator> iter(batch.NewIterator(&cf2));
352 iter->Seek("");
353 ASSERT_OK(iter->status());
354 ASSERT_TRUE(iter->Valid());
355 ASSERT_EQ("aaa", iter->Entry().key.ToString());
356 iter->Next();
357 ASSERT_OK(iter->status());
358 ASSERT_TRUE(iter->Valid());
359 ASSERT_EQ("eee", iter->Entry().key.ToString());
360 iter->Next();
361 ASSERT_OK(iter->status());
362 ASSERT_TRUE(!iter->Valid());
363 }
364
365 {
366 std::unique_ptr<WBWIIterator> iter(batch.NewIterator(&reverse_cf));
367 iter->Seek("");
368 ASSERT_OK(iter->status());
369 ASSERT_TRUE(!iter->Valid());
370
371 iter->Seek("z");
372 ASSERT_OK(iter->status());
373 ASSERT_TRUE(iter->Valid());
374 ASSERT_EQ("a33", iter->Entry().key.ToString());
375 iter->Next();
376 ASSERT_OK(iter->status());
377 ASSERT_TRUE(iter->Valid());
378 ASSERT_EQ("a22", iter->Entry().key.ToString());
379 iter->Next();
380 ASSERT_OK(iter->status());
381 ASSERT_TRUE(iter->Valid());
382 ASSERT_EQ("a11", iter->Entry().key.ToString());
383 iter->Next();
384 ASSERT_OK(iter->status());
385 ASSERT_TRUE(!iter->Valid());
386
387 iter->Seek("a22");
388 ASSERT_OK(iter->status());
389 ASSERT_TRUE(iter->Valid());
390 ASSERT_EQ("a22", iter->Entry().key.ToString());
391
392 iter->Seek("a13");
393 ASSERT_OK(iter->status());
394 ASSERT_TRUE(iter->Valid());
395 ASSERT_EQ("a11", iter->Entry().key.ToString());
396 }
397 }
398
TEST_F(WriteBatchWithIndexTest,TestOverwriteKey)399 TEST_F(WriteBatchWithIndexTest, TestOverwriteKey) {
400 ColumnFamilyHandleImplDummy cf1(6, nullptr);
401 ColumnFamilyHandleImplDummy reverse_cf(66, ReverseBytewiseComparator());
402 ColumnFamilyHandleImplDummy cf2(88, BytewiseComparator());
403 WriteBatchWithIndex batch(BytewiseComparator(), 20, true);
404
405 batch.Put(&cf1, "ddd", "");
406 batch.Merge(&cf1, "ddd", "");
407 batch.Delete(&cf1, "ddd");
408 batch.Put(&cf2, "aaa", "");
409 batch.Delete(&cf2, "aaa");
410 batch.Put(&cf2, "aaa", "aaa");
411 batch.Put(&cf2, "eee", "eee");
412 batch.Put(&cf1, "ccc", "");
413 batch.Put(&reverse_cf, "a11", "");
414 batch.Delete(&cf1, "ccc");
415 batch.Put(&reverse_cf, "a33", "a33");
416 batch.Put(&reverse_cf, "a11", "a11");
417 Slice slices[] = {"a", "3", "3"};
418 batch.Delete(&reverse_cf, SliceParts(slices, 3));
419
420 {
421 std::unique_ptr<WBWIIterator> iter(batch.NewIterator(&cf1));
422 iter->Seek("");
423 ASSERT_OK(iter->status());
424 ASSERT_TRUE(iter->Valid());
425 ASSERT_EQ("ccc", iter->Entry().key.ToString());
426 ASSERT_TRUE(iter->Entry().type == WriteType::kDeleteRecord);
427 iter->Next();
428 ASSERT_OK(iter->status());
429 ASSERT_TRUE(iter->Valid());
430 ASSERT_EQ("ddd", iter->Entry().key.ToString());
431 ASSERT_TRUE(iter->Entry().type == WriteType::kDeleteRecord);
432 iter->Next();
433 ASSERT_OK(iter->status());
434 ASSERT_TRUE(!iter->Valid());
435 }
436
437 {
438 std::unique_ptr<WBWIIterator> iter(batch.NewIterator(&cf2));
439 iter->SeekToLast();
440 ASSERT_OK(iter->status());
441 ASSERT_TRUE(iter->Valid());
442 ASSERT_EQ("eee", iter->Entry().key.ToString());
443 ASSERT_EQ("eee", iter->Entry().value.ToString());
444 iter->Prev();
445 ASSERT_OK(iter->status());
446 ASSERT_TRUE(iter->Valid());
447 ASSERT_EQ("aaa", iter->Entry().key.ToString());
448 ASSERT_EQ("aaa", iter->Entry().value.ToString());
449 iter->Prev();
450 ASSERT_OK(iter->status());
451 ASSERT_TRUE(!iter->Valid());
452
453 iter->SeekToFirst();
454 ASSERT_OK(iter->status());
455 ASSERT_TRUE(iter->Valid());
456 ASSERT_EQ("aaa", iter->Entry().key.ToString());
457 ASSERT_EQ("aaa", iter->Entry().value.ToString());
458 iter->Next();
459 ASSERT_OK(iter->status());
460 ASSERT_TRUE(iter->Valid());
461 ASSERT_EQ("eee", iter->Entry().key.ToString());
462 ASSERT_EQ("eee", iter->Entry().value.ToString());
463 iter->Next();
464 ASSERT_OK(iter->status());
465 ASSERT_TRUE(!iter->Valid());
466 }
467
468 {
469 std::unique_ptr<WBWIIterator> iter(batch.NewIterator(&reverse_cf));
470 iter->Seek("");
471 ASSERT_OK(iter->status());
472 ASSERT_TRUE(!iter->Valid());
473
474 iter->Seek("z");
475 ASSERT_OK(iter->status());
476 ASSERT_TRUE(iter->Valid());
477 ASSERT_EQ("a33", iter->Entry().key.ToString());
478 ASSERT_TRUE(iter->Entry().type == WriteType::kDeleteRecord);
479 iter->Next();
480 ASSERT_OK(iter->status());
481 ASSERT_TRUE(iter->Valid());
482 ASSERT_EQ("a11", iter->Entry().key.ToString());
483 ASSERT_EQ("a11", iter->Entry().value.ToString());
484 iter->Next();
485 ASSERT_OK(iter->status());
486 ASSERT_TRUE(!iter->Valid());
487
488 iter->SeekToLast();
489 ASSERT_TRUE(iter->Valid());
490 ASSERT_EQ("a11", iter->Entry().key.ToString());
491 ASSERT_EQ("a11", iter->Entry().value.ToString());
492 iter->Prev();
493
494 ASSERT_OK(iter->status());
495 ASSERT_TRUE(iter->Valid());
496 ASSERT_EQ("a33", iter->Entry().key.ToString());
497 ASSERT_TRUE(iter->Entry().type == WriteType::kDeleteRecord);
498 iter->Prev();
499 ASSERT_TRUE(!iter->Valid());
500 }
501 }
502
503 namespace {
504 typedef std::map<std::string, std::string> KVMap;
505
506 class KVIter : public Iterator {
507 public:
KVIter(const KVMap * map)508 explicit KVIter(const KVMap* map) : map_(map), iter_(map_->end()) {}
Valid() const509 bool Valid() const override { return iter_ != map_->end(); }
SeekToFirst()510 void SeekToFirst() override { iter_ = map_->begin(); }
SeekToLast()511 void SeekToLast() override {
512 if (map_->empty()) {
513 iter_ = map_->end();
514 } else {
515 iter_ = map_->find(map_->rbegin()->first);
516 }
517 }
Seek(const Slice & k)518 void Seek(const Slice& k) override {
519 iter_ = map_->lower_bound(k.ToString());
520 }
SeekForPrev(const Slice & k)521 void SeekForPrev(const Slice& k) override {
522 iter_ = map_->upper_bound(k.ToString());
523 Prev();
524 }
Next()525 void Next() override { ++iter_; }
Prev()526 void Prev() override {
527 if (iter_ == map_->begin()) {
528 iter_ = map_->end();
529 return;
530 }
531 --iter_;
532 }
533
key() const534 Slice key() const override { return iter_->first; }
value() const535 Slice value() const override { return iter_->second; }
status() const536 Status status() const override { return Status::OK(); }
537
538 private:
539 const KVMap* const map_;
540 KVMap::const_iterator iter_;
541 };
542
AssertIter(Iterator * iter,const std::string & key,const std::string & value)543 void AssertIter(Iterator* iter, const std::string& key,
544 const std::string& value) {
545 ASSERT_OK(iter->status());
546 ASSERT_TRUE(iter->Valid());
547 ASSERT_EQ(key, iter->key().ToString());
548 ASSERT_EQ(value, iter->value().ToString());
549 }
550
AssertItersEqual(Iterator * iter1,Iterator * iter2)551 void AssertItersEqual(Iterator* iter1, Iterator* iter2) {
552 ASSERT_EQ(iter1->Valid(), iter2->Valid());
553 if (iter1->Valid()) {
554 ASSERT_EQ(iter1->key().ToString(), iter2->key().ToString());
555 ASSERT_EQ(iter1->value().ToString(), iter2->value().ToString());
556 }
557 }
558 } // namespace
559
TEST_F(WriteBatchWithIndexTest,TestRandomIteraratorWithBase)560 TEST_F(WriteBatchWithIndexTest, TestRandomIteraratorWithBase) {
561 std::vector<std::string> source_strings = {"a", "b", "c", "d", "e",
562 "f", "g", "h", "i", "j"};
563 for (int rand_seed = 301; rand_seed < 366; rand_seed++) {
564 Random rnd(rand_seed);
565
566 ColumnFamilyHandleImplDummy cf1(6, BytewiseComparator());
567 ColumnFamilyHandleImplDummy cf2(2, BytewiseComparator());
568 ColumnFamilyHandleImplDummy cf3(8, BytewiseComparator());
569
570 WriteBatchWithIndex batch(BytewiseComparator(), 20, true);
571
572 if (rand_seed % 2 == 0) {
573 batch.Put(&cf2, "zoo", "bar");
574 }
575 if (rand_seed % 4 == 1) {
576 batch.Put(&cf3, "zoo", "bar");
577 }
578
579 KVMap map;
580 KVMap merged_map;
581 for (auto key : source_strings) {
582 std::string value = key + key;
583 int type = rnd.Uniform(6);
584 switch (type) {
585 case 0:
586 // only base has it
587 map[key] = value;
588 merged_map[key] = value;
589 break;
590 case 1:
591 // only delta has it
592 batch.Put(&cf1, key, value);
593 map[key] = value;
594 merged_map[key] = value;
595 break;
596 case 2:
597 // both has it. Delta should win
598 batch.Put(&cf1, key, value);
599 map[key] = "wrong_value";
600 merged_map[key] = value;
601 break;
602 case 3:
603 // both has it. Delta is delete
604 batch.Delete(&cf1, key);
605 map[key] = "wrong_value";
606 break;
607 case 4:
608 // only delta has it. Delta is delete
609 batch.Delete(&cf1, key);
610 map[key] = "wrong_value";
611 break;
612 default:
613 // Neither iterator has it.
614 break;
615 }
616 }
617
618 std::unique_ptr<Iterator> iter(
619 batch.NewIteratorWithBase(&cf1, new KVIter(&map)));
620 std::unique_ptr<Iterator> result_iter(new KVIter(&merged_map));
621
622 bool is_valid = false;
623 for (int i = 0; i < 128; i++) {
624 // Random walk and make sure iter and result_iter returns the
625 // same key and value
626 int type = rnd.Uniform(6);
627 ASSERT_OK(iter->status());
628 switch (type) {
629 case 0:
630 // Seek to First
631 iter->SeekToFirst();
632 result_iter->SeekToFirst();
633 break;
634 case 1:
635 // Seek to last
636 iter->SeekToLast();
637 result_iter->SeekToLast();
638 break;
639 case 2: {
640 // Seek to random key
641 auto key_idx = rnd.Uniform(static_cast<int>(source_strings.size()));
642 auto key = source_strings[key_idx];
643 iter->Seek(key);
644 result_iter->Seek(key);
645 break;
646 }
647 case 3: {
648 // SeekForPrev to random key
649 auto key_idx = rnd.Uniform(static_cast<int>(source_strings.size()));
650 auto key = source_strings[key_idx];
651 iter->SeekForPrev(key);
652 result_iter->SeekForPrev(key);
653 break;
654 }
655 case 4:
656 // Next
657 if (is_valid) {
658 iter->Next();
659 result_iter->Next();
660 } else {
661 continue;
662 }
663 break;
664 default:
665 assert(type == 5);
666 // Prev
667 if (is_valid) {
668 iter->Prev();
669 result_iter->Prev();
670 } else {
671 continue;
672 }
673 break;
674 }
675 AssertItersEqual(iter.get(), result_iter.get());
676 is_valid = iter->Valid();
677 }
678 }
679 }
680
TEST_F(WriteBatchWithIndexTest,TestIteraratorWithBase)681 TEST_F(WriteBatchWithIndexTest, TestIteraratorWithBase) {
682 ColumnFamilyHandleImplDummy cf1(6, BytewiseComparator());
683 ColumnFamilyHandleImplDummy cf2(2, BytewiseComparator());
684 WriteBatchWithIndex batch(BytewiseComparator(), 20, true);
685
686 {
687 KVMap map;
688 map["a"] = "aa";
689 map["c"] = "cc";
690 map["e"] = "ee";
691 std::unique_ptr<Iterator> iter(
692 batch.NewIteratorWithBase(&cf1, new KVIter(&map)));
693
694 iter->SeekToFirst();
695 AssertIter(iter.get(), "a", "aa");
696 iter->Next();
697 AssertIter(iter.get(), "c", "cc");
698 iter->Next();
699 AssertIter(iter.get(), "e", "ee");
700 iter->Next();
701 ASSERT_OK(iter->status());
702 ASSERT_TRUE(!iter->Valid());
703
704 iter->SeekToLast();
705 AssertIter(iter.get(), "e", "ee");
706 iter->Prev();
707 AssertIter(iter.get(), "c", "cc");
708 iter->Prev();
709 AssertIter(iter.get(), "a", "aa");
710 iter->Prev();
711 ASSERT_OK(iter->status());
712 ASSERT_TRUE(!iter->Valid());
713
714 iter->Seek("b");
715 AssertIter(iter.get(), "c", "cc");
716
717 iter->Prev();
718 AssertIter(iter.get(), "a", "aa");
719
720 iter->Seek("a");
721 AssertIter(iter.get(), "a", "aa");
722 }
723
724 // Test the case that there is one element in the write batch
725 batch.Put(&cf2, "zoo", "bar");
726 batch.Put(&cf1, "a", "aa");
727 {
728 KVMap empty_map;
729 std::unique_ptr<Iterator> iter(
730 batch.NewIteratorWithBase(&cf1, new KVIter(&empty_map)));
731
732 iter->SeekToFirst();
733 AssertIter(iter.get(), "a", "aa");
734 iter->Next();
735 ASSERT_OK(iter->status());
736 ASSERT_TRUE(!iter->Valid());
737 }
738
739 batch.Delete(&cf1, "b");
740 batch.Put(&cf1, "c", "cc");
741 batch.Put(&cf1, "d", "dd");
742 batch.Delete(&cf1, "e");
743
744 {
745 KVMap map;
746 map["b"] = "";
747 map["cc"] = "cccc";
748 map["f"] = "ff";
749 std::unique_ptr<Iterator> iter(
750 batch.NewIteratorWithBase(&cf1, new KVIter(&map)));
751
752 iter->SeekToFirst();
753 AssertIter(iter.get(), "a", "aa");
754 iter->Next();
755 AssertIter(iter.get(), "c", "cc");
756 iter->Next();
757 AssertIter(iter.get(), "cc", "cccc");
758 iter->Next();
759 AssertIter(iter.get(), "d", "dd");
760 iter->Next();
761 AssertIter(iter.get(), "f", "ff");
762 iter->Next();
763 ASSERT_OK(iter->status());
764 ASSERT_TRUE(!iter->Valid());
765
766 iter->SeekToLast();
767 AssertIter(iter.get(), "f", "ff");
768 iter->Prev();
769 AssertIter(iter.get(), "d", "dd");
770 iter->Prev();
771 AssertIter(iter.get(), "cc", "cccc");
772 iter->Prev();
773 AssertIter(iter.get(), "c", "cc");
774 iter->Next();
775 AssertIter(iter.get(), "cc", "cccc");
776 iter->Prev();
777 AssertIter(iter.get(), "c", "cc");
778 iter->Prev();
779 AssertIter(iter.get(), "a", "aa");
780 iter->Prev();
781 ASSERT_OK(iter->status());
782 ASSERT_TRUE(!iter->Valid());
783
784 iter->Seek("c");
785 AssertIter(iter.get(), "c", "cc");
786
787 iter->Seek("cb");
788 AssertIter(iter.get(), "cc", "cccc");
789
790 iter->Seek("cc");
791 AssertIter(iter.get(), "cc", "cccc");
792 iter->Next();
793 AssertIter(iter.get(), "d", "dd");
794
795 iter->Seek("e");
796 AssertIter(iter.get(), "f", "ff");
797
798 iter->Prev();
799 AssertIter(iter.get(), "d", "dd");
800
801 iter->Next();
802 AssertIter(iter.get(), "f", "ff");
803 }
804
805 {
806 KVMap empty_map;
807 std::unique_ptr<Iterator> iter(
808 batch.NewIteratorWithBase(&cf1, new KVIter(&empty_map)));
809
810 iter->SeekToFirst();
811 AssertIter(iter.get(), "a", "aa");
812 iter->Next();
813 AssertIter(iter.get(), "c", "cc");
814 iter->Next();
815 AssertIter(iter.get(), "d", "dd");
816 iter->Next();
817 ASSERT_OK(iter->status());
818 ASSERT_TRUE(!iter->Valid());
819
820 iter->SeekToLast();
821 AssertIter(iter.get(), "d", "dd");
822 iter->Prev();
823 AssertIter(iter.get(), "c", "cc");
824 iter->Prev();
825 AssertIter(iter.get(), "a", "aa");
826
827 iter->Prev();
828 ASSERT_OK(iter->status());
829 ASSERT_TRUE(!iter->Valid());
830
831 iter->Seek("aa");
832 AssertIter(iter.get(), "c", "cc");
833 iter->Next();
834 AssertIter(iter.get(), "d", "dd");
835
836 iter->Seek("ca");
837 AssertIter(iter.get(), "d", "dd");
838
839 iter->Prev();
840 AssertIter(iter.get(), "c", "cc");
841 }
842 }
843
TEST_F(WriteBatchWithIndexTest,TestIteraratorWithBaseReverseCmp)844 TEST_F(WriteBatchWithIndexTest, TestIteraratorWithBaseReverseCmp) {
845 ColumnFamilyHandleImplDummy cf1(6, ReverseBytewiseComparator());
846 ColumnFamilyHandleImplDummy cf2(2, ReverseBytewiseComparator());
847 WriteBatchWithIndex batch(BytewiseComparator(), 20, true);
848
849 // Test the case that there is one element in the write batch
850 batch.Put(&cf2, "zoo", "bar");
851 batch.Put(&cf1, "a", "aa");
852 {
853 KVMap empty_map;
854 std::unique_ptr<Iterator> iter(
855 batch.NewIteratorWithBase(&cf1, new KVIter(&empty_map)));
856
857 iter->SeekToFirst();
858 AssertIter(iter.get(), "a", "aa");
859 iter->Next();
860 ASSERT_OK(iter->status());
861 ASSERT_TRUE(!iter->Valid());
862 }
863
864 batch.Put(&cf1, "c", "cc");
865 {
866 KVMap map;
867 std::unique_ptr<Iterator> iter(
868 batch.NewIteratorWithBase(&cf1, new KVIter(&map)));
869
870 iter->SeekToFirst();
871 AssertIter(iter.get(), "c", "cc");
872 iter->Next();
873 AssertIter(iter.get(), "a", "aa");
874 iter->Next();
875 ASSERT_OK(iter->status());
876 ASSERT_TRUE(!iter->Valid());
877
878 iter->SeekToLast();
879 AssertIter(iter.get(), "a", "aa");
880 iter->Prev();
881 AssertIter(iter.get(), "c", "cc");
882 iter->Prev();
883 ASSERT_OK(iter->status());
884 ASSERT_TRUE(!iter->Valid());
885
886 iter->Seek("b");
887 AssertIter(iter.get(), "a", "aa");
888
889 iter->Prev();
890 AssertIter(iter.get(), "c", "cc");
891
892 iter->Seek("a");
893 AssertIter(iter.get(), "a", "aa");
894 }
895
896 // default column family
897 batch.Put("a", "b");
898 {
899 KVMap map;
900 map["b"] = "";
901 std::unique_ptr<Iterator> iter(batch.NewIteratorWithBase(new KVIter(&map)));
902
903 iter->SeekToFirst();
904 AssertIter(iter.get(), "a", "b");
905 iter->Next();
906 AssertIter(iter.get(), "b", "");
907 iter->Next();
908 ASSERT_OK(iter->status());
909 ASSERT_TRUE(!iter->Valid());
910
911 iter->SeekToLast();
912 AssertIter(iter.get(), "b", "");
913 iter->Prev();
914 AssertIter(iter.get(), "a", "b");
915 iter->Prev();
916 ASSERT_OK(iter->status());
917 ASSERT_TRUE(!iter->Valid());
918
919 iter->Seek("b");
920 AssertIter(iter.get(), "b", "");
921
922 iter->Prev();
923 AssertIter(iter.get(), "a", "b");
924
925 iter->Seek("0");
926 AssertIter(iter.get(), "a", "b");
927 }
928 }
929
TEST_F(WriteBatchWithIndexTest,TestGetFromBatch)930 TEST_F(WriteBatchWithIndexTest, TestGetFromBatch) {
931 Options options;
932 WriteBatchWithIndex batch;
933 Status s;
934 std::string value;
935
936 s = batch.GetFromBatch(options, "b", &value);
937 ASSERT_TRUE(s.IsNotFound());
938
939 batch.Put("a", "a");
940 batch.Put("b", "b");
941 batch.Put("c", "c");
942 batch.Put("a", "z");
943 batch.Delete("c");
944 batch.Delete("d");
945 batch.Delete("e");
946 batch.Put("e", "e");
947
948 s = batch.GetFromBatch(options, "b", &value);
949 ASSERT_OK(s);
950 ASSERT_EQ("b", value);
951
952 s = batch.GetFromBatch(options, "a", &value);
953 ASSERT_OK(s);
954 ASSERT_EQ("z", value);
955
956 s = batch.GetFromBatch(options, "c", &value);
957 ASSERT_TRUE(s.IsNotFound());
958
959 s = batch.GetFromBatch(options, "d", &value);
960 ASSERT_TRUE(s.IsNotFound());
961
962 s = batch.GetFromBatch(options, "x", &value);
963 ASSERT_TRUE(s.IsNotFound());
964
965 s = batch.GetFromBatch(options, "e", &value);
966 ASSERT_OK(s);
967 ASSERT_EQ("e", value);
968
969 batch.Merge("z", "z");
970
971 s = batch.GetFromBatch(options, "z", &value);
972 ASSERT_NOK(s); // No merge operator specified.
973
974 s = batch.GetFromBatch(options, "b", &value);
975 ASSERT_OK(s);
976 ASSERT_EQ("b", value);
977 }
978
TEST_F(WriteBatchWithIndexTest,TestGetFromBatchMerge)979 TEST_F(WriteBatchWithIndexTest, TestGetFromBatchMerge) {
980 DB* db;
981 Options options;
982 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
983 options.create_if_missing = true;
984
985 std::string dbname = test::PerThreadDBPath("write_batch_with_index_test");
986
987 DestroyDB(dbname, options);
988 Status s = DB::Open(options, dbname, &db);
989 ASSERT_OK(s);
990
991 ColumnFamilyHandle* column_family = db->DefaultColumnFamily();
992 WriteBatchWithIndex batch;
993 std::string value;
994
995 s = batch.GetFromBatch(options, "x", &value);
996 ASSERT_TRUE(s.IsNotFound());
997
998 batch.Put("x", "X");
999 std::string expected = "X";
1000
1001 for (int i = 0; i < 5; i++) {
1002 batch.Merge("x", ToString(i));
1003 expected = expected + "," + ToString(i);
1004
1005 if (i % 2 == 0) {
1006 batch.Put("y", ToString(i / 2));
1007 }
1008
1009 batch.Merge("z", "z");
1010
1011 s = batch.GetFromBatch(column_family, options, "x", &value);
1012 ASSERT_OK(s);
1013 ASSERT_EQ(expected, value);
1014
1015 s = batch.GetFromBatch(column_family, options, "y", &value);
1016 ASSERT_OK(s);
1017 ASSERT_EQ(ToString(i / 2), value);
1018
1019 s = batch.GetFromBatch(column_family, options, "z", &value);
1020 ASSERT_TRUE(s.IsMergeInProgress());
1021 }
1022
1023 delete db;
1024 DestroyDB(dbname, options);
1025 }
1026
TEST_F(WriteBatchWithIndexTest,TestGetFromBatchMerge2)1027 TEST_F(WriteBatchWithIndexTest, TestGetFromBatchMerge2) {
1028 DB* db;
1029 Options options;
1030 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1031 options.create_if_missing = true;
1032
1033 std::string dbname = test::PerThreadDBPath("write_batch_with_index_test");
1034
1035 DestroyDB(dbname, options);
1036 Status s = DB::Open(options, dbname, &db);
1037 ASSERT_OK(s);
1038
1039 ColumnFamilyHandle* column_family = db->DefaultColumnFamily();
1040
1041 // Test batch with overwrite_key=true
1042 WriteBatchWithIndex batch(BytewiseComparator(), 0, true);
1043 std::string value;
1044
1045 s = batch.GetFromBatch(column_family, options, "X", &value);
1046 ASSERT_TRUE(s.IsNotFound());
1047
1048 batch.Put(column_family, "X", "x");
1049 s = batch.GetFromBatch(column_family, options, "X", &value);
1050 ASSERT_OK(s);
1051 ASSERT_EQ("x", value);
1052
1053 batch.Put(column_family, "X", "x2");
1054 s = batch.GetFromBatch(column_family, options, "X", &value);
1055 ASSERT_OK(s);
1056 ASSERT_EQ("x2", value);
1057
1058 batch.Merge(column_family, "X", "aaa");
1059 s = batch.GetFromBatch(column_family, options, "X", &value);
1060 ASSERT_TRUE(s.IsMergeInProgress());
1061
1062 batch.Merge(column_family, "X", "bbb");
1063 s = batch.GetFromBatch(column_family, options, "X", &value);
1064 ASSERT_TRUE(s.IsMergeInProgress());
1065
1066 batch.Put(column_family, "X", "x3");
1067 s = batch.GetFromBatch(column_family, options, "X", &value);
1068 ASSERT_OK(s);
1069 ASSERT_EQ("x3", value);
1070
1071 batch.Merge(column_family, "X", "ccc");
1072 s = batch.GetFromBatch(column_family, options, "X", &value);
1073 ASSERT_TRUE(s.IsMergeInProgress());
1074
1075 batch.Delete(column_family, "X");
1076 s = batch.GetFromBatch(column_family, options, "X", &value);
1077 ASSERT_TRUE(s.IsNotFound());
1078
1079 batch.Merge(column_family, "X", "ddd");
1080 s = batch.GetFromBatch(column_family, options, "X", &value);
1081 ASSERT_TRUE(s.IsMergeInProgress());
1082
1083 delete db;
1084 DestroyDB(dbname, options);
1085 }
1086
TEST_F(WriteBatchWithIndexTest,TestGetFromBatchAndDB)1087 TEST_F(WriteBatchWithIndexTest, TestGetFromBatchAndDB) {
1088 DB* db;
1089 Options options;
1090 options.create_if_missing = true;
1091 std::string dbname = test::PerThreadDBPath("write_batch_with_index_test");
1092
1093 DestroyDB(dbname, options);
1094 Status s = DB::Open(options, dbname, &db);
1095 ASSERT_OK(s);
1096
1097 WriteBatchWithIndex batch;
1098 ReadOptions read_options;
1099 WriteOptions write_options;
1100 std::string value;
1101
1102 s = db->Put(write_options, "a", "a");
1103 ASSERT_OK(s);
1104
1105 s = db->Put(write_options, "b", "b");
1106 ASSERT_OK(s);
1107
1108 s = db->Put(write_options, "c", "c");
1109 ASSERT_OK(s);
1110
1111 batch.Put("a", "batch.a");
1112 batch.Delete("b");
1113
1114 s = batch.GetFromBatchAndDB(db, read_options, "a", &value);
1115 ASSERT_OK(s);
1116 ASSERT_EQ("batch.a", value);
1117
1118 s = batch.GetFromBatchAndDB(db, read_options, "b", &value);
1119 ASSERT_TRUE(s.IsNotFound());
1120
1121 s = batch.GetFromBatchAndDB(db, read_options, "c", &value);
1122 ASSERT_OK(s);
1123 ASSERT_EQ("c", value);
1124
1125 s = batch.GetFromBatchAndDB(db, read_options, "x", &value);
1126 ASSERT_TRUE(s.IsNotFound());
1127
1128 db->Delete(write_options, "x");
1129
1130 s = batch.GetFromBatchAndDB(db, read_options, "x", &value);
1131 ASSERT_TRUE(s.IsNotFound());
1132
1133 delete db;
1134 DestroyDB(dbname, options);
1135 }
1136
TEST_F(WriteBatchWithIndexTest,TestGetFromBatchAndDBMerge)1137 TEST_F(WriteBatchWithIndexTest, TestGetFromBatchAndDBMerge) {
1138 DB* db;
1139 Options options;
1140
1141 options.create_if_missing = true;
1142 std::string dbname = test::PerThreadDBPath("write_batch_with_index_test");
1143
1144 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1145
1146 DestroyDB(dbname, options);
1147 Status s = DB::Open(options, dbname, &db);
1148 assert(s.ok());
1149
1150 WriteBatchWithIndex batch;
1151 ReadOptions read_options;
1152 WriteOptions write_options;
1153 std::string value;
1154
1155 s = db->Put(write_options, "a", "a0");
1156 ASSERT_OK(s);
1157
1158 s = db->Put(write_options, "b", "b0");
1159 ASSERT_OK(s);
1160
1161 s = db->Merge(write_options, "b", "b1");
1162 ASSERT_OK(s);
1163
1164 s = db->Merge(write_options, "c", "c0");
1165 ASSERT_OK(s);
1166
1167 s = db->Merge(write_options, "d", "d0");
1168 ASSERT_OK(s);
1169
1170 batch.Merge("a", "a1");
1171 batch.Merge("a", "a2");
1172 batch.Merge("b", "b2");
1173 batch.Merge("d", "d1");
1174 batch.Merge("e", "e0");
1175
1176 s = batch.GetFromBatchAndDB(db, read_options, "a", &value);
1177 ASSERT_OK(s);
1178 ASSERT_EQ("a0,a1,a2", value);
1179
1180 s = batch.GetFromBatchAndDB(db, read_options, "b", &value);
1181 ASSERT_OK(s);
1182 ASSERT_EQ("b0,b1,b2", value);
1183
1184 s = batch.GetFromBatchAndDB(db, read_options, "c", &value);
1185 ASSERT_OK(s);
1186 ASSERT_EQ("c0", value);
1187
1188 s = batch.GetFromBatchAndDB(db, read_options, "d", &value);
1189 ASSERT_OK(s);
1190 ASSERT_EQ("d0,d1", value);
1191
1192 s = batch.GetFromBatchAndDB(db, read_options, "e", &value);
1193 ASSERT_OK(s);
1194 ASSERT_EQ("e0", value);
1195
1196 s = db->Delete(write_options, "x");
1197 ASSERT_OK(s);
1198
1199 s = batch.GetFromBatchAndDB(db, read_options, "x", &value);
1200 ASSERT_TRUE(s.IsNotFound());
1201
1202 const Snapshot* snapshot = db->GetSnapshot();
1203 ReadOptions snapshot_read_options;
1204 snapshot_read_options.snapshot = snapshot;
1205
1206 s = db->Delete(write_options, "a");
1207 ASSERT_OK(s);
1208
1209 s = batch.GetFromBatchAndDB(db, read_options, "a", &value);
1210 ASSERT_OK(s);
1211 ASSERT_EQ("a1,a2", value);
1212
1213 s = batch.GetFromBatchAndDB(db, snapshot_read_options, "a", &value);
1214 ASSERT_OK(s);
1215 ASSERT_EQ("a0,a1,a2", value);
1216
1217 batch.Delete("a");
1218
1219 s = batch.GetFromBatchAndDB(db, read_options, "a", &value);
1220 ASSERT_TRUE(s.IsNotFound());
1221
1222 s = batch.GetFromBatchAndDB(db, snapshot_read_options, "a", &value);
1223 ASSERT_TRUE(s.IsNotFound());
1224
1225 s = db->Merge(write_options, "c", "c1");
1226 ASSERT_OK(s);
1227
1228 s = batch.GetFromBatchAndDB(db, read_options, "c", &value);
1229 ASSERT_OK(s);
1230 ASSERT_EQ("c0,c1", value);
1231
1232 s = batch.GetFromBatchAndDB(db, snapshot_read_options, "c", &value);
1233 ASSERT_OK(s);
1234 ASSERT_EQ("c0", value);
1235
1236 s = db->Put(write_options, "e", "e1");
1237 ASSERT_OK(s);
1238
1239 s = batch.GetFromBatchAndDB(db, read_options, "e", &value);
1240 ASSERT_OK(s);
1241 ASSERT_EQ("e1,e0", value);
1242
1243 s = batch.GetFromBatchAndDB(db, snapshot_read_options, "e", &value);
1244 ASSERT_OK(s);
1245 ASSERT_EQ("e0", value);
1246
1247 s = db->Delete(write_options, "e");
1248 ASSERT_OK(s);
1249
1250 s = batch.GetFromBatchAndDB(db, read_options, "e", &value);
1251 ASSERT_OK(s);
1252 ASSERT_EQ("e0", value);
1253
1254 s = batch.GetFromBatchAndDB(db, snapshot_read_options, "e", &value);
1255 ASSERT_OK(s);
1256 ASSERT_EQ("e0", value);
1257
1258 db->ReleaseSnapshot(snapshot);
1259 delete db;
1260 DestroyDB(dbname, options);
1261 }
1262
TEST_F(WriteBatchWithIndexTest,TestGetFromBatchAndDBMerge2)1263 TEST_F(WriteBatchWithIndexTest, TestGetFromBatchAndDBMerge2) {
1264 DB* db;
1265 Options options;
1266
1267 options.create_if_missing = true;
1268 std::string dbname = test::PerThreadDBPath("write_batch_with_index_test");
1269
1270 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1271
1272 DestroyDB(dbname, options);
1273 Status s = DB::Open(options, dbname, &db);
1274 assert(s.ok());
1275
1276 // Test batch with overwrite_key=true
1277 WriteBatchWithIndex batch(BytewiseComparator(), 0, true);
1278
1279 ReadOptions read_options;
1280 WriteOptions write_options;
1281 std::string value;
1282
1283 s = batch.GetFromBatchAndDB(db, read_options, "A", &value);
1284 ASSERT_TRUE(s.IsNotFound());
1285
1286 batch.Merge("A", "xxx");
1287
1288 s = batch.GetFromBatchAndDB(db, read_options, "A", &value);
1289 ASSERT_TRUE(s.IsMergeInProgress());
1290
1291 batch.Merge("A", "yyy");
1292
1293 s = batch.GetFromBatchAndDB(db, read_options, "A", &value);
1294 ASSERT_TRUE(s.IsMergeInProgress());
1295
1296 s = db->Put(write_options, "A", "a0");
1297 ASSERT_OK(s);
1298
1299 s = batch.GetFromBatchAndDB(db, read_options, "A", &value);
1300 ASSERT_TRUE(s.IsMergeInProgress());
1301
1302 batch.Delete("A");
1303
1304 s = batch.GetFromBatchAndDB(db, read_options, "A", &value);
1305 ASSERT_TRUE(s.IsNotFound());
1306
1307 delete db;
1308 DestroyDB(dbname, options);
1309 }
1310
TEST_F(WriteBatchWithIndexTest,TestGetFromBatchAndDBMerge3)1311 TEST_F(WriteBatchWithIndexTest, TestGetFromBatchAndDBMerge3) {
1312 DB* db;
1313 Options options;
1314
1315 options.create_if_missing = true;
1316 std::string dbname = test::PerThreadDBPath("write_batch_with_index_test");
1317
1318 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1319
1320 DestroyDB(dbname, options);
1321 Status s = DB::Open(options, dbname, &db);
1322 assert(s.ok());
1323
1324 ReadOptions read_options;
1325 WriteOptions write_options;
1326 FlushOptions flush_options;
1327 std::string value;
1328
1329 WriteBatchWithIndex batch;
1330
1331 ASSERT_OK(db->Put(write_options, "A", "1"));
1332 ASSERT_OK(db->Flush(flush_options, db->DefaultColumnFamily()));
1333 ASSERT_OK(batch.Merge("A", "2"));
1334
1335 ASSERT_OK(batch.GetFromBatchAndDB(db, read_options, "A", &value));
1336 ASSERT_EQ(value, "1,2");
1337
1338 delete db;
1339 DestroyDB(dbname, options);
1340 }
1341
AssertKey(std::string key,WBWIIterator * iter)1342 void AssertKey(std::string key, WBWIIterator* iter) {
1343 ASSERT_TRUE(iter->Valid());
1344 ASSERT_EQ(key, iter->Entry().key.ToString());
1345 }
1346
AssertValue(std::string value,WBWIIterator * iter)1347 void AssertValue(std::string value, WBWIIterator* iter) {
1348 ASSERT_TRUE(iter->Valid());
1349 ASSERT_EQ(value, iter->Entry().value.ToString());
1350 }
1351
1352 // Tests that we can write to the WBWI while we iterate (from a single thread).
1353 // iteration should see the newest writes
TEST_F(WriteBatchWithIndexTest,MutateWhileIteratingCorrectnessTest)1354 TEST_F(WriteBatchWithIndexTest, MutateWhileIteratingCorrectnessTest) {
1355 WriteBatchWithIndex batch(BytewiseComparator(), 0, true);
1356 for (char c = 'a'; c <= 'z'; ++c) {
1357 batch.Put(std::string(1, c), std::string(1, c));
1358 }
1359
1360 std::unique_ptr<WBWIIterator> iter(batch.NewIterator());
1361 iter->Seek("k");
1362 AssertKey("k", iter.get());
1363 iter->Next();
1364 AssertKey("l", iter.get());
1365 batch.Put("ab", "cc");
1366 iter->Next();
1367 AssertKey("m", iter.get());
1368 batch.Put("mm", "kk");
1369 iter->Next();
1370 AssertKey("mm", iter.get());
1371 AssertValue("kk", iter.get());
1372 batch.Delete("mm");
1373
1374 iter->Next();
1375 AssertKey("n", iter.get());
1376 iter->Prev();
1377 AssertKey("mm", iter.get());
1378 ASSERT_EQ(kDeleteRecord, iter->Entry().type);
1379
1380 iter->Seek("ab");
1381 AssertKey("ab", iter.get());
1382 batch.Delete("x");
1383 iter->Seek("x");
1384 AssertKey("x", iter.get());
1385 ASSERT_EQ(kDeleteRecord, iter->Entry().type);
1386 iter->Prev();
1387 AssertKey("w", iter.get());
1388 }
1389
AssertIterKey(std::string key,Iterator * iter)1390 void AssertIterKey(std::string key, Iterator* iter) {
1391 ASSERT_TRUE(iter->Valid());
1392 ASSERT_EQ(key, iter->key().ToString());
1393 }
1394
AssertIterValue(std::string value,Iterator * iter)1395 void AssertIterValue(std::string value, Iterator* iter) {
1396 ASSERT_TRUE(iter->Valid());
1397 ASSERT_EQ(value, iter->value().ToString());
1398 }
1399
1400 // same thing as above, but testing IteratorWithBase
TEST_F(WriteBatchWithIndexTest,MutateWhileIteratingBaseCorrectnessTest)1401 TEST_F(WriteBatchWithIndexTest, MutateWhileIteratingBaseCorrectnessTest) {
1402 WriteBatchWithIndex batch(BytewiseComparator(), 0, true);
1403 for (char c = 'a'; c <= 'z'; ++c) {
1404 batch.Put(std::string(1, c), std::string(1, c));
1405 }
1406
1407 KVMap map;
1408 map["aa"] = "aa";
1409 map["cc"] = "cc";
1410 map["ee"] = "ee";
1411 map["em"] = "me";
1412
1413 std::unique_ptr<Iterator> iter(
1414 batch.NewIteratorWithBase(new KVIter(&map)));
1415 iter->Seek("k");
1416 AssertIterKey("k", iter.get());
1417 iter->Next();
1418 AssertIterKey("l", iter.get());
1419 batch.Put("ab", "cc");
1420 iter->Next();
1421 AssertIterKey("m", iter.get());
1422 batch.Put("mm", "kk");
1423 iter->Next();
1424 AssertIterKey("mm", iter.get());
1425 AssertIterValue("kk", iter.get());
1426 batch.Delete("mm");
1427 iter->Next();
1428 AssertIterKey("n", iter.get());
1429 iter->Prev();
1430 // "mm" is deleted, so we're back at "m"
1431 AssertIterKey("m", iter.get());
1432
1433 iter->Seek("ab");
1434 AssertIterKey("ab", iter.get());
1435 iter->Prev();
1436 AssertIterKey("aa", iter.get());
1437 iter->Prev();
1438 AssertIterKey("a", iter.get());
1439 batch.Delete("aa");
1440 iter->Next();
1441 AssertIterKey("ab", iter.get());
1442 iter->Prev();
1443 AssertIterKey("a", iter.get());
1444
1445 batch.Delete("x");
1446 iter->Seek("x");
1447 AssertIterKey("y", iter.get());
1448 iter->Next();
1449 AssertIterKey("z", iter.get());
1450 iter->Prev();
1451 iter->Prev();
1452 AssertIterKey("w", iter.get());
1453
1454 batch.Delete("e");
1455 iter->Seek("e");
1456 AssertIterKey("ee", iter.get());
1457 AssertIterValue("ee", iter.get());
1458 batch.Put("ee", "xx");
1459 // still the same value
1460 AssertIterValue("ee", iter.get());
1461 iter->Next();
1462 AssertIterKey("em", iter.get());
1463 iter->Prev();
1464 // new value
1465 AssertIterValue("xx", iter.get());
1466 }
1467
1468 // stress testing mutations with IteratorWithBase
TEST_F(WriteBatchWithIndexTest,MutateWhileIteratingBaseStressTest)1469 TEST_F(WriteBatchWithIndexTest, MutateWhileIteratingBaseStressTest) {
1470 WriteBatchWithIndex batch(BytewiseComparator(), 0, true);
1471 for (char c = 'a'; c <= 'z'; ++c) {
1472 batch.Put(std::string(1, c), std::string(1, c));
1473 }
1474
1475 KVMap map;
1476 for (char c = 'a'; c <= 'z'; ++c) {
1477 map[std::string(2, c)] = std::string(2, c);
1478 }
1479
1480 std::unique_ptr<Iterator> iter(
1481 batch.NewIteratorWithBase(new KVIter(&map)));
1482
1483 Random rnd(301);
1484 for (int i = 0; i < 1000000; ++i) {
1485 int random = rnd.Uniform(8);
1486 char c = static_cast<char>(rnd.Uniform(26) + 'a');
1487 switch (random) {
1488 case 0:
1489 batch.Put(std::string(1, c), "xxx");
1490 break;
1491 case 1:
1492 batch.Put(std::string(2, c), "xxx");
1493 break;
1494 case 2:
1495 batch.Delete(std::string(1, c));
1496 break;
1497 case 3:
1498 batch.Delete(std::string(2, c));
1499 break;
1500 case 4:
1501 iter->Seek(std::string(1, c));
1502 break;
1503 case 5:
1504 iter->Seek(std::string(2, c));
1505 break;
1506 case 6:
1507 if (iter->Valid()) {
1508 iter->Next();
1509 }
1510 break;
1511 case 7:
1512 if (iter->Valid()) {
1513 iter->Prev();
1514 }
1515 break;
1516 default:
1517 assert(false);
1518 }
1519 }
1520 }
1521
PrintContents(WriteBatchWithIndex * batch,ColumnFamilyHandle * column_family)1522 static std::string PrintContents(WriteBatchWithIndex* batch,
1523 ColumnFamilyHandle* column_family) {
1524 std::string result;
1525
1526 WBWIIterator* iter;
1527 if (column_family == nullptr) {
1528 iter = batch->NewIterator();
1529 } else {
1530 iter = batch->NewIterator(column_family);
1531 }
1532
1533 iter->SeekToFirst();
1534 while (iter->Valid()) {
1535 WriteEntry e = iter->Entry();
1536
1537 if (e.type == kPutRecord) {
1538 result.append("PUT(");
1539 result.append(e.key.ToString());
1540 result.append("):");
1541 result.append(e.value.ToString());
1542 } else if (e.type == kMergeRecord) {
1543 result.append("MERGE(");
1544 result.append(e.key.ToString());
1545 result.append("):");
1546 result.append(e.value.ToString());
1547 } else if (e.type == kSingleDeleteRecord) {
1548 result.append("SINGLE-DEL(");
1549 result.append(e.key.ToString());
1550 result.append(")");
1551 } else {
1552 assert(e.type == kDeleteRecord);
1553 result.append("DEL(");
1554 result.append(e.key.ToString());
1555 result.append(")");
1556 }
1557
1558 result.append(",");
1559 iter->Next();
1560 }
1561
1562 delete iter;
1563 return result;
1564 }
1565
PrintContents(WriteBatchWithIndex * batch,KVMap * base_map,ColumnFamilyHandle * column_family)1566 static std::string PrintContents(WriteBatchWithIndex* batch, KVMap* base_map,
1567 ColumnFamilyHandle* column_family) {
1568 std::string result;
1569
1570 Iterator* iter;
1571 if (column_family == nullptr) {
1572 iter = batch->NewIteratorWithBase(new KVIter(base_map));
1573 } else {
1574 iter = batch->NewIteratorWithBase(column_family, new KVIter(base_map));
1575 }
1576
1577 iter->SeekToFirst();
1578 while (iter->Valid()) {
1579 assert(iter->status().ok());
1580
1581 Slice key = iter->key();
1582 Slice value = iter->value();
1583
1584 result.append(key.ToString());
1585 result.append(":");
1586 result.append(value.ToString());
1587 result.append(",");
1588
1589 iter->Next();
1590 }
1591
1592 delete iter;
1593 return result;
1594 }
1595
TEST_F(WriteBatchWithIndexTest,SavePointTest)1596 TEST_F(WriteBatchWithIndexTest, SavePointTest) {
1597 WriteBatchWithIndex batch;
1598 ColumnFamilyHandleImplDummy cf1(1, BytewiseComparator());
1599 Status s;
1600
1601 batch.Put("A", "a");
1602 batch.Put("B", "b");
1603 batch.Put("A", "aa");
1604 batch.Put(&cf1, "A", "a1");
1605 batch.Delete(&cf1, "B");
1606 batch.Put(&cf1, "C", "c1");
1607 batch.Put(&cf1, "E", "e1");
1608
1609 batch.SetSavePoint(); // 1
1610
1611 batch.Put("C", "cc");
1612 batch.Put("B", "bb");
1613 batch.Delete("A");
1614 batch.Put(&cf1, "B", "b1");
1615 batch.Delete(&cf1, "A");
1616 batch.SingleDelete(&cf1, "E");
1617 batch.SetSavePoint(); // 2
1618
1619 batch.Put("A", "aaa");
1620 batch.Put("A", "xxx");
1621 batch.Delete("B");
1622 batch.Put(&cf1, "B", "b2");
1623 batch.Delete(&cf1, "C");
1624 batch.SetSavePoint(); // 3
1625 batch.SetSavePoint(); // 4
1626 batch.SingleDelete("D");
1627 batch.Delete(&cf1, "D");
1628 batch.Delete(&cf1, "E");
1629
1630 ASSERT_EQ(
1631 "PUT(A):a,PUT(A):aa,DEL(A),PUT(A):aaa,PUT(A):xxx,PUT(B):b,PUT(B):bb,DEL("
1632 "B)"
1633 ",PUT(C):cc,SINGLE-DEL(D),",
1634 PrintContents(&batch, nullptr));
1635
1636 ASSERT_EQ(
1637 "PUT(A):a1,DEL(A),DEL(B),PUT(B):b1,PUT(B):b2,PUT(C):c1,DEL(C),"
1638 "DEL(D),PUT(E):e1,SINGLE-DEL(E),DEL(E),",
1639 PrintContents(&batch, &cf1));
1640
1641 ASSERT_OK(batch.RollbackToSavePoint()); // rollback to 4
1642 ASSERT_EQ(
1643 "PUT(A):a,PUT(A):aa,DEL(A),PUT(A):aaa,PUT(A):xxx,PUT(B):b,PUT(B):bb,DEL("
1644 "B)"
1645 ",PUT(C):cc,",
1646 PrintContents(&batch, nullptr));
1647
1648 ASSERT_EQ(
1649 "PUT(A):a1,DEL(A),DEL(B),PUT(B):b1,PUT(B):b2,PUT(C):c1,DEL(C),"
1650 "PUT(E):e1,SINGLE-DEL(E),",
1651 PrintContents(&batch, &cf1));
1652
1653 ASSERT_OK(batch.RollbackToSavePoint()); // rollback to 3
1654 ASSERT_EQ(
1655 "PUT(A):a,PUT(A):aa,DEL(A),PUT(A):aaa,PUT(A):xxx,PUT(B):b,PUT(B):bb,DEL("
1656 "B)"
1657 ",PUT(C):cc,",
1658 PrintContents(&batch, nullptr));
1659
1660 ASSERT_EQ(
1661 "PUT(A):a1,DEL(A),DEL(B),PUT(B):b1,PUT(B):b2,PUT(C):c1,DEL(C),"
1662 "PUT(E):e1,SINGLE-DEL(E),",
1663 PrintContents(&batch, &cf1));
1664
1665 ASSERT_OK(batch.RollbackToSavePoint()); // rollback to 2
1666 ASSERT_EQ("PUT(A):a,PUT(A):aa,DEL(A),PUT(B):b,PUT(B):bb,PUT(C):cc,",
1667 PrintContents(&batch, nullptr));
1668
1669 ASSERT_EQ(
1670 "PUT(A):a1,DEL(A),DEL(B),PUT(B):b1,PUT(C):c1,"
1671 "PUT(E):e1,SINGLE-DEL(E),",
1672 PrintContents(&batch, &cf1));
1673
1674 batch.SetSavePoint(); // 5
1675 batch.Put("X", "x");
1676
1677 ASSERT_EQ("PUT(A):a,PUT(A):aa,DEL(A),PUT(B):b,PUT(B):bb,PUT(C):cc,PUT(X):x,",
1678 PrintContents(&batch, nullptr));
1679
1680 ASSERT_OK(batch.RollbackToSavePoint()); // rollback to 5
1681 ASSERT_EQ("PUT(A):a,PUT(A):aa,DEL(A),PUT(B):b,PUT(B):bb,PUT(C):cc,",
1682 PrintContents(&batch, nullptr));
1683
1684 ASSERT_EQ(
1685 "PUT(A):a1,DEL(A),DEL(B),PUT(B):b1,PUT(C):c1,"
1686 "PUT(E):e1,SINGLE-DEL(E),",
1687 PrintContents(&batch, &cf1));
1688
1689 ASSERT_OK(batch.RollbackToSavePoint()); // rollback to 1
1690 ASSERT_EQ("PUT(A):a,PUT(A):aa,PUT(B):b,", PrintContents(&batch, nullptr));
1691
1692 ASSERT_EQ("PUT(A):a1,DEL(B),PUT(C):c1,PUT(E):e1,",
1693 PrintContents(&batch, &cf1));
1694
1695 s = batch.RollbackToSavePoint(); // no savepoint found
1696 ASSERT_TRUE(s.IsNotFound());
1697 ASSERT_EQ("PUT(A):a,PUT(A):aa,PUT(B):b,", PrintContents(&batch, nullptr));
1698
1699 ASSERT_EQ("PUT(A):a1,DEL(B),PUT(C):c1,PUT(E):e1,",
1700 PrintContents(&batch, &cf1));
1701
1702 batch.SetSavePoint(); // 6
1703
1704 batch.Clear();
1705 ASSERT_EQ("", PrintContents(&batch, nullptr));
1706 ASSERT_EQ("", PrintContents(&batch, &cf1));
1707
1708 s = batch.RollbackToSavePoint(); // rollback to 6
1709 ASSERT_TRUE(s.IsNotFound());
1710 }
1711
TEST_F(WriteBatchWithIndexTest,SingleDeleteTest)1712 TEST_F(WriteBatchWithIndexTest, SingleDeleteTest) {
1713 WriteBatchWithIndex batch;
1714 Status s;
1715 std::string value;
1716 DBOptions db_options;
1717
1718 batch.SingleDelete("A");
1719
1720 s = batch.GetFromBatch(db_options, "A", &value);
1721 ASSERT_TRUE(s.IsNotFound());
1722 s = batch.GetFromBatch(db_options, "B", &value);
1723 ASSERT_TRUE(s.IsNotFound());
1724 value = PrintContents(&batch, nullptr);
1725 ASSERT_EQ("SINGLE-DEL(A),", value);
1726
1727 batch.Clear();
1728 batch.Put("A", "a");
1729 batch.Put("A", "a2");
1730 batch.Put("B", "b");
1731 batch.SingleDelete("A");
1732
1733 s = batch.GetFromBatch(db_options, "A", &value);
1734 ASSERT_TRUE(s.IsNotFound());
1735 s = batch.GetFromBatch(db_options, "B", &value);
1736 ASSERT_OK(s);
1737 ASSERT_EQ("b", value);
1738
1739 value = PrintContents(&batch, nullptr);
1740 ASSERT_EQ("PUT(A):a,PUT(A):a2,SINGLE-DEL(A),PUT(B):b,", value);
1741
1742 batch.Put("C", "c");
1743 batch.Put("A", "a3");
1744 batch.Delete("B");
1745 batch.SingleDelete("B");
1746 batch.SingleDelete("C");
1747
1748 s = batch.GetFromBatch(db_options, "A", &value);
1749 ASSERT_OK(s);
1750 ASSERT_EQ("a3", value);
1751 s = batch.GetFromBatch(db_options, "B", &value);
1752 ASSERT_TRUE(s.IsNotFound());
1753 s = batch.GetFromBatch(db_options, "C", &value);
1754 ASSERT_TRUE(s.IsNotFound());
1755 s = batch.GetFromBatch(db_options, "D", &value);
1756 ASSERT_TRUE(s.IsNotFound());
1757
1758 value = PrintContents(&batch, nullptr);
1759 ASSERT_EQ(
1760 "PUT(A):a,PUT(A):a2,SINGLE-DEL(A),PUT(A):a3,PUT(B):b,DEL(B),SINGLE-DEL(B)"
1761 ",PUT(C):c,SINGLE-DEL(C),",
1762 value);
1763
1764 batch.Put("B", "b4");
1765 batch.Put("C", "c4");
1766 batch.Put("D", "d4");
1767 batch.SingleDelete("D");
1768 batch.SingleDelete("D");
1769 batch.Delete("A");
1770
1771 s = batch.GetFromBatch(db_options, "A", &value);
1772 ASSERT_TRUE(s.IsNotFound());
1773 s = batch.GetFromBatch(db_options, "B", &value);
1774 ASSERT_OK(s);
1775 ASSERT_EQ("b4", value);
1776 s = batch.GetFromBatch(db_options, "C", &value);
1777 ASSERT_OK(s);
1778 ASSERT_EQ("c4", value);
1779 s = batch.GetFromBatch(db_options, "D", &value);
1780 ASSERT_TRUE(s.IsNotFound());
1781
1782 value = PrintContents(&batch, nullptr);
1783 ASSERT_EQ(
1784 "PUT(A):a,PUT(A):a2,SINGLE-DEL(A),PUT(A):a3,DEL(A),PUT(B):b,DEL(B),"
1785 "SINGLE-DEL(B),PUT(B):b4,PUT(C):c,SINGLE-DEL(C),PUT(C):c4,PUT(D):d4,"
1786 "SINGLE-DEL(D),SINGLE-DEL(D),",
1787 value);
1788 }
1789
TEST_F(WriteBatchWithIndexTest,SingleDeleteDeltaIterTest)1790 TEST_F(WriteBatchWithIndexTest, SingleDeleteDeltaIterTest) {
1791 Status s;
1792 std::string value;
1793 DBOptions db_options;
1794 WriteBatchWithIndex batch(BytewiseComparator(), 20, true /* overwrite_key */);
1795 batch.Put("A", "a");
1796 batch.Put("A", "a2");
1797 batch.Put("B", "b");
1798 batch.SingleDelete("A");
1799 batch.Delete("B");
1800
1801 KVMap map;
1802 value = PrintContents(&batch, &map, nullptr);
1803 ASSERT_EQ("", value);
1804
1805 map["A"] = "aa";
1806 map["C"] = "cc";
1807 map["D"] = "dd";
1808
1809 batch.SingleDelete("B");
1810 batch.SingleDelete("C");
1811 batch.SingleDelete("Z");
1812
1813 value = PrintContents(&batch, &map, nullptr);
1814 ASSERT_EQ("D:dd,", value);
1815
1816 batch.Put("A", "a3");
1817 batch.Put("B", "b3");
1818 batch.SingleDelete("A");
1819 batch.SingleDelete("A");
1820 batch.SingleDelete("D");
1821 batch.SingleDelete("D");
1822 batch.Delete("D");
1823
1824 map["E"] = "ee";
1825
1826 value = PrintContents(&batch, &map, nullptr);
1827 ASSERT_EQ("B:b3,E:ee,", value);
1828 }
1829
1830 } // namespace ROCKSDB_NAMESPACE
1831
main(int argc,char ** argv)1832 int main(int argc, char** argv) {
1833 ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
1834 ::testing::InitGoogleTest(&argc, argv);
1835 return RUN_ALL_TESTS();
1836 }
1837
1838 #else
1839 #include <stdio.h>
1840
main()1841 int main() {
1842 fprintf(stderr, "SKIPPED\n");
1843 return 0;
1844 }
1845
1846 #endif // !ROCKSDB_LITE
1847