OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_ | 5 #ifndef BASE_LOOKUP_STRING_IN_FIXED_SET_H_ |
6 #define NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_ | 6 #define BASE_LOOKUP_STRING_IN_FIXED_SET_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 | 9 |
10 #include "net/base/net_export.h" | 10 #include "base/base_export.h" |
11 | 11 |
12 namespace net { | 12 namespace base { |
13 | 13 |
14 enum { | 14 enum { |
15 kDafsaNotFound = -1, // key is not in set | 15 kDafsaNotFound = -1, // key is not in set |
16 kDafsaFound = 0, // key is in set | 16 kDafsaFound = 0, // key is in set |
17 // The following return values are used by the implementation of | 17 // The following return values are used by the implementation of |
18 // GetDomainAndRegistry() and are probably not generally useful. | 18 // GetDomainAndRegistry() and are probably not generally useful. |
19 kDafsaExceptionRule = 1, // key excluded from set via exception | 19 kDafsaExceptionRule = 1, // key excluded from set via exception |
20 kDafsaWildcardRule = 2, // key matched a wildcard rule | 20 kDafsaWildcardRule = 2, // key matched a wildcard rule |
21 kDafsaPrivateRule = 4, // key matched a private rule | 21 kDafsaPrivateRule = 4, // key matched a private rule |
22 }; | 22 }; |
23 | 23 |
24 // Looks up the string |key| with length |key_length| in a fixed set of | 24 // Looks up the string |key| with length |key_length| in a fixed set of |
25 // strings. The set of strings must be known at compile time. It is converted to | 25 // strings. The set of strings must be known at compile time. It is converted to |
26 // a graph structure named a DAFSA (Deterministic Acyclic Finite State | 26 // a graph structure named a DAFSA (Deterministic Acyclic Finite State |
27 // Automaton) by the script make_dafsa.py during compilation. This permits | 27 // Automaton) by the script make_dafsa.py during compilation. This permits |
28 // efficient (in time and space) lookup. The graph generated by make_dafsa.py | 28 // efficient (in time and space) lookup. The graph generated by make_dafsa.py |
29 // takes the form of a constant byte array which should be supplied via the | 29 // takes the form of a constant byte array which should be supplied via the |
30 // |graph| and |length| parameters. The return value is kDafsaNotFound, | 30 // |graph| and |length| parameters. The return value is kDafsaNotFound, |
31 // kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule, | 31 // kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule, |
32 // kDafsaWildcardRule and kDafsaPrivateRule ORed together. | 32 // kDafsaWildcardRule and kDafsaPrivateRule ORed together. |
33 // | 33 // |
34 // TODO(nick): Replace this with FixedSetIncrementalLookup everywhere. | 34 // TODO(nick): Replace this with FixedSetIncrementalLookup everywhere. |
35 NET_EXPORT int LookupStringInFixedSet(const unsigned char* graph, | 35 BASE_EXPORT int LookupStringInFixedSet(const unsigned char* graph, |
36 size_t length, | 36 size_t length, |
37 const char* key, | 37 const char* key, |
38 size_t key_length); | 38 size_t key_length); |
39 | 39 |
40 // FixedSetIncrementalLookup provides efficient membership and prefix queries | 40 // FixedSetIncrementalLookup provides efficient membership and prefix queries |
41 // against a fixed set of strings. The set of strings must be known at compile | 41 // against a fixed set of strings. The set of strings must be known at compile |
42 // time. The set is converted to a graph structure named a DAFSA (Deterministic | 42 // time. The set is converted to a graph structure named a DAFSA (Deterministic |
43 // Acyclic Finite State Automaton) by the script //net/tools/dafsa/make_dafsa.py | 43 // Acyclic Finite State Automaton) by the script //net/tools/dafsa/make_dafsa.py |
44 // during compilation. The conversion generates a C++ header file defining the | 44 // during compilation. The conversion generates a C++ header file defining the |
45 // encoded graph as a constant byte array. This class provides a fast, constant- | 45 // encoded graph as a constant byte array. This class provides a fast, constant- |
(...skipping 23 matching lines...) Expand all Loading... |
69 // FixedSetIncrementalLookup prefix_lookup(kDafsa, sizeof(kDafsa)); | 69 // FixedSetIncrementalLookup prefix_lookup(kDafsa, sizeof(kDafsa)); |
70 // size_t longest_match_end = 0; | 70 // size_t longest_match_end = 0; |
71 // for (size_t i = 0; i < input.length(); ++i) { | 71 // for (size_t i = 0; i < input.length(); ++i) { |
72 // if (!prefix_lookup.Advance(input[i])) | 72 // if (!prefix_lookup.Advance(input[i])) |
73 // break; | 73 // break; |
74 // if (prefix_lookup.GetResultForCurrentSequence() == 3) | 74 // if (prefix_lookup.GetResultForCurrentSequence() == 3) |
75 // longest_match_end = (i + 1); | 75 // longest_match_end = (i + 1); |
76 // } | 76 // } |
77 // return input.substr(0, longest_match_end); | 77 // return input.substr(0, longest_match_end); |
78 // | 78 // |
79 class NET_EXPORT FixedSetIncrementalLookup { | 79 class BASE_EXPORT FixedSetIncrementalLookup { |
80 public: | 80 public: |
81 // Begin a lookup against the provided fixed set. |graph| and |length| | 81 // Begin a lookup against the provided fixed set. |graph| and |length| |
82 // describe a byte buffer generated by the make_dafsa.py script, as described | 82 // describe a byte buffer generated by the make_dafsa.py script, as described |
83 // in the class comment. | 83 // in the class comment. |
84 // | 84 // |
85 // FixedSetIncrementalLookup is initialized to a state corresponding to the | 85 // FixedSetIncrementalLookup is initialized to a state corresponding to the |
86 // empty input sequence. Calling GetResultForCurrentSequence() in the initial | 86 // empty input sequence. Calling GetResultForCurrentSequence() in the initial |
87 // state would indicate whether the empty string appears in the fixed set. | 87 // state would indicate whether the empty string appears in the fixed set. |
88 // Characters can be added to the sequence by calling Advance(), and the | 88 // Characters can be added to the sequence by calling Advance(), and the |
89 // lookup result can be checked after each addition by calling | 89 // lookup result can be checked after each addition by calling |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
135 // Pointer just past the end of the graph. |pos_| should never get here. This | 135 // Pointer just past the end of the graph. |pos_| should never get here. This |
136 // is used only in DCHECKs. | 136 // is used only in DCHECKs. |
137 const unsigned char* end_; | 137 const unsigned char* end_; |
138 | 138 |
139 // Contains the current decoder state. If true, |pos_| points to a label | 139 // Contains the current decoder state. If true, |pos_| points to a label |
140 // character or a return code. If false, |pos_| points to a sequence of | 140 // character or a return code. If false, |pos_| points to a sequence of |
141 // offsets that indicate the child nodes of the current state. | 141 // offsets that indicate the child nodes of the current state. |
142 bool pos_is_label_character_; | 142 bool pos_is_label_character_; |
143 }; | 143 }; |
144 | 144 |
145 } // namespace net | 145 } // namespace base |
146 | 146 |
147 #endif // NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_ | 147 #endif // BASE_LOOKUP_STRING_IN_FIXED_SET_H_ |
OLD | NEW |