1 // Copyright (C) 2019 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "icing/legacy/index/icing-dynamic-trie.h"
16
17 #include <cstddef>
18 #include <cstdint>
19 #include <cstdio>
20 #include <memory>
21 #include <string>
22 #include <unordered_map>
23 #include <vector>
24
25 #include "icing/text_classifier/lib3/utils/hash/farmhash.h"
26 #include "gmock/gmock.h"
27 #include "gtest/gtest.h"
28 #include "icing/legacy/core/icing-string-util.h"
29 #include "icing/legacy/index/icing-filesystem.h"
30 #include "icing/testing/tmp-directory.h"
31
32 using testing::ElementsAre;
33
34 namespace icing {
35 namespace lib {
36
37 namespace {
38
39 constexpr std::string_view kKeys[] = {
40 "", "ab", "ac", "abd", "bac", "bb", "bacd", "abbb", "abcdefg",
41 };
42 constexpr uint32_t kNumKeys = ABSL_ARRAYSIZE(kKeys);
43
44 class IcingDynamicTrieTest : public ::testing::Test {
45 protected:
46 class NewValueMap : public IcingDynamicTrie::NewValueMap {
47 public:
GetNewValue(uint32_t old_value_index) const48 const void* GetNewValue(uint32_t old_value_index) const override {
49 const_cast<NewValueMap*>(this)->buf_ = old_value_index;
50 return &buf_;
51 }
52
53 private:
54 uint32_t buf_;
55 };
56
57 // Output trie stats to stderr.
StatsDump(const IcingDynamicTrie & trie)58 static void StatsDump(const IcingDynamicTrie& trie) {
59 IcingDynamicTrie::Stats stats;
60 trie.CollectStats(&stats);
61 DLOG(INFO) << "Stats:\n" << stats.DumpStats(true);
62 }
63
AddToTrie(IcingDynamicTrie * trie,uint32_t num_keys)64 static void AddToTrie(IcingDynamicTrie* trie, uint32_t num_keys) {
65 std::string key;
66 for (uint32_t i = 0; i < kNumKeys; i++) {
67 key.clear();
68 IcingStringUtil::SStringAppendF(&key, 0, "%u+%010u", i % 2, i);
69 bool inserted = trie->Insert(key.c_str(), &i);
70 ASSERT_TRUE(inserted);
71 }
72 }
73
CheckTrie(const IcingDynamicTrie & trie,uint32_t num_keys)74 static void CheckTrie(const IcingDynamicTrie& trie, uint32_t num_keys) {
75 std::string key;
76 for (uint32_t i = 0; i < kNumKeys; i++) {
77 key.clear();
78 IcingStringUtil::SStringAppendF(&key, 0, "%u+%010u", i % 2, i);
79 uint32_t val;
80 bool found = trie.Find(key.c_str(), &val);
81 EXPECT_TRUE(found);
82 EXPECT_EQ(i, val);
83 }
84 }
85
PrintTrie(const IcingDynamicTrie & trie)86 static void PrintTrie(const IcingDynamicTrie& trie) {
87 std::vector<std::string> keys;
88 std::ostringstream os;
89 DLOG(INFO) << "Trie:\n";
90 trie.DumpTrie(&os, &keys);
91 DLOG(INFO) << os.str();
92 }
93
SetUp()94 void SetUp() override {
95 trie_files_dir_ = GetTestTempDir() + "/trie_files";
96 trie_files_prefix_ = trie_files_dir_ + "/test_file_";
97 }
98
TearDown()99 void TearDown() override {
100 IcingFilesystem filesystem;
101 filesystem.DeleteDirectoryRecursively(trie_files_dir_.c_str());
102 }
103
104 std::string trie_files_dir_;
105 std::string trie_files_prefix_;
106 };
107
108 constexpr std::string_view kCommonEnglishWords[] = {
109 "that", "was", "for", "on", "are", "with", "they", "be", "at",
110 "one", "have", "this", "from", "word", "but", "what", "some", "you",
111 "had", "the", "and", "can", "out", "other", "were", "which", "their",
112 "time", "will", "how", "said", "each", "tell", "may", "three"};
113 constexpr uint32_t kCommonEnglishWordArrayLen =
114 sizeof(kCommonEnglishWords) / sizeof(std::string_view);
115
TEST_F(IcingDynamicTrieTest,Simple)116 TEST_F(IcingDynamicTrieTest, Simple) {
117 // Test simple key insertions.
118 IcingFilesystem filesystem;
119 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
120 &filesystem);
121 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
122 ASSERT_TRUE(trie.Init());
123
124 for (uint32_t i = 0; i < kNumKeys; i++) {
125 ASSERT_TRUE(trie.Insert(kKeys[i].data(), &i));
126
127 uint32_t val;
128 bool found = trie.Find(kKeys[i].data(), &val);
129 EXPECT_TRUE(found) << kKeys[i];
130 if (found) EXPECT_EQ(i, val) << kKeys[i] << " " << val;
131 }
132
133 EXPECT_EQ(trie.size(), kNumKeys);
134
135 StatsDump(trie);
136 std::vector<std::string> keys;
137 std::ostringstream os;
138 DLOG(INFO) << "Trie:\n";
139 trie.DumpTrie(&os, &keys);
140 DLOG(INFO) << os.str();
141 EXPECT_EQ(keys.size(), kNumKeys);
142 }
143
TEST_F(IcingDynamicTrieTest,Init)144 TEST_F(IcingDynamicTrieTest, Init) {
145 // Test create/init behavior.
146 IcingFilesystem filesystem;
147 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
148 &filesystem);
149 EXPECT_FALSE(trie.is_initialized());
150 EXPECT_FALSE(trie.Init());
151
152 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
153 EXPECT_TRUE(trie.Init());
154 EXPECT_TRUE(trie.is_initialized());
155 }
156
TEST_F(IcingDynamicTrieTest,Iterator)157 TEST_F(IcingDynamicTrieTest, Iterator) {
158 // Test iterator.
159 IcingFilesystem filesystem;
160 uint32_t val;
161 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
162 &filesystem);
163 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
164 ASSERT_TRUE(trie.Init());
165
166 for (uint32_t i = 0; i < kNumKeys; i++) {
167 ASSERT_TRUE(trie.Insert(kKeys[i].data(), &i));
168 }
169
170 // We try everything twice to test that Reset also works.
171
172 // Should get the entire trie.
173 IcingDynamicTrie::Iterator it_all(trie, "");
174 for (int i = 0; i < 2; i++) {
175 uint32_t count = 0;
176 for (; it_all.IsValid(); it_all.Advance()) {
177 uint32_t val_idx = it_all.GetValueIndex();
178 EXPECT_EQ(it_all.GetValue(), trie.GetValueAtIndex(val_idx));
179 count++;
180 }
181 EXPECT_EQ(count, kNumKeys);
182 it_all.Reset();
183 }
184
185 // Get everything under "a".
186 IcingDynamicTrie::Iterator it1(trie, "a");
187 for (int i = 0; i < 2; i++) {
188 ASSERT_TRUE(it1.IsValid());
189 EXPECT_STREQ(it1.GetKey(), "ab");
190 static const uint32_t kOne = 1;
191 ASSERT_TRUE(it1.GetValue() != nullptr);
192 EXPECT_TRUE(!memcmp(it1.GetValue(), &kOne, sizeof(kOne)));
193
194 ASSERT_TRUE(it1.Advance());
195 ASSERT_TRUE(it1.IsValid());
196 EXPECT_STREQ(it1.GetKey(), "abbb");
197
198 ASSERT_TRUE(it1.Advance());
199 ASSERT_TRUE(it1.IsValid());
200 EXPECT_STREQ(it1.GetKey(), "abcdefg");
201
202 ASSERT_TRUE(it1.Advance());
203 ASSERT_TRUE(it1.IsValid());
204 EXPECT_STREQ(it1.GetKey(), "abd");
205
206 ASSERT_TRUE(it1.Advance());
207 ASSERT_TRUE(it1.IsValid());
208 EXPECT_STREQ(it1.GetKey(), "ac");
209
210 EXPECT_FALSE(it1.Advance());
211 EXPECT_FALSE(it1.IsValid());
212
213 it1.Reset();
214 }
215
216 // Now "b".
217 IcingDynamicTrie::Iterator it2(trie, "b");
218 for (int i = 0; i < 2; i++) {
219 ASSERT_TRUE(it2.IsValid());
220 EXPECT_STREQ(it2.GetKey(), "bac");
221 val = 1;
222 ASSERT_TRUE(it1.GetValue() != nullptr);
223 EXPECT_TRUE(!memcmp(it1.GetValue(), &val, sizeof(val)));
224 val = 4;
225 ASSERT_TRUE(it2.GetValue() != nullptr);
226 EXPECT_TRUE(!memcmp(it2.GetValue(), &val, sizeof(val)));
227
228 ASSERT_TRUE(it2.Advance());
229 ASSERT_TRUE(it2.IsValid());
230 EXPECT_STREQ(it2.GetKey(), "bacd");
231
232 ASSERT_TRUE(it2.Advance());
233 ASSERT_TRUE(it2.IsValid());
234 EXPECT_STREQ(it2.GetKey(), "bb");
235
236 EXPECT_FALSE(it2.Advance());
237 EXPECT_FALSE(it2.IsValid());
238
239 it2.Reset();
240 }
241
242 // Get everything under "ab".
243 IcingDynamicTrie::Iterator it3(trie, "ab");
244 for (int i = 0; i < 2; i++) {
245 ASSERT_TRUE(it3.IsValid());
246 EXPECT_STREQ(it3.GetKey(), "ab");
247 val = 1;
248 ASSERT_TRUE(it3.GetValue() != nullptr);
249 EXPECT_TRUE(!memcmp(it3.GetValue(), &val, sizeof(val)));
250
251 ASSERT_TRUE(it3.Advance());
252 ASSERT_TRUE(it3.IsValid());
253 EXPECT_STREQ(it3.GetKey(), "abbb");
254
255 ASSERT_TRUE(it3.Advance());
256 ASSERT_TRUE(it3.IsValid());
257 EXPECT_STREQ(it3.GetKey(), "abcdefg");
258
259 ASSERT_TRUE(it3.Advance());
260 ASSERT_TRUE(it3.IsValid());
261 EXPECT_STREQ(it3.GetKey(), "abd");
262
263 EXPECT_FALSE(it3.Advance());
264 EXPECT_FALSE(it3.IsValid());
265
266 it3.Reset();
267 }
268
269 // Should match only one key exactly.
270 constexpr std::string_view kOneMatch[] = {
271 "abd",
272 "abcd",
273 "abcdef",
274 "abcdefg",
275 };
276 // With the following match:
277 constexpr std::string_view kOneMatchMatched[] = {
278 "abd",
279 "abcdefg",
280 "abcdefg",
281 "abcdefg",
282 };
283
284 for (size_t k = 0; k < ABSL_ARRAYSIZE(kOneMatch); k++) {
285 IcingDynamicTrie::Iterator it_single(trie, kOneMatch[k].data());
286 for (int i = 0; i < 2; i++) {
287 ASSERT_TRUE(it_single.IsValid()) << kOneMatch[k];
288 EXPECT_STREQ(it_single.GetKey(), kOneMatchMatched[k].data());
289 EXPECT_FALSE(it_single.Advance()) << kOneMatch[k];
290 EXPECT_FALSE(it_single.IsValid()) << kOneMatch[k];
291
292 it_single.Reset();
293 }
294 }
295
296 // Matches nothing.
297 constexpr std::string_view kNoMatch[] = {
298 "abbd",
299 "abcdeg",
300 "abcdefh",
301 };
302 for (size_t k = 0; k < ABSL_ARRAYSIZE(kNoMatch); k++) {
303 IcingDynamicTrie::Iterator it_empty(trie, kNoMatch[k].data());
304 for (int i = 0; i < 2; i++) {
305 EXPECT_FALSE(it_empty.IsValid());
306
307 it_empty.Reset();
308 }
309 }
310
311 // Clear.
312 trie.Clear();
313 EXPECT_FALSE(IcingDynamicTrie::Iterator(trie, "").IsValid());
314 EXPECT_EQ(0u, trie.size());
315 EXPECT_EQ(1.0, trie.min_free_fraction());
316 }
317
TEST_F(IcingDynamicTrieTest,Persistence)318 TEST_F(IcingDynamicTrieTest, Persistence) {
319 // Test persistence on the English dictionary.
320 IcingFilesystem filesystem;
321 {
322 // Test with a trie including strings in words. Test will fail if
323 // words are not unique.
324 IcingDynamicTrie trie(trie_files_prefix_,
325 IcingDynamicTrie::RuntimeOptions(), &filesystem);
326 EXPECT_FALSE(trie.Init());
327 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
328 ASSERT_TRUE(trie.Init());
329
330 for (uint32_t i = 0; i < kCommonEnglishWordArrayLen; i++) {
331 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &i));
332 }
333 // Explicitly omit sync.
334
335 StatsDump(trie);
336 }
337
338 {
339 IcingDynamicTrie trie(trie_files_prefix_,
340 IcingDynamicTrie::RuntimeOptions(), &filesystem);
341 ASSERT_TRUE(trie.Init());
342 EXPECT_EQ(0U, trie.size());
343
344 for (uint32_t i = 0; i < kCommonEnglishWordArrayLen; i++) {
345 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &i));
346 }
347 trie.Sync();
348
349 StatsDump(trie);
350 }
351
352 {
353 IcingDynamicTrie trie(trie_files_prefix_,
354 IcingDynamicTrie::RuntimeOptions(), &filesystem);
355 ASSERT_TRUE(trie.Init());
356
357 // Make sure we can find everything with the right value.
358 uint32_t found_count = 0;
359 uint32_t matched_count = 0;
360 for (size_t i = 0; i < kCommonEnglishWordArrayLen; i++) {
361 uint32_t val;
362 bool found = trie.Find(kCommonEnglishWords[i].data(), &val);
363 if (found) {
364 found_count++;
365 if (i == val) {
366 matched_count++;
367 }
368 }
369 }
370 EXPECT_EQ(found_count, kCommonEnglishWordArrayLen);
371 EXPECT_EQ(matched_count, kCommonEnglishWordArrayLen);
372
373 StatsDump(trie);
374 }
375 }
376
TEST_F(IcingDynamicTrieTest,PersistenceShared)377 TEST_F(IcingDynamicTrieTest, PersistenceShared) {
378 // Test persistence on the English dictionary.
379 IcingFilesystem filesystem;
380 IcingDynamicTrie::RuntimeOptions ropt;
381
382 {
383 // Test with a trie including strings in words. Test will fail if
384 // words are not unique.
385 ropt.storage_policy = IcingDynamicTrie::RuntimeOptions::kMapSharedWithCrc;
386 IcingDynamicTrie trie(trie_files_prefix_, ropt, &filesystem);
387 EXPECT_FALSE(trie.Init());
388 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
389 ASSERT_TRUE(trie.Init());
390
391 uint32_t next_reopen = kCommonEnglishWordArrayLen / 16;
392 for (uint32_t i = 0; i < kCommonEnglishWordArrayLen; i++) {
393 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &i));
394
395 if (i == next_reopen) {
396 ASSERT_NE(0u, trie.UpdateCrc());
397 trie.Close();
398 ASSERT_TRUE(trie.Init());
399
400 next_reopen += next_reopen / 2;
401 }
402 }
403 // Explicitly omit sync. Shared should automatically persist.
404
405 StatsDump(trie);
406 }
407
408 // Go back and forth between the two policies.
409 for (int i = 0; i < 5; i++) {
410 if (i % 2 == 0) {
411 DLOG(INFO) << "Opening with map shared";
412 ropt.storage_policy = IcingDynamicTrie::RuntimeOptions::kMapSharedWithCrc;
413 } else {
414 DLOG(INFO) << "Opening with explicit flush";
415 ropt.storage_policy = IcingDynamicTrie::RuntimeOptions::kExplicitFlush;
416 }
417 IcingDynamicTrie trie(trie_files_prefix_, ropt, &filesystem);
418 ASSERT_TRUE(trie.Init());
419
420 // Make sure we can find everything with the right value.
421 uint32_t found_count = 0;
422 uint32_t matched_count = 0;
423 for (size_t i = 0; i < kCommonEnglishWordArrayLen; i++) {
424 uint32_t val;
425 bool found = trie.Find(kCommonEnglishWords[i].data(), &val);
426 if (found) {
427 found_count++;
428 if (i == val) {
429 matched_count++;
430 }
431 }
432 }
433 EXPECT_EQ(found_count, kCommonEnglishWordArrayLen);
434 EXPECT_EQ(matched_count, kCommonEnglishWordArrayLen);
435
436 StatsDump(trie);
437 }
438
439 // Clear and re-open.
440 ropt.storage_policy = IcingDynamicTrie::RuntimeOptions::kMapSharedWithCrc;
441 IcingDynamicTrie trie(trie_files_prefix_, ropt, &filesystem);
442 ASSERT_TRUE(trie.Init());
443 trie.Clear();
444 trie.Close();
445 ASSERT_TRUE(trie.Init());
446 }
447
TEST_F(IcingDynamicTrieTest,Sync)448 TEST_F(IcingDynamicTrieTest, Sync) {
449 IcingFilesystem filesystem;
450 {
451 IcingDynamicTrie trie(trie_files_prefix_,
452 IcingDynamicTrie::RuntimeOptions(), &filesystem);
453 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
454 ASSERT_TRUE(trie.Init());
455
456 for (uint32_t i = 0; i < kNumKeys; i++) {
457 ASSERT_TRUE(trie.Insert(kKeys[i].data(), &i));
458
459 uint32_t val;
460 bool found = trie.Find(kKeys[i].data(), &val);
461 EXPECT_TRUE(found) << kKeys[i];
462 if (found) EXPECT_EQ(i, val) << kKeys[i] << " " << val;
463 }
464
465 StatsDump(trie);
466 PrintTrie(trie);
467
468 trie.Sync();
469
470 for (uint32_t i = 0; i < kNumKeys; i++) {
471 uint32_t val;
472 bool found = trie.Find(kKeys[i].data(), &val);
473 EXPECT_TRUE(found) << kKeys[i];
474 if (found) EXPECT_EQ(i, val) << kKeys[i] << " " << val;
475 }
476 }
477
478 {
479 IcingDynamicTrie trie(trie_files_prefix_,
480 IcingDynamicTrie::RuntimeOptions(), &filesystem);
481 ASSERT_TRUE(trie.Init());
482
483 for (uint32_t i = 0; i < kNumKeys; i++) {
484 uint32_t val;
485 bool found = trie.Find(kKeys[i].data(), &val);
486 EXPECT_TRUE(found) << kKeys[i];
487 if (found) EXPECT_EQ(i, val) << kKeys[i] << " " << val;
488 }
489
490 StatsDump(trie);
491 PrintTrie(trie);
492 }
493 }
494
TEST_F(IcingDynamicTrieTest,LimitsZero)495 TEST_F(IcingDynamicTrieTest, LimitsZero) {
496 // Don't crash if we set limits to 0.
497 IcingFilesystem filesystem;
498 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
499 &filesystem);
500 ASSERT_FALSE(trie.CreateIfNotExist(IcingDynamicTrie::Options(0, 0, 0, 0)));
501 }
502
TEST_F(IcingDynamicTrieTest,LimitsSmall)503 TEST_F(IcingDynamicTrieTest, LimitsSmall) {
504 // Test limits with a few keys.
505 IcingFilesystem filesystem;
506 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
507 &filesystem);
508 ASSERT_TRUE(trie.CreateIfNotExist(
509 IcingDynamicTrie::Options(10, 300, 30, sizeof(uint32_t))));
510 ASSERT_TRUE(trie.Init());
511
512 ASSERT_LT(3U, kNumKeys);
513
514 for (uint32_t i = 0; i < 3; i++) {
515 ASSERT_TRUE(trie.Insert(kKeys[i].data(), &i)) << i;
516
517 uint32_t val;
518 bool found = trie.Find(kKeys[i].data(), &val);
519 EXPECT_TRUE(found) << kKeys[i];
520 if (found) EXPECT_EQ(i, val) << kKeys[i] << " " << val;
521 }
522
523 uint32_t val = 3;
524 EXPECT_FALSE(trie.Insert(kKeys[3].data(), &val));
525
526 StatsDump(trie);
527 PrintTrie(trie);
528 }
529
TEST_F(IcingDynamicTrieTest,DISABLEDFingerprintedKeys)530 TEST_F(IcingDynamicTrieTest, DISABLEDFingerprintedKeys) {
531 IcingFilesystem filesystem;
532 IcingDynamicTrie::Options options(4 << 20, 4 << 20, 20 << 20,
533 sizeof(uint32_t));
534 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
535 &filesystem);
536 ASSERT_TRUE(trie.CreateIfNotExist(options));
537 ASSERT_TRUE(trie.Init());
538 IcingDynamicTrie triefp(trie_files_prefix_ + ".fps",
539 IcingDynamicTrie::RuntimeOptions(), &filesystem);
540 ASSERT_TRUE(triefp.CreateIfNotExist(options));
541 ASSERT_TRUE(triefp.Init());
542
543 static const uint32_t kNumKeys = 1000000;
544 std::string key;
545 for (uint32_t i = 0; i < kNumKeys; i++) {
546 key.clear();
547 IcingStringUtil::SStringAppendF(
548 &key, 1000, "content://gmail-ls/account/conversation/%u/message/%u", i,
549 10 * i);
550 ASSERT_TRUE(trie.Insert(key.c_str(), &i));
551
552 // Now compute a fingerprint.
553 uint64_t fpkey = tc3farmhash::Fingerprint64(key);
554
555 // Convert to base255 since keys in trie cannot contain 0.
556 uint8_t fpkey_base255[9];
557 for (int j = 0; j < 8; j++) {
558 fpkey_base255[j] = (fpkey % 255) + 1;
559 fpkey /= 255;
560 }
561 fpkey_base255[8] = '\0';
562 ASSERT_TRUE(
563 triefp.Insert(reinterpret_cast<const char*>(fpkey_base255), &i));
564
565 // Sync periodically to gauge write locality.
566 if ((i + 1) % (kNumKeys / 10) == 0) {
567 DLOG(INFO) << "Trie sync";
568 trie.Sync();
569 DLOG(INFO) << "Trie fp sync";
570 triefp.Sync();
571 }
572 }
573
574 DLOG(INFO) << "Trie stats";
575 StatsDump(trie);
576 DLOG(INFO) << "Trie fp stats";
577 StatsDump(triefp);
578 }
579
TEST_F(IcingDynamicTrieTest,AddDups)580 TEST_F(IcingDynamicTrieTest, AddDups) {
581 IcingFilesystem filesystem;
582 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
583 &filesystem);
584 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
585 ASSERT_TRUE(trie.Init());
586
587 static const uint32_t kNumKeys = 5000;
588 AddToTrie(&trie, kNumKeys);
589 CheckTrie(trie, kNumKeys);
590
591 DLOG(INFO) << "Trie stats";
592 StatsDump(trie);
593
594 AddToTrie(&trie, kNumKeys);
595 CheckTrie(trie, kNumKeys);
596 DLOG(INFO) << "Trie stats";
597 StatsDump(trie);
598 }
599
TEST_F(IcingDynamicTrieTest,Properties)600 TEST_F(IcingDynamicTrieTest, Properties) {
601 IcingFilesystem filesystem;
602 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
603 &filesystem);
604 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
605 ASSERT_TRUE(trie.Init());
606
607 static const uint32_t kOne = 1;
608 uint32_t val_idx;
609 trie.Insert("abcd", &kOne, &val_idx, false);
610 trie.SetProperty(val_idx, 0);
611 trie.SetProperty(val_idx, 3);
612
613 {
614 IcingDynamicTrie::PropertyReader reader(trie, 3);
615 ASSERT_TRUE(reader.Exists());
616 EXPECT_TRUE(reader.HasProperty(val_idx));
617 EXPECT_FALSE(reader.HasProperty(1000));
618 }
619
620 // Disappear after close.
621 trie.Close();
622 ASSERT_TRUE(trie.Init());
623 {
624 IcingDynamicTrie::PropertyReader reader(trie, 3);
625 EXPECT_FALSE(reader.HasProperty(val_idx));
626 }
627
628 // Persist after sync.
629 trie.Insert("abcd", &kOne, &val_idx, false);
630 trie.SetProperty(val_idx, 1);
631 ASSERT_TRUE(trie.Sync());
632 trie.Close();
633 ASSERT_TRUE(trie.Init());
634
635 uint32_t val;
636 ASSERT_TRUE(trie.Find("abcd", &val, &val_idx));
637 EXPECT_EQ(1u, val);
638 {
639 IcingDynamicTrie::PropertyReader reader(trie, 1);
640 EXPECT_TRUE(reader.HasProperty(val_idx));
641 }
642
643 // Get all.
644 {
645 IcingDynamicTrie::PropertyReadersAll readers(trie);
646 ASSERT_EQ(4u, readers.size());
647 EXPECT_TRUE(readers.Exists(0));
648 EXPECT_TRUE(readers.Exists(1));
649 EXPECT_FALSE(readers.Exists(2));
650 EXPECT_TRUE(readers.Exists(3));
651 }
652 }
653
TEST_F(IcingDynamicTrieTest,ClearSingleProperty)654 TEST_F(IcingDynamicTrieTest, ClearSingleProperty) {
655 IcingFilesystem filesystem;
656 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
657 &filesystem);
658 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
659 ASSERT_TRUE(trie.Init());
660
661 static const uint32_t kOne = 1;
662 uint32_t val_idx[3];
663 trie.Insert("abcd", &kOne, &val_idx[0], false);
664 trie.SetProperty(val_idx[0], 0);
665 trie.SetProperty(val_idx[0], 3);
666
667 trie.Insert("efgh", &kOne, &val_idx[1], false);
668 trie.SetProperty(val_idx[1], 0);
669 trie.SetProperty(val_idx[1], 3);
670
671 trie.Insert("ijkl", &kOne, &val_idx[2], false);
672 trie.SetProperty(val_idx[2], 0);
673 trie.SetProperty(val_idx[2], 3);
674
675 {
676 IcingDynamicTrie::PropertyReadersAll readers(trie);
677 ASSERT_EQ(4u, readers.size());
678 EXPECT_TRUE(readers.Exists(0));
679 EXPECT_FALSE(readers.Exists(1));
680 EXPECT_FALSE(readers.Exists(2));
681 EXPECT_TRUE(readers.Exists(3));
682 for (size_t i = 0; i < readers.size(); i++) {
683 if (readers.Exists(i)) {
684 for (size_t j = 0; j < sizeof(val_idx) / sizeof(uint32_t); ++j) {
685 EXPECT_TRUE(readers.HasProperty(i, val_idx[j]));
686 }
687 }
688 }
689 }
690
691 EXPECT_TRUE(trie.ClearPropertyForAllValues(3));
692
693 {
694 IcingDynamicTrie::PropertyReadersAll readers(trie);
695 ASSERT_EQ(4u, readers.size());
696 EXPECT_TRUE(readers.Exists(0));
697 EXPECT_FALSE(readers.Exists(1));
698 EXPECT_FALSE(readers.Exists(2));
699 // Clearing the property causes all values to be deleted.
700 EXPECT_FALSE(readers.Exists(3));
701 for (size_t i = 0; i < readers.size(); i++) {
702 for (size_t j = 0; j < sizeof(val_idx) / sizeof(uint32_t); ++j) {
703 if (i == 0) {
704 EXPECT_TRUE(readers.HasProperty(i, val_idx[j]));
705 } else {
706 EXPECT_FALSE(readers.HasProperty(i, val_idx[j]));
707 }
708 }
709 }
710 }
711 }
712
TEST_F(IcingDynamicTrieTest,Compact)713 TEST_F(IcingDynamicTrieTest, Compact) {
714 IcingFilesystem filesystem;
715 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
716 &filesystem);
717 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
718 ASSERT_TRUE(trie.Init());
719
720 for (uint32_t i = 0; i < kNumKeys; i++) {
721 ASSERT_TRUE(trie.Insert(kKeys[i].data(), &i));
722
723 uint32_t val;
724 bool found = trie.Find(kKeys[i].data(), &val);
725 EXPECT_TRUE(found) << kKeys[i];
726 if (found) EXPECT_EQ(i, val) << kKeys[i] << " " << val;
727 }
728
729 EXPECT_EQ(trie.size(), kNumKeys);
730
731 StatsDump(trie);
732 PrintTrie(trie);
733
734 IcingDynamicTrie trie2(trie_files_prefix_ + "-2",
735 IcingDynamicTrie::RuntimeOptions(), &filesystem);
736 ASSERT_TRUE(trie2.CreateIfNotExist(IcingDynamicTrie::Options()));
737 ASSERT_TRUE(trie2.Init());
738
739 std::unordered_map<uint32_t, uint32_t> old_to_new_tvi;
740 trie.Compact(NewValueMap(), &trie2, &old_to_new_tvi);
741 for (uint32_t i = 0; i < kNumKeys; i++) {
742 uint32_t val;
743 bool found = trie2.Find(kKeys[i].data(), &val);
744 EXPECT_TRUE(found) << kKeys[i];
745 EXPECT_TRUE(old_to_new_tvi.find(val) != old_to_new_tvi.end());
746 }
747 }
748
TEST_F(IcingDynamicTrieTest,DeletionShouldWorkWhenRootIsLeaf)749 TEST_F(IcingDynamicTrieTest, DeletionShouldWorkWhenRootIsLeaf) {
750 IcingFilesystem filesystem;
751 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
752 &filesystem);
753 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
754 ASSERT_TRUE(trie.Init());
755
756 // Inserts a key, the root is a leaf.
757 uint32_t value = 1;
758 ASSERT_TRUE(trie.Insert("foo", &value));
759 ASSERT_TRUE(trie.Find("foo", &value));
760
761 // Deletes the key.
762 EXPECT_TRUE(trie.Delete("foo"));
763 EXPECT_FALSE(trie.Find("foo", &value));
764 }
765
TEST_F(IcingDynamicTrieTest,DeletionShouldWorkWhenLastCharIsLeaf)766 TEST_F(IcingDynamicTrieTest, DeletionShouldWorkWhenLastCharIsLeaf) {
767 IcingFilesystem filesystem;
768 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
769 &filesystem);
770 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
771 ASSERT_TRUE(trie.Init());
772
773 // Inserts "bar" and "ba", the trie structure looks like:
774 // root
775 // |
776 // b
777 // |
778 // a
779 // / \
780 // null r
781 uint32_t value = 1;
782 ASSERT_TRUE(trie.Insert("bar", &value));
783 ASSERT_TRUE(trie.Insert("ba", &value));
784 ASSERT_TRUE(trie.Find("bar", &value));
785 ASSERT_TRUE(trie.Find("ba", &value));
786
787 // Deletes "bar". "r" is a leaf node in the trie.
788 EXPECT_TRUE(trie.Delete("bar"));
789 EXPECT_FALSE(trie.Find("bar", &value));
790 EXPECT_TRUE(trie.Find("ba", &value));
791 }
792
TEST_F(IcingDynamicTrieTest,DeletionShouldWorkWithTerminationNode)793 TEST_F(IcingDynamicTrieTest, DeletionShouldWorkWithTerminationNode) {
794 IcingFilesystem filesystem;
795 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
796 &filesystem);
797 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
798 ASSERT_TRUE(trie.Init());
799
800 // Inserts "bar" and "ba", the trie structure looks like:
801 // root
802 // |
803 // b
804 // |
805 // a
806 // / \
807 // null r
808 uint32_t value = 1;
809 ASSERT_TRUE(trie.Insert("bar", &value));
810 ASSERT_TRUE(trie.Insert("ba", &value));
811 ASSERT_TRUE(trie.Find("bar", &value));
812 ASSERT_TRUE(trie.Find("ba", &value));
813
814 // Deletes "ba" which is a key with termination node in the trie.
815 EXPECT_TRUE(trie.Delete("ba"));
816 EXPECT_FALSE(trie.Find("ba", &value));
817 EXPECT_TRUE(trie.Find("bar", &value));
818 }
819
TEST_F(IcingDynamicTrieTest,DeletionShouldWorkWithMultipleNexts)820 TEST_F(IcingDynamicTrieTest, DeletionShouldWorkWithMultipleNexts) {
821 IcingFilesystem filesystem;
822 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
823 &filesystem);
824 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
825 ASSERT_TRUE(trie.Init());
826
827 // Inserts "ba", "bb", "bc", and "bd", the trie structure looks like:
828 // root
829 // |
830 // b
831 // / | | \
832 // a b c d
833 uint32_t value = 1;
834 ASSERT_TRUE(trie.Insert("ba", &value));
835 ASSERT_TRUE(trie.Insert("bb", &value));
836 ASSERT_TRUE(trie.Insert("bc", &value));
837 ASSERT_TRUE(trie.Insert("bd", &value));
838 ASSERT_TRUE(trie.Find("ba", &value));
839 ASSERT_TRUE(trie.Find("bb", &value));
840 ASSERT_TRUE(trie.Find("bc", &value));
841 ASSERT_TRUE(trie.Find("bd", &value));
842
843 // Deletes "bc".
844 EXPECT_TRUE(trie.Delete("bc"));
845 EXPECT_FALSE(trie.Find("bc", &value));
846 EXPECT_TRUE(trie.Find("ba", &value));
847 EXPECT_TRUE(trie.Find("bb", &value));
848 EXPECT_TRUE(trie.Find("bd", &value));
849 }
850
TEST_F(IcingDynamicTrieTest,DeletionShouldWorkWithMultipleTrieBranches)851 TEST_F(IcingDynamicTrieTest, DeletionShouldWorkWithMultipleTrieBranches) {
852 IcingFilesystem filesystem;
853 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
854 &filesystem);
855 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
856 ASSERT_TRUE(trie.Init());
857
858 // Inserts "batter", "battle", and "bar", the trie structure looks like:
859 // root
860 // |
861 // b
862 // |
863 // a
864 // / \
865 // t r
866 // |
867 // t
868 // / \
869 // e l
870 // | |
871 // r e
872 uint32_t value = 1;
873 ASSERT_TRUE(trie.Insert("batter", &value));
874 ASSERT_TRUE(trie.Insert("battle", &value));
875 ASSERT_TRUE(trie.Insert("bar", &value));
876 ASSERT_TRUE(trie.Find("batter", &value));
877 ASSERT_TRUE(trie.Find("battle", &value));
878 ASSERT_TRUE(trie.Find("bar", &value));
879
880 // Deletes "batter".
881 EXPECT_TRUE(trie.Delete("batter"));
882 EXPECT_FALSE(trie.Find("batter", &value));
883 EXPECT_TRUE(trie.Find("battle", &value));
884 EXPECT_TRUE(trie.Find("bar", &value));
885 }
886
TEST_F(IcingDynamicTrieTest,InsertionShouldWorkAfterDeletion)887 TEST_F(IcingDynamicTrieTest, InsertionShouldWorkAfterDeletion) {
888 IcingFilesystem filesystem;
889 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
890 &filesystem);
891 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
892 ASSERT_TRUE(trie.Init());
893
894 // Inserts some keys.
895 uint32_t value = 1;
896 ASSERT_TRUE(trie.Insert("bar", &value));
897 ASSERT_TRUE(trie.Insert("bed", &value));
898 ASSERT_TRUE(trie.Insert("foo", &value));
899
900 // Deletes a key
901 ASSERT_TRUE(trie.Delete("bed"));
902 ASSERT_FALSE(trie.Find("bed", &value));
903
904 // Inserts after deletion
905 EXPECT_TRUE(trie.Insert("bed", &value));
906 EXPECT_TRUE(trie.Insert("bedroom", &value));
907 EXPECT_TRUE(trie.Find("bed", &value));
908 EXPECT_TRUE(trie.Find("bedroom", &value));
909 }
910
TEST_F(IcingDynamicTrieTest,IteratorShouldWorkAfterDeletion)911 TEST_F(IcingDynamicTrieTest, IteratorShouldWorkAfterDeletion) {
912 IcingFilesystem filesystem;
913 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
914 &filesystem);
915 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
916 ASSERT_TRUE(trie.Init());
917
918 // Inserts some keys.
919 uint32_t value = 1;
920 ASSERT_TRUE(trie.Insert("bar", &value));
921 ASSERT_TRUE(trie.Insert("bed", &value));
922 ASSERT_TRUE(trie.Insert("foo", &value));
923
924 // Deletes a key
925 ASSERT_TRUE(trie.Delete("bed"));
926
927 // Iterates through all keys
928 IcingDynamicTrie::Iterator iterator_all(trie, "");
929 std::vector<std::string> results;
930 for (; iterator_all.IsValid(); iterator_all.Advance()) {
931 results.emplace_back(iterator_all.GetKey());
932 }
933 EXPECT_THAT(results, ElementsAre("bar", "foo"));
934
935 // Iterates through keys that start with "b"
936 IcingDynamicTrie::Iterator iterator_b(trie, "b");
937 results.clear();
938 for (; iterator_b.IsValid(); iterator_b.Advance()) {
939 results.emplace_back(iterator_b.GetKey());
940 }
941 EXPECT_THAT(results, ElementsAre("bar"));
942 }
943
TEST_F(IcingDynamicTrieTest,DeletingNonExistingKeyShouldReturnTrue)944 TEST_F(IcingDynamicTrieTest, DeletingNonExistingKeyShouldReturnTrue) {
945 IcingFilesystem filesystem;
946 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
947 &filesystem);
948 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
949 ASSERT_TRUE(trie.Init());
950
951 // Inserts some keys.
952 uint32_t value = 1;
953 ASSERT_TRUE(trie.Insert("bar", &value));
954 ASSERT_TRUE(trie.Insert("bed", &value));
955
956 // "ba" and bedroom are not keys in the trie.
957 EXPECT_TRUE(trie.Delete("ba"));
958 EXPECT_TRUE(trie.Delete("bedroom"));
959
960 // The original keys are not affected.
961 EXPECT_TRUE(trie.Find("bar", &value));
962 EXPECT_TRUE(trie.Find("bed", &value));
963 }
964
965 } // namespace
966
967 // The tests below are accessing private methods and fields of IcingDynamicTrie
968 // so can't be in the anonymous namespace.
969
TEST_F(IcingDynamicTrieTest,TrieShouldRespectLimits)970 TEST_F(IcingDynamicTrieTest, TrieShouldRespectLimits) {
971 // Test limits on numbers of nodes, nexts, and suffixes size.
972 IcingFilesystem filesystem;
973
974 // These 3 numbers are the entities we need in order to insert all the test
975 // words before the last one.
976 uint32_t num_nodes_enough;
977 uint32_t num_nexts_enough;
978 uint32_t suffixes_size_enough;
979
980 // First, try to fill the 3 numbers above.
981 {
982 IcingDynamicTrie trie(trie_files_prefix_,
983 IcingDynamicTrie::RuntimeOptions(), &filesystem);
984 ASSERT_TRUE(trie.Remove());
985 // Creates a trie with enough numbers of nodes, nexts, and suffix file size.
986 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options(
987 /*max_nodes_in=*/1000, /*max_nexts_in=*/1000,
988 /*max_suffixes_size_in=*/1000, sizeof(uint32_t))));
989 ASSERT_TRUE(trie.Init());
990
991 // Inserts all the test words before the last one.
992 uint32_t value = 0;
993 for (size_t i = 0; i < kCommonEnglishWordArrayLen - 1; ++i) {
994 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &value));
995 }
996
997 IcingDynamicTrieHeader header;
998 trie.GetHeader(&header);
999
1000 // Before each insertion, it requires that there're (2 + 1 + key_length)
1001 // nodes left, so we need 8 nodes to insert the last word. +7 here will make
1002 // it just enough to insert the word before the last one.
1003 num_nodes_enough = header.num_nodes() + 7;
1004
1005 // Before each insertion, it requires that there're (2 + 1 + key_length +
1006 // kMaxNextArraySize) nexts left, so we need (8 + kMaxNextArraySize) nexts
1007 // to insert the last word. (7 + kMaxNextArraySize) here will make it just
1008 // enough to insert the word before the last one.
1009 num_nexts_enough =
1010 header.num_nexts() + 7 + IcingDynamicTrie::kMaxNextArraySize;
1011
1012 // Before each insertion, it requires that there're (1 + key_length +
1013 // value_size) bytes left for suffixes, so we need (6 + sizeof(uint32_t))
1014 // bytes to insert the last word. (5 + sizeof(uint32_t)) here will make it
1015 // just enough to insert the word before the last one.
1016 suffixes_size_enough = header.suffixes_size() + 5 + sizeof(uint32_t);
1017 }
1018
1019 // Test a trie with just enough number of nodes.
1020 {
1021 IcingDynamicTrie trie(trie_files_prefix_,
1022 IcingDynamicTrie::RuntimeOptions(), &filesystem);
1023 ASSERT_TRUE(trie.Remove());
1024 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options(
1025 num_nodes_enough, /*max_nexts_in=*/1000,
1026 /*max_suffixes_size_in=*/1000, sizeof(uint32_t))));
1027 ASSERT_TRUE(trie.Init());
1028
1029 // Inserts all the test words before the last one.
1030 uint32_t value = 0;
1031 for (size_t i = 0; i < kCommonEnglishWordArrayLen - 1; ++i) {
1032 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &value));
1033 }
1034
1035 // Fails to insert the last word because no enough nodes left.
1036 EXPECT_FALSE(trie.Insert(
1037 kCommonEnglishWords[kCommonEnglishWordArrayLen - 1].data(), &value));
1038 }
1039
1040 // Test a trie with just enough number of nexts.
1041 {
1042 IcingDynamicTrie trie(trie_files_prefix_,
1043 IcingDynamicTrie::RuntimeOptions(), &filesystem);
1044 ASSERT_TRUE(trie.Remove());
1045 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options(
1046 /*max_nodes_in=*/1000, num_nexts_enough,
1047 /*max_suffixes_size_in=*/1000, sizeof(uint32_t))));
1048 ASSERT_TRUE(trie.Init());
1049
1050 // Inserts all the test words before the last one.
1051 uint32_t value = 0;
1052 for (size_t i = 0; i < kCommonEnglishWordArrayLen - 1; ++i) {
1053 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &value));
1054 }
1055
1056 // Fails to insert the last word because no enough nexts left.
1057 EXPECT_FALSE(trie.Insert(
1058 kCommonEnglishWords[kCommonEnglishWordArrayLen - 1].data(), &value));
1059 }
1060
1061 // Test a trie with just enough suffixes size.
1062 {
1063 IcingDynamicTrie trie(trie_files_prefix_,
1064 IcingDynamicTrie::RuntimeOptions(), &filesystem);
1065 ASSERT_TRUE(trie.Remove());
1066 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options(
1067 /*max_nodes_in=*/1000, /*max_nexts_in=*/1000, suffixes_size_enough,
1068 sizeof(uint32_t))));
1069 ASSERT_TRUE(trie.Init());
1070
1071 // Inserts all the test words before the last one.
1072 uint32_t value = 0;
1073 for (size_t i = 0; i < kCommonEnglishWordArrayLen - 1; ++i) {
1074 ASSERT_TRUE(trie.Insert(kCommonEnglishWords[i].data(), &value));
1075 }
1076
1077 // Fails to insert the last word because no enough space for more suffixes.
1078 EXPECT_FALSE(trie.Insert(
1079 kCommonEnglishWords[kCommonEnglishWordArrayLen - 1].data(), &value));
1080 }
1081 }
1082
TEST_F(IcingDynamicTrieTest,SyncErrorRecovery)1083 TEST_F(IcingDynamicTrieTest, SyncErrorRecovery) {
1084 IcingFilesystem filesystem;
1085 IcingDynamicTrie trie(trie_files_prefix_, IcingDynamicTrie::RuntimeOptions(),
1086 &filesystem);
1087 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
1088 ASSERT_TRUE(trie.Init());
1089
1090 static const uint32_t kNumKeys = 5000;
1091 AddToTrie(&trie, kNumKeys);
1092 CheckTrie(trie, kNumKeys);
1093
1094 trie.Sync();
1095 trie.Close();
1096
1097 // Reach into the file and set the value_size.
1098 ASSERT_TRUE(trie.Init());
1099 IcingDynamicTrieHeader hdr;
1100 trie.GetHeader(&hdr);
1101 hdr.set_value_size(hdr.value_size() + 123);
1102 trie.SetHeader(hdr);
1103 trie.Close();
1104
1105 ASSERT_FALSE(trie.Init());
1106 }
1107
TEST_F(IcingDynamicTrieTest,BitmapsClosedWhenInitFails)1108 TEST_F(IcingDynamicTrieTest, BitmapsClosedWhenInitFails) {
1109 // Create trie with one property.
1110 IcingFilesystem filesystem;
1111 IcingDynamicTrie trie(
1112 trie_files_prefix_,
1113 IcingDynamicTrie::RuntimeOptions().set_storage_policy(
1114 IcingDynamicTrie::RuntimeOptions::kMapSharedWithCrc),
1115 &filesystem);
1116 ASSERT_TRUE(trie.CreateIfNotExist(IcingDynamicTrie::Options()));
1117 ASSERT_TRUE(trie.Init());
1118 ASSERT_TRUE(trie.deleted_bitmap_);
1119 trie.SetProperty(0, 0);
1120 ASSERT_EQ(1, trie.property_bitmaps_.size());
1121 ASSERT_TRUE(trie.property_bitmaps_[0]);
1122 trie.Close();
1123
1124 // Intentionally corrupt deleted_bitmap file to make Init() fail.
1125 FILE* fp = fopen(trie.deleted_bitmap_filename_.c_str(), "r+");
1126 ASSERT_TRUE(fp);
1127 ASSERT_EQ(16, fwrite("################", 1, 16, fp));
1128 fclose(fp);
1129 ASSERT_FALSE(trie.Init());
1130
1131 // Check that both the bitmap and the property files have been closed.
1132 ASSERT_FALSE(trie.deleted_bitmap_);
1133 ASSERT_EQ(0, trie.property_bitmaps_.size());
1134 }
1135
1136 } // namespace lib
1137 } // namespace icing
1138