yat/utility/BasicQueue.h

Code
Comments
Other
Rev Date Author Line
3717 20 Nov 17 peter 1 #ifndef theplu_yat_utility_basic_queue
3717 20 Nov 17 peter 2 #define theplu_yat_utility_basic_queue
3717 20 Nov 17 peter 3
3717 20 Nov 17 peter 4 // $Id$
3717 20 Nov 17 peter 5
4346 24 Apr 23 peter 6 /*
4346 24 Apr 23 peter 7   Copyright (C) 2017, 2018, 2020, 2021, 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
3721 21 Nov 17 peter 25 #include "config_public.h"
3721 21 Nov 17 peter 26
3946 20 Jul 20 peter 27 #include <condition_variable>
4043 01 Mar 21 peter 28 #include <limits>
3946 20 Jul 20 peter 29 #include <mutex>
3717 20 Nov 17 peter 30
3717 20 Nov 17 peter 31 namespace theplu {
3717 20 Nov 17 peter 32 namespace yat {
3717 20 Nov 17 peter 33 namespace utility {
3717 20 Nov 17 peter 34 namespace detail {
3717 20 Nov 17 peter 35
3717 20 Nov 17 peter 36   /**
3717 20 Nov 17 peter 37      \internal Base class for Queue and PriorityQueue
3717 20 Nov 17 peter 38    */
3717 20 Nov 17 peter 39   template<class Derived, typename T, class Container>
3717 20 Nov 17 peter 40   class BasicQueue
3717 20 Nov 17 peter 41   {
3717 20 Nov 17 peter 42   public:
3717 20 Nov 17 peter 43     /// Type of object stored
3717 20 Nov 17 peter 44     typedef typename Container::value_type value_type;
3717 20 Nov 17 peter 45
3717 20 Nov 17 peter 46     /**
3717 20 Nov 17 peter 47        An unsigned integral type. \see size(void)
3717 20 Nov 17 peter 48     */
3717 20 Nov 17 peter 49     typedef typename Container::size_type size_type;
3717 20 Nov 17 peter 50
3717 20 Nov 17 peter 51     /**
3717 20 Nov 17 peter 52        Default constructor
3717 20 Nov 17 peter 53      */
4043 01 Mar 21 peter 54     BasicQueue(void)
4043 01 Mar 21 peter 55       : capacity_(std::numeric_limits<size_t>::max())
4043 01 Mar 21 peter 56     {}
3717 20 Nov 17 peter 57
3717 20 Nov 17 peter 58     /**
3717 20 Nov 17 peter 59        Copy constructor
3717 20 Nov 17 peter 60      */
3719 21 Nov 17 peter 61     BasicQueue(const BasicQueue& other)
3719 21 Nov 17 peter 62     {
3946 20 Jul 20 peter 63       std::unique_lock<std::mutex> lock(other.mutex_);
3719 21 Nov 17 peter 64       q_ = other.q_;
4043 01 Mar 21 peter 65       capacity_ = other.capacity_;
3719 21 Nov 17 peter 66     } // lock is released here
3717 20 Nov 17 peter 67
3717 20 Nov 17 peter 68     /**
3717 20 Nov 17 peter 69        Construct queue from underlying Container
3717 20 Nov 17 peter 70      */
4043 01 Mar 21 peter 71     explicit BasicQueue(const Container& container)
4043 01 Mar 21 peter 72       : q_(container), capacity_(std::numeric_limits<size_t>::max())
4043 01 Mar 21 peter 73     {}
3717 20 Nov 17 peter 74
4043 01 Mar 21 peter 75
3717 20 Nov 17 peter 76     /**
4043 01 Mar 21 peter 77        \return maximal number of element stored in container
4043 01 Mar 21 peter 78
4043 01 Mar 21 peter 79        \since New in yat 0.19
4043 01 Mar 21 peter 80      */
4043 01 Mar 21 peter 81     size_t capacity(void)
4043 01 Mar 21 peter 82     {
4043 01 Mar 21 peter 83       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 84       return capacity_;
4043 01 Mar 21 peter 85     }
4043 01 Mar 21 peter 86
4043 01 Mar 21 peter 87
4043 01 Mar 21 peter 88     /**
4043 01 Mar 21 peter 89        \brief change maximal number of element stored in container
4043 01 Mar 21 peter 90
4043 01 Mar 21 peter 91        \since New in yat 0.19
4043 01 Mar 21 peter 92     */
4043 01 Mar 21 peter 93     void capacity(size_t c)
4043 01 Mar 21 peter 94     {
4043 01 Mar 21 peter 95       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 96       capacity_ = c;
4043 01 Mar 21 peter 97
4043 01 Mar 21 peter 98       lock.unlock();
4043 01 Mar 21 peter 99       // Notify pushers that there is potentially space
4043 01 Mar 21 peter 100       push_condition_.notify_all();
4043 01 Mar 21 peter 101     }
4043 01 Mar 21 peter 102
4043 01 Mar 21 peter 103     /**
3717 20 Nov 17 peter 104        \brief clear queue
3717 20 Nov 17 peter 105
3717 20 Nov 17 peter 106        \since new in yat 0.15
3717 20 Nov 17 peter 107      */
3717 20 Nov 17 peter 108     void clear(void)
3717 20 Nov 17 peter 109     {
3946 20 Jul 20 peter 110       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 111       q_.clear();
4043 01 Mar 21 peter 112       lock.unlock(); // unlock the mutex
4043 01 Mar 21 peter 113
4043 01 Mar 21 peter 114       // Notify pushers that there is space to push
4043 01 Mar 21 peter 115       push_condition_.notify_all();
3717 20 Nov 17 peter 116     }
3717 20 Nov 17 peter 117
3717 20 Nov 17 peter 118
3717 20 Nov 17 peter 119     /**
3717 20 Nov 17 peter 120        \return \c true if container's size is zero
3717 20 Nov 17 peter 121      */
3717 20 Nov 17 peter 122     bool empty(void) const
3717 20 Nov 17 peter 123     {
3946 20 Jul 20 peter 124       std::unique_lock<std::mutex> lock(mutex_);
3717 20 Nov 17 peter 125       return q_.empty();
3717 20 Nov 17 peter 126     } // lock is released here
3717 20 Nov 17 peter 127
3717 20 Nov 17 peter 128
3717 20 Nov 17 peter 129     /**
3717 20 Nov 17 peter 130        \brief access next element in queue
3717 20 Nov 17 peter 131
3717 20 Nov 17 peter 132        Access the next element is queue. If container is empty,
3717 20 Nov 17 peter 133        process is waiting until other process is inserting element
3717 20 Nov 17 peter 134        into container.
3717 20 Nov 17 peter 135      */
3717 20 Nov 17 peter 136     void pop(T& value)
3717 20 Nov 17 peter 137     {
3946 20 Jul 20 peter 138       std::unique_lock<std::mutex> lock(mutex_);
3717 20 Nov 17 peter 139       while (q_.empty())
4043 01 Mar 21 peter 140         pop_condition_.wait(lock);
3717 20 Nov 17 peter 141       // The obvious choice would be to create a temp copy of front,
3717 20 Nov 17 peter 142       // pop the queue and then return by-value. This is, however,
3717 20 Nov 17 peter 143       // dangerous becasue if the copy constructor throws, the queue
3717 20 Nov 17 peter 144       // has been popped and the element is lost. Instead we choose to
3717 20 Nov 17 peter 145       // pass via passed reference.
3717 20 Nov 17 peter 146       static_cast<Derived*>(this)->pop_impl(value, lock);
4043 01 Mar 21 peter 147       lock.unlock(); // unlock the mutex
4043 01 Mar 21 peter 148       push_condition_.notify_one();
3717 20 Nov 17 peter 149     } // lock is released here
3717 20 Nov 17 peter 150
3717 20 Nov 17 peter 151
3717 20 Nov 17 peter 152     /**
3717 20 Nov 17 peter 153        \brief insert an element into container
4043 01 Mar 21 peter 154
4043 01 Mar 21 peter 155        If size of queue is equal (or greater) to its capacity, the
4043 01 Mar 21 peter 156        function is waiting until this is not the case.
3717 20 Nov 17 peter 157      */
3717 20 Nov 17 peter 158     void push(const T& t)
3717 20 Nov 17 peter 159     {
3946 20 Jul 20 peter 160       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 161       while (q_.size() >= capacity_)
4043 01 Mar 21 peter 162         push_condition_.wait(lock);
3717 20 Nov 17 peter 163       static_cast<Derived*>(this)->push_impl(t, lock);
3717 20 Nov 17 peter 164       lock.unlock(); // unlock the mutex
3717 20 Nov 17 peter 165
3717 20 Nov 17 peter 166       // Notify others that data is ready after we have unlocked
4043 01 Mar 21 peter 167       pop_condition_.notify_one();
3717 20 Nov 17 peter 168     }
3717 20 Nov 17 peter 169
3717 20 Nov 17 peter 170
3717 20 Nov 17 peter 171     /**
3717 20 Nov 17 peter 172        \brief insert an element into container
3717 20 Nov 17 peter 173
3717 20 Nov 17 peter 174        \since New in yat 0.15
3717 20 Nov 17 peter 175      */
3717 20 Nov 17 peter 176     void push(T&& t)
3717 20 Nov 17 peter 177     {
3946 20 Jul 20 peter 178       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 179       while (q_.size() >= capacity_)
4043 01 Mar 21 peter 180         push_condition_.wait(lock);
3717 20 Nov 17 peter 181       static_cast<Derived*>(this)->push_impl(std::move(t), lock);
3717 20 Nov 17 peter 182       lock.unlock(); // unlock the mutex
3717 20 Nov 17 peter 183
3717 20 Nov 17 peter 184       // Notify others that data is ready after we have unlocked
4043 01 Mar 21 peter 185       pop_condition_.notify_one();
3717 20 Nov 17 peter 186     }
3717 20 Nov 17 peter 187
3717 20 Nov 17 peter 188
3717 20 Nov 17 peter 189     /**
3717 20 Nov 17 peter 190        \return Number of elements stored in container
3717 20 Nov 17 peter 191      */
3717 20 Nov 17 peter 192     size_type size(void) const
3717 20 Nov 17 peter 193     {
3946 20 Jul 20 peter 194       std::unique_lock<std::mutex> lock(mutex_);
3717 20 Nov 17 peter 195       return q_.size();
3717 20 Nov 17 peter 196     } // lock is released here
3717 20 Nov 17 peter 197
3717 20 Nov 17 peter 198
3717 20 Nov 17 peter 199     /**
3717 20 Nov 17 peter 200        If Queue is empty() do nothing and return \c false, else pop
3717 20 Nov 17 peter 201        the element into \a value and return \c true
3717 20 Nov 17 peter 202      */
3717 20 Nov 17 peter 203     bool try_pop(T& value)
3717 20 Nov 17 peter 204     {
3946 20 Jul 20 peter 205       std::unique_lock<std::mutex> lock(mutex_);
3717 20 Nov 17 peter 206       if (q_.empty())
3717 20 Nov 17 peter 207         return false;
3717 20 Nov 17 peter 208       static_cast<Derived*>(this)->pop_impl(value, lock);
4043 01 Mar 21 peter 209       lock.unlock(); // unlock the mutex
4043 01 Mar 21 peter 210
4043 01 Mar 21 peter 211       // Notify others that data is ready after we have unlocked
4043 01 Mar 21 peter 212       push_condition_.notify_one();
3717 20 Nov 17 peter 213       return true;
3717 20 Nov 17 peter 214     } // lock is released here
3717 20 Nov 17 peter 215
4043 01 Mar 21 peter 216
4043 01 Mar 21 peter 217     /**
4043 01 Mar 21 peter 218        If Queue size is less than capacity push \a value and return \c
4043 01 Mar 21 peter 219        true; otherwise return \c false
4043 01 Mar 21 peter 220
4043 01 Mar 21 peter 221        \since New in yat 0.19
4043 01 Mar 21 peter 222      */
4043 01 Mar 21 peter 223     bool try_push(T& value)
4043 01 Mar 21 peter 224     {
4043 01 Mar 21 peter 225       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 226       if (q_.size() >= capacity_)
4043 01 Mar 21 peter 227         return false;
4043 01 Mar 21 peter 228       static_cast<Derived*>(this)->push_impl(value, lock);
4043 01 Mar 21 peter 229       lock.unlock(); // unlock the mutex
4043 01 Mar 21 peter 230
4043 01 Mar 21 peter 231       // Notify others that data is ready after we have unlocked
4043 01 Mar 21 peter 232       pop_condition_.notify_one();
4043 01 Mar 21 peter 233       return true;
4043 01 Mar 21 peter 234     } // lock is released here
4043 01 Mar 21 peter 235
4043 01 Mar 21 peter 236
4043 01 Mar 21 peter 237     /**
4043 01 Mar 21 peter 238        If Queue size is less than capacity push \a value and return \c
4043 01 Mar 21 peter 239        true; otherwise return \c false
4043 01 Mar 21 peter 240
4043 01 Mar 21 peter 241        \since New in yat 0.19
4043 01 Mar 21 peter 242      */
4043 01 Mar 21 peter 243     bool try_push(T&& value)
4043 01 Mar 21 peter 244     {
4043 01 Mar 21 peter 245       std::unique_lock<std::mutex> lock(mutex_);
4043 01 Mar 21 peter 246       if (q_.size() >= capacity_)
4043 01 Mar 21 peter 247         return false;
4043 01 Mar 21 peter 248       static_cast<Derived*>(this)->push_impl(std::move(value), lock);
4043 01 Mar 21 peter 249       lock.unlock(); // unlock the mutex
4043 01 Mar 21 peter 250
4043 01 Mar 21 peter 251       // Notify others that data is ready after we have unlocked
4043 01 Mar 21 peter 252       pop_condition_.notify_one();
4043 01 Mar 21 peter 253       return true;
4043 01 Mar 21 peter 254     } // lock is released here
4043 01 Mar 21 peter 255
3717 20 Nov 17 peter 256   protected:
3717 20 Nov 17 peter 257     /**
3717 20 Nov 17 peter 258        assign other to this
3717 20 Nov 17 peter 259      */
3717 20 Nov 17 peter 260     void assign(const BasicQueue& other)
3717 20 Nov 17 peter 261     {
3719 21 Nov 17 peter 262       if (this != &other) {
3946 20 Jul 20 peter 263         // std::lock guarantees that the two mutexes are locked in
3721 21 Nov 17 peter 264         // the same order regardless of passed order and thereby
3721 21 Nov 17 peter 265         // avoiding deadlock when two threads are calling
3721 21 Nov 17 peter 266         // lhs.assign(rhs) and rhs.assign(lhs) simultaneously.
3946 20 Jul 20 peter 267         std::lock(mutex_, other.mutex_);
3946 20 Jul 20 peter 268         std::unique_lock<std::mutex> lock(mutex_, std::adopt_lock_t());
3946 20 Jul 20 peter 269         std::unique_lock<std::mutex> other_lock(other.mutex_,
3946 20 Jul 20 peter 270                                                 std::adopt_lock_t());
3719 21 Nov 17 peter 271         q_ = other.q_;
4043 01 Mar 21 peter 272         capacity_ = other.capacity_;
3719 21 Nov 17 peter 273       }
3717 20 Nov 17 peter 274     }
3717 20 Nov 17 peter 275
3717 20 Nov 17 peter 276     /// data
3717 20 Nov 17 peter 277     Container q_;
3717 20 Nov 17 peter 278   private:
3946 20 Jul 20 peter 279     mutable std::mutex mutex_;
4043 01 Mar 21 peter 280     std::condition_variable pop_condition_;
4043 01 Mar 21 peter 281     std::condition_variable push_condition_;
4043 01 Mar 21 peter 282     size_t capacity_;
3717 20 Nov 17 peter 283   };
3717 20 Nov 17 peter 284
3717 20 Nov 17 peter 285 }}}}
3717 20 Nov 17 peter 286 #endif

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