1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "utils/container/double-array-trie.h"
18
19 #include "utils/base/logging.h"
20
21 namespace libtextclassifier3 {
22
GatherPrefixMatches(StringPiece input,const std::function<void (Match)> & update_fn) const23 bool DoubleArrayTrie::GatherPrefixMatches(
24 StringPiece input, const std::function<void(Match)>& update_fn) const {
25 uint32 pos = 0;
26 if (nodes_length_ == 0) {
27 TC3_LOG(WARNING) << "Trie is empty. Skipping.";
28 return true;
29 }
30 pos = offset(0);
31 for (int i = 0; i < input.size(); i++) {
32 if (input[i] == 0) {
33 break;
34 }
35 pos ^= static_cast<unsigned char>(input[i]);
36 // We exhausted the trie, no more matches possible.
37 if (pos < 0 || pos >= nodes_length_) {
38 break;
39 }
40 if (label(pos) != input[i]) {
41 break;
42 }
43 const bool node_has_leaf = has_leaf(pos);
44 pos ^= offset(pos);
45 if (pos < 0 || pos > nodes_length_) {
46 TC3_LOG(ERROR) << "Out-of-bounds trie search position.";
47 return false;
48 }
49 if (node_has_leaf) {
50 update_fn(Match(/*id=*/value(pos), /*match_length=*/i + 1));
51 }
52 }
53 return true;
54 }
55
FindAllPrefixMatches(StringPiece input,std::vector<Match> * matches) const56 bool DoubleArrayTrie::FindAllPrefixMatches(StringPiece input,
57 std::vector<Match>* matches) const {
58 return GatherPrefixMatches(
59 input, [matches](const Match match) { matches->push_back(match); });
60 }
61
LongestPrefixMatch(StringPiece input,Match * longest_match) const62 bool DoubleArrayTrie::LongestPrefixMatch(StringPiece input,
63 Match* longest_match) const {
64 *longest_match = Match();
65 return GatherPrefixMatches(
66 input, [longest_match](const Match match) { *longest_match = match; });
67 }
68
69 } // namespace libtextclassifier3
70