libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/queue.h 00026 * @brief Lock-free double-ended queue. 00027 * This file is a GNU parallel extension to the Standard C++ Library. 00028 */ 00029 00030 // Written by Johannes Singler. 00031 00032 #ifndef _GLIBCXX_PARALLEL_QUEUE_H 00033 #define _GLIBCXX_PARALLEL_QUEUE_H 1 00034 00035 #include <parallel/types.h> 00036 #include <parallel/base.h> 00037 #include <parallel/compatibility.h> 00038 00039 /** @brief Decide whether to declare certain variable volatile in this file. */ 00040 #define _GLIBCXX_VOLATILE volatile 00041 00042 namespace __gnu_parallel 00043 { 00044 /**@brief Double-ended queue of bounded size, allowing lock-free 00045 * atomic access. push_front() and pop_front() must not be called 00046 * concurrently to each other, while pop_back() can be called 00047 * concurrently at all times. 00048 * @c empty(), @c size(), and @c top() are intentionally not provided. 00049 * Calling them would not make sense in a concurrent setting. 00050 * @param _Tp Contained element type. */ 00051 template<typename _Tp> 00052 class _RestrictedBoundedConcurrentQueue 00053 { 00054 private: 00055 /** @brief Array of elements, seen as cyclic buffer. */ 00056 _Tp* _M_base; 00057 00058 /** @brief Maximal number of elements contained at the same time. */ 00059 _SequenceIndex _M_max_size; 00060 00061 /** @brief Cyclic __begin and __end pointers contained in one 00062 atomically changeable value. */ 00063 _GLIBCXX_VOLATILE _CASable _M_borders; 00064 00065 public: 00066 /** @brief Constructor. Not to be called concurrent, of course. 00067 * @param __max_size Maximal number of elements to be contained. */ 00068 _RestrictedBoundedConcurrentQueue(_SequenceIndex __max_size) 00069 { 00070 _M_max_size = __max_size; 00071 _M_base = new _Tp[__max_size]; 00072 _M_borders = __encode2(0, 0); 00073 #pragma omp flush 00074 } 00075 00076 /** @brief Destructor. Not to be called concurrent, of course. */ 00077 ~_RestrictedBoundedConcurrentQueue() 00078 { delete[] _M_base; } 00079 00080 /** @brief Pushes one element into the queue at the front end. 00081 * Must not be called concurrently with pop_front(). */ 00082 void 00083 push_front(const _Tp& __t) 00084 { 00085 _CASable __former_borders = _M_borders; 00086 int __former_front, __former_back; 00087 __decode2(__former_borders, __former_front, __former_back); 00088 *(_M_base + __former_front % _M_max_size) = __t; 00089 #if _GLIBCXX_ASSERTIONS 00090 // Otherwise: front - back > _M_max_size eventually. 00091 _GLIBCXX_PARALLEL_ASSERT(((__former_front + 1) - __former_back) 00092 <= _M_max_size); 00093 #endif 00094 __fetch_and_add(&_M_borders, __encode2(1, 0)); 00095 } 00096 00097 /** @brief Pops one element from the queue at the front end. 00098 * Must not be called concurrently with pop_front(). */ 00099 bool 00100 pop_front(_Tp& __t) 00101 { 00102 int __former_front, __former_back; 00103 #pragma omp flush 00104 __decode2(_M_borders, __former_front, __former_back); 00105 while (__former_front > __former_back) 00106 { 00107 // Chance. 00108 _CASable __former_borders = __encode2(__former_front, 00109 __former_back); 00110 _CASable __new_borders = __encode2(__former_front - 1, 00111 __former_back); 00112 if (__compare_and_swap(&_M_borders, __former_borders, 00113 __new_borders)) 00114 { 00115 __t = *(_M_base + (__former_front - 1) % _M_max_size); 00116 return true; 00117 } 00118 #pragma omp flush 00119 __decode2(_M_borders, __former_front, __former_back); 00120 } 00121 return false; 00122 } 00123 00124 /** @brief Pops one element from the queue at the front end. 00125 * Must not be called concurrently with pop_front(). */ 00126 bool 00127 pop_back(_Tp& __t) //queue behavior 00128 { 00129 int __former_front, __former_back; 00130 #pragma omp flush 00131 __decode2(_M_borders, __former_front, __former_back); 00132 while (__former_front > __former_back) 00133 { 00134 // Chance. 00135 _CASable __former_borders = __encode2(__former_front, 00136 __former_back); 00137 _CASable __new_borders = __encode2(__former_front, 00138 __former_back + 1); 00139 if (__compare_and_swap(&_M_borders, __former_borders, 00140 __new_borders)) 00141 { 00142 __t = *(_M_base + __former_back % _M_max_size); 00143 return true; 00144 } 00145 #pragma omp flush 00146 __decode2(_M_borders, __former_front, __former_back); 00147 } 00148 return false; 00149 } 00150 }; 00151 } //namespace __gnu_parallel 00152 00153 #undef _GLIBCXX_VOLATILE 00154 00155 #endif /* _GLIBCXX_PARALLEL_QUEUE_H */