3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
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
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
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. */
58 class RestrictedBoundedConcurrentQueue
61 /** @brief Array of elements, seen as cyclic buffer. */
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
;
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);
82 /** @brief Destructor. Not to be called concurrent, of course. */
83 ~RestrictedBoundedConcurrentQueue()
86 /** @brief Pushes one element into the queue at the front end.
87 * Must not be called concurrently with pop_front(). */
89 push_front(const T
& t
)
91 lcas_t former_borders
= borders
;
92 int former_front
, former_back
;
93 decode2(former_borders
, former_front
, former_back
);
94 *(base
+ former_front
% max_size
) = t
;
95 #if _GLIBCXX_ASSERTIONS
96 // Otherwise: front - back > max_size eventually.
97 _GLIBCXX_PARALLEL_ASSERT(((former_front
+ 1) - former_back
)
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(). */
108 int former_front
, former_back
;
110 decode2(borders
, former_front
, former_back
);
111 while (former_front
> former_back
)
114 lcas_t former_borders
= encode2(former_front
, former_back
);
115 lcas_t new_borders
= encode2(former_front
- 1, former_back
);
116 if (compare_and_swap(&borders
, former_borders
, new_borders
))
118 t
= *(base
+ (former_front
- 1) % max_size
);
122 decode2(borders
, former_front
, former_back
);
127 /** @brief Pops one element from the queue at the front end.
128 * Must not be called concurrently with pop_front(). */
130 pop_back(T
& t
) //queue behavior
132 int former_front
, former_back
;
134 decode2(borders
, former_front
, former_back
);
135 while (former_front
> former_back
)
138 lcas_t former_borders
= encode2(former_front
, former_back
);
139 lcas_t new_borders
= encode2(former_front
, former_back
+ 1);
140 if (compare_and_swap(&borders
, former_borders
, new_borders
))
142 t
= *(base
+ former_back
% max_size
);
146 decode2(borders
, former_front
, former_back
);
151 } //namespace __gnu_parallel
153 #undef _GLIBCXX_VOLATILE
155 #endif /* _GLIBCXX_PARALLEL_QUEUE_H */