Merged with mainline at revision 128810.
[official-gcc.git] / libstdc++-v3 / include / parallel / queue.h
blob9d2143b5787eb59f46dd2db35d5d6adcce5520e2
1 // -*- C++ -*-
3 // Copyright (C) 2007 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 2, or (at your option) any later
9 // version.
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.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
29 // Public License.
31 /** @file parallel/queue.h
32 * @brief Lock-free double-ended queue.
33 * This file is a GNU parallel extension to the Standard C++ Library.
36 // Written by Johannes Singler.
38 #ifndef _GLIBCXX_PARALLEL_QUEUE_H
39 #define _GLIBCXX_PARALLEL_QUEUE_H 1
41 #include <parallel/types.h>
42 #include <parallel/base.h>
43 #include <parallel/compatibility.h>
45 /** @brief Decide whether to declare certain variable volatile in this file. */
46 #define _GLIBCXX_VOLATILE volatile
48 namespace __gnu_parallel
50 /**@brief Double-ended queue of bounded size, allowing lock-free
51 * atomic access. push_front() and pop_front() must not be called
52 * concurrently to each other, while pop_back() can be called
53 * concurrently at all times.
54 * @c empty(), @c size(), and @c top() are intentionally not provided.
55 * Calling them would not make sense in a concurrent setting.
56 * @param T Contained element type. */
57 template<typename T>
58 class RestrictedBoundedConcurrentQueue
60 private:
61 /** @brief Array of elements, seen as cyclic buffer. */
62 T* base;
64 /** @brief Maximal number of elements contained at the same time. */
65 sequence_index_t max_size;
67 /** @brief Cyclic begin and end pointers contained in one
68 atomically changeable value. */
69 _GLIBCXX_VOLATILE lcas_t borders;
71 public:
72 /** @brief Constructor. Not to be called concurrent, of course.
73 * @param max_size Maximal number of elements to be contained. */
74 RestrictedBoundedConcurrentQueue(sequence_index_t max_size)
76 this->max_size = max_size;
77 base = new T[max_size];
78 borders = encode2(0, 0);
79 #pragma omp flush
82 /** @brief Destructor. Not to be called concurrent, of course. */
83 ~RestrictedBoundedConcurrentQueue()
85 delete[] base;
88 /** @brief Pushes one element into the queue at the front end.
89 * Must not be called concurrently with pop_front(). */
90 void push_front(const T& t)
92 lcas_t former_borders = borders;
93 int former_front, former_back;
94 decode2(former_borders, former_front, former_back);
95 *(base + former_front % max_size) = t;
96 #if _GLIBCXX_ASSERTIONS
97 // Otherwise: front - back > max_size eventually.
98 _GLIBCXX_PARALLEL_ASSERT(((former_front + 1) - former_back) <= max_size);
99 #endif
100 fetch_and_add(&borders, encode2(1, 0));
103 /** @brief Pops one element from the queue at the front end.
104 * Must not be called concurrently with pop_front(). */
105 bool pop_front(T& t)
107 int former_front, former_back;
108 #pragma omp flush
109 decode2(borders, former_front, former_back);
110 while (former_front > former_back)
112 // Chance.
113 lcas_t former_borders = encode2(former_front, former_back);
114 lcas_t new_borders = encode2(former_front - 1, former_back);
115 if (compare_and_swap(&borders, former_borders, new_borders))
117 t = *(base + (former_front - 1) % max_size);
118 return true;
120 #pragma omp flush
121 decode2(borders, former_front, former_back);
123 return false;
126 /** @brief Pops one element from the queue at the front end.
127 * Must not be called concurrently with pop_front(). */
128 bool pop_back(T& t) //queue behavior
130 int former_front, former_back;
131 #pragma omp flush
132 decode2(borders, former_front, former_back);
133 while (former_front > former_back)
135 // Chance.
136 lcas_t former_borders = encode2(former_front, former_back);
137 lcas_t new_borders = encode2(former_front, former_back + 1);
138 if (compare_and_swap(&borders, former_borders, new_borders))
140 t = *(base + former_back % max_size);
141 return true;
143 #pragma omp flush
144 decode2(borders, former_front, former_back);
146 return false;
149 } //namespace __gnu_parallel
151 #undef _GLIBCXX_VOLATILE
153 #endif