OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 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 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
42 // 4 byte version number | 42 // 4 byte version number |
43 // 4 byte |index_.size()| | 43 // 4 byte |index_.size()| |
44 // 4 byte |deltas_.size()| | 44 // 4 byte |deltas_.size()| |
45 // n * 8 byte |&index_[0]..&index_[n]| | 45 // n * 8 byte |&index_[0]..&index_[n]| |
46 // m * 2 byte |&deltas_[0]..&deltas_[m]| | 46 // m * 2 byte |&deltas_[0]..&deltas_[m]| |
47 // 16 byte digest | 47 // 16 byte digest |
48 | 48 |
49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ | 49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ |
50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ | 50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ |
51 | 51 |
| 52 #include <stddef.h> |
| 53 #include <stdint.h> |
| 54 |
52 #include <utility> | 55 #include <utility> |
53 #include <vector> | 56 #include <vector> |
54 | 57 |
55 #include "base/gtest_prod_util.h" | 58 #include "base/gtest_prod_util.h" |
56 #include "base/macros.h" | 59 #include "base/macros.h" |
57 #include "base/memory/scoped_ptr.h" | 60 #include "base/memory/scoped_ptr.h" |
58 #include "components/safe_browsing_db/util.h" | 61 #include "components/safe_browsing_db/util.h" |
59 | 62 |
60 namespace base { | 63 namespace base { |
61 class FilePath; | 64 class FilePath; |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); | 101 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); |
99 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); | 102 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); |
100 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); | 103 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); |
101 | 104 |
102 // Maximum number of consecutive deltas to encode before generating | 105 // Maximum number of consecutive deltas to encode before generating |
103 // a new index entry. This helps keep the worst-case performance | 106 // a new index entry. This helps keep the worst-case performance |
104 // for |Exists()| under control. | 107 // for |Exists()| under control. |
105 static const size_t kMaxRun = 100; | 108 static const size_t kMaxRun = 100; |
106 | 109 |
107 // Helpers to make |index_| easier to deal with. | 110 // Helpers to make |index_| easier to deal with. |
108 typedef std::pair<SBPrefix, uint32> IndexPair; | 111 typedef std::pair<SBPrefix, uint32_t> IndexPair; |
109 typedef std::vector<IndexPair> IndexVector; | 112 typedef std::vector<IndexPair> IndexVector; |
110 static bool PrefixLess(const IndexPair& a, const IndexPair& b); | 113 static bool PrefixLess(const IndexPair& a, const IndexPair& b); |
111 | 114 |
112 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is | 115 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is |
113 // added to |index_|, with the other elements added into |deltas_|. | 116 // added to |index_|, with the other elements added into |deltas_|. |
114 void AddRun(SBPrefix index_prefix, | 117 void AddRun(SBPrefix index_prefix, |
115 const uint16* run_begin, const uint16* run_end); | 118 const uint16_t* run_begin, |
| 119 const uint16_t* run_end); |
116 | 120 |
117 // |true| if |prefix| is one of the prefixes passed to the set's builder. | 121 // |true| if |prefix| is one of the prefixes passed to the set's builder. |
118 // Provided for testing purposes. | 122 // Provided for testing purposes. |
119 bool PrefixExists(SBPrefix prefix) const; | 123 bool PrefixExists(SBPrefix prefix) const; |
120 | 124 |
121 // Regenerate the vector of prefixes passed to the constructor into | 125 // Regenerate the vector of prefixes passed to the constructor into |
122 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. | 126 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. |
123 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; | 127 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; |
124 | 128 |
125 // Used by |PrefixSetBuilder|. | 129 // Used by |PrefixSetBuilder|. |
126 PrefixSet(); | 130 PrefixSet(); |
127 | 131 |
128 // Helper for |LoadFile()|. Steals vector contents using |swap()|. | 132 // Helper for |LoadFile()|. Steals vector contents using |swap()|. |
129 PrefixSet(IndexVector* index, | 133 PrefixSet(IndexVector* index, |
130 std::vector<uint16>* deltas, | 134 std::vector<uint16_t>* deltas, |
131 std::vector<SBFullHash>* full_hashes); | 135 std::vector<SBFullHash>* full_hashes); |
132 | 136 |
133 // Top-level index of prefix to offset in |deltas_|. Each pair | 137 // Top-level index of prefix to offset in |deltas_|. Each pair |
134 // indicates a base prefix and where the deltas from that prefix | 138 // indicates a base prefix and where the deltas from that prefix |
135 // begin in |deltas_|. The deltas for a pair end at the next pair's | 139 // begin in |deltas_|. The deltas for a pair end at the next pair's |
136 // index into |deltas_|. | 140 // index into |deltas_|. |
137 IndexVector index_; | 141 IndexVector index_; |
138 | 142 |
139 // Deltas which are added to the prefix in |index_| to generate | 143 // Deltas which are added to the prefix in |index_| to generate |
140 // prefixes. Deltas are only valid between consecutive items from | 144 // prefixes. Deltas are only valid between consecutive items from |
141 // |index_|, or the end of |deltas_| for the last |index_| pair. | 145 // |index_|, or the end of |deltas_| for the last |index_| pair. |
142 std::vector<uint16> deltas_; | 146 std::vector<uint16_t> deltas_; |
143 | 147 |
144 // Full hashes ordered by SBFullHashLess. | 148 // Full hashes ordered by SBFullHashLess. |
145 std::vector<SBFullHash> full_hashes_; | 149 std::vector<SBFullHash> full_hashes_; |
146 | 150 |
147 DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 151 DISALLOW_COPY_AND_ASSIGN(PrefixSet); |
148 }; | 152 }; |
149 | 153 |
150 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes. | 154 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes. |
151 class PrefixSetBuilder { | 155 class PrefixSetBuilder { |
152 public: | 156 public: |
(...skipping 25 matching lines...) Expand all Loading... |
178 // Buffers prefixes until enough are avaliable to emit a run. | 182 // Buffers prefixes until enough are avaliable to emit a run. |
179 std::vector<SBPrefix> buffer_; | 183 std::vector<SBPrefix> buffer_; |
180 | 184 |
181 // The PrefixSet being built. | 185 // The PrefixSet being built. |
182 scoped_ptr<PrefixSet> prefix_set_; | 186 scoped_ptr<PrefixSet> prefix_set_; |
183 }; | 187 }; |
184 | 188 |
185 } // namespace safe_browsing | 189 } // namespace safe_browsing |
186 | 190 |
187 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ | 191 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ |
OLD | NEW |