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/index/hit/hit.h"
16
17 #include "icing/store/document-id.h"
18 #include "icing/util/bit-util.h"
19
20 namespace icing {
21 namespace lib {
22
23 namespace {
24
25 enum FlagOffset {
26 // This hit, whether exact or not, came from a prefixed section and will
27 // need to be backfilled into branching posting lists if/when those are
28 // created.
29 kInPrefixSection = 0,
30 // This hit represents a prefix of a longer term. If exact matches are
31 // required, then this hit should be ignored.
32 kPrefixHit = 1,
33 // Whether or not the hit has a term_frequency other than
34 // kDefaultTermFrequency.
35 kHasTermFrequency = 2,
36 kNumFlags = 3,
37 };
38 static_assert(kDocumentIdBits + kSectionIdBits + kNumFlags <=
39 sizeof(Hit::Value) * 8,
40 "HitOverflow");
41
InvertDocumentId(DocumentId document_id)42 inline DocumentId InvertDocumentId(DocumentId document_id) {
43 static_assert(kMaxDocumentId <= (std::numeric_limits<DocumentId>::max() - 1),
44 "(kMaxDocumentId + 1) must not overflow.");
45 static_assert(
46 (kMaxDocumentId + 1) < (1U << kDocumentIdBits),
47 "(kMaxDocumentId + 1) must also fit in kDocumentIdBits wide bitfield");
48 // Invert the document_id value. +1 is added so the resulting range is [1,
49 // kMaxDocumentId + 1].
50 return (kMaxDocumentId + 1) - document_id;
51 }
52
53 } // namespace
54
Hit(SectionId section_id,DocumentId document_id,Hit::TermFrequency term_frequency,bool is_in_prefix_section,bool is_prefix_hit)55 Hit::Hit(SectionId section_id, DocumentId document_id,
56 Hit::TermFrequency term_frequency, bool is_in_prefix_section,
57 bool is_prefix_hit)
58 : term_frequency_(term_frequency) {
59 // Values are stored so that when sorted, they appear in document_id
60 // descending, section_id ascending, order. Also, all else being
61 // equal, non-prefix hits sort before prefix hits. So inverted
62 // document_id appears in the most significant bits, followed by
63 // (uninverted) section_id.
64 Value temp_value = 0;
65 bit_util::BitfieldSet(InvertDocumentId(document_id),
66 kSectionIdBits + kNumFlags, kDocumentIdBits,
67 &temp_value);
68 bit_util::BitfieldSet(section_id, kNumFlags, kSectionIdBits, &temp_value);
69 bit_util::BitfieldSet(term_frequency != kDefaultTermFrequency,
70 kHasTermFrequency, /*len=*/1, &temp_value);
71 bit_util::BitfieldSet(is_prefix_hit, kPrefixHit, /*len=*/1, &temp_value);
72 bit_util::BitfieldSet(is_in_prefix_section, kInPrefixSection,
73 /*len=*/1, &temp_value);
74 value_ = temp_value;
75 }
76
document_id() const77 DocumentId Hit::document_id() const {
78 DocumentId inverted_document_id = bit_util::BitfieldGet(
79 value(), kSectionIdBits + kNumFlags, kDocumentIdBits);
80 // Undo the document_id inversion.
81 return InvertDocumentId(inverted_document_id);
82 }
83
section_id() const84 SectionId Hit::section_id() const {
85 return bit_util::BitfieldGet(value(), kNumFlags, kSectionIdBits);
86 }
87
has_term_frequency() const88 bool Hit::has_term_frequency() const {
89 return bit_util::BitfieldGet(value(), kHasTermFrequency, 1);
90 }
91
is_prefix_hit() const92 bool Hit::is_prefix_hit() const {
93 return bit_util::BitfieldGet(value(), kPrefixHit, 1);
94 }
95
is_in_prefix_section() const96 bool Hit::is_in_prefix_section() const {
97 return bit_util::BitfieldGet(value(), kInPrefixSection, 1);
98 }
99
operator ()(const Hit & hit1,const Hit & hit2) const100 bool Hit::EqualsDocumentIdAndSectionId::operator()(const Hit& hit1,
101 const Hit& hit2) const {
102 return (hit1.value() >> kNumFlags) == (hit2.value() >> kNumFlags);
103 }
104
105 } // namespace lib
106 } // namespace icing
107