| // Copyright 2020 The Chromium OS Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef DLCSERVICE_UNIQUE_QUEUE_H_ |
| #define DLCSERVICE_UNIQUE_QUEUE_H_ |
| |
| #include <list> |
| #include <unordered_map> |
| #include <utility> |
| |
| namespace dlcservice { |
| |
| // |UniqueQueue| is a queue that only holds unique elements. |
| // - Constant time deletion of an element. |
| // - Constant time check of an element. |
| // Template arguments: |
| // - |T| the element type to queue. |
| // - |T_Hasher| the hashing function for |T|. |
| template <typename T, typename T_Hasher> |
| class UniqueQueue { |
| public: |
| UniqueQueue() = default; |
| virtual ~UniqueQueue() = default; |
| |
| // Returns true if there are any elements. |
| bool Empty() const { return list_.empty(); } |
| |
| // Returns true if element |t| exists. |
| bool Has(const T& t) { return map_.find(t) != map_.end(); } |
| |
| // Inserts the element to the back of the queue. |
| void Push(const T& t) { |
| if (!Has(t)) { |
| list_.push_back(t); |
| map_.insert({{t, --list_.end()}}); |
| } |
| } |
| |
| // Returns a const reference to the first element. |
| const T& Peek() const { return list_.front(); } |
| |
| // Removes the front element. |
| void Pop() { |
| map_.erase(list_.front()); |
| list_.pop_front(); |
| } |
| |
| // Removes a single element |t|. |
| void Erase(const T& t) { |
| auto iter = map_.find(t); |
| if (iter == map_.end()) |
| return; |
| list_.erase(iter->second); |
| map_.erase(iter); |
| } |
| |
| // Remove all elements. |
| void Clear() { |
| list_.clear(); |
| map_.clear(); |
| } |
| |
| private: |
| std::list<T> list_; |
| std::unordered_map<T, typename decltype(list_)::iterator, T_Hasher> map_; |
| |
| UniqueQueue(const UniqueQueue&) = delete; |
| UniqueQueue& operator=(const UniqueQueue&) = delete; |
| }; |
| |
| } // namespace dlcservice |
| |
| #endif // DLCSERVICE_UNIQUE_QUEUE_H_ |