parallel_foreach.hpp 17.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 29 30 31 32 33 34 35 36

namespace CGoGN
{

namespace Algo
{

namespace Parallel
{

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

47
public:
48 49
	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)
50 51 52
	{
	}

53 54
	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){}
55 56 57 58 59

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

68

Sylvain Thery's avatar
Sylvain Thery committed
69 70


71 72 73 74 75
/**
 *
 */
template<typename MAP>
class ThreadFunction
Sylvain Thery's avatar
Sylvain Thery committed
76 77
{
protected:
78
	std::vector<Dart>& m_darts;
Sylvain Thery's avatar
Sylvain Thery committed
79 80 81
	boost::barrier& m_sync1;
	boost::barrier& m_sync2;
	bool& m_finished;
82 83
	unsigned int m_id;
	FunctorMapThreaded<MAP>* m_functor;
Sylvain Thery's avatar
Sylvain Thery committed
84
public:
85 86
	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)
87 88 89
	{
	}

90 91
	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
92 93 94 95 96 97

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

105

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


112

113
inline unsigned int optimalNbThreads()
Sylvain Thery's avatar
Sylvain Thery committed
114
{
115 116 117
	unsigned int nb = nbThreads();
	if (nb>4)
		return nb/2 ;
Sylvain Thery's avatar
Sylvain Thery committed
118

119 120
	return nb;
}
Sylvain Thery's avatar
Sylvain Thery committed
121 122


123 124 125 126 127
template <typename MAP, unsigned int ORBIT>
void foreach_cell(MAP& map, FunctorMapThreaded<MAP>& func, bool shared, unsigned int nbth, bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
{
	if (nbth == 0)
		nbth = optimalNbThreads();
Sylvain Thery's avatar
Sylvain Thery committed
128

129 130
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);
131

132
	if (shared)
133
	{
134
		for (unsigned int i = 0; i < nbth; ++i)
135
			funcs.push_back(&func);
136 137 138
	}
	else
	{
139
		for (unsigned int i = 0; i < nbth; ++i)
140
			funcs.push_back(func.duplicate());
141
	}
Sylvain Thery's avatar
Sylvain Thery committed
142 143


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

146
	if (!shared)
147
		for (unsigned int i = 0; i < nbth; ++i)
148
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
149 150
}

151 152
template <typename MAP, unsigned int ORBIT>
void foreach_cell(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcs, unsigned int nbth, bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
Sylvain Thery's avatar
Sylvain Thery committed
153
{
154 155
	assert(funcs.size() ==  nbth);

sylvain thery's avatar
sylvain thery committed
156 157
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
	boost::thread** threads = new boost::thread*[nbth];
Sylvain Thery's avatar
Sylvain Thery committed
158 159

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

163 164 165 166 167 168 169 170 171 172 173

	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
174
	{
175 176 177 178 179
		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
180
		{
181 182 183 184 185 186 187
			d = quickTraversal->operator[](di);
			if (good(d))
			{
				vd[nb%nbth].push_back(d);
				nb++;
			}
			cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
188 189
		}
	}
190
	else
191
	{
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
		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) )
			{
				if (good(d) && (!cmark->isMarked(d)))
				{
					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) )
			{
				if (good(d) && (!dmark->isMarked(d)))
				{
					dmark->markOrbit<ORBIT>(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
225 226
	}

Sylvain Thery's avatar
Sylvain Thery committed
227 228 229 230
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished=false;
	// lauch threads
231 232
	if (needMarkers)
	{
233 234 235
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
236
	}
237 238 239 240

	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
241
	// and continue to traverse the map
sylvain thery's avatar
sylvain thery committed
242 243
	std::vector<Dart>* tempo = new std::vector<Dart>[nbth];

244
	for (unsigned int i = 0; i < nbth; ++i)
245
		tempo[i].reserve(SIZE_BUFFER_THREAD);
Sylvain Thery's avatar
Sylvain Thery committed
246 247


248 249 250
	if (cont)
	{
		while (di != cont->end())
Sylvain Thery's avatar
Sylvain Thery committed
251
		{
252 253 254 255
			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
256
			{
257 258 259 260 261 262 263
				d = quickTraversal->operator[](di);
				if (good(d))
				{
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
264
			}
265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
			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) )
			{
				if (good(d) && (!cmark->isMarked(d)))
				{
					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) )
			{
				if (good(d) && (!dmark->isMarked(d)))
				{
					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
315 316 317 318 319 320 321 322
		}
	}

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

	//wait for all theads to be finished
323
	for (unsigned int i = 0; i < nbth; ++i)
Sylvain Thery's avatar
Sylvain Thery committed
324 325 326 327
	{
		threads[i]->join();
		delete threads[i];
	}
sylvain thery's avatar
sylvain thery committed
328 329 330
	delete[] threads;
	delete[] vd;
	delete[] tempo;
Sylvain Thery's avatar
Sylvain Thery committed
331

332 333
	if (cmark != NULL)
		delete cmark;
Sylvain Thery's avatar
Sylvain Thery committed
334

335 336 337
	if (dmark != NULL)
		delete dmark;
}
Sylvain Thery's avatar
Sylvain Thery committed
338 339 340



341 342 343 344 345
template <typename MAP>
void foreach_dart(MAP& map, FunctorMapThreaded<MAP>& func, bool shared, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
{
	if (nbth == 0)
		nbth = optimalNbThreads();
346

347 348 349 350
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);

	if (shared)
351
	{
352
		for (unsigned int i = 0; i < nbth; ++i)
353
			funcs.push_back(&func);
354 355 356
	}
	else
	{
357
		for (unsigned int i = 0; i < nbth; ++i)
358
			funcs.push_back(func.duplicate());
359
	}
Sylvain Thery's avatar
Sylvain Thery committed
360

361
	foreach_dart<MAP>(map,funcs,nbth,needMarkers,good);
Sylvain Thery's avatar
Sylvain Thery committed
362

363
	if (!shared)
364
		for (unsigned int i = 0; i < nbth; ++i)
365
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
366 367
}

368 369 370

template <typename MAP>
void foreach_dart(MAP& map, std::vector<FunctorMapThreaded<MAP>*> funcs, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
371
{
372 373
	assert(funcs.size() ==  nbth);

374 375 376
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
	boost::thread** threads = new boost::thread*[nbth];

377
	Dart d = map.begin();
378 379

	// nbth new functions, new thread (with good darts !)
380
	for (unsigned int i = 0; i < nbth; ++i)
381
		vd[i].reserve(SIZE_BUFFER_THREAD);
382 383

	// fill each vd buffers with 4096 darts
384
	unsigned int nb = 0;
385
	while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
386
	{
387
		if (good(d))
388 389 390 391 392 393 394
		{
			vd[nb%nbth].push_back(d);
			nb++;
		}
		map.next(d);
	}

395 396 397 398
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished = false;
	// lauch threads
399 400 401 402 403 404 405
	if (needMarkers)
	{
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

406
	for (unsigned int i = 0; i < nbth; ++i)
407
	{
408 409
//		funcs[i]->setThreadID(1+i);
		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd[i],sync1,sync2, finished,1+i));
410 411 412 413
	}

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

417
	while (d != map.end())
418
	{
419
		for (unsigned int i = 0; i < nbth; ++i)
420 421
			tempo[i].clear();

422 423
		unsigned int nb =0;
		while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
424
		{
425
			if (good(d))
426 427 428 429 430 431 432 433
			{
				tempo[nb%nbth].push_back(d);
				nb++;
			}
			map.next(d);
		}

		sync1.wait();
434
		for (unsigned int i = 0; i < nbth; ++i)
435 436 437 438 439 440 441 442
			vd[i].swap(tempo[i]);
		sync2.wait();
	}

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

443
	//wait for all theads to be finished
444
	for (unsigned int i = 0; i < nbth; ++i)
445 446 447 448
	{
		threads[i]->join();
		delete threads[i];
	}
449 450 451 452
	
	delete vd;
	delete threads;
	delete tempo;
453 454 455 456
}



457 458 459 460
inline void foreach_attrib(AttributeContainer& attr_cont, FunctorAttribThreaded& func, bool shared, unsigned int nbth)
{
	if (nbth == 0)
		nbth = optimalNbThreads();
461

462 463
	std::vector<FunctorAttribThreaded*> funcs;
	funcs.reserve(nbth);
464

465
	if (shared)
466
	{
467
		for (unsigned int i = 0; i < nbth; ++i)
468
			funcs.push_back(&func);
469 470 471
	}
	else
	{
472
		for (unsigned int i = 0; i < nbth; ++i)
473
			funcs.push_back(func.duplicate());
474 475
	}

476
	foreach_attrib(attr_cont,funcs,nbth);
477

478
	if (!shared)
479
		for (unsigned int i = 0; i < nbth; ++i)
480
			delete funcs[i];
481 482 483

}

484 485

inline void foreach_attrib(AttributeContainer& attr_cont, std::vector<FunctorAttribThreaded*> funcs, unsigned int nbth)
486
{
487
	assert(funcs.size() ==  nbth);
488

489 490
	std::vector<unsigned int >* vid = new std::vector<unsigned int>[2*nbth];
	boost::thread** threads = new boost::thread*[nbth];
491

492 493
	for (unsigned int i = 0; i < 2*nbth; ++i)
		vid[i].reserve(SIZE_BUFFER_THREAD);
494

495 496
	// fill each vid buffers with 4096 id
	unsigned int id = attr_cont.begin();
497
	unsigned int nb = 0;
498 499
	unsigned int nbm = nbth*SIZE_BUFFER_THREAD;
	while ((id != attr_cont.end()) && (nb < nbm))
500
	{
501 502 503
		vid[nb%nbth].push_back(id);
		nb++;
		attr_cont.next(id);
504 505 506 507 508
	}


	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
509
	bool finished=false;
510
	// lauch threads
511
	for (unsigned int i = 0; i < nbth; ++i)
512
		threads[i] = new boost::thread(ThreadFunctionAttrib(funcs[i], vid[i],sync1,sync2, finished,1+i));
513

514
	while (id != attr_cont.end())
515
	{
516 517
		for (unsigned int i = nbth; i < 2*nbth; ++i)
			vid[i].clear();
518

519
		unsigned int nb = 0;
520
		while ((id != attr_cont.end()) && (nb < nbm))
521
		{
522 523 524
			vid[nbth + nb%nbth].push_back(id);
			nb++;
			attr_cont.next(id);
525 526 527
		}

		sync1.wait();
528
		for (unsigned int i = 0; i < nbth; ++i)
529
			vid[i].swap(vid[nbth+i]);
530 531 532 533 534 535 536
		sync2.wait();
	}

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

537
	//wait for all theads to be finished
538
	for (unsigned int i = 0; i < nbth; ++i)
539 540 541 542 543
	{
		threads[i]->join();
		delete threads[i];
	}
	delete[] threads;
544
	delete[] vid;
545 546 547 548
}



549
// TODO same modification for transparent usage of dart marker / cell marker / quick traversal
550

551 552
template <typename MAP, unsigned int CELL>
void foreach_cell2Pass(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcsFrontnBack, unsigned int nbLoops, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
553
{
554
	std::vector<Dart>* vd = new std::vector<Dart>[2*nbth];
555
	for (unsigned int i = 0; i < nbth; ++i)
556
		vd[i].reserve(SIZE_BUFFER_THREAD);
557

558
	boost::thread** threadsAB = new boost::thread*[2*nbth];
559 560 561 562 563 564 565 566 567

	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);
	}

568 569 570 571
	CellMarkerNoUnmark<CELL> cm(map); // for 2 pass front mark / back unmark

	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
572 573 574 575 576 577

	for (unsigned int loop=0; loop< nbLoops; ++loop)
	{
		// PASS FRONT (A)
		{
			Dart d = map.begin();
578
			// fill each vd buffers with SIZE_BUFFER_THREAD darts
579
			unsigned int nb = 0;
580
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
581 582 583 584 585 586 587 588 589 590 591
			{
				if (good(d) && (!cm.isMarked(d)))
				{
					cm.mark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}

			bool finished=false;
592 593 594 595 596
			// lauch threads funcsFrontnBack

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

597 598 599 600 601
			// and continue to traverse the map

			while (d != map.end())
			{
				for (unsigned int i = 0; i < nbth; ++i)
602
					vd[nbth+i].clear();
603 604

				unsigned int nb = 0;
605
				while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
606 607 608 609
				{
					if (good(d) && (!cm.isMarked(d)))
					{
						cm.mark(d);
610
						vd[nbth+nb%nbth].push_back(d);
611 612 613 614 615 616 617
						nb++;
					}
					map.next(d);
				}

				sync1.wait();
				for (unsigned int i = 0; i < nbth; ++i)
618
					vd[i].swap(vd[nbth+i]);
619 620 621 622 623 624 625 626 627
				sync2.wait();
			}

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

			//wait for all theads to be finished
			for (unsigned int i = 0; i < nbth; ++i)
628
				threadsAB[i]->join();
629 630 631 632 633 634
		}
		// PASS BACK (B)
		{
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].clear();
			Dart d = map.begin();
635
			// fill each vd buffers with SIZE_BUFFER_THREAD darts
636
			unsigned int nb = 0;
637
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
638 639 640 641 642 643 644 645 646 647 648
			{
				if (good(d) && (cm.isMarked(d)))
				{
					cm.unmark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}

			bool finished=false;
649 650 651
			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));

652 653 654 655 656
			// and continue to traverse the map

			while (d != map.end())
			{
				for (unsigned int i = 0; i < nbth; ++i)
657
					vd[nbth+i].clear();
658 659

				unsigned int nb = 0;
660
				while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
661 662 663 664
				{
					if (good(d) && (cm.isMarked(d)))
					{
						cm.unmark(d);
665
						vd[nbth+nb%nbth].push_back(d);
666 667 668 669 670 671 672
						nb++;
					}
					map.next(d);
				}

				sync1.wait();
				for (unsigned int i = 0; i < nbth; ++i)
673
					vd[i].swap(vd[nbth+i]);
674 675 676 677 678 679 680 681 682
				sync2.wait();
			}

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

			//wait for all theads to be finished
			for (unsigned int i = 0; i < nbth; ++i)
683
				threadsAB[nbth+i]->join();
684 685 686 687
		}
	}

	// free buffers and threads
688
	for (unsigned int i = 0; i < 2*nbth; ++i)
689
	{
690
		delete threadsAB[i];
691
	}
692
	delete[] threadsAB;
693 694 695 696 697
	delete[] vd;
}



698 699 700 701 702
template <typename MAP, unsigned int CELL>
void foreach_cell2Pass(MAP& map, FunctorMapThreaded<MAP>& funcFront, FunctorMapThreaded<MAP>& funcBack, bool shared, unsigned int nbLoops, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
{
	if (nbth == 0)
		nbth = optimalNbThreads();
703

704 705
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);
706

707 708 709 710 711 712 713 714 715 716 717 718 719 720
	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
	{
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(funcFront.duplicate());
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(funcBack.duplicate());
	}
721 722


723
	foreach_cell2Pass<MAP,CELL>(map,funcs,nbLoops,nbth,needMarkers,good);
724

725 726 727
	if (!shared)
		for (unsigned int i = 0; i < nbth; ++i)
			delete funcs[i];
728

729
}
730 731


732
} // namespace Parallel
733

734
} // namespace Algo
735

736
} // namespace CGoGN