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 #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
00040 #define _GLIBCXX_VOLATILE volatile
00041
00042 namespace __gnu_parallel
00043 {
00044
00045
00046
00047
00048
00049
00050
00051 template<typename T>
00052 class RestrictedBoundedConcurrentQueue
00053 {
00054 private:
00055
00056 T* base;
00057
00058
00059 sequence_index_t max_size;
00060
00061
00062
00063 _GLIBCXX_VOLATILE lcas_t borders;
00064
00065 public:
00066
00067
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
00077 ~RestrictedBoundedConcurrentQueue()
00078 { delete[] base; }
00079
00080
00081
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
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
00098
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
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
00122
00123 bool
00124 pop_back(T& t)
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
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 }
00146
00147 #undef _GLIBCXX_VOLATILE
00148
00149 #endif