| 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 |