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 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> 93 LeakyBondedQueue<T>::LeakyBondedQueue(size_t capacity) { 94 capacity_ = capacity; 95 } 96 97 template <class T> 98 LeakyBondedQueue<T>::~LeakyBondedQueue() {} 99 100 template <class T> 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> 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> 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> 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> 142 size_t LeakyBondedQueue<T>::Length() { 143 std::lock_guard<std::mutex> lock(lock_); 144 return queue_.size(); 145 } 146 147 template <class T> 148 size_t LeakyBondedQueue<T>::Capacity() { 149 return capacity_; 150 } 151 152 template <class T> 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
