queue.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef _GLIBCXX_PARALLEL_QUEUE_H
00039 #define _GLIBCXX_PARALLEL_QUEUE_H 1
00040
00041 #include <parallel/types.h>
00042 #include <parallel/base.h>
00043 #include <parallel/compatibility.h>
00044
00045
00046 #define _GLIBCXX_VOLATILE volatile
00047
00048 namespace __gnu_parallel
00049 {
00050
00051
00052
00053
00054
00055
00056
00057 template<typename T>
00058 class RestrictedBoundedConcurrentQueue
00059 {
00060 private:
00061
00062 T* base;
00063
00064
00065 sequence_index_t max_size;
00066
00067
00068
00069 _GLIBCXX_VOLATILE lcas_t borders;
00070
00071 public:
00072
00073
00074 RestrictedBoundedConcurrentQueue(sequence_index_t max_size)
00075 {
00076 this->max_size = max_size;
00077 base = new T[max_size];
00078 borders = encode2(0, 0);
00079 #pragma omp flush
00080 }
00081
00082
00083 ~RestrictedBoundedConcurrentQueue()
00084 { delete[] base; }
00085
00086
00087
00088 void
00089 push_front(const T& t)
00090 {
00091 lcas_t former_borders = borders;
00092 int former_front, former_back;
00093 decode2(former_borders, former_front, former_back);
00094 *(base + former_front % max_size) = t;
00095 #if _GLIBCXX_ASSERTIONS
00096
00097 _GLIBCXX_PARALLEL_ASSERT(((former_front + 1) - former_back)
00098 <= max_size);
00099 #endif
00100 fetch_and_add(&borders, encode2(1, 0));
00101 }
00102
00103
00104
00105 bool
00106 pop_front(T& t)
00107 {
00108 int former_front, former_back;
00109 #pragma omp flush
00110 decode2(borders, former_front, former_back);
00111 while (former_front > former_back)
00112 {
00113
00114 lcas_t former_borders = encode2(former_front, former_back);
00115 lcas_t new_borders = encode2(former_front - 1, former_back);
00116 if (compare_and_swap(&borders, former_borders, new_borders))
00117 {
00118 t = *(base + (former_front - 1) % max_size);
00119 return true;
00120 }
00121 #pragma omp flush
00122 decode2(borders, former_front, former_back);
00123 }
00124 return false;
00125 }
00126
00127
00128
00129 bool
00130 pop_back(T& t)
00131 {
00132 int former_front, former_back;
00133 #pragma omp flush
00134 decode2(borders, former_front, former_back);
00135 while (former_front > former_back)
00136 {
00137
00138 lcas_t former_borders = encode2(former_front, former_back);
00139 lcas_t new_borders = encode2(former_front, former_back + 1);
00140 if (compare_and_swap(&borders, former_borders, new_borders))
00141 {
00142 t = *(base + former_back % max_size);
00143 return true;
00144 }
00145 #pragma omp flush
00146 decode2(borders, former_front, former_back);
00147 }
00148 return false;
00149 }
00150 };
00151 }
00152
00153 #undef _GLIBCXX_VOLATILE
00154
00155 #endif