chrome/browser/safe_browsing/chunk_range.cc

   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 <algorithm>
   8
   9 #include "chrome/browser/safe_browsing/chunk_range.h"
  10
  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"
  15
  16 ChunkRange::ChunkRange(int start) : start_(start), stop_(start) {
  17 }
  18
  19 ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) {
  20 }
  21
  22 ChunkRange::ChunkRange(const ChunkRange& rhs)
  23     : start_(rhs.start()), stop_(rhs.stop()) {
  24 }
  25
  26 // Helper functions -----------------------------------------------------------
  27
  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());
  32
  33   DCHECK(result);
  34   result->clear();
  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;
  39
  40     // Extend the range forward across duplicates and increments.
  41     for (; iter != sorted_chunks.end() && *iter <= range_end + 1; ++iter) {
  42       range_end = *iter;
  43     }
  44
  45     if (!result->empty())
  46       result->append(",");
  47     result->append(base::IntToString(range_begin));
  48     if (range_end > range_begin) {
  49       result->append("-");
  50       result->append(base::IntToString(range_end));
  51     }
  52   }
  53 }
  54
  55 void RangesToChunks(const std::vector<ChunkRange>& ranges,
  56                     std::vector<int>* chunks) {
  57   DCHECK(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);
  62     }
  63   }
  64 }
  65
  66 bool StringToRanges(const std::string& input,
  67                     std::vector<ChunkRange>* ranges) {
  68   DCHECK(ranges);
  69
  70   // Crack the string into chunk parts, then crack each part looking for a
  71   // range.
  72   std::vector<std::string> chunk_parts;
  73   base::SplitString(input, ',', &chunk_parts);
  74
  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());
  79     int stop = start;
  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.
  84       ranges->clear();
  85       return false;
  86     }
  87     ranges->push_back(ChunkRange(start, stop));
  88   }
  89
  90   return true;
  91 }
  92
  93 // Binary search over a series of ChunkRanges.
  94 bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) {
  95   if (ranges.empty())
  96     return false;
  97
  98   int low = 0;
  99   int high = ranges.size() - 1;
 100
 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.
 107
 108     // Adjust our mid point.
 109     if (chunk.stop() < chunk_number)
 110       low = mid + 1;
 111     else
 112       high = mid - 1;
 113   }
 114
 115   return false;
 116 }