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