1 /******************************************************************************
2  *
3  *  Copyright (C) 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 system_bt_osi {
25 
26 /*
27  *   LeakyBondedQueue<T>
28  *
29  * - LeakyLondedQueue<T> is a fixed size queue that leaks oldest item when
30  *   reaching its capacity. This is useful in creating memory bonded data
31  *   structure where freshness is more important than full coverage.
32  * - The queue is protected by a simple mutex and is thread-safe, although
33  *   improvements could be made to lock enqueue and dequeue separately, it
34  *   is not implemented at this moment due to lack of demand
35  * - The queue uses unique_ptr to automatically free its content when it is
36  *   destructed. It is the user's responsibility to implement T's destructor
37  *   correctly.
38  *
39  */
40 template <class T>
41 class LeakyBondedQueue {
42  public:
43   LeakyBondedQueue(size_t capacity);
44   /* Default destructor
45    *
46    * Call Clear() and free the queue structure itself
47    */
48   ~LeakyBondedQueue();
49   /*
50    * Add item NEW_ITEM to the underlining queue. If the queue is full, pop
51    * the oldest item
52    */
53   void Enqueue(T* new_item);
54   /*
55    * Add item NEW_ITEM to the underlining queue. If the queue is full, dequeue
56    * the oldest item and returns it to the caller. Return nullptr otherwise.
57    */
58   T* EnqueueWithPop(T* new_item);
59   /*
60    * Dequeues the oldest item from the queue. Return nullptr if queue is empty
61    */
62   T* Dequeue();
63   /*
64    * Returns the length of queue
65    */
66   size_t Length();
67   /*
68    * Returns the defined capacity of the queue
69    */
70   size_t Capacity();
71   /*
72    * Returns whether the queue is empty
73    */
74   bool Empty();
75   /*
76    * Pops all items from the queue
77    */
78   void Clear();
79 
80  private:
81   // Put item in unique_ptr so that they get freed automatically when poped or
82   // when queue_ is freed
83   std::queue<std::unique_ptr<T>> queue_;
84   std::mutex lock_;
85   size_t capacity_;
86 };
87 
88 /*
89 * Definitions must be in the header for template classes
90 */
91 
92 template <class T>
LeakyBondedQueue(size_t capacity)93 LeakyBondedQueue<T>::LeakyBondedQueue(size_t capacity) {
94   capacity_ = capacity;
95 }
96 
97 template <class T>
~LeakyBondedQueue()98 LeakyBondedQueue<T>::~LeakyBondedQueue() {}
99 
100 template <class T>
Enqueue(T * new_item)101 void LeakyBondedQueue<T>::Enqueue(T* new_item) {
102   std::lock_guard<std::mutex> lock(lock_);
103   if ((queue_.size() + 1) > capacity_) {
104     queue_.pop();
105   }
106   std::unique_ptr<T> item_ptr(new_item);
107   queue_.push(std::move(item_ptr));
108 }
109 
110 template <class T>
EnqueueWithPop(T * new_item)111 T* LeakyBondedQueue<T>::EnqueueWithPop(T* new_item) {
112   std::lock_guard<std::mutex> lock(lock_);
113   T* old_item = nullptr;
114   if ((queue_.size() + 1) > capacity_) {
115     std::unique_ptr<T> item = std::move(queue_.front());
116     queue_.pop();
117     old_item = item.release();
118   }
119   std::unique_ptr<T> item_ptr(new_item);
120   queue_.push(std::move(item_ptr));
121   return old_item;
122 }
123 
124 template <class T>
Dequeue()125 T* LeakyBondedQueue<T>::Dequeue() {
126   std::lock_guard<std::mutex> lock(lock_);
127   std::unique_ptr<T> item = std::move(queue_.front());
128   queue_.pop();
129   return item.release();
130 }
131 
132 template <class T>
Clear()133 void LeakyBondedQueue<T>::Clear() {
134   std::lock_guard<std::mutex> lock(lock_);
135   while (!queue_.empty()) {
136     // unique_ptr does not need to be freed
137     queue_.pop();
138   }
139 }
140 
141 template <class T>
Length()142 size_t LeakyBondedQueue<T>::Length() {
143   std::lock_guard<std::mutex> lock(lock_);
144   return queue_.size();
145 }
146 
147 template <class T>
Capacity()148 size_t LeakyBondedQueue<T>::Capacity() {
149   return capacity_;
150 }
151 
152 template <class T>
Empty()153 bool LeakyBondedQueue<T>::Empty() {
154   std::lock_guard<std::mutex> lock(lock_);
155   return queue_.empty();
156 }
157 
158 }  // namespace system_bt_osi
159