1 // Copyright (C) 2022 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/index/numeric/posting-list-integer-index-accessor.h"
16
17 #include <cstdint>
18 #include <memory>
19 #include <string>
20 #include <utility>
21 #include <vector>
22
23 #include "icing/text_classifier/lib3/utils/base/status.h"
24 #include "gmock/gmock.h"
25 #include "gtest/gtest.h"
26 #include "icing/file/filesystem.h"
27 #include "icing/file/posting_list/flash-index-storage.h"
28 #include "icing/file/posting_list/posting-list-common.h"
29 #include "icing/file/posting_list/posting-list-identifier.h"
30 #include "icing/index/numeric/integer-index-data.h"
31 #include "icing/index/numeric/posting-list-integer-index-serializer.h"
32 #include "icing/schema/section.h"
33 #include "icing/store/document-id.h"
34 #include "icing/testing/common-matchers.h"
35 #include "icing/testing/tmp-directory.h"
36
37 namespace icing {
38 namespace lib {
39
40 namespace {
41
42 using ::testing::ElementsAre;
43 using ::testing::ElementsAreArray;
44 using ::testing::Eq;
45 using ::testing::Lt;
46 using ::testing::Ne;
47 using ::testing::SizeIs;
48
49 class PostingListIntegerIndexAccessorTest : public ::testing::Test {
50 protected:
SetUp()51 void SetUp() override {
52 test_dir_ = GetTestTempDir() + "/test_dir";
53 file_name_ = test_dir_ + "/test_file.idx.index";
54
55 ASSERT_TRUE(filesystem_.DeleteDirectoryRecursively(test_dir_.c_str()));
56 ASSERT_TRUE(filesystem_.CreateDirectoryRecursively(test_dir_.c_str()));
57
58 serializer_ = std::make_unique<PostingListIntegerIndexSerializer>();
59
60 ICING_ASSERT_OK_AND_ASSIGN(
61 FlashIndexStorage flash_index_storage,
62 FlashIndexStorage::Create(file_name_, &filesystem_, serializer_.get()));
63 flash_index_storage_ =
64 std::make_unique<FlashIndexStorage>(std::move(flash_index_storage));
65 }
66
TearDown()67 void TearDown() override {
68 flash_index_storage_.reset();
69 serializer_.reset();
70 ASSERT_TRUE(filesystem_.DeleteDirectoryRecursively(test_dir_.c_str()));
71 }
72
73 Filesystem filesystem_;
74 std::string test_dir_;
75 std::string file_name_;
76 std::unique_ptr<PostingListIntegerIndexSerializer> serializer_;
77 std::unique_ptr<FlashIndexStorage> flash_index_storage_;
78 };
79
CreateData(int num_data,DocumentId start_document_id,int64_t start_key)80 std::vector<IntegerIndexData> CreateData(int num_data,
81 DocumentId start_document_id,
82 int64_t start_key) {
83 SectionId section_id = kMaxSectionId;
84
85 std::vector<IntegerIndexData> data;
86 data.reserve(num_data);
87 for (int i = 0; i < num_data; ++i) {
88 data.push_back(IntegerIndexData(section_id, start_document_id, start_key));
89
90 if (section_id == kMinSectionId) {
91 section_id = kMaxSectionId;
92 } else {
93 --section_id;
94 }
95 ++start_document_id;
96 ++start_key;
97 }
98 return data;
99 }
100
TEST_F(PostingListIntegerIndexAccessorTest,DataAddAndRetrieveProperly)101 TEST_F(PostingListIntegerIndexAccessorTest, DataAddAndRetrieveProperly) {
102 ICING_ASSERT_OK_AND_ASSIGN(
103 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
104 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
105 serializer_.get()));
106 // Add some integer index data
107 std::vector<IntegerIndexData> data_vec =
108 CreateData(/*num_data=*/5, /*start_document_id=*/0, /*start_key=*/819);
109 for (const IntegerIndexData& data : data_vec) {
110 EXPECT_THAT(pl_accessor->PrependData(data), IsOk());
111 }
112 PostingListAccessor::FinalizeResult result =
113 std::move(*pl_accessor).Finalize();
114 EXPECT_THAT(result.status, IsOk());
115 EXPECT_THAT(result.id.block_index(), Eq(1));
116 EXPECT_THAT(result.id.posting_list_index(), Eq(0));
117
118 // Retrieve some data.
119 ICING_ASSERT_OK_AND_ASSIGN(PostingListHolder pl_holder,
120 flash_index_storage_->GetPostingList(result.id));
121 EXPECT_THAT(
122 serializer_->GetData(&pl_holder.posting_list),
123 IsOkAndHolds(ElementsAreArray(data_vec.rbegin(), data_vec.rend())));
124 EXPECT_THAT(pl_holder.next_block_index, Eq(kInvalidBlockIndex));
125 }
126
TEST_F(PostingListIntegerIndexAccessorTest,PreexistingPLKeepOnSameBlock)127 TEST_F(PostingListIntegerIndexAccessorTest, PreexistingPLKeepOnSameBlock) {
128 ICING_ASSERT_OK_AND_ASSIGN(
129 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
130 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
131 serializer_.get()));
132 // Add a single data. This will fit in a min-sized posting list.
133 IntegerIndexData data1(/*section_id=*/1, /*document_id=*/0, /*key=*/12345);
134 ICING_ASSERT_OK(pl_accessor->PrependData(data1));
135 PostingListAccessor::FinalizeResult result1 =
136 std::move(*pl_accessor).Finalize();
137 ICING_ASSERT_OK(result1.status);
138 // Should be allocated to the first block.
139 ASSERT_THAT(result1.id.block_index(), Eq(1));
140 ASSERT_THAT(result1.id.posting_list_index(), Eq(0));
141
142 // Add one more data. The minimum size for a posting list must be able to fit
143 // two data, so this should NOT cause the previous pl to be reallocated.
144 ICING_ASSERT_OK_AND_ASSIGN(
145 pl_accessor,
146 PostingListIntegerIndexAccessor::CreateFromExisting(
147 flash_index_storage_.get(), serializer_.get(), result1.id));
148 IntegerIndexData data2(/*section_id=*/1, /*document_id=*/1, /*key=*/23456);
149 ICING_ASSERT_OK(pl_accessor->PrependData(data2));
150 PostingListAccessor::FinalizeResult result2 =
151 std::move(*pl_accessor).Finalize();
152 ICING_ASSERT_OK(result2.status);
153 // Should be in the same posting list.
154 EXPECT_THAT(result2.id, Eq(result1.id));
155
156 // The posting list at result2.id should hold all of the data that have been
157 // added.
158 ICING_ASSERT_OK_AND_ASSIGN(PostingListHolder pl_holder,
159 flash_index_storage_->GetPostingList(result2.id));
160 EXPECT_THAT(serializer_->GetData(&pl_holder.posting_list),
161 IsOkAndHolds(ElementsAre(data2, data1)));
162 }
163
TEST_F(PostingListIntegerIndexAccessorTest,PreexistingPLReallocateToLargerPL)164 TEST_F(PostingListIntegerIndexAccessorTest, PreexistingPLReallocateToLargerPL) {
165 ICING_ASSERT_OK_AND_ASSIGN(
166 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
167 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
168 serializer_.get()));
169 // Adding 3 data should cause Finalize allocating a 48-byte posting list,
170 // which can store at most 4 data.
171 std::vector<IntegerIndexData> data_vec1 =
172 CreateData(/*num_data=*/3, /*start_document_id=*/0, /*start_key=*/819);
173 for (const IntegerIndexData& data : data_vec1) {
174 ICING_ASSERT_OK(pl_accessor->PrependData(data));
175 }
176 PostingListAccessor::FinalizeResult result1 =
177 std::move(*pl_accessor).Finalize();
178 ICING_ASSERT_OK(result1.status);
179 // Should be allocated to the first block.
180 ASSERT_THAT(result1.id.block_index(), Eq(1));
181 ASSERT_THAT(result1.id.posting_list_index(), Eq(0));
182
183 // Now add more data.
184 ICING_ASSERT_OK_AND_ASSIGN(
185 pl_accessor,
186 PostingListIntegerIndexAccessor::CreateFromExisting(
187 flash_index_storage_.get(), serializer_.get(), result1.id));
188 // The current posting list can fit 1 more data. Adding 12 more data should
189 // result in these data being moved to a larger posting list. Also the total
190 // size of these data won't exceed max size posting list, so there will be
191 // only one single posting list and no chain.
192 std::vector<IntegerIndexData> data_vec2 = CreateData(
193 /*num_data=*/12,
194 /*start_document_id=*/data_vec1.back().basic_hit().document_id() + 1,
195 /*start_key=*/819);
196
197 for (const IntegerIndexData& data : data_vec2) {
198 ICING_ASSERT_OK(pl_accessor->PrependData(data));
199 }
200 PostingListAccessor::FinalizeResult result2 =
201 std::move(*pl_accessor).Finalize();
202 ICING_ASSERT_OK(result2.status);
203 // Should be allocated to the second (new) block because the posting list
204 // should grow beyond the size that the first block maintains.
205 EXPECT_THAT(result2.id.block_index(), Eq(2));
206 EXPECT_THAT(result2.id.posting_list_index(), Eq(0));
207
208 // The posting list at result2.id should hold all of the data that have been
209 // added.
210 std::vector<IntegerIndexData> all_data_vec;
211 all_data_vec.reserve(data_vec1.size() + data_vec2.size());
212 all_data_vec.insert(all_data_vec.end(), data_vec1.begin(), data_vec1.end());
213 all_data_vec.insert(all_data_vec.end(), data_vec2.begin(), data_vec2.end());
214 ICING_ASSERT_OK_AND_ASSIGN(PostingListHolder pl_holder,
215 flash_index_storage_->GetPostingList(result2.id));
216 EXPECT_THAT(serializer_->GetData(&pl_holder.posting_list),
217 IsOkAndHolds(ElementsAreArray(all_data_vec.rbegin(),
218 all_data_vec.rend())));
219 }
220
TEST_F(PostingListIntegerIndexAccessorTest,MultiBlockChainsBlocksProperly)221 TEST_F(PostingListIntegerIndexAccessorTest, MultiBlockChainsBlocksProperly) {
222 ICING_ASSERT_OK_AND_ASSIGN(
223 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
224 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
225 serializer_.get()));
226 // Block size is 4096, sizeof(BlockHeader) is 12 and sizeof(IntegerIndexData)
227 // is 12, so the max size posting list can store (4096 - 12) / 12 = 340 data.
228 // Adding 341 data should cause:
229 // - 2 max size posting lists being allocated to block 1 and block 2.
230 // - Chaining: block 2 -> block 1
231 std::vector<IntegerIndexData> data_vec =
232 CreateData(/*num_data=*/341, /*start_document_id=*/0, /*start_key=*/819);
233 for (const IntegerIndexData& data : data_vec) {
234 ICING_ASSERT_OK(pl_accessor->PrependData(data));
235 }
236 PostingListAccessor::FinalizeResult result1 =
237 std::move(*pl_accessor).Finalize();
238 ICING_ASSERT_OK(result1.status);
239 PostingListIdentifier second_block_id = result1.id;
240 // Should be allocated to the second block.
241 EXPECT_THAT(second_block_id, Eq(PostingListIdentifier(
242 /*block_index=*/2, /*posting_list_index=*/0,
243 /*posting_list_index_bits=*/0)));
244
245 // We should be able to retrieve all data.
246 ICING_ASSERT_OK_AND_ASSIGN(
247 PostingListHolder pl_holder,
248 flash_index_storage_->GetPostingList(second_block_id));
249 // This pl_holder will only hold a posting list with the data that didn't fit
250 // on the first block.
251 ICING_ASSERT_OK_AND_ASSIGN(std::vector<IntegerIndexData> second_block_data,
252 serializer_->GetData(&pl_holder.posting_list));
253 ASSERT_THAT(second_block_data, SizeIs(Lt(data_vec.size())));
254 auto first_block_data_start = data_vec.rbegin() + second_block_data.size();
255 EXPECT_THAT(second_block_data,
256 ElementsAreArray(data_vec.rbegin(), first_block_data_start));
257
258 // Now retrieve all of the data that were on the first block.
259 uint32_t first_block_id = pl_holder.next_block_index;
260 EXPECT_THAT(first_block_id, Eq(1));
261
262 PostingListIdentifier pl_id(first_block_id, /*posting_list_index=*/0,
263 /*posting_list_index_bits=*/0);
264 ICING_ASSERT_OK_AND_ASSIGN(pl_holder,
265 flash_index_storage_->GetPostingList(pl_id));
266 EXPECT_THAT(
267 serializer_->GetData(&pl_holder.posting_list),
268 IsOkAndHolds(ElementsAreArray(first_block_data_start, data_vec.rend())));
269 }
270
TEST_F(PostingListIntegerIndexAccessorTest,PreexistingMultiBlockReusesBlocksProperly)271 TEST_F(PostingListIntegerIndexAccessorTest,
272 PreexistingMultiBlockReusesBlocksProperly) {
273 ICING_ASSERT_OK_AND_ASSIGN(
274 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
275 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
276 serializer_.get()));
277 // Block size is 4096, sizeof(BlockHeader) is 12 and sizeof(IntegerIndexData)
278 // is 12, so the max size posting list can store (4096 - 12) / 12 = 340 data.
279 // Adding 341 data will cause:
280 // - 2 max size posting lists being allocated to block 1 and block 2.
281 // - Chaining: block 2 -> block 1
282 std::vector<IntegerIndexData> data_vec1 =
283 CreateData(/*num_data=*/341, /*start_document_id=*/0, /*start_key=*/819);
284 for (const IntegerIndexData& data : data_vec1) {
285 ICING_ASSERT_OK(pl_accessor->PrependData(data));
286 }
287 PostingListAccessor::FinalizeResult result1 =
288 std::move(*pl_accessor).Finalize();
289 ICING_ASSERT_OK(result1.status);
290 PostingListIdentifier first_add_id = result1.id;
291 EXPECT_THAT(first_add_id, Eq(PostingListIdentifier(
292 /*block_index=*/2, /*posting_list_index=*/0,
293 /*posting_list_index_bits=*/0)));
294
295 // Now add more data. These should fit on the existing second block and not
296 // fill it up.
297 ICING_ASSERT_OK_AND_ASSIGN(
298 pl_accessor,
299 PostingListIntegerIndexAccessor::CreateFromExisting(
300 flash_index_storage_.get(), serializer_.get(), first_add_id));
301 std::vector<IntegerIndexData> data_vec2 = CreateData(
302 /*num_data=*/10,
303 /*start_document_id=*/data_vec1.back().basic_hit().document_id() + 1,
304 /*start_key=*/819);
305 for (const IntegerIndexData& data : data_vec2) {
306 ICING_ASSERT_OK(pl_accessor->PrependData(data));
307 }
308 PostingListAccessor::FinalizeResult result2 =
309 std::move(*pl_accessor).Finalize();
310 ICING_ASSERT_OK(result2.status);
311 PostingListIdentifier second_add_id = result2.id;
312 EXPECT_THAT(second_add_id, Eq(first_add_id));
313
314 // We should be able to retrieve all data.
315 std::vector<IntegerIndexData> all_data_vec;
316 all_data_vec.reserve(data_vec1.size() + data_vec2.size());
317 all_data_vec.insert(all_data_vec.end(), data_vec1.begin(), data_vec1.end());
318 all_data_vec.insert(all_data_vec.end(), data_vec2.begin(), data_vec2.end());
319 ICING_ASSERT_OK_AND_ASSIGN(
320 PostingListHolder pl_holder,
321 flash_index_storage_->GetPostingList(second_add_id));
322 // This pl_holder will only hold a posting list with the data that didn't fit
323 // on the first block.
324 ICING_ASSERT_OK_AND_ASSIGN(std::vector<IntegerIndexData> second_block_data,
325 serializer_->GetData(&pl_holder.posting_list));
326 ASSERT_THAT(second_block_data, SizeIs(Lt(all_data_vec.size())));
327 auto first_block_data_start =
328 all_data_vec.rbegin() + second_block_data.size();
329 EXPECT_THAT(second_block_data,
330 ElementsAreArray(all_data_vec.rbegin(), first_block_data_start));
331
332 // Now retrieve all of the data that were on the first block.
333 uint32_t first_block_id = pl_holder.next_block_index;
334 EXPECT_THAT(first_block_id, Eq(1));
335
336 PostingListIdentifier pl_id(first_block_id, /*posting_list_index=*/0,
337 /*posting_list_index_bits=*/0);
338 ICING_ASSERT_OK_AND_ASSIGN(pl_holder,
339 flash_index_storage_->GetPostingList(pl_id));
340 EXPECT_THAT(serializer_->GetData(&pl_holder.posting_list),
341 IsOkAndHolds(ElementsAreArray(first_block_data_start,
342 all_data_vec.rend())));
343 }
344
TEST_F(PostingListIntegerIndexAccessorTest,InvalidDataShouldReturnInvalidArgument)345 TEST_F(PostingListIntegerIndexAccessorTest,
346 InvalidDataShouldReturnInvalidArgument) {
347 ICING_ASSERT_OK_AND_ASSIGN(
348 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
349 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
350 serializer_.get()));
351 IntegerIndexData invalid_data;
352 EXPECT_THAT(pl_accessor->PrependData(invalid_data),
353 StatusIs(libtextclassifier3::StatusCode::INVALID_ARGUMENT));
354 }
355
TEST_F(PostingListIntegerIndexAccessorTest,BasicHitIncreasingShouldReturnInvalidArgument)356 TEST_F(PostingListIntegerIndexAccessorTest,
357 BasicHitIncreasingShouldReturnInvalidArgument) {
358 ICING_ASSERT_OK_AND_ASSIGN(
359 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
360 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
361 serializer_.get()));
362 IntegerIndexData data1(/*section_id=*/3, /*document_id=*/1, /*key=*/12345);
363 ICING_ASSERT_OK(pl_accessor->PrependData(data1));
364
365 IntegerIndexData data2(/*section_id=*/6, /*document_id=*/1, /*key=*/12345);
366 EXPECT_THAT(pl_accessor->PrependData(data2),
367 StatusIs(libtextclassifier3::StatusCode::INVALID_ARGUMENT));
368
369 IntegerIndexData data3(/*section_id=*/2, /*document_id=*/0, /*key=*/12345);
370 EXPECT_THAT(pl_accessor->PrependData(data3),
371 StatusIs(libtextclassifier3::StatusCode::INVALID_ARGUMENT));
372 }
373
TEST_F(PostingListIntegerIndexAccessorTest,NewPostingListNoDataAddedShouldReturnInvalidArgument)374 TEST_F(PostingListIntegerIndexAccessorTest,
375 NewPostingListNoDataAddedShouldReturnInvalidArgument) {
376 ICING_ASSERT_OK_AND_ASSIGN(
377 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor,
378 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
379 serializer_.get()));
380 PostingListAccessor::FinalizeResult result =
381 std::move(*pl_accessor).Finalize();
382 EXPECT_THAT(result.status,
383 StatusIs(libtextclassifier3::StatusCode::INVALID_ARGUMENT));
384 }
385
TEST_F(PostingListIntegerIndexAccessorTest,PreexistingPostingListNoDataAddedShouldSucceed)386 TEST_F(PostingListIntegerIndexAccessorTest,
387 PreexistingPostingListNoDataAddedShouldSucceed) {
388 ICING_ASSERT_OK_AND_ASSIGN(
389 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor1,
390 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
391 serializer_.get()));
392 IntegerIndexData data1(/*section_id=*/3, /*document_id=*/1, /*key=*/12345);
393 ICING_ASSERT_OK(pl_accessor1->PrependData(data1));
394 PostingListAccessor::FinalizeResult result1 =
395 std::move(*pl_accessor1).Finalize();
396 ICING_ASSERT_OK(result1.status);
397
398 ICING_ASSERT_OK_AND_ASSIGN(
399 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor2,
400 PostingListIntegerIndexAccessor::CreateFromExisting(
401 flash_index_storage_.get(), serializer_.get(), result1.id));
402 PostingListAccessor::FinalizeResult result2 =
403 std::move(*pl_accessor2).Finalize();
404 EXPECT_THAT(result2.status, IsOk());
405 }
406
TEST_F(PostingListIntegerIndexAccessorTest,GetAllDataAndFree)407 TEST_F(PostingListIntegerIndexAccessorTest, GetAllDataAndFree) {
408 IntegerIndexData data1(/*section_id=*/3, /*document_id=*/1, /*key=*/123);
409 IntegerIndexData data2(/*section_id=*/3, /*document_id=*/2, /*key=*/456);
410
411 ICING_ASSERT_OK_AND_ASSIGN(
412 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor1,
413 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
414 serializer_.get()));
415 // Add 2 data.
416 ICING_ASSERT_OK(pl_accessor1->PrependData(data1));
417 ICING_ASSERT_OK(pl_accessor1->PrependData(data2));
418 PostingListAccessor::FinalizeResult result1 =
419 std::move(*pl_accessor1).Finalize();
420 ICING_ASSERT_OK(result1.status);
421
422 ICING_ASSERT_OK_AND_ASSIGN(
423 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor2,
424 PostingListIntegerIndexAccessor::CreateFromExisting(
425 flash_index_storage_.get(), serializer_.get(), result1.id));
426 EXPECT_THAT(pl_accessor2->GetAllDataAndFree(),
427 IsOkAndHolds(ElementsAre(data2, data1)));
428
429 // Allocate a new posting list with same size again.
430 ICING_ASSERT_OK_AND_ASSIGN(
431 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor3,
432 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
433 serializer_.get()));
434 // Add 2 data.
435 ICING_ASSERT_OK(pl_accessor3->PrependData(data1));
436 ICING_ASSERT_OK(pl_accessor3->PrependData(data2));
437 PostingListAccessor::FinalizeResult result3 =
438 std::move(*pl_accessor3).Finalize();
439 ICING_ASSERT_OK(result3.status);
440 // We should get the same id if the previous one has been freed correctly by
441 // GetAllDataAndFree.
442 EXPECT_THAT(result3.id, Eq(result1.id));
443 }
444
TEST_F(PostingListIntegerIndexAccessorTest,GetAllDataAndFreePostingListChain)445 TEST_F(PostingListIntegerIndexAccessorTest, GetAllDataAndFreePostingListChain) {
446 uint32_t block_size = FlashIndexStorage::SelectBlockSize();
447 uint32_t max_posting_list_bytes = IndexBlock::CalculateMaxPostingListBytes(
448 block_size, serializer_->GetDataTypeBytes());
449 uint32_t max_num_data_single_posting_list =
450 max_posting_list_bytes / serializer_->GetDataTypeBytes();
451
452 ICING_ASSERT_OK_AND_ASSIGN(
453 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor1,
454 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
455 serializer_.get()));
456
457 // Prepend max_num_data_single_posting_list + 1 data.
458 std::vector<IntegerIndexData> data_vec;
459 for (uint32_t i = 0; i < max_num_data_single_posting_list + 1; ++i) {
460 IntegerIndexData data(/*section_id=*/3, static_cast<DocumentId>(i),
461 /*key=*/i);
462 ICING_ASSERT_OK(pl_accessor1->PrependData(data));
463 data_vec.push_back(data);
464 }
465
466 // This will cause:
467 // - Allocate the first max-sized posting list at block index = 1, storing
468 // max_num_data_single_posting_list data.
469 // - Allocate the second max-sized posting list at block index = 2, storing 1
470 // data. Also its next_block_index is 1.
471 // - IOW, we will get 2 -> 1 and result1.id points to 2.
472 PostingListAccessor::FinalizeResult result1 =
473 std::move(*pl_accessor1).Finalize();
474 ICING_ASSERT_OK(result1.status);
475
476 uint32_t first_pl_block_index = kInvalidBlockIndex;
477 {
478 // result1.id points at the second (max-sized) PL, and next_block_index of
479 // the second PL points to the first PL's block. Fetch the first PL's block
480 // index manually.
481 ICING_ASSERT_OK_AND_ASSIGN(
482 PostingListHolder pl_holder,
483 flash_index_storage_->GetPostingList(result1.id));
484 first_pl_block_index = pl_holder.next_block_index;
485 }
486 ASSERT_THAT(first_pl_block_index, Ne(kInvalidBlockIndex));
487
488 // Call GetAllDataAndFree. This will free block 2 and block 1.
489 // Free block list: 1 -> 2 (since free block list is LIFO).
490 ICING_ASSERT_OK_AND_ASSIGN(
491 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor2,
492 PostingListIntegerIndexAccessor::CreateFromExisting(
493 flash_index_storage_.get(), serializer_.get(), result1.id));
494 EXPECT_THAT(
495 pl_accessor2->GetAllDataAndFree(),
496 IsOkAndHolds(ElementsAreArray(data_vec.rbegin(), data_vec.rend())));
497 pl_accessor2.reset();
498
499 // Allocate a new posting list with same size again.
500 ICING_ASSERT_OK_AND_ASSIGN(
501 std::unique_ptr<PostingListIntegerIndexAccessor> pl_accessor3,
502 PostingListIntegerIndexAccessor::Create(flash_index_storage_.get(),
503 serializer_.get()));
504 // Add same set of data.
505 for (uint32_t i = 0; i < max_num_data_single_posting_list + 1; ++i) {
506 ICING_ASSERT_OK(pl_accessor3->PrependData(data_vec[i]));
507 }
508
509 // This will cause:
510 // - Allocate the first max-sized posting list from the free block list, which
511 // is block index = 1, storing max_num_data_single_posting_list data.
512 // - Allocate the second max-sized posting list from the next block in free
513 // block list, which is block index = 2, storing 1 data. Also its
514 // next_block_index should be 1.
515 PostingListAccessor::FinalizeResult result3 =
516 std::move(*pl_accessor3).Finalize();
517 ICING_ASSERT_OK(result3.status);
518 // We should get the same id if the previous one has been freed correctly by
519 // GetAllDataAndFree.
520 EXPECT_THAT(result3.id, Eq(result1.id));
521 // Also the first PL should be the same if it has been freed correctly by
522 // GetAllDataAndFree. Since it is a max-sized posting list, we just need to
523 // verify the block index.
524 {
525 ICING_ASSERT_OK_AND_ASSIGN(
526 PostingListHolder pl_holder,
527 flash_index_storage_->GetPostingList(result3.id));
528 EXPECT_THAT(pl_holder.next_block_index, Eq(first_pl_block_index));
529 }
530 }
531
532 } // namespace
533
534 } // namespace lib
535 } // namespace icing
536