1 // Copyright (c) 2011 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 // DnsQueue is implemented as an almost FIFO circular buffer for text 6 // strings that don't have embedded nulls ('\0'). The "almost" element is that 7 // some duplicate strings may be removed (i.e., the string won't really be 8 // pushed *if* the class happens to notice that a duplicate is already in the 9 // queue). 10 // The buffers internal format is null terminated character strings 11 // (a.k.a., c_strings). 12 // It is written to be as fast as possible during push() operations, so 13 // that there will be minimal performance impact on a supplier thread. 14 // The push() operation will not block, and no memory allocation is involved 15 // (internally) during the push operations. 16 // The one caveat is that if there is insufficient space in the buffer to 17 // accept additional string via a push(), then the push() will fail, and 18 // the buffer will be unmodified. 19 20 // This class was designed for use in DNS prefetch operations. During 21 // rendering, the supplier is the renderer (typically), and the consumer 22 // is a thread that sends messages to an async DNS resolver. 23 24 #ifndef CHROME_RENDERER_NET_PREDICTOR_QUEUE_H__ 25 #define CHROME_RENDERER_NET_PREDICTOR_QUEUE_H__ 26 27 #include <string> 28 29 #include "base/basictypes.h" 30 #include "base/memory/scoped_ptr.h" 31 32 class DnsQueue { 33 public: 34 // BufferSize is a signed type used for indexing into a buffer. 35 typedef int32 BufferSize; 36 37 enum PushResult { SUCCESSFUL_PUSH, OVERFLOW_PUSH, REDUNDANT_PUSH }; 38 39 // The size specified in the constructor creates a buffer large enough 40 // to hold at most one string of that length, or "many" 41 // strings of considerably shorter length. Note that strings 42 // are padded internally with a terminal '\0" while stored, 43 // so if you are trying to be precise and get N strings of 44 // length K to fit, you should actually construct a buffer with 45 // an internal size of N*(K+1). 46 explicit DnsQueue(BufferSize size); 47 ~DnsQueue(void); 48 Size()49 size_t Size() const { return size_; } 50 void Clear(); 51 52 // Push takes an unterminated string of the given length 53 // and inserts it into the queue for later 54 // extraction by read. For each successful push(), there 55 // can later be a corresponding read() to extracted the text. 56 // The string must not contain an embedded null terminator 57 // Exactly length chars are written, or the push fails (where 58 // "fails" means nothing is written). 59 // Returns true for success, false for failure (nothing written). 60 PushResult Push(const char* source, const size_t length); 61 Push(std::string source)62 PushResult Push(std::string source) { 63 return Push(source.c_str(), source.length()); 64 } 65 66 // Extract the next available string from the buffer. 67 // If the buffer is empty, then return false. 68 bool Pop(std::string* out_string); 69 70 private: 71 bool Validate(); // Checks that all internal data is valid. 72 73 const scoped_ptr<char[]> buffer_; // Circular buffer, plus extra char ('\0'). 74 const BufferSize buffer_size_; // Size one smaller than allocated space. 75 const BufferSize buffer_sentinel_; // Index of extra '\0' at end of buffer_. 76 77 // If writable_ == readable_, then the buffer is empty. 78 BufferSize readable_; // Next readable char in buffer_. 79 BufferSize writeable_; // The next space in buffer_ to push. 80 81 // Number of queued strings 82 size_t size_; 83 84 DISALLOW_COPY_AND_ASSIGN(DnsQueue); 85 }; // class DnsQueue 86 87 #endif // CHROME_RENDERER_NET_PREDICTOR_QUEUE_H__ 88