1*38fd1498Szrj // -*- C++ -*- 2*38fd1498Szrj 3*38fd1498Szrj // Copyright (C) 2007-2018 Free Software Foundation, Inc. 4*38fd1498Szrj // 5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free 6*38fd1498Szrj // software; you can redistribute it and/or modify it under the terms 7*38fd1498Szrj // of the GNU General Public License as published by the Free Software 8*38fd1498Szrj // Foundation; either version 3, or (at your option) any later 9*38fd1498Szrj // version. 10*38fd1498Szrj 11*38fd1498Szrj // This library is distributed in the hope that it will be useful, but 12*38fd1498Szrj // WITHOUT ANY WARRANTY; without even the implied warranty of 13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14*38fd1498Szrj // General Public License for more details. 15*38fd1498Szrj 16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional 17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version 18*38fd1498Szrj // 3.1, as published by the Free Software Foundation. 19*38fd1498Szrj 20*38fd1498Szrj // You should have received a copy of the GNU General Public License and 21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program; 22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*38fd1498Szrj // <http://www.gnu.org/licenses/>. 24*38fd1498Szrj 25*38fd1498Szrj /** @file parallel/queue.h 26*38fd1498Szrj * @brief Lock-free double-ended queue. 27*38fd1498Szrj * This file is a GNU parallel extension to the Standard C++ Library. 28*38fd1498Szrj */ 29*38fd1498Szrj 30*38fd1498Szrj // Written by Johannes Singler. 31*38fd1498Szrj 32*38fd1498Szrj #ifndef _GLIBCXX_PARALLEL_QUEUE_H 33*38fd1498Szrj #define _GLIBCXX_PARALLEL_QUEUE_H 1 34*38fd1498Szrj 35*38fd1498Szrj #include <parallel/types.h> 36*38fd1498Szrj #include <parallel/base.h> 37*38fd1498Szrj #include <parallel/compatibility.h> 38*38fd1498Szrj 39*38fd1498Szrj /** @brief Decide whether to declare certain variable volatile in this file. */ 40*38fd1498Szrj #define _GLIBCXX_VOLATILE volatile 41*38fd1498Szrj 42*38fd1498Szrj namespace __gnu_parallel 43*38fd1498Szrj { 44*38fd1498Szrj /**@brief Double-ended queue of bounded size, allowing lock-free 45*38fd1498Szrj * atomic access. push_front() and pop_front() must not be called 46*38fd1498Szrj * concurrently to each other, while pop_back() can be called 47*38fd1498Szrj * concurrently at all times. 48*38fd1498Szrj * @c empty(), @c size(), and @c top() are intentionally not provided. 49*38fd1498Szrj * Calling them would not make sense in a concurrent setting. 50*38fd1498Szrj * @param _Tp Contained element type. */ 51*38fd1498Szrj template<typename _Tp> 52*38fd1498Szrj class _RestrictedBoundedConcurrentQueue 53*38fd1498Szrj { 54*38fd1498Szrj private: 55*38fd1498Szrj /** @brief Array of elements, seen as cyclic buffer. */ 56*38fd1498Szrj _Tp* _M_base; 57*38fd1498Szrj 58*38fd1498Szrj /** @brief Maximal number of elements contained at the same time. */ 59*38fd1498Szrj _SequenceIndex _M_max_size; 60*38fd1498Szrj 61*38fd1498Szrj /** @brief Cyclic __begin and __end pointers contained in one 62*38fd1498Szrj atomically changeable value. */ 63*38fd1498Szrj _GLIBCXX_VOLATILE _CASable _M_borders; 64*38fd1498Szrj 65*38fd1498Szrj public: 66*38fd1498Szrj /** @brief Constructor. Not to be called concurrent, of course. 67*38fd1498Szrj * @param __max_size Maximal number of elements to be contained. */ _RestrictedBoundedConcurrentQueue(_SequenceIndex __max_size)68*38fd1498Szrj _RestrictedBoundedConcurrentQueue(_SequenceIndex __max_size) 69*38fd1498Szrj { 70*38fd1498Szrj _M_max_size = __max_size; 71*38fd1498Szrj _M_base = new _Tp[__max_size]; 72*38fd1498Szrj _M_borders = __encode2(0, 0); 73*38fd1498Szrj #pragma omp flush 74*38fd1498Szrj } 75*38fd1498Szrj 76*38fd1498Szrj /** @brief Destructor. Not to be called concurrent, of course. */ ~_RestrictedBoundedConcurrentQueue()77*38fd1498Szrj ~_RestrictedBoundedConcurrentQueue() 78*38fd1498Szrj { delete[] _M_base; } 79*38fd1498Szrj 80*38fd1498Szrj /** @brief Pushes one element into the queue at the front end. 81*38fd1498Szrj * Must not be called concurrently with pop_front(). */ 82*38fd1498Szrj void push_front(const _Tp & __t)83*38fd1498Szrj push_front(const _Tp& __t) 84*38fd1498Szrj { 85*38fd1498Szrj _CASable __former_borders = _M_borders; 86*38fd1498Szrj int __former_front, __former_back; 87*38fd1498Szrj __decode2(__former_borders, __former_front, __former_back); 88*38fd1498Szrj *(_M_base + __former_front % _M_max_size) = __t; 89*38fd1498Szrj #if _GLIBCXX_PARALLEL_ASSERTIONS 90*38fd1498Szrj // Otherwise: front - back > _M_max_size eventually. 91*38fd1498Szrj _GLIBCXX_PARALLEL_ASSERT(((__former_front + 1) - __former_back) 92*38fd1498Szrj <= _M_max_size); 93*38fd1498Szrj #endif 94*38fd1498Szrj __fetch_and_add(&_M_borders, __encode2(1, 0)); 95*38fd1498Szrj } 96*38fd1498Szrj 97*38fd1498Szrj /** @brief Pops one element from the queue at the front end. 98*38fd1498Szrj * Must not be called concurrently with pop_front(). */ 99*38fd1498Szrj bool pop_front(_Tp & __t)100*38fd1498Szrj pop_front(_Tp& __t) 101*38fd1498Szrj { 102*38fd1498Szrj int __former_front, __former_back; 103*38fd1498Szrj #pragma omp flush 104*38fd1498Szrj __decode2(_M_borders, __former_front, __former_back); 105*38fd1498Szrj while (__former_front > __former_back) 106*38fd1498Szrj { 107*38fd1498Szrj // Chance. 108*38fd1498Szrj _CASable __former_borders = __encode2(__former_front, 109*38fd1498Szrj __former_back); 110*38fd1498Szrj _CASable __new_borders = __encode2(__former_front - 1, 111*38fd1498Szrj __former_back); 112*38fd1498Szrj if (__compare_and_swap(&_M_borders, __former_borders, 113*38fd1498Szrj __new_borders)) 114*38fd1498Szrj { 115*38fd1498Szrj __t = *(_M_base + (__former_front - 1) % _M_max_size); 116*38fd1498Szrj return true; 117*38fd1498Szrj } 118*38fd1498Szrj #pragma omp flush 119*38fd1498Szrj __decode2(_M_borders, __former_front, __former_back); 120*38fd1498Szrj } 121*38fd1498Szrj return false; 122*38fd1498Szrj } 123*38fd1498Szrj 124*38fd1498Szrj /** @brief Pops one element from the queue at the front end. 125*38fd1498Szrj * Must not be called concurrently with pop_front(). */ 126*38fd1498Szrj bool pop_back(_Tp & __t)127*38fd1498Szrj pop_back(_Tp& __t) //queue behavior 128*38fd1498Szrj { 129*38fd1498Szrj int __former_front, __former_back; 130*38fd1498Szrj #pragma omp flush 131*38fd1498Szrj __decode2(_M_borders, __former_front, __former_back); 132*38fd1498Szrj while (__former_front > __former_back) 133*38fd1498Szrj { 134*38fd1498Szrj // Chance. 135*38fd1498Szrj _CASable __former_borders = __encode2(__former_front, 136*38fd1498Szrj __former_back); 137*38fd1498Szrj _CASable __new_borders = __encode2(__former_front, 138*38fd1498Szrj __former_back + 1); 139*38fd1498Szrj if (__compare_and_swap(&_M_borders, __former_borders, 140*38fd1498Szrj __new_borders)) 141*38fd1498Szrj { 142*38fd1498Szrj __t = *(_M_base + __former_back % _M_max_size); 143*38fd1498Szrj return true; 144*38fd1498Szrj } 145*38fd1498Szrj #pragma omp flush 146*38fd1498Szrj __decode2(_M_borders, __former_front, __former_back); 147*38fd1498Szrj } 148*38fd1498Szrj return false; 149*38fd1498Szrj } 150*38fd1498Szrj }; 151*38fd1498Szrj } //namespace __gnu_parallel 152*38fd1498Szrj 153*38fd1498Szrj #undef _GLIBCXX_VOLATILE 154*38fd1498Szrj 155*38fd1498Szrj #endif /* _GLIBCXX_PARALLEL_QUEUE_H */ 156