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)95LeakyBondedQueue<T>::LeakyBondedQueue(size_t capacity) { 96 capacity_ = capacity; 97 } 98 99 template <class T> ~LeakyBondedQueue()100LeakyBondedQueue<T>::~LeakyBondedQueue() {} 101 102 template <class T> Enqueue(T * new_item)103void 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)113T* 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()127T* 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()135void 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()144size_t LeakyBondedQueue<T>::Length() { 145 std::lock_guard<std::mutex> lock(lock_); 146 return queue_.size(); 147 } 148 149 template <class T> Capacity()150size_t LeakyBondedQueue<T>::Capacity() { 151 return capacity_; 152 } 153 154 template <class T> Empty()155bool 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