libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 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 T Contained element type. */ 00051 template<typename T> 00052 class RestrictedBoundedConcurrentQueue 00053 { 00054 private: 00055 /** @brief Array of elements, seen as cyclic buffer. */ 00056 T* base; 00057 00058 /** @brief Maximal number of elements contained at the same time. */ 00059 sequence_index_t max_size; 00060 00061 /** @brief Cyclic begin and end pointers contained in one 00062 atomically changeable value. */ 00063 _GLIBCXX_VOLATILE lcas_t 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(sequence_index_t max_size) 00069 { 00070 this->max_size = max_size; 00071 base = new T[max_size]; 00072 borders = encode2(0, 0); 00073 #pragma omp flush 00074 } 00075 00076 /** @brief Destructor. Not to be called concurrent, of course. */ 00077 ~RestrictedBoundedConcurrentQueue() 00078 { delete[] 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 T& t) 00084 { 00085 lcas_t former_borders = borders; 00086 int former_front, former_back; 00087 decode2(former_borders, former_front, former_back); 00088 *(base + former_front % max_size) = t; 00089 #if _GLIBCXX_ASSERTIONS 00090 // Otherwise: front - back > max_size eventually. 00091 _GLIBCXX_PARALLEL_ASSERT(((former_front + 1) - former_back) 00092 <= max_size); 00093 #endif 00094 fetch_and_add(&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(T& t) 00101 { 00102 int former_front, former_back; 00103 #pragma omp flush 00104 decode2(borders, former_front, former_back); 00105 while (former_front > former_back) 00106 { 00107 // Chance. 00108 lcas_t former_borders = encode2(former_front, former_back); 00109 lcas_t new_borders = encode2(former_front - 1, former_back); 00110 if (compare_and_swap(&borders, former_borders, new_borders)) 00111 { 00112 t = *(base + (former_front - 1) % max_size); 00113 return true; 00114 } 00115 #pragma omp flush 00116 decode2(borders, former_front, former_back); 00117 } 00118 return false; 00119 } 00120 00121 /** @brief Pops one element from the queue at the front end. 00122 * Must not be called concurrently with pop_front(). */ 00123 bool 00124 pop_back(T& t) //queue behavior 00125 { 00126 int former_front, former_back; 00127 #pragma omp flush 00128 decode2(borders, former_front, former_back); 00129 while (former_front > former_back) 00130 { 00131 // Chance. 00132 lcas_t former_borders = encode2(former_front, former_back); 00133 lcas_t new_borders = encode2(former_front, former_back + 1); 00134 if (compare_and_swap(&borders, former_borders, new_borders)) 00135 { 00136 t = *(base + former_back % max_size); 00137 return true; 00138 } 00139 #pragma omp flush 00140 decode2(borders, former_front, former_back); 00141 } 00142 return false; 00143 } 00144 }; 00145 } //namespace __gnu_parallel 00146 00147 #undef _GLIBCXX_VOLATILE 00148 00149 #endif /* _GLIBCXX_PARALLEL_QUEUE_H */