1 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 // Implementation of ChunkRange class.
9 #include "chrome/browser/safe_browsing/chunk_range.h"
11 #include "base/logging.h"
12 #include "base/strings/string_number_conversions.h"
13 #include "base/strings/string_split.h"
14 #include "base/strings/string_util.h"
16 ChunkRange::ChunkRange(int start) : start_(start), stop_(start) {
19 ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) {
22 ChunkRange::ChunkRange(const ChunkRange& rhs)
23 : start_(rhs.start()), stop_(rhs.stop()) {
26 // Helper functions -----------------------------------------------------------
28 void ChunksToRangeString(const std::vector<int>& chunks, std::string* result) {
29 // The following code requires the range to be sorted.
30 std::vector<int> sorted_chunks(chunks);
31 std::sort(sorted_chunks.begin(), sorted_chunks.end());
35 std::vector<int>::const_iterator iter = sorted_chunks.begin();
36 while (iter != sorted_chunks.end()) {
37 const int range_begin = *iter;
38 int range_end = *iter;
40 // Extend the range forward across duplicates and increments.
41 for (; iter != sorted_chunks.end() && *iter <= range_end + 1; ++iter) {
47 result->append(base::IntToString(range_begin));
48 if (range_end > range_begin) {
50 result->append(base::IntToString(range_end));
55 void RangesToChunks(const std::vector<ChunkRange>& ranges,
56 std::vector<int>* chunks) {
58 for (size_t i = 0; i < ranges.size(); ++i) {
59 const ChunkRange& range = ranges[i];
60 for (int chunk = range.start(); chunk <= range.stop(); ++chunk) {
61 chunks->push_back(chunk);
66 bool StringToRanges(const std::string& input,
67 std::vector<ChunkRange>* ranges) {
70 // Crack the string into chunk parts, then crack each part looking for a
72 std::vector<std::string> chunk_parts;
73 base::SplitString(input, ',', &chunk_parts);
75 for (size_t i = 0; i < chunk_parts.size(); ++i) {
76 std::vector<std::string> chunk_ranges;
77 base::SplitString(chunk_parts[i], '-', &chunk_ranges);
78 int start = atoi(chunk_ranges[0].c_str());
80 if (chunk_ranges.size() == 2)
81 stop = atoi(chunk_ranges[1].c_str());
82 if (start == 0 || stop == 0) {
83 // atoi error, since chunk numbers are guaranteed to never be 0.
87 ranges->push_back(ChunkRange(start, stop));
93 // Binary search over a series of ChunkRanges.
94 bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) {
99 int high = ranges.size() - 1;
101 while (low <= high) {
102 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
103 int mid = ((unsigned int)low + (unsigned int)high) >> 1;
104 const ChunkRange& chunk = ranges[mid];
105 if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number))
106 return true; // chunk_number is in range.
108 // Adjust our mid point.
109 if (chunk.stop() < chunk_number)