components/dns_prefetch/renderer/predictor_queue.cc

   1 // Copyright (c) 2006-2008 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 // See header file for description of DnsQueue class
   6
   7 #include "components/dns_prefetch/renderer/predictor_queue.h"
   8
   9 #include "base/logging.h"
  10 #include "base/metrics/stats_counters.h"
  11
  12 namespace dns_prefetch {
  13
  14 DnsQueue::DnsQueue(BufferSize size)
  15     : buffer_(new char[size + 2]),
  16       buffer_size_(size + 1),
  17       buffer_sentinel_(size + 1),
  18       size_(0) {
  19   CHECK(0 < static_cast<BufferSize>(size + 3));  // Avoid overflow worries.
  20   buffer_[buffer_sentinel_] = '\0';  // Guard byte to help reading data.
  21   readable_ = writeable_ = 0;  // Buffer starts empty.
  22 }
  23
  24 DnsQueue::~DnsQueue(void) {
  25 }
  26
  27 void DnsQueue::Clear() {
  28   size_ = 0;
  29   readable_ = writeable_;
  30   DCHECK(Validate());
  31 }
  32
  33 // Push takes an unterminated string plus its length.
  34 // The string must not contain a null terminator.
  35 // Exactly length chars are written, or nothing is written.
  36 // Returns true for success, false there was no room to push.
  37 DnsQueue::PushResult DnsQueue::Push(const char* source,
  38                                     const size_t unsigned_length) {
  39   BufferSize length = static_cast<BufferSize>(unsigned_length);
  40   if (0 > length+1)  // Avoid overflows in conversion to signed.
  41     return OVERFLOW_PUSH;
  42
  43   // To save on sites with a LOT of links to the SAME domain, we have a
  44   // a compaction hack that removes duplicates when we try to push() a
  45   // match with the last push.
  46   if (0 < size_ && readable_ + length < buffer_sentinel_ &&
  47     0 == strncmp(source, &buffer_[readable_], unsigned_length) &&
  48     '\0' == buffer_[readable_ + unsigned_length]) {
  49     SIMPLE_STATS_COUNTER("DNS.PrefetchDnsRedundantPush");
  50
  51     // We already wrote this name to the queue, so we'll skip this repeat.
  52     return REDUNDANT_PUSH;
  53   }
  54
  55   // Calling convention precludes nulls.
  56   DCHECK(!length || '\0' != source[length - 1]);
  57
  58   DCHECK(Validate());
  59
  60   BufferSize available_space = readable_ - writeable_;
  61
  62   if (0 >= available_space) {
  63     available_space += buffer_size_;
  64   }
  65
  66   if (length + 1 >= available_space) {
  67     SIMPLE_STATS_COUNTER("DNS.PrefetchDnsQueueFull");
  68     return OVERFLOW_PUSH;  // Not enough space to push.
  69   }
  70
  71   BufferSize dest = writeable_;
  72   BufferSize space_till_wrap = buffer_sentinel_ - dest;
  73   if (space_till_wrap < length + 1) {
  74     // Copy until we run out of room at end of buffer.
  75     std::memcpy(&buffer_[dest], source, space_till_wrap);
  76     // Ensure caller didn't have embedded '\0' and also
  77     // ensure trailing sentinel was in place.
  78     // Relies on sentinel.
  79     DCHECK(static_cast<size_t>(space_till_wrap) == strlen(&buffer_[dest]));
  80
  81     length -= space_till_wrap;
  82     source += space_till_wrap;
  83     dest = 0;  // Continue writing at start of buffer.
  84   }
  85
  86   // Copy any remaining portion of source.
  87   std::memcpy(&buffer_[dest], source, length);
  88   DCHECK(dest + length < buffer_sentinel_);
  89   buffer_[dest + length] = '\0';  // We need termination in our buffer.
  90   // Preclude embedded '\0'.
  91   DCHECK(static_cast<size_t>(length) == strlen(&buffer_[dest]));
  92
  93   dest += length + 1;
  94   if (dest == buffer_sentinel_)
  95     dest = 0;
  96
  97   writeable_ = dest;
  98   size_++;
  99   DCHECK(Validate());
 100   return SUCCESSFUL_PUSH;
 101 }
 102
 103 // Extracts the next available string from the buffer.
 104 // The returned string is null terminated, and hence has length
 105 // that is exactly one greater than the written string.
 106 // If the buffer is empty, then the Pop and returns false.
 107 bool DnsQueue::Pop(std::string* out_string) {
 108   DCHECK(Validate());
 109   // Sentinel will preclude memory reads beyond buffer's end.
 110   DCHECK('\0' == buffer_[buffer_sentinel_]);
 111
 112   if (readable_ == writeable_) {
 113     return false;  // buffer was empty
 114   }
 115
 116   // Constructor *may* rely on sentinel for null termination.
 117   (*out_string) = &buffer_[readable_];
 118   // Our sentinel_ at end of buffer precludes an overflow in cast.
 119   BufferSize first_fragment_size = static_cast<BufferSize> (out_string->size());
 120
 121   BufferSize terminal_null;
 122   if (readable_ + first_fragment_size >= buffer_sentinel_) {
 123     // Sentinel was used, so we need the portion after the wrap.
 124     out_string->append(&buffer_[0]);  // Fragment at start of buffer.
 125     // Sentinel precludes overflow in cast to signed type.
 126     terminal_null = static_cast<BufferSize>(out_string->size())
 127                     - first_fragment_size;
 128   } else {
 129     terminal_null = readable_ + first_fragment_size;
 130   }
 131   DCHECK('\0' == buffer_[terminal_null]);
 132
 133   BufferSize new_readable = terminal_null + 1;
 134   if (buffer_sentinel_ == new_readable)
 135     new_readable = 0;
 136
 137   readable_ = new_readable;
 138   size_--;
 139   if (readable_ == writeable_ || 0 == size_) {
 140     // Queue is empty, so reset to start of buffer to help with peeking.
 141     readable_ = writeable_ = 0;
 142   }
 143   DCHECK(Validate());
 144   return true;
 145 }
 146
 147 bool DnsQueue::Validate() {
 148   return (readable_ >= 0) &&
 149           readable_ < buffer_sentinel_ &&
 150           writeable_ >= 0 &&
 151           writeable_ < buffer_sentinel_ &&
 152           '\0' == buffer_[buffer_sentinel_] &&
 153           ((0 == size_) == (readable_ == writeable_));
 154 }
 155
 156 }  // namespace dns_prefetch