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 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
52 #pragma once | 52 #pragma once |
53 | 53 |
54 #include <vector> | 54 #include <vector> |
55 | 55 |
56 #include "chrome/browser/safe_browsing/safe_browsing_util.h" | 56 #include "chrome/browser/safe_browsing/safe_browsing_util.h" |
57 | 57 |
58 namespace safe_browsing { | 58 namespace safe_browsing { |
59 | 59 |
60 class PrefixSet { | 60 class PrefixSet { |
61 public: | 61 public: |
62 explicit PrefixSet(const std::vector<SBPrefix>& prefixes); | 62 explicit PrefixSet(const std::vector<SBPrefix>& sorted_prefixes); |
63 ~PrefixSet(); | 63 ~PrefixSet(); |
64 | 64 |
65 // |true| if |prefix| was in |prefixes| passed to the constructor. | 65 // |true| if |prefix| was in |prefixes| passed to the constructor. |
66 bool Exists(SBPrefix prefix) const; | 66 bool Exists(SBPrefix prefix) const; |
67 | 67 |
| 68 // Regenerate the vector of prefixes passed to the constructor into |
| 69 // |prefixes|. Prefixes will be added in sorted order. |
| 70 void GetPrefixes(std::vector<SBPrefix>* prefixes); |
| 71 |
68 private: | 72 private: |
69 // Maximum delta that can be encoded in a 16-bit unsigned. | 73 // Maximum delta that can be encoded in a 16-bit unsigned. |
70 static const unsigned kMaxDelta = 256 * 256; | 74 static const unsigned kMaxDelta = 256 * 256; |
71 | 75 |
72 // Maximum number of consecutive deltas to encode before generating | 76 // Maximum number of consecutive deltas to encode before generating |
73 // a new index entry. This helps keep the worst-case performance | 77 // a new index entry. This helps keep the worst-case performance |
74 // for |Exists()| under control. | 78 // for |Exists()| under control. |
75 static const size_t kMaxRun = 100; | 79 static const size_t kMaxRun = 100; |
76 | 80 |
77 // Top-level index of prefix to offset in |deltas_|. Each pair | 81 // Top-level index of prefix to offset in |deltas_|. Each pair |
78 // indicates a base prefix and where the deltas from that prefix | 82 // indicates a base prefix and where the deltas from that prefix |
79 // begin in |deltas_|. The deltas for a pair end at the next pair's | 83 // begin in |deltas_|. The deltas for a pair end at the next pair's |
80 // index into |deltas_|. | 84 // index into |deltas_|. |
81 std::vector<std::pair<SBPrefix,size_t> > index_; | 85 std::vector<std::pair<SBPrefix,size_t> > index_; |
82 | 86 |
83 // Deltas which are added to the prefix in |index_| to generate | 87 // Deltas which are added to the prefix in |index_| to generate |
84 // prefixes. Deltas are only valid between consecutive items from | 88 // prefixes. Deltas are only valid between consecutive items from |
85 // |index_|, or the end of |deltas_| for the last |index_| pair. | 89 // |index_|, or the end of |deltas_| for the last |index_| pair. |
86 std::vector<uint16> deltas_; | 90 std::vector<uint16> deltas_; |
87 | 91 |
88 DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 92 DISALLOW_COPY_AND_ASSIGN(PrefixSet); |
89 }; | 93 }; |
90 | 94 |
91 } // namespace safe_browsing | 95 } // namespace safe_browsing |
92 | 96 |
93 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 97 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
OLD | NEW |