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
32class 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
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
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