chunk_range.cc revision 513209b27ff55e2841eac0e4120199c23acce758 
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.
4//
5// Implementation of ChunkRange class.
6
7#include "chrome/browser/safe_browsing/chunk_range.h"
8
9#include "base/logging.h"
10#include "base/string_number_conversions.h"
11#include "base/string_split.h"
12#include "base/string_util.h"
13
14ChunkRange::ChunkRange(int start) : start_(start), stop_(start) {
15}
16
17ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) {
18}
19
20ChunkRange::ChunkRange(const ChunkRange& rhs)
21    : start_(rhs.start()), stop_(rhs.stop()) {
22}
23
24// Helper functions -----------------------------------------------------------
25
26void ChunksToRangeString(const std::vector<int>& chunks, std::string* result) {
27  // The following code requires the range to be sorted.
28  std::vector<int> sorted_chunks(chunks);
29  std::sort(sorted_chunks.begin(), sorted_chunks.end());
30
31  DCHECK(result);
32  result->clear();
33  std::vector<int>::const_iterator iter = sorted_chunks.begin();
34  while (iter != sorted_chunks.end()) {
35    const int range_begin = *iter;
36    int range_end = *iter;
37
38    // Extend the range forward across duplicates and increments.
39    for (; iter != sorted_chunks.end() && *iter <= range_end + 1; ++iter) {
40      range_end = *iter;
41    }
42
43    if (!result->empty())
44      result->append(",");
45    result->append(base::IntToString(range_begin));
46    if (range_end > range_begin) {
47      result->append("-");
48      result->append(base::IntToString(range_end));
49    }
50  }
51}
52
53void RangesToChunks(const std::vector<ChunkRange>& ranges,
54                    std::vector<int>* chunks) {
55  DCHECK(chunks);
56  for (size_t i = 0; i < ranges.size(); ++i) {
57    const ChunkRange& range = ranges[i];
58    for (int chunk = range.start(); chunk <= range.stop(); ++chunk) {
59      chunks->push_back(chunk);
60    }
61  }
62}
63
64bool StringToRanges(const std::string& input,
65                    std::vector<ChunkRange>* ranges) {
66  DCHECK(ranges);
67
68  // Crack the string into chunk parts, then crack each part looking for a
69  // range.
70  std::vector<std::string> chunk_parts;
71  base::SplitString(input, ',', &chunk_parts);
72
73  for (size_t i = 0; i < chunk_parts.size(); ++i) {
74    std::vector<std::string> chunk_ranges;
75    base::SplitString(chunk_parts[i], '-', &chunk_ranges);
76    int start = atoi(chunk_ranges[0].c_str());
77    int stop = start;
78    if (chunk_ranges.size() == 2)
79      stop = atoi(chunk_ranges[1].c_str());
80    if (start == 0 || stop == 0) {
81      // atoi error, since chunk numbers are guaranteed to never be 0.
82      ranges->clear();
83      return false;
84    }
85    ranges->push_back(ChunkRange(start, stop));
86  }
87
88  return true;
89}
90
91// Binary search over a series of ChunkRanges.
92bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) {
93  if (ranges.empty())
94    return false;
95
96  int low = 0;
97  int high = ranges.size() - 1;
98
99  while (low <= high) {
100    // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
101    int mid = ((unsigned int)low + (unsigned int)high) >> 1;
102    const ChunkRange& chunk = ranges[mid];
103    if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number))
104      return true;  // chunk_number is in range.
105
106    // Adjust our mid point.
107    if (chunk.stop() < chunk_number)
108      low = mid + 1;
109    else
110      high = mid - 1;
111  }
112
113  return false;
114}
115