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