1    :  // Copyright 2014 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  //
  15    :  // A simple circular queue.
  16    :  // The queue has two ends, the front/head and the back/tail.
  17    :  // Elements are pushed in the back/tail end, and popped from the front/head end.
  18    :  // The queue will refuse to push elements when it is full.
  19    :  // The underlying container reserves the memory only once, making the queue
  20    :  // memory-wise efficient, avoiding the memory fragmentation caused by lots of
  21    :  // small allocations.
  22    :  // To avoid misuse, the constructor taking a MemoryNotiferInterface*
  23    :  // parameter is enabled IFF the specified allocator is of type
  24    :  // MemoryNotifierAllocator<T>.
  25    :  //
  26    :  // CORRECT USAGE:
  27    :  // CircularQueue<int, MemoryNotifierAllocator<int>> q(capacity, &notifier);
  28    :  // CircularQueue<int> q(capacity);  // Using default allocator without notifier.
  29    :  //
  30    :  // INCORRECT USAGE (causes compilation error):
  31    :  // CircularQueue<int> q(capacity, &notifier);
  32    :  
  33    :  #ifndef SYZYGY_AGENT_ASAN_CIRCULAR_QUEUE_H_
  34    :  #define SYZYGY_AGENT_ASAN_CIRCULAR_QUEUE_H_
  35    :  
  36    :  #include <memory>
  37    :  #include <vector>
  38    :  
  39    :  #include "syzygy/agent/asan/memory_notifier.h"
  40    :  
  41  m :  namespace agent {
  42  m :  namespace asan {
  43    :  
  44    :  // A simple circular queue.
  45    :  // @tparam T the type of the elements.
  46    :  // @tparam Alloc the type of the allocator used by the underlying container.
  47  m :  template<typename T, typename Alloc = std::allocator<T>>
  48  m :  class CircularQueue {
  49  m :   public:
  50  m :    typedef typename std::vector<T, Alloc> Container;
  51    :  
  52    :    // Constructor.
  53    :    // @param max_capacity Maximum number of elements the queue can store.
  54  m :    explicit CircularQueue(size_t max_capacity);
  55    :  
  56    :    // Constructor.
  57    :    // @param max_capacity Maximum number of elements the queue can store.
  58    :    // @param alloc The allocator to use with this container.
  59  m :    CircularQueue(size_t max_capacity, const Alloc& alloc);
  60    :  
  61    :    // Inserts an element in the back/tail of the queue if possible.
  62    :    // @param the element to be inserted.
  63    :    // @returns true if the operation succeeded and the element was inserted,
  64    :    //     false if the queue is full.
  65  m :    bool push(const T&);
  66    :  
  67    :    // Removes an element from the front/head of the queue if possible.
  68    :    // @returns true if an element was popped fron the front/head,
  69    :    //     false if the queue is empty.
  70  m :    bool pop();
  71    :  
  72    :    // @returns the element in the front/head of the queue.
  73  m :    const T& front() const;
  74    :  
  75    :    // Gives the current number of elements in the queue.
  76    :    // @returns the number of elements currently stored in the queue.
  77  m :    size_t size() const;
  78    :  
  79    :    // Tests if the queue is empty.
  80    :    // @returns true if the queue is empty, false otherwise.
  81  m :    bool empty() const;
  82    :  
  83    :    // @returns the maximum number of elements the queue can handle.
  84  m :    size_t max_capacity() const;
  85    :  
  86  m :   private:
  87    :    // The index of the first enqueued/pushed element.
  88  m :    size_t head_;
  89    :  
  90    :    // The index of the next free position.
  91    :    // The index to be used to store an element in the next call to Push.
  92  m :    size_t tail_;
  93    :  
  94    :    // The number of elements contained in the queue.
  95  m :    size_t size_;
  96    :  
  97    :    // The queue underlying container.
  98  m :    Container buffer_;
  99  m :  };
 100    :  
 101  m :  }  // namespace asan
 102  m :  }  // namespace agent
 103    :  
 104    :  #include "syzygy/agent/asan/circular_queue_impl.h"
 105    :  
 106    :  #endif  // SYZYGY_AGENT_ASAN_CIRCULAR_QUEUE_H_