parallel_foreach.hpp 24.1 KB
Newer Older
Sylvain Thery's avatar
Sylvain Thery committed
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
Sylvain Thery's avatar
Sylvain Thery committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                           *
Sylvain Thery's avatar
Sylvain Thery committed
21
22
23
24
25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/
#include <boost/thread.hpp>
#include <boost/thread/barrier.hpp>
sylvain thery's avatar
sylvain thery committed
26
#include <vector>
Sylvain Thery's avatar
Sylvain Thery committed
27

28

Sylvain Thery's avatar
Sylvain Thery committed
29
30
31
32
33
34
35
36
37
namespace CGoGN
{

namespace Algo
{

namespace Parallel
{

38
/// internal functor for boost call
39
class ThreadFunctionAttrib
40
41
{
protected:
42
	std::vector<unsigned int>& m_ids;
43
44
45
	boost::barrier& m_sync1;
	boost::barrier& m_sync2;
	bool& m_finished;
46
47
48
	unsigned int m_id;
	FunctorAttribThreaded* m_functor;

49
public:
50
51
	ThreadFunctionAttrib(FunctorAttribThreaded* func, std::vector<unsigned int>& vid, boost::barrier& s1, boost::barrier& s2, bool& finished, unsigned int id):
		m_ids(vid), m_sync1(s1), m_sync2(s2), m_finished(finished), m_id(id), m_functor(func)
52
53
54
	{
	}

55
56
	ThreadFunctionAttrib(const ThreadFunctionAttrib& tf):
		m_ids(tf.m_ids), m_sync1(tf.m_sync1), m_sync2(tf.m_sync2), m_finished(tf.m_finished), m_id(tf.m_id), m_functor(tf.m_functor){}
57
58
59
60
61

	void operator()()
	{
		while (!m_finished)
		{
62
			for (std::vector<unsigned int>::const_iterator it = m_ids.begin(); it != m_ids.end(); ++it)
63
				m_functor->run(*it,m_id);
64
65
66
67
			m_sync1.wait();
			m_sync2.wait();
		}
	}
68
69
};

70

71
/// internal functor for boost call
72
73
template<typename MAP>
class ThreadFunction
Sylvain Thery's avatar
Sylvain Thery committed
74
75
{
protected:
76
	std::vector<Dart>& m_darts;
Sylvain Thery's avatar
Sylvain Thery committed
77
78
79
	boost::barrier& m_sync1;
	boost::barrier& m_sync2;
	bool& m_finished;
80
81
	unsigned int m_id;
	FunctorMapThreaded<MAP>* m_functor;
Sylvain Thery's avatar
Sylvain Thery committed
82
public:
83
84
	ThreadFunction(FunctorMapThreaded<MAP>* func, std::vector<Dart>& vd, boost::barrier& s1, boost::barrier& s2, bool& finished, unsigned int id):
		m_darts(vd), m_sync1(s1), m_sync2(s2), m_finished(finished), m_id(id), m_functor(func)
85
86
87
	{
	}

88
89
	ThreadFunction(const ThreadFunction<MAP>& tf):
		m_darts(tf.m_darts), m_sync1(tf.m_sync1), m_sync2(tf.m_sync2), m_finished(tf.m_finished), m_id(tf.m_id), m_functor(tf.m_functor){}
Sylvain Thery's avatar
Sylvain Thery committed
90
91
92
93
94
95

	void operator()()
	{
		while (!m_finished)
		{
			for (std::vector<Dart>::const_iterator it = m_darts.begin(); it != m_darts.end(); ++it)
96
				m_functor->run(*it,m_id);
Sylvain Thery's avatar
Sylvain Thery committed
97
98
99
100
101
102
			m_sync1.wait();
			m_sync2.wait();
		}
	}
};

103

104
105
106
107
108
109
inline unsigned int nbThreads()
{
	return boost::thread::hardware_concurrency();
}


110
inline unsigned int optimalNbThreads(NbParam p)
Sylvain Thery's avatar
Sylvain Thery committed
111
{
112
113
114
115
116
117
118
119
	if (p==NB_HIGHCOMPUTE)
		return nbThreads();
	if (p==NB_VERYHIGHMEMORY)
		return 2;

 // NB_HIGHMEMORY
	if (NBCORES != 0)
		return NBCORES;
120
121
122
123
	unsigned int nb = nbThreads();
	if (nb>4)
		return nb/2 ;
	return nb;
124

125
}
Sylvain Thery's avatar
Sylvain Thery committed
126
127


128

129
template <typename MAP, unsigned int ORBIT>
130
void foreach_cell(MAP& map, FunctorMapThreaded<MAP>& func, unsigned int nbth, bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
131
132
133
{
	if (nbth == 0)
		nbth = optimalNbThreads();
Sylvain Thery's avatar
Sylvain Thery committed
134

135
136
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);
137

138
139
140
	FunctorMapThreaded<MAP>* ptr = func.duplicate();
	bool shared = (ptr == NULL);

141
	if (shared)
142
	{
143
		for (unsigned int i = 0; i < nbth; ++i)
144
			funcs.push_back(&func);
145
146
147
	}
	else
	{
148
149
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
150
			funcs.push_back(func.duplicate());
151
	}
Sylvain Thery's avatar
Sylvain Thery committed
152

153
	foreach_cell<MAP,ORBIT>(map,funcs,needMarkers,good,currentThread);
Sylvain Thery's avatar
Sylvain Thery committed
154

155
	if (!shared)
156
		for (unsigned int i = 0; i < nbth; ++i)
157
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
158
159
}

160
template <typename MAP, unsigned int ORBIT>
161
void foreach_cell(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcs, bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
Sylvain Thery's avatar
Sylvain Thery committed
162
{
163
	unsigned int nbth = funcs.size();
164

sylvain thery's avatar
sylvain thery committed
165
166
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
	boost::thread** threads = new boost::thread*[nbth];
Sylvain Thery's avatar
Sylvain Thery committed
167
168

	// nbth new functions, new thread (with good darts !)
169
	for (unsigned int i = 0; i < nbth; ++i)
170
		vd[i].reserve(SIZE_BUFFER_THREAD);
Sylvain Thery's avatar
Sylvain Thery committed
171

172
173
174
175
176
177
178
179
180
181
	AttributeContainer* cont = NULL;
	DartMarker* dmark = NULL;
	CellMarker<ORBIT>* cmark = NULL;
	AttributeMultiVector<Dart>* quickTraversal = map.template getQuickTraversal<ORBIT>() ;

	// fill each vd buffers with SIZE_BUFFER_THREAD darts
	Dart d;
	unsigned int di=0;

	if(quickTraversal != NULL)
Sylvain Thery's avatar
Sylvain Thery committed
182
	{
183
184
185
186
187
		cont = &(map.template getAttributeContainer<ORBIT>()) ;

		di = cont->begin();
		unsigned int nb = 0;
		while ((di != cont->end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
Sylvain Thery's avatar
Sylvain Thery committed
188
		{
189
190
191
192
193
194
195
			d = quickTraversal->operator[](di);
			if (good(d))
			{
				vd[nb%nbth].push_back(d);
				nb++;
			}
			cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
196
197
		}
	}
198
	else
199
	{
200
201
202
203
204
205
206
207
		if(map.template isOrbitEmbedded<ORBIT>())
		{
			cmark = new CellMarker<ORBIT>(map, currentThread) ;

			d = map.begin();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
208
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
				{
					cmark->mark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
		else
		{
			dmark = new DartMarker(map, currentThread) ;
			d = map.begin();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
224
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
225
226
227
228
229
230
231
232
				{
					dmark->markOrbit<ORBIT>(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
233
234
	}

Sylvain Thery's avatar
Sylvain Thery committed
235
236
237
238
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished=false;
	// lauch threads
239
240
	if (needMarkers)
	{
241
242
243
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
244
	}
245
246
247
248

	for (unsigned int i = 0; i < nbth; ++i)
		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd[i],sync1,sync2, finished,1+i));

Sylvain Thery's avatar
Sylvain Thery committed
249
	// and continue to traverse the map
sylvain thery's avatar
sylvain thery committed
250
251
	std::vector<Dart>* tempo = new std::vector<Dart>[nbth];

252
	for (unsigned int i = 0; i < nbth; ++i)
253
		tempo[i].reserve(SIZE_BUFFER_THREAD);
Sylvain Thery's avatar
Sylvain Thery committed
254
255


256
257
258
	if (cont)
	{
		while (di != cont->end())
Sylvain Thery's avatar
Sylvain Thery committed
259
		{
260
261
262
263
			for (unsigned int i = 0; i < nbth; ++i)
				tempo[i].clear();
			unsigned int nb = 0;
			while ((di != cont->end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
Sylvain Thery's avatar
Sylvain Thery committed
264
			{
265
266
267
268
269
270
271
				d = quickTraversal->operator[](di);
				if (good(d))
				{
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
272
			}
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
			sync1.wait();
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].swap(tempo[i]);
			sync2.wait();
		}
	}
	else if (cmark)
	{
		while (d != map.end())
		{
			for (unsigned int i = 0; i < nbth; ++i)
				tempo[i].clear();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
288
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
				{
					cmark->mark(d);
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].swap(tempo[i]);
			sync2.wait();
		}
	}
	else
	{
		while (d != map.end())
		{
			for (unsigned int i = 0; i < nbth; ++i)
				tempo[i].clear();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
311
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
312
313
314
315
316
317
318
319
320
321
322
				{
					dmark->markOrbit<ORBIT>(d);
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].swap(tempo[i]);
			sync2.wait();
Sylvain Thery's avatar
Sylvain Thery committed
323
324
325
326
327
328
329
330
		}
	}

	sync1.wait();
	finished = true;
	sync2.wait();

	//wait for all theads to be finished
331
	for (unsigned int i = 0; i < nbth; ++i)
Sylvain Thery's avatar
Sylvain Thery committed
332
333
334
335
	{
		threads[i]->join();
		delete threads[i];
	}
sylvain thery's avatar
sylvain thery committed
336
337
338
	delete[] threads;
	delete[] vd;
	delete[] tempo;
Sylvain Thery's avatar
Sylvain Thery committed
339

340
341
	if (cmark != NULL)
		delete cmark;
Sylvain Thery's avatar
Sylvain Thery committed
342

343
344
345
	if (dmark != NULL)
		delete dmark;
}
Sylvain Thery's avatar
Sylvain Thery committed
346
347
348



349
template <typename MAP>
350
void foreach_dart(MAP& map, FunctorMapThreaded<MAP>& func, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
351
352
353
{
	if (nbth == 0)
		nbth = optimalNbThreads();
354

355
356
357
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);

358
359
360
	FunctorMapThreaded<MAP>* ptr = func.duplicate();
	bool shared = (ptr == NULL);

361
	if (shared)
362
	{
363
		for (unsigned int i = 0; i < nbth; ++i)
364
			funcs.push_back(&func);
365
366
367
	}
	else
	{
368
369
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
370
			funcs.push_back(func.duplicate());
371
	}
Sylvain Thery's avatar
Sylvain Thery committed
372

373
	foreach_dart<MAP>(map,funcs,needMarkers,good);
Sylvain Thery's avatar
Sylvain Thery committed
374

375
	if (!shared)
376
		for (unsigned int i = 0; i < nbth; ++i)
377
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
378
379
}

380
381

template <typename MAP>
382
void foreach_dart(MAP& map, std::vector<FunctorMapThreaded<MAP>*> funcs, bool needMarkers, const FunctorSelect& good)
383
{
384
	unsigned int nbth = funcs.size();
385

386
387
388
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
	boost::thread** threads = new boost::thread*[nbth];

389
	Dart d = map.begin();
390
391

	// nbth new functions, new thread (with good darts !)
392
	for (unsigned int i = 0; i < nbth; ++i)
393
		vd[i].reserve(SIZE_BUFFER_THREAD);
394
395

	// fill each vd buffers with 4096 darts
396
	unsigned int nb = 0;
397
	while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
398
	{
399
		if (good(d))
400
401
402
403
404
405
406
		{
			vd[nb%nbth].push_back(d);
			nb++;
		}
		map.next(d);
	}

407
408
409
410
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished = false;
	// lauch threads
411
412
413
414
415
416
417
	if (needMarkers)
	{
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

418
	for (unsigned int i = 0; i < nbth; ++i)
419
	{
420
		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd[i],sync1,sync2, finished,1+i));
421
422
423
424
	}

	// and continue to traverse the map
	std::vector<Dart>* tempo = new std::vector<Dart>[nbth];
425
	for (unsigned int i = 0; i < nbth; ++i)
426
		tempo[i].reserve(SIZE_BUFFER_THREAD);
427

428
	while (d != map.end())
429
	{
430
		for (unsigned int i = 0; i < nbth; ++i)
431
432
			tempo[i].clear();

433
434
		unsigned int nb =0;
		while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
435
		{
436
			if (good(d))
437
438
439
440
441
442
443
444
			{
				tempo[nb%nbth].push_back(d);
				nb++;
			}
			map.next(d);
		}

		sync1.wait();
445
		for (unsigned int i = 0; i < nbth; ++i)
446
447
448
449
450
451
452
453
			vd[i].swap(tempo[i]);
		sync2.wait();
	}

	sync1.wait();
	finished = true;
	sync2.wait();

454
	//wait for all theads to be finished
455
	for (unsigned int i = 0; i < nbth; ++i)
456
457
458
459
	{
		threads[i]->join();
		delete threads[i];
	}
460
461
462
463
	
	delete vd;
	delete threads;
	delete tempo;
464
465
466
}


467
// TODO same modification for transparent usage of dart marker / cell marker / quick traversal ??
468

469
template <typename MAP, unsigned int CELL>
470
void foreach_cell2Pass(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcsFrontnBack, unsigned int nbLoops, bool needMarkers, const FunctorSelect& good)
471
{
472
473
	unsigned int nbth = funcsFrontnBack.size()/2;

474
	std::vector<Dart>* vd = new std::vector<Dart>[2*nbth];
475
	for (unsigned int i = 0; i < nbth; ++i)
476
		vd[i].reserve(SIZE_BUFFER_THREAD);
477

478
	boost::thread** threadsAB = new boost::thread*[2*nbth];
479
480
481
482
483
484
485
486
487

	if (needMarkers)
	{
		// ensure that there is enough threads
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

488
489
490
491
	CellMarkerNoUnmark<CELL> cm(map); // for 2 pass front mark / back unmark

	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
492
493
494
495
496
497

	for (unsigned int loop=0; loop< nbLoops; ++loop)
	{
		// PASS FRONT (A)
		{
			Dart d = map.begin();
498
			// fill each vd buffers with SIZE_BUFFER_THREAD darts
499
			unsigned int nb = 0;
500
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
501
502
503
504
505
506
507
508
509
510
511
			{
				if (good(d) && (!cm.isMarked(d)))
				{
					cm.mark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}

			bool finished=false;
512
513
514
515

			for (unsigned int i = 0; i < nbth; ++i)
				threadsAB[i] = new boost::thread(ThreadFunction<MAP>(funcsFrontnBack[i], vd[i], sync1, sync2, finished,1+i));

516
517
518
			while (d != map.end())
			{
				for (unsigned int i = 0; i < nbth; ++i)
519
					vd[nbth+i].clear();
520
521

				unsigned int nb = 0;
522
				while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
523
524
525
526
				{
					if (good(d) && (!cm.isMarked(d)))
					{
						cm.mark(d);
527
						vd[nbth+nb%nbth].push_back(d);
528
529
530
531
532
533
534
						nb++;
					}
					map.next(d);
				}

				sync1.wait();
				for (unsigned int i = 0; i < nbth; ++i)
535
					vd[i].swap(vd[nbth+i]);
536
537
538
539
540
541
542
543
544
				sync2.wait();
			}

			sync1.wait();
			finished = true;
			sync2.wait();

			//wait for all theads to be finished
			for (unsigned int i = 0; i < nbth; ++i)
545
				threadsAB[i]->join();
546
547
548
549
550
551
		}
		// PASS BACK (B)
		{
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].clear();
			Dart d = map.begin();
552
			// fill each vd buffers with SIZE_BUFFER_THREAD darts
553
			unsigned int nb = 0;
554
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
555
556
557
558
559
560
561
562
563
564
565
			{
				if (good(d) && (cm.isMarked(d)))
				{
					cm.unmark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}

			bool finished=false;
566
567
568
			for (unsigned int i = 0; i < nbth; ++i)
				threadsAB[nbth+i] = new boost::thread(ThreadFunction<MAP>(funcsFrontnBack[nbth+i], vd[i],sync1,sync2, finished,1+i));

569
570
571
572
573
			// and continue to traverse the map

			while (d != map.end())
			{
				for (unsigned int i = 0; i < nbth; ++i)
574
					vd[nbth+i].clear();
575
576

				unsigned int nb = 0;
577
				while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
578
579
580
581
				{
					if (good(d) && (cm.isMarked(d)))
					{
						cm.unmark(d);
582
						vd[nbth+nb%nbth].push_back(d);
583
584
585
586
587
588
589
						nb++;
					}
					map.next(d);
				}

				sync1.wait();
				for (unsigned int i = 0; i < nbth; ++i)
590
					vd[i].swap(vd[nbth+i]);
591
592
593
594
595
596
597
598
599
				sync2.wait();
			}

			sync1.wait();
			finished = true;
			sync2.wait();

			//wait for all theads to be finished
			for (unsigned int i = 0; i < nbth; ++i)
600
				threadsAB[nbth+i]->join();
601
602
603
604
		}
	}

	// free buffers and threads
605
	for (unsigned int i = 0; i < 2*nbth; ++i)
606
	{
607
		delete threadsAB[i];
608
	}
609
	delete[] threadsAB;
610
611
612
613
614
	delete[] vd;
}



615
template <typename MAP, unsigned int CELL>
616
void foreach_cell2Pass(MAP& map, FunctorMapThreaded<MAP>& funcFront, FunctorMapThreaded<MAP>& funcBack, unsigned int nbLoops, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
617
618
619
{
	if (nbth == 0)
		nbth = optimalNbThreads();
620

621
622
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);
623

624
625
626
	FunctorMapThreaded<MAP>* ptr = funcFront.duplicate();
	bool shared = (ptr == NULL);

627
628
629
630
631
632
633
634
635
	if (shared)
	{
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(&funcFront);
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(&funcBack);
	}
	else
	{
636
637
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
638
639
640
			funcs.push_back(funcFront.duplicate());
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(funcBack.duplicate());
641

642
	}
643

644
	foreach_cell2Pass<MAP,CELL>(map,funcs,nbLoops,needMarkers,good);
645

646
	if (!shared)
647
		for (unsigned int i = 0; i < 2*nbth; ++i)
648
649
			delete funcs[i];
}
650

651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
//
//
//template <typename MAP>
//void Foreach<MAP>::Foreach(MAP& map, unsigned int nbth):
//m_nbth(nbth)
//{
//	if (m_nbth == 0)
//		m_nbth = optimalNbThreads();
//
//	m_funcs.reserve(m_nbth);
//
//	m_vd = new std::vector<Dart>[2*nbth];
//	for (unsigned int i = 0; i < 2*nbth; ++i)
//		m_vd[i].reserve(SIZE_BUFFER_THREAD);
//}
//
//template <typename MAP>
//Foreach<MAP>::~Foreach(MAP& map, unsigned int nbth)
//{
//	delete[] m_vd;
//}
//
//
//template <typename MAP>
//void Foreach<MAP>:: clearFunctors()
//{
//	m_funcs.clear();
//}
//
//template <typename MAP>
//void Foreach<MAP>:: addFunctor(FunctorMapThreaded<MAP>* funcPtr)
//{
//	m_funcs.push_back(funcPtr);
//}
//
//template <typename MAP>
//template<typename T>
//T* Foreach<MAP>::getFunctor(unsigned int i)
//{
//	assert(i < m_funcs.size());
//	return dynamic_cast<T*>(m_funcs[i]);
//}
//
//
//template <typename MAP>
//template <unsigned int ORBIT>
//void Foreach<MAP>::traverseCell<ORBIT>(bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
//{
//	assert(m_funcs.size() ==  m_nbth);
//
//	boost::thread** threads = new boost::thread*[m_nbth];
//
//	AttributeContainer* cont = NULL;
//	DartMarker* dmark = NULL;
//	CellMarker<ORBIT>* cmark = NULL;
//	AttributeMultiVector<Dart>* quickTraversal = m_map.template getQuickTraversal<ORBIT>() ;
//
//	// fill each vd buffers with SIZE_BUFFER_THREAD darts
//	Dart d;
//	unsigned int di=0;
//
//	if(quickTraversal != NULL)
//	{
//		cont = &(m_map.template getAttributeContainer<ORBIT>()) ;
//
//		di = cont->begin();
//		unsigned int nb = 0;
//		while ((di != cont->end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//		{
//			d = quickTraversal->operator[](di);
//			if (good(d))
//			{
//				m_vd[nb%m_nbth].push_back(d);
//				nb++;
//			}
//			cont->next(di);
//		}
//	}
//	else
//	{
//		if(m_map.template isOrbitEmbedded<ORBIT>())
//		{
//			cmark = new CellMarker<ORBIT>(m_map, currentThread) ;
//
//			d = m_map.begin();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
//				{
//					cmark->mark(d);
//					m_vd[nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//		}
//		else
//		{
//			dmark = new DartMarker(m_map, currentThread) ;
//			d = m_map.begin();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
//				{
//					dmark->markOrbit<ORBIT>(d);
//					m_vd[nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//		}
//	}
//
//	boost::barrier sync1(m_nbth+1);
//	boost::barrier sync2(m_nbth+1);
//	bool finished=false;
//	// lauch threads
//	if (needMarkers)
//	{
//		unsigned int nbth_prec = m_map.getNbThreadMarkers();
//		if (nbth_prec < m_nbth+1)
//			m_map.addThreadMarker(m_nbth+1-nbth_prec);
//	}
//
//	for (unsigned int i = 0; i < m_nbth; ++i)
//		threads[i] = new boost::thread(ThreadFunction<MAP>(m_funcs[i], m_vd[i],sync1,sync2, finished,1+i));
//
//
//	if (cont)
//	{
//		while (di != cont->end())
//		{
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[m_nbth+i].clear();
//			unsigned int nb = 0;
//			while ((di != cont->end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				d = quickTraversal->operator[](di);
//				if (good(d))
//				{
//					m_vd[m_nbth + nb%m_nbth].push_back(d);
//					nb++;
//				}
//				cont->next(di);
//			}
//			sync1.wait();
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[i].swap(m_vd[m_nbth+i]);
//			sync2.wait();
//		}
//	}
//	else if (cmark)
//	{
//		while (d != m_map.end())
//		{
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[m_nbth+i].clear();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
//				{
//					cmark->mark(d);
//					m_vd[m_nbth+nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//			sync1.wait();
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[i].swap(m_vd[m_nbth+i]);
//			sync2.wait();
//		}
//	}
//	else
//	{
//		while (d != m_map.end())
//		{
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[m_nbth+i].clear();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
//				{
//					dmark->markOrbit<ORBIT>(d);
//					m_vd[m_nbth+nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//			sync1.wait();
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[i].swap(m_vd[m_nbth+i]);
//			sync2.wait();
//		}
//	}
//
//	sync1.wait();
//	finished = true;
//	sync2.wait();
//
//	//wait for all theads to be finished
//	for (unsigned int i = 0; i < m_nbth; ++i)
//	{
//		threads[i]->join();
//		delete threads[i];
//	}
//	delete[] threads;
//	delete[] m_vd;
//
//	if (cmark != NULL)
//		delete cmark;
//
//	if (dmark != NULL)
//		delete dmark;
//}
//
//



template <typename MAP, unsigned int ORBIT>
void foreach_cell_all_thread(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcs, bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
{
	unsigned int nbth = funcs.size();

	boost::thread** threads = new boost::thread*[nbth];

	std::vector<Dart> vd;
	vd.reserve(SIZE_BUFFER_THREAD);

	AttributeContainer* cont = NULL;
	DartMarker* dmark = NULL;
	CellMarker<ORBIT>* cmark = NULL;
	AttributeMultiVector<Dart>* quickTraversal = map.template getQuickTraversal<ORBIT>() ;

	// fill each vd buffers with SIZE_BUFFER_THREAD darts
	Dart d;
	unsigned int di=0;

	if(quickTraversal != NULL)
	{
		cont = &(map.template getAttributeContainer<ORBIT>()) ;
		di = cont->begin();
		unsigned int nb = 0;
		while ((di != cont->end()) && (nb < SIZE_BUFFER_THREAD) )
		{
			d = quickTraversal->operator[](di);
			if (good(d))
			{
				vd.push_back(d);
				nb++;
			}
			cont->next(di);
		}
	}
	else
	{
		if(map.template isOrbitEmbedded<ORBIT>())
		{
			cmark = new CellMarker<ORBIT>(map, currentThread) ;
			d = map.begin();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
				{
					cmark->mark(d);
					vd.push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
		else
		{
			dmark = new DartMarker(map, currentThread) ;
			d = map.begin();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
				{
					dmark->markOrbit<ORBIT>(d);
					vd.push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
	}

	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished=false;
	// lauch threads
	if (needMarkers)
	{
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

	for (unsigned int i = 0; i < nbth; ++i)
		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd,sync1,sync2, finished,1+i));

	// and continue to traverse the map
	std::vector<Dart> tempo;
	tempo.reserve(SIZE_BUFFER_THREAD);

	if (cont)
	{
		while (di != cont->end())
		{
			tempo.clear();
			unsigned int nb=0;
			while ((di != cont->end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				d = quickTraversal->operator[](di);
				if (good(d))
				{
					tempo.push_back(d);
					nb++;
				}
				cont->next(di);
			}
			sync1.wait();
			vd.swap(tempo);
			sync2.wait();
		}
	}
	else if (cmark)
	{
		while (d != map.end())
		{
			tempo.clear();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
				{
					cmark->mark(d);
					tempo.push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			vd.swap(tempo);
			sync2.wait();
		}
	}
	else
	{
		while (d != map.end())
		{
			tempo.clear();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
				{
					dmark->markOrbit<ORBIT>(d);
					tempo.push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			vd.swap(tempo);
			sync2.wait();
		}
	}

	sync1.wait();
	finished = true;
	sync2.wait();

	//wait for all theads to be finished
	for (unsigned int i = 0; i < nbth; ++i)
	{
		threads[i]->join();
		delete threads[i];
	}
	delete[] threads;

	if (cmark != NULL)
		delete cmark;

	if (dmark != NULL)
		delete dmark;
}







1053

1054
} // namespace Parallel
1055

1056
} // namespace Algo
1057

1058
} // namespace CGoGN