15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DnsQueue is implemented as an almost FIFO circular buffer for text 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// strings that don't have embedded nulls ('\0'). The "almost" element is that 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// some duplicate strings may be removed (i.e., the string won't really be 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pushed *if* the class happens to notice that a duplicate is already in the 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// queue). 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The buffers internal format is null terminated character strings 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (a.k.a., c_strings). 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// It is written to be as fast as possible during push() operations, so 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that there will be minimal performance impact on a supplier thread. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The push() operation will not block, and no memory allocation is involved 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (internally) during the push operations. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The one caveat is that if there is insufficient space in the buffer to 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// accept additional string via a push(), then the push() will fail, and 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the buffer will be unmodified. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class was designed for use in DNS prefetch operations. During 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// rendering, the supplier is the renderer (typically), and the consumer 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is a thread that sends messages to an async DNS resolver. 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef CHROME_RENDERER_NET_PREDICTOR_QUEUE_H__ 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define CHROME_RENDERER_NET_PREDICTOR_QUEUE_H__ 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string> 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/memory/scoped_ptr.h" 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class DnsQueue { 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // BufferSize is a signed type used for indexing into a buffer. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef int32 BufferSize; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum PushResult { SUCCESSFUL_PUSH, OVERFLOW_PUSH, REDUNDANT_PUSH }; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The size specified in the constructor creates a buffer large enough 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to hold at most one string of that length, or "many" 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // strings of considerably shorter length. Note that strings 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // are padded internally with a terminal '\0" while stored, 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // so if you are trying to be precise and get N strings of 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // length K to fit, you should actually construct a buffer with 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // an internal size of N*(K+1). 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit DnsQueue(BufferSize size); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~DnsQueue(void); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t Size() const { return size_; } 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Clear(); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Push takes an unterminated string of the given length 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and inserts it into the queue for later 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // extraction by read. For each successful push(), there 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can later be a corresponding read() to extracted the text. 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The string must not contain an embedded null terminator 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Exactly length chars are written, or the push fails (where 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // "fails" means nothing is written). 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true for success, false for failure (nothing written). 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PushResult Push(const char* source, const size_t length); 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PushResult Push(std::string source) { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Push(source.c_str(), source.length()); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Extract the next available string from the buffer. 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the buffer is empty, then return false. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Pop(std::string* out_string); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Validate(); // Checks that all internal data is valid. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const scoped_ptr<char[]> buffer_; // Circular buffer, plus extra char ('\0'). 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BufferSize buffer_size_; // Size one smaller than allocated space. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BufferSize buffer_sentinel_; // Index of extra '\0' at end of buffer_. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If writable_ == readable_, then the buffer is empty. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BufferSize readable_; // Next readable char in buffer_. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BufferSize writeable_; // The next space in buffer_ to push. 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Number of queued strings 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t size_; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(DnsQueue); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; // class DnsQueue 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // CHROME_RENDERER_NET_PREDICTOR_QUEUE_H__ 88