OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 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 // A read-only set implementation for |SBPrefix| items. Prefixes are | 5 // A read-only set implementation for |SBPrefix| items. Prefixes are |
6 // sorted and stored as 16-bit deltas from the previous prefix. An | 6 // sorted and stored as 16-bit deltas from the previous prefix. An |
7 // index structure provides quick random access, and also handles | 7 // index structure provides quick random access, and also handles |
8 // cases where 16 bits cannot encode a delta. | 8 // cases where 16 bits cannot encode a delta. |
9 // | 9 // |
10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would | 10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
65 | 65 |
66 // |true| if |prefix| was in |prefixes| passed to the constructor. | 66 // |true| if |prefix| was in |prefixes| passed to the constructor. |
67 bool Exists(SBPrefix prefix) const; | 67 bool Exists(SBPrefix prefix) const; |
68 | 68 |
69 // Persist the set on disk. | 69 // Persist the set on disk. |
70 static PrefixSet* LoadFile(const FilePath& filter_name); | 70 static PrefixSet* LoadFile(const FilePath& filter_name); |
71 bool WriteFile(const FilePath& filter_name) const; | 71 bool WriteFile(const FilePath& filter_name) const; |
72 | 72 |
73 // Regenerate the vector of prefixes passed to the constructor into | 73 // Regenerate the vector of prefixes passed to the constructor into |
74 // |prefixes|. Prefixes will be added in sorted order. | 74 // |prefixes|. Prefixes will be added in sorted order. |
75 void GetPrefixes(std::vector<SBPrefix>* prefixes); | 75 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; |
76 | 76 |
77 private: | 77 private: |
78 // Maximum delta that can be encoded in a 16-bit unsigned. | |
79 static const unsigned kMaxDelta = 256 * 256; | |
80 | |
81 // Maximum number of consecutive deltas to encode before generating | 78 // Maximum number of consecutive deltas to encode before generating |
82 // a new index entry. This helps keep the worst-case performance | 79 // a new index entry. This helps keep the worst-case performance |
83 // for |Exists()| under control. | 80 // for |Exists()| under control. |
84 static const size_t kMaxRun = 100; | 81 static const size_t kMaxRun = 100; |
85 | 82 |
86 // Helper for |LoadFile()|. Steals the contents of |index| and | 83 // Helper for |LoadFile()|. Steals the contents of |index| and |
87 // |deltas| using |swap()|. | 84 // |deltas| using |swap()|. |
88 PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, | 85 PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, |
89 std::vector<uint16> *deltas); | 86 std::vector<uint16> *deltas); |
90 | 87 |
91 // Top-level index of prefix to offset in |deltas_|. Each pair | 88 // Top-level index of prefix to offset in |deltas_|. Each pair |
92 // indicates a base prefix and where the deltas from that prefix | 89 // indicates a base prefix and where the deltas from that prefix |
93 // begin in |deltas_|. The deltas for a pair end at the next pair's | 90 // begin in |deltas_|. The deltas for a pair end at the next pair's |
94 // index into |deltas_|. | 91 // index into |deltas_|. |
95 std::vector<std::pair<SBPrefix,size_t> > index_; | 92 std::vector<std::pair<SBPrefix,size_t> > index_; |
96 | 93 |
97 // Deltas which are added to the prefix in |index_| to generate | 94 // Deltas which are added to the prefix in |index_| to generate |
98 // prefixes. Deltas are only valid between consecutive items from | 95 // prefixes. Deltas are only valid between consecutive items from |
99 // |index_|, or the end of |deltas_| for the last |index_| pair. | 96 // |index_|, or the end of |deltas_| for the last |index_| pair. |
100 std::vector<uint16> deltas_; | 97 std::vector<uint16> deltas_; |
101 | 98 |
102 DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 99 DISALLOW_COPY_AND_ASSIGN(PrefixSet); |
103 }; | 100 }; |
104 | 101 |
105 } // namespace safe_browsing | 102 } // namespace safe_browsing |
106 | 103 |
107 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 104 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
OLD | NEW |