1 files changed, 156 insertions, 0 deletions
diff --git a/components/network_hints/renderer/dns_prefetch_queue.cc b/components/network_hints/renderer/dns_prefetch_queue.cc
new file mode 100644
index 0000000..8328df9
--- /dev/null
+++ b/components/network_hints/renderer/dns_prefetch_queue.cc
@@ -0,0 +1,156 @@
+// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// See header file for description of DnsQueue class
+
+#include "components/network_hints/renderer/dns_prefetch_queue.h"
+
+#include "base/logging.h"
+#include "base/metrics/stats_counters.h"
+
+namespace network_hints {
+
+DnsQueue::DnsQueue(BufferSize size)
+    : buffer_(new char[size + 2]),
+      buffer_size_(size + 1),
+      buffer_sentinel_(size + 1),
+      size_(0) {
+  CHECK(0 < static_cast<BufferSize>(size + 3));  // Avoid overflow worries.
+  buffer_[buffer_sentinel_] = '\0';  // Guard byte to help reading data.
+  readable_ = writeable_ = 0;  // Buffer starts empty.
+}
+
+DnsQueue::~DnsQueue(void) {
+}
+
+void DnsQueue::Clear() {
+  size_ = 0;
+  readable_ = writeable_;
+  DCHECK(Validate());
+}
+
+// Push takes an unterminated string plus its length.
+// The string must not contain a null terminator.
+// Exactly length chars are written, or nothing is written.
+// Returns true for success, false there was no room to push.
+DnsQueue::PushResult DnsQueue::Push(const char* source,
+                                    const size_t unsigned_length) {
+  BufferSize length = static_cast<BufferSize>(unsigned_length);
+  if (0 > length+1)  // Avoid overflows in conversion to signed.
+    return OVERFLOW_PUSH;
+
+  // To save on sites with a LOT of links to the SAME domain, we have a
+  // a compaction hack that removes duplicates when we try to push() a
+  // match with the last push.
+  if (0 < size_ && readable_ + length < buffer_sentinel_ &&
+    0 == strncmp(source, &buffer_[readable_], unsigned_length) &&
+    '\0' == buffer_[readable_ + unsigned_length]) {
+    SIMPLE_STATS_COUNTER("DNS.PrefetchDnsRedundantPush");
+
+    // We already wrote this name to the queue, so we'll skip this repeat.
+    return REDUNDANT_PUSH;
+  }
+
+  // Calling convention precludes nulls.
+  DCHECK(!length || '\0' != source[length - 1]);
+
+  DCHECK(Validate());
+
+  BufferSize available_space = readable_ - writeable_;
+
+  if (0 >= available_space) {
+    available_space += buffer_size_;
+  }
+
+  if (length + 1 >= available_space) {
+    SIMPLE_STATS_COUNTER("DNS.PrefetchDnsQueueFull");
+    return OVERFLOW_PUSH;  // Not enough space to push.
+  }
+
+  BufferSize dest = writeable_;
+  BufferSize space_till_wrap = buffer_sentinel_ - dest;
+  if (space_till_wrap < length + 1) {
+    // Copy until we run out of room at end of buffer.
+    std::memcpy(&buffer_[dest], source, space_till_wrap);
+    // Ensure caller didn't have embedded '\0' and also
+    // ensure trailing sentinel was in place.
+    // Relies on sentinel.
+    DCHECK(static_cast<size_t>(space_till_wrap) == strlen(&buffer_[dest]));
+
+    length -= space_till_wrap;
+    source += space_till_wrap;
+    dest = 0;  // Continue writing at start of buffer.
+  }
+
+  // Copy any remaining portion of source.
+  std::memcpy(&buffer_[dest], source, length);
+  DCHECK(dest + length < buffer_sentinel_);
+  buffer_[dest + length] = '\0';  // We need termination in our buffer.
+  // Preclude embedded '\0'.
+  DCHECK(static_cast<size_t>(length) == strlen(&buffer_[dest]));
+
+  dest += length + 1;
+  if (dest == buffer_sentinel_)
+    dest = 0;
+
+  writeable_ = dest;
+  size_++;
+  DCHECK(Validate());
+  return SUCCESSFUL_PUSH;
+}
+
+// Extracts the next available string from the buffer.
+// The returned string is null terminated, and hence has length
+// that is exactly one greater than the written string.
+// If the buffer is empty, then the Pop and returns false.
+bool DnsQueue::Pop(std::string* out_string) {
+  DCHECK(Validate());
+  // Sentinel will preclude memory reads beyond buffer's end.
+  DCHECK('\0' == buffer_[buffer_sentinel_]);
+
+  if (readable_ == writeable_) {
+    return false;  // buffer was empty
+  }
+
+  // Constructor *may* rely on sentinel for null termination.
+  (*out_string) = &buffer_[readable_];
+  // Our sentinel_ at end of buffer precludes an overflow in cast.
+  BufferSize first_fragment_size = static_cast<BufferSize> (out_string->size());
+
+  BufferSize terminal_null;
+  if (readable_ + first_fragment_size >= buffer_sentinel_) {
+    // Sentinel was used, so we need the portion after the wrap.
+    out_string->append(&buffer_[0]);  // Fragment at start of buffer.
+    // Sentinel precludes overflow in cast to signed type.
+    terminal_null = static_cast<BufferSize>(out_string->size())
+                    - first_fragment_size;
+  } else {
+    terminal_null = readable_ + first_fragment_size;
+  }
+  DCHECK('\0' == buffer_[terminal_null]);
+
+  BufferSize new_readable = terminal_null + 1;
+  if (buffer_sentinel_ == new_readable)
+    new_readable = 0;
+
+  readable_ = new_readable;
+  size_--;
+  if (readable_ == writeable_ || 0 == size_) {
+    // Queue is empty, so reset to start of buffer to help with peeking.
+    readable_ = writeable_ = 0;
+  }
+  DCHECK(Validate());
+  return true;
+}
+
+bool DnsQueue::Validate() {
+  return (readable_ >= 0) &&
+          readable_ < buffer_sentinel_ &&
+          writeable_ >= 0 &&
+          writeable_ < buffer_sentinel_ &&
+          '\0' == buffer_[buffer_sentinel_] &&
+          ((0 == size_) == (readable_ == writeable_));
+}
+
+}  // namespace network_hints