| Index: net/base/lookup_string_in_fixed_set.h
|
| diff --git a/net/base/lookup_string_in_fixed_set.h b/net/base/lookup_string_in_fixed_set.h
|
| deleted file mode 100644
|
| index 3da3856951933dfddbe172426bbcb94cc563d2e5..0000000000000000000000000000000000000000
|
| --- a/net/base/lookup_string_in_fixed_set.h
|
| +++ /dev/null
|
| @@ -1,147 +0,0 @@
|
| -// Copyright 2015 The Chromium Authors. All rights reserved.
|
| -// Use of this source code is governed by a BSD-style license that can be
|
| -// found in the LICENSE file.
|
| -
|
| -#ifndef NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
|
| -#define NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
|
| -
|
| -#include <stddef.h>
|
| -
|
| -#include "net/base/net_export.h"
|
| -
|
| -namespace net {
|
| -
|
| -enum {
|
| - kDafsaNotFound = -1, // key is not in set
|
| - kDafsaFound = 0, // key is in set
|
| - // The following return values are used by the implementation of
|
| - // GetDomainAndRegistry() and are probably not generally useful.
|
| - kDafsaExceptionRule = 1, // key excluded from set via exception
|
| - kDafsaWildcardRule = 2, // key matched a wildcard rule
|
| - kDafsaPrivateRule = 4, // key matched a private rule
|
| -};
|
| -
|
| -// Looks up the string |key| with length |key_length| in a fixed set of
|
| -// strings. The set of strings must be known at compile time. It is converted to
|
| -// a graph structure named a DAFSA (Deterministic Acyclic Finite State
|
| -// Automaton) by the script make_dafsa.py during compilation. This permits
|
| -// efficient (in time and space) lookup. The graph generated by make_dafsa.py
|
| -// takes the form of a constant byte array which should be supplied via the
|
| -// |graph| and |length| parameters. The return value is kDafsaNotFound,
|
| -// kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule,
|
| -// kDafsaWildcardRule and kDafsaPrivateRule ORed together.
|
| -//
|
| -// TODO(nick): Replace this with FixedSetIncrementalLookup everywhere.
|
| -NET_EXPORT int LookupStringInFixedSet(const unsigned char* graph,
|
| - size_t length,
|
| - const char* key,
|
| - size_t key_length);
|
| -
|
| -// FixedSetIncrementalLookup provides efficient membership and prefix queries
|
| -// against a fixed set of strings. The set of strings must be known at compile
|
| -// time. The set is converted to a graph structure named a DAFSA (Deterministic
|
| -// Acyclic Finite State Automaton) by the script //net/tools/dafsa/make_dafsa.py
|
| -// during compilation. The conversion generates a C++ header file defining the
|
| -// encoded graph as a constant byte array. This class provides a fast, constant-
|
| -// space lookup operation against such byte arrays.
|
| -//
|
| -// The lookup proceeds incrementally, with input characters provided one at a
|
| -// time. This approach allow queries of the form: "given an input string, which
|
| -// prefixes of that string that appear in the fixed set?" As the matching
|
| -// prefixes (and their result codes) are enumerated, the most suitable match
|
| -// among them can be selected in a single pass.
|
| -//
|
| -// This class can also be used to perform suffix queries (instead of prefix
|
| -// queries) against a fixed set, so long as the DAFSA is constructed on reversed
|
| -// values, and the input is provided in reverse order.
|
| -//
|
| -// Example usage for simple membership query; |input| is a std::string:
|
| -//
|
| -// FixedSetIncrementalLookup lookup(kDafsa, sizeof(kDafsa));
|
| -// for (char c : input) {
|
| -// if (!lookup.Advance(c))
|
| -// return false;
|
| -// }
|
| -// return lookup.GetResultForCurrentSequence() != kDafsaNotFound;
|
| -//
|
| -// Example usage for 'find longest prefix in set with result code == 3' query:
|
| -//
|
| -// FixedSetIncrementalLookup prefix_lookup(kDafsa, sizeof(kDafsa));
|
| -// size_t longest_match_end = 0;
|
| -// for (size_t i = 0; i < input.length(); ++i) {
|
| -// if (!prefix_lookup.Advance(input[i]))
|
| -// break;
|
| -// if (prefix_lookup.GetResultForCurrentSequence() == 3)
|
| -// longest_match_end = (i + 1);
|
| -// }
|
| -// return input.substr(0, longest_match_end);
|
| -//
|
| -class NET_EXPORT FixedSetIncrementalLookup {
|
| - public:
|
| - // Begin a lookup against the provided fixed set. |graph| and |length|
|
| - // describe a byte buffer generated by the make_dafsa.py script, as described
|
| - // in the class comment.
|
| - //
|
| - // FixedSetIncrementalLookup is initialized to a state corresponding to the
|
| - // empty input sequence. Calling GetResultForCurrentSequence() in the initial
|
| - // state would indicate whether the empty string appears in the fixed set.
|
| - // Characters can be added to the sequence by calling Advance(), and the
|
| - // lookup result can be checked after each addition by calling
|
| - // GetResultForCurrentSequence().
|
| - FixedSetIncrementalLookup(const unsigned char* graph, size_t length);
|
| -
|
| - // FixedSetIncrementalLookup is copyable so that callers can save/restore
|
| - // their position in the search. This is for cases where branching or
|
| - // backtracking might be required (e.g. to probe for the presence of a
|
| - // designated wildcard character).
|
| - FixedSetIncrementalLookup(const FixedSetIncrementalLookup&);
|
| - FixedSetIncrementalLookup& operator=(const FixedSetIncrementalLookup&);
|
| -
|
| - ~FixedSetIncrementalLookup();
|
| -
|
| - // Advance the query by adding a character to the input sequence. |input| can
|
| - // be any char value, but only ASCII characters will ever result in matches,
|
| - // since the fixed set itself is limited to ASCII strings.
|
| - //
|
| - // Returns true if the resulting input sequence either appears in the fixed
|
| - // set itself, or is a prefix of some longer string in the fixed set. Returns
|
| - // false otherwise, implying that the graph is exhausted and
|
| - // GetResultForCurrentSequence() will return kDafsaNotFound.
|
| - //
|
| - // Once Advance() has returned false, the caller can safely stop feeding more
|
| - // characters, as subsequent calls to Advance() will return false and have no
|
| - // effect.
|
| - bool Advance(char input);
|
| -
|
| - // Returns the result code corresponding to the input sequence provided thus
|
| - // far to Advance().
|
| - //
|
| - // If the sequence does not appear in the fixed set, the return value is
|
| - // kDafsaNotFound. Otherwise, the value is a non-negative integer (currently
|
| - // limited to 0-7) corresponding to the result code for that string, as listed
|
| - // in the .gperf file from which the DAFSA was generated. For
|
| - // GetDomainAndRegistry DAFSAs, these values should be interpreted as a
|
| - // bitmask of kDafsaExceptionRule, kDafsaWildcardRule, and kDafsaPrivateRule.
|
| - //
|
| - // It is okay to call this function, and then extend the sequence further by
|
| - // calling Advance().
|
| - int GetResultForCurrentSequence() const;
|
| -
|
| - private:
|
| - // Pointer to the current position in the graph indicating the current state
|
| - // of the automaton, or nullptr if the graph is exhausted.
|
| - const unsigned char* pos_;
|
| -
|
| - // Pointer just past the end of the graph. |pos_| should never get here. This
|
| - // is used only in DCHECKs.
|
| - const unsigned char* end_;
|
| -
|
| - // Contains the current decoder state. If true, |pos_| points to a label
|
| - // character or a return code. If false, |pos_| points to a sequence of
|
| - // offsets that indicate the child nodes of the current state.
|
| - bool pos_is_label_character_;
|
| -};
|
| -
|
| -} // namespace net
|
| -
|
| -#endif // NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
|
|
|