xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/parallel/queue.h (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
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