yat/utility/PriorityQueue.h

Code
Comments
Other
Rev Date Author Line
3399 30 Mar 15 peter 1 #ifndef theplu_yat_utility_priority_queue
3399 30 Mar 15 peter 2 #define theplu_yat_utility_priority_queue
3399 30 Mar 15 peter 3
3399 30 Mar 15 peter 4 // $Id$
3399 30 Mar 15 peter 5
4346 24 Apr 23 peter 6 /*
4346 24 Apr 23 peter 7   Copyright (C) 2015, 2016, 2017, 2018, 2019, 2020, 2023 Peter Johansson
4346 24 Apr 23 peter 8
4346 24 Apr 23 peter 9   This file is part of the yat library, https://dev.thep.lu.se/yat
4346 24 Apr 23 peter 10
4346 24 Apr 23 peter 11   The yat library is free software; you can redistribute it and/or
4346 24 Apr 23 peter 12   modify it under the terms of the GNU General Public License as
4346 24 Apr 23 peter 13   published by the Free Software Foundation; either version 3 of the
4346 24 Apr 23 peter 14   License, or (at your option) any later version.
4346 24 Apr 23 peter 15
4346 24 Apr 23 peter 16   The yat library is distributed in the hope that it will be useful,
4346 24 Apr 23 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
4346 24 Apr 23 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4346 24 Apr 23 peter 19   General Public License for more details.
4346 24 Apr 23 peter 20
4346 24 Apr 23 peter 21   You should have received a copy of the GNU General Public License
4346 24 Apr 23 peter 22   along with yat. If not, see <https://www.gnu.org/licenses/>.
4346 24 Apr 23 peter 23 */
4346 24 Apr 23 peter 24
3717 20 Nov 17 peter 25 #include "BasicQueue.h"
3722 21 Nov 17 peter 26 #include "utility.h"
3399 30 Mar 15 peter 27 #include "yat_assert.h"
3399 30 Mar 15 peter 28
3947 20 Jul 20 peter 29 #include <mutex>
3399 30 Mar 15 peter 30 #include <set>
3399 30 Mar 15 peter 31 #include <utility>
3399 30 Mar 15 peter 32
3399 30 Mar 15 peter 33 namespace theplu {
3399 30 Mar 15 peter 34 namespace yat {
3399 30 Mar 15 peter 35 namespace utility {
3399 30 Mar 15 peter 36
3399 30 Mar 15 peter 37   /**
3399 30 Mar 15 peter 38      \brief Multi-thread safe priority queue
3399 30 Mar 15 peter 39
3399 30 Mar 15 peter 40      This class provides a multi-thread safe priority_queue. The
3399 30 Mar 15 peter 41      PriorityQueue is typically shared by multiple threads such that
3399 30 Mar 15 peter 42      some threads push elements and some pop elements. The
3399 30 Mar 15 peter 43      PriorityQueue is a specifically designed so you can only access
3399 30 Mar 15 peter 44      the greatest element similar to<a
3399 30 Mar 15 peter 45      href="http://www.sgi.com/tech/stl/priority_queue.html">std::priority_queue</a>. The
3399 30 Mar 15 peter 46      difference is that Queue is multi-thread safe, in other words,
3399 30 Mar 15 peter 47      when one thread access the Queue, other threads are locked out
3399 30 Mar 15 peter 48      from access so that only one thread touches the Queue at a time
3399 30 Mar 15 peter 49      and its behaviour is well defined. In a single-thread application
3399 30 Mar 15 peter 50      there is no point in using the class as std::queue should be
3399 30 Mar 15 peter 51      prefereble.
3399 30 Mar 15 peter 52
3399 30 Mar 15 peter 53      \note Copy constructor and assignment are available but they are
3399 30 Mar 15 peter 54      not thread safe in the current implementation.
3399 30 Mar 15 peter 55
3399 30 Mar 15 peter 56      \since New in yat 0.13
3399 30 Mar 15 peter 57    */
3399 30 Mar 15 peter 58   template<typename T, class Compare = std::less<T> >
3399 30 Mar 15 peter 59   class PriorityQueue
3717 20 Nov 17 peter 60     : public detail::BasicQueue<PriorityQueue<T, Compare>
3717 20 Nov 17 peter 61                                 , T
3832 06 Aug 19 peter 62                                 , std::multiset<T, Compare> >
3399 30 Mar 15 peter 63   {
3718 21 Nov 17 peter 64     friend class detail::BasicQueue<PriorityQueue<T, Compare>
3832 06 Aug 19 peter 65                                     ,T,std::multiset<T,Compare> >;
3717 20 Nov 17 peter 66     typedef detail::BasicQueue<PriorityQueue<T, Compare>
3717 20 Nov 17 peter 67                                , T
3832 06 Aug 19 peter 68                                , std::multiset<T,Compare> > Base;
3399 30 Mar 15 peter 69   public:
3399 30 Mar 15 peter 70     /**
3399 30 Mar 15 peter 71        \brief Create a PriorityQueue with no elements
3399 30 Mar 15 peter 72     */
3399 30 Mar 15 peter 73     PriorityQueue(void) {}
3399 30 Mar 15 peter 74
3399 30 Mar 15 peter 75     /**
3403 31 Mar 15 peter 76        \brief Create a PriorityQueue with \a comp as Compare functor
3403 31 Mar 15 peter 77     */
3717 20 Nov 17 peter 78     explicit PriorityQueue(const Compare& comp)
3832 06 Aug 19 peter 79       : Base(std::multiset<T, Compare>(comp)) {}
3403 31 Mar 15 peter 80
3403 31 Mar 15 peter 81     /**
3399 30 Mar 15 peter 82        \brief Copy constructor
3399 30 Mar 15 peter 83     */
3717 20 Nov 17 peter 84     PriorityQueue(const PriorityQueue& other)
3717 20 Nov 17 peter 85       : Base(other) {}
3399 30 Mar 15 peter 86
3399 30 Mar 15 peter 87     /**
3399 30 Mar 15 peter 88        \brief assignment operator
3399 30 Mar 15 peter 89      */
3399 30 Mar 15 peter 90     PriorityQueue& operator=(const PriorityQueue& lhs)
3399 30 Mar 15 peter 91     {
3717 20 Nov 17 peter 92       this->assign(lhs);
3399 30 Mar 15 peter 93       return *this;
3719 21 Nov 17 peter 94     }
3399 30 Mar 15 peter 95
3399 30 Mar 15 peter 96   private:
3946 20 Jul 20 peter 97     void pop_impl(T& value, const std::unique_lock<std::mutex>& lock)
3399 30 Mar 15 peter 98     {
3399 30 Mar 15 peter 99       // The obvious choice would be to create a temp copy of front,
3399 30 Mar 15 peter 100       // pop the queue and then return by-value. This is, however,
3399 30 Mar 15 peter 101       // dangerous because if the copy constructor throws, the queue
3399 30 Mar 15 peter 102       // has been popped and the element is lost. Instead we choose to
3399 30 Mar 15 peter 103       // return via passed reference.
3832 06 Aug 19 peter 104       typename std::multiset<T, Compare>::iterator it = this->q_.end();
3717 20 Nov 17 peter 105       YAT_ASSERT(this->q_.size());
3399 30 Mar 15 peter 106       --it;
3955 23 Jul 20 peter 107       value = std::move_if_noexcept(*it);
3717 20 Nov 17 peter 108       this->q_.erase(it);
3399 30 Mar 15 peter 109     }
3508 21 Jul 16 peter 110
3946 20 Jul 20 peter 111     void push_impl(const T& value, std::unique_lock<std::mutex>& lock)
3508 21 Jul 16 peter 112     {
3717 20 Nov 17 peter 113       this->q_.insert(value);
3717 20 Nov 17 peter 114     }
3717 20 Nov 17 peter 115
3717 20 Nov 17 peter 116
3946 20 Jul 20 peter 117     void push_impl(T&& value, std::unique_lock<std::mutex>& lock)
3717 20 Nov 17 peter 118     {
3717 20 Nov 17 peter 119       this->q_.insert(std::move(value));
3717 20 Nov 17 peter 120     }
3399 30 Mar 15 peter 121   };
3399 30 Mar 15 peter 122
3399 30 Mar 15 peter 123 }}}
3399 30 Mar 15 peter 124 #endif

Generated on Sat Oct 14 02:25:10 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)