replicode
pipe.h
Go to the documentation of this file.
1 /*
2  * HUMANOBS - mBrane
3  *
4  * Eric Nivel
5  * Center for Analysis and Design of Intelligent Agents
6  * Reykjavik University, Menntavegur 1, 101 Reykjavik, Iceland
7  * http://cadia.ru.is
8  * Copyright(c)2012
9  *
10  * This software was developed by the above copyright holder as part of
11  * the HUMANOBS EU research project, in collaboration with the
12  * following parties:
13  *
14  * Autonomous Systems Laboratory
15  * Technical University of Madrid, Spain
16  * http://www.aslab.org/
17  *
18  * Communicative Machines
19  * Edinburgh, United Kingdom
20  * http://www.cmlabs.com/
21  *
22  * Istituto Dalle Molle di Studi sull'Intelligenza Artificiale
23  * University of Lugano and SUPSI, Switzerland
24  * http://www.idsia.ch/
25  *
26  * Institute of Cognitive Sciences and Technologies
27  * Consiglio Nazionale delle Ricerche, Italy
28  * http://www.istc.cnr.it/
29  *
30  * Dipartimento di Ingegneria Informatica
31  * University of Palermo, Italy
32  * http://roboticslab.dinfo.unipa.it/index.php/Main/HomePage
33  *
34  *
35  * --- HUMANOBS Open-Source BSD License, with CADIA Clause v 1.0 ---
36  *
37  * Redistribution and use in source and binary forms, with or without
38  * modification, is permitted provided that the following conditions
39  * are met:
40  *
41  * - Redistributions of source code must retain the above copyright
42  * and collaboration notice, this list of conditions and the
43  * following disclaimer.
44  *
45  * - Redistributions in binary form must reproduce the above copyright
46  * notice, this list of conditions and the following
47  * disclaimer in the documentation and/or other materials provided
48  * with the distribution.
49  *
50  * - Neither the name of its copyright holders nor the names of its
51  * contributors may be used to endorse or promote products
52  * derived from this software without specific prior written permission.
53  *
54  * - CADIA Clause: The license granted in and to the software under this
55  * agreement is a limited-use license. The software may not be used in
56  * furtherance of:
57  * (i) intentionally causing bodily injury or severe emotional distress
58  * to any person;
59  * (ii) invading the personal privacy or violating the human rights of
60  * any person; or
61  * (iii) committing or preparing for any act of war.
62  *
63  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
64  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
65  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
66  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
67  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
68  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
69  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
70  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
71  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
72  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
73  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
74  */
75 
76 #ifndef core_pipe_h
77 #define core_pipe_h
78 
79 #include "utils.h"
80 
81 
82 #define PIPE_1
83 
84 namespace core
85 {
86 
87 // Pipes are thread safe, depending on their type:
88 // 11: 1 writer, 1 reader
89 // 1N: 1 writer, N readers
90 // N1: N writers, 1 reader
91 // NN: N writers, N readers
92 #ifdef PIPE_1
93 template<typename T, uint32_t _S> class Pipe11:
94  public Semaphore,
95  public CriticalSection
96 {
97 private:
98  class Block
99  {
100  public:
101  T buffer[_S * sizeof(T)];
103  Block(Block *prev): next(NULL)
104  {
105  if (prev) {
106  prev->next = this;
107  }
108  }
110  {
111  if (next) {
112  delete next;
113  }
114  }
115  };
116  int32_t head;
117  int32_t tail;
118  Block *first;
119  Block *last;
120  Block *spare;
121 protected:
122  void _clear();
123  T _pop();
124 public:
125  Pipe11();
126  ~Pipe11();
127  void clear();
128  void push(T &t); // increases the size as necessary
129  T pop(); // decreases the size as necessary
130 };
131 
132 template<typename T, uint32_t _S> class Pipe1N:
133  public Pipe11<T, _S>
134 {
135 private:
137 public:
138  Pipe1N();
139  ~Pipe1N();
140  void clear();
141  T pop();
142 };
143 
144 template<typename T, uint32_t _S> class PipeN1:
145  public Pipe11<T, _S>
146 {
147 private:
149 public:
150  PipeN1();
151  ~PipeN1();
152  void clear();
153  void push(T &t);
154 };
155 
156 template<typename T, uint32_t _S> class PipeNN:
157  public Pipe11<T, _S>
158 {
159 private:
162 public:
163  PipeNN();
164  ~PipeNN();
165  void clear();
166  void push(T &t);
167  T pop();
168 };
169 #elif defined PIPE_2
170 template<typename T, uint32_t _S, class Pipe> class Push1;
171 template<typename T, uint32_t _S, class Pipe> class PushN;
172 template<typename T, uint32_t _S, class Pipe> class Pop1;
173 template<typename T, uint32_t _S, class Pipe> class PopN;
174 
175 // a Pipe<T,_S> is a linked list of blocks containing _S objects of type T
176 // push() adds an object at the tail of the last block and moves the tail forward; when the tail reaches the end of the last block, a new block is appended to the list
177 // pop() moves the head forward and returns the object at this location; when the head reaches the end of the first block, this block is deallocated
178 // Synchronization between readers and writers is lock-free under no contention (reqCount), and uses a lock (Semaphore::) under contention
179 // single writer pipes can use an int32_t tail, whereas multiple writer versions require int32_t volatile tail; idem for readers
180 // The Head and Tail argument is meant to allow the parameterizing of heads and tails
181 // Push and Pop are functors tailored to the multiplicity of resp. the read and write threads
182 // P is the actual pipe class (e.g. Pipe11, etc.)
183 template<typename T, uint32_t _S, typename Head, typename Tail, class P, template<typename, uint32_t, class> class Push, template<typename, uint32_t, class> class Pop> class Pipe:
184  public Semaphore
185 {
186  template<typename T, uint32_t _S, class Pipe> friend class Push1;
187  template<typename T, uint32_t _S, class Pipe> friend class PushN;
188  template<typename T, uint32_t _S, class Pipe> friend class Pop1;
189  template<typename T, uint32_t _S, class Pipe> friend class PopN;
190 protected:
191  class Block
192  {
193  public:
194  T buffer[_S];
195  Block *next;
196  Block(Block *prev): next(NULL)
197  {
198  if (prev) {
199  prev->next = this;
200  }
201  }
202  ~Block()
203  {
204  if (next) {
205  delete next;
206  }
207  }
208  };
209  Block *first;
210  Block *last;
211  Block *spare; // pipes always retain a spare block: if a block is to be deallocated and there is no spare, it becomes the spare
212 
213  Head head; // starts at -1
214  Tail tail; // starts at 0
215  int32_t volatile waitingList; // amount of readers that have to wait, negative value indicate free lunch
216 
217  Push<T, _S, P> *_push;
218  Pop<T, _S, P> *_pop;
219 
220  void shrink(); // deallocates the first block when head reaches its end
221  void grow(); // allocate a new last block when tail reaches its end
222 
223  Pipe();
224 public:
225  ~Pipe();
226  void push(T &t);
227  T pop();
228 };
229 
230 template<class Pipe> class PipeFunctor
231 {
232 protected:
233  Pipe &const pipe;
234  PipeFunctor(Pipe &p);
235 };
236 
237 template<typename T, uint32_t _S, class Pipe> class Push1:
238  public PipeFunctor<Pipe>
239 {
240 public:
241  Push1(Pipe &p);
242  void operator()(T &t);
243 };
244 
245 template<typename T, uint32_t _S, class Pipe> class PushN:
246  public PipeFunctor<Pipe>,
247  public Semaphore
248 {
249 public:
250  PushN(Pipe &p);
251  void operator()(T &t);
252 };
253 
254 template<typename T, uint32_t _S, class Pipe> class Pop1:
255  public PipeFunctor<Pipe>
256 {
257 public:
258  Pop1(Pipe &p);
259  T operator()();
260 };
261 
262 template<typename T, uint32_t _S, class Pipe> class PopN:
263  public PipeFunctor<Pipe>,
264  public Semaphore
265 {
266 public:
267  PopN(Pipe &p);
268  T operator()();
269 };
270 
271 template<typename T, uint32_t S> class Pipe11:
272  public Pipe<T, S, int32_t, int32_t, Pipe11<T, S>, Push1, Pop1>
273 {
274 public:
275  Pipe11();
276  ~Pipe11();
277 };
278 
279 template<typename T, uint32_t S> class Pipe1N:
280  public Pipe<T, S, int32_t, int32_t volatile, Pipe1N<T, S>, Push1, PopN>
281 {
282 public:
283  Pipe1N();
284  ~Pipe1N();
285 };
286 
287 template<typename T, uint32_t S> class PipeN1:
288  public Pipe<T, S, int32_t volatile, int32_t, PipeN1<T, S>, PushN, Pop1>
289 {
290 public:
291  PipeN1();
292  ~PipeN1();
293 };
294 
295 template<typename T, uint32_t S> class PipeNN:
296  public Pipe<T, S, int32_t volatile, int32_t volatile, PipeNN<T, S>, PushN, PopN>
297 {
298 public:
299  PipeNN();
300  ~PipeNN();
301 };
302 #endif
303 }
304 
305 
306 #include "pipe.tpl.cpp"
307 
308 
309 #endif
Definition: utils.h:167
Block * last
Definition: pipe.h:119
Definition: base.cpp:81
int32_t head
Definition: pipe.h:116
Block * next
Definition: pipe.h:102
Definition: pipe.h:144
CriticalSection pushCS
Definition: pipe.h:160
CriticalSection popCS
Definition: pipe.h:136
Definition: utils.h:199
void push(T &t)
Block(Block *prev)
Definition: pipe.h:103
Block * first
Definition: pipe.h:118
~Block()
Definition: pipe.h:109
T buffer[_S *sizeof(T)]
Definition: pipe.h:101
Definition: pipe.h:132
CriticalSection pushCS
Definition: pipe.h:148
Definition: pipe.h:98
Definition: pipe.h:156
int32_t tail
Definition: pipe.h:117
void push(T &t)
void push(T &t)
Definition: pipe.h:93
Block * spare
Definition: pipe.h:120
CriticalSection popCS
Definition: pipe.h:161