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