1 /******************************************************************************
2  *
3  *  Copyright 2016 Google, Inc.
4  *
5  *  Licensed under the Apache License, Version 2.0 (the "License");
6  *  you may not use this file except in compliance with the License.
7  *  You may obtain a copy of the License at:
8  *
9  *  http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  *
17  ******************************************************************************/
18 #pragma once
19 
20 #include <memory>
21 #include <mutex>
22 #include <queue>
23 
24 namespace bluetooth {
25 
26 namespace common {
27 
28 /*
29  *   LeakyBondedQueue<T>
30  *
31  * - LeakyLondedQueue<T> is a fixed size queue that leaks oldest item when
32  *   reaching its capacity. This is useful in creating memory bonded data
33  *   structure where freshness is more important than full coverage.
34  * - The queue is protected by a simple mutex and is thread-safe, although
35  *   improvements could be made to lock enqueue and dequeue separately, it
36  *   is not implemented at this moment due to lack of demand
37  * - The queue uses unique_ptr to automatically free its content when it is
38  *   destructed. It is the user's responsibility to implement T's destructor
39  *   correctly.
40  *
41  */
42 template <class T>
43 class LeakyBondedQueue {
44  public:
45   LeakyBondedQueue(size_t capacity);
46   /* Default destructor
47    *
48    * Call Clear() and free the queue structure itself
49    */
50   ~LeakyBondedQueue();
51   /*
52    * Add item NEW_ITEM to the underlining queue. If the queue is full, pop
53    * the oldest item
54    */
55   void Enqueue(T* new_item);
56   /*
57    * Add item NEW_ITEM to the underlining queue. If the queue is full, dequeue
58    * the oldest item and returns it to the caller. Return nullptr otherwise.
59    */
60   T* EnqueueWithPop(T* new_item);
61   /*
62    * Dequeues the oldest item from the queue. Return nullptr if queue is empty
63    */
64   T* Dequeue();
65   /*
66    * Returns the length of queue
67    */
68   size_t Length();
69   /*
70    * Returns the defined capacity of the queue
71    */
72   size_t Capacity();
73   /*
74    * Returns whether the queue is empty
75    */
76   bool Empty();
77   /*
78    * Pops all items from the queue
79    */
80   void Clear();
81 
82  private:
83   // Put item in unique_ptr so that they get freed automatically when poped or
84   // when queue_ is freed
85   std::queue<std::unique_ptr<T>> queue_;
86   std::mutex lock_;
87   size_t capacity_;
88 };
89 
90 /*
91  * Definitions must be in the header for template classes
92  */
93 
94 template <class T>
LeakyBondedQueue(size_t capacity)95 LeakyBondedQueue<T>::LeakyBondedQueue(size_t capacity) {
96   capacity_ = capacity;
97 }
98 
99 template <class T>
~LeakyBondedQueue()100 LeakyBondedQueue<T>::~LeakyBondedQueue() {}
101 
102 template <class T>
Enqueue(T * new_item)103 void LeakyBondedQueue<T>::Enqueue(T* new_item) {
104   std::lock_guard<std::mutex> lock(lock_);
105   if ((queue_.size() + 1) > capacity_) {
106     queue_.pop();
107   }
108   std::unique_ptr<T> item_ptr(new_item);
109   queue_.push(std::move(item_ptr));
110 }
111 
112 template <class T>
EnqueueWithPop(T * new_item)113 T* LeakyBondedQueue<T>::EnqueueWithPop(T* new_item) {
114   std::lock_guard<std::mutex> lock(lock_);
115   T* old_item = nullptr;
116   if ((queue_.size() + 1) > capacity_) {
117     std::unique_ptr<T> item = std::move(queue_.front());
118     queue_.pop();
119     old_item = item.release();
120   }
121   std::unique_ptr<T> item_ptr(new_item);
122   queue_.push(std::move(item_ptr));
123   return old_item;
124 }
125 
126 template <class T>
Dequeue()127 T* LeakyBondedQueue<T>::Dequeue() {
128   std::lock_guard<std::mutex> lock(lock_);
129   std::unique_ptr<T> item = std::move(queue_.front());
130   queue_.pop();
131   return item.release();
132 }
133 
134 template <class T>
Clear()135 void LeakyBondedQueue<T>::Clear() {
136   std::lock_guard<std::mutex> lock(lock_);
137   while (!queue_.empty()) {
138     // unique_ptr does not need to be freed
139     queue_.pop();
140   }
141 }
142 
143 template <class T>
Length()144 size_t LeakyBondedQueue<T>::Length() {
145   std::lock_guard<std::mutex> lock(lock_);
146   return queue_.size();
147 }
148 
149 template <class T>
Capacity()150 size_t LeakyBondedQueue<T>::Capacity() {
151   return capacity_;
152 }
153 
154 template <class T>
Empty()155 bool LeakyBondedQueue<T>::Empty() {
156   std::lock_guard<std::mutex> lock(lock_);
157   return queue_.empty();
158 }
159 
160 }  // namespace common
161 
162 }  // namespace bluetooth
163