source: trunk/yat/utility/PriorityQueue.h @ 3792

Last change on this file since 3792 was 3792, checked in by Peter, 4 years ago

update copyright years

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