libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
priority_queue.hpp
Go to the documentation of this file.
1 /******************************************************************************
2 ** Copyright © 2004 by J.M.McGuiness, coder@hussar.me.uk
3 **
4 ** This library is free software; you can redistribute it and/or
5 ** modify it under the terms of the GNU Lesser General Public
6 ** License as published by the Free Software Foundation; either
7 ** version 2.1 of the License, or (at your option) any later version.
8 **
9 ** This library is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ** Lesser General Public License for more details.
13 **
14 ** You should have received a copy of the GNU Lesser General Public
15 ** License along with this library; if not, write to the Free Software
16 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 
19 #include "thread_safe_adaptors.hpp"
20 
21 #include "config.h"
22 
23 #include <queue>
24 
25 namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE { namespace ppd {
26 
27  /// A thread-safety-assisted adaptor for a priority_queue.
28  /**
29  The algorithmic complexities of the operations is based upon those of the input collection C.
30  By default the adapted collection does not use a read-write lock.
31  Note that if the read_lock_type and write_lock_types are the same, i.e. an exclusive lock were used, then the adaptor will exhibit EREW semantics. If a read-writer lock is used for them ,then it will exhibit CREW semantics.
32 
33  \see safe_colln
34  */
35  template<
36  typename C, ///< The collection to be adapted, usually std::set or std::multiset.
37  typename M, ///< The underlying lock object to use that will be locked in some (EREW or CREW or other) manner.
38  typename WL, ///< The type of write-lock to use. This allows the possibility of using a read-write lock.
39  class Sig, ///< Used to enable functionality to atomically signal if the collection contains work or not.
40  class ValRet=typename C::value_type ///< The type to return from remove items from the queue. This can be used to return a collection of items from the queue, in the order in which they were inserted.
41  >
42  class priority_queue : public safe_colln<C, M, WL, Sig, typename lock::any_order::all<M::lock_traits::api_type, typename M::lock_traits::model_type, M, M> > {
43  public:
44  typedef safe_colln<C, M, WL, Sig, typename lock::any_order::all<M::lock_traits::api_type, typename M::lock_traits::model_type, M, M> > base_t;
45  typedef typename base_t::thread_traits thread_traits;
46  typedef typename base_t::container_type container_type;
47  typedef typename base_t::write_lock_type write_lock_type;
48  typedef typename base_t::read_lock_type read_lock_type;
49  typedef typename base_t::atomic_t atomic_t;
50  typedef typename container_type::reference reference;
51  typedef typename container_type::const_reference const_reference;
52  typedef typename container_type::size_type size_type;
53  typedef typename container_type::value_type value_type;
54  typedef ValRet value_ret_type;
55 
56  constexpr priority_queue() noexcept(true) FORCE_INLINE
57  : base_t() {}
58  explicit priority_queue(typename base_t::have_work_type::atomic_t &a) noexcept(true) FORCE_INLINE
59  : base_t(a) {}
60 
61  void __fastcall push_back(value_type const &v) noexcept(true) FORCE_INLINE {
62  const write_lock_type lk(this->push_lock(), atomic_t::lock_traits::infinite_timeout());
63  this->colln().push(v);
64  this->have_work.add();
65  }
66  void __fastcall push_back(value_type &&v) noexcept(true) FORCE_INLINE {
67  const write_lock_type lk(this->push_lock(), atomic_t::lock_traits::infinite_timeout());
68  this->colln().push(v);
69  this->have_work.add();
70  }
71 
72  value_type __fastcall pop_front_1_nochk_nolk() noexcept(true) FORCE_INLINE {
73  const value_type ret(this->colln().top());
74  [[maybe_unused]] const typename base_t::have_work_type::atomic_t::lock_result_type work_lk_res=this->have_work.remove();
75  assert(work_lk_res.second!=base_t::have_work_type::lock_traits::atom_abandoned);
76  this->colln().pop();
77  return ret;
78  }
79  /**
80  This is used to return a collection of items from the signalled_work_queue, in the order in which they were inserted. At least one item will be returned, and if there are sufficient items in the signalled_work_queue, then max_size items will be returned. This implies that the thread that extracts items from the queue does the work in batching them.
81  This should only be used carefully! It isn't thread-safe!
82 
83  \return A batch of either one or max_size items.
84  */
85  value_ret_type __fastcall pop_front_nochk_nolk() noexcept(true) FORCE_INLINE {
86  value_ret_type ret;
87  typename value_ret_type::size_type i=0;
88  do {
89  ret[i]=this->pop_front_1_nochk_nolk();
90  } while (++i<ret.size() && this->colln().size()>=ret.size());
91  std::fill_n(ret.begin()+i, ret.size()-i, typename value_ret_type::value_type());
92  return ret;
93  }
94  value_type __fastcall pop_front_1_nochk_nosig() noexcept(true) FORCE_INLINE {
95  const write_lock_type lk(this->pop_lock(), atomic_t::lock_traits::infinite_timeout());
96  const value_type ret(this->colln().top());
97  this->colln().pop();
98  return ret;
99  }
100  value_ret_type __fastcall pop_front_nolk() noexcept(true) FORCE_INLINE {
101  return this->pop_front_nochk_nolk();
102  }
103  /**
104  \return The value popped off the queue.
105  */
106  value_ret_type __fastcall pop_front() noexcept(true) FORCE_INLINE {
107  const write_lock_type lk(this->pop_lock(), atomic_t::lock_traits::infinite_timeout());
108  return this->pop_front_nolk();
109  }
110  };
111 
112 } } }