libstdc++: set_operations.h Source File (original) (raw)

34#ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H

35#define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1

37#include <omp.h>

43{

44 template<typename _IIter, typename _OutputIterator>

45 _OutputIterator

48 {

50 {

51 do

52 {

53 *__r++ = *__b.first++;

54 }

56 }

57 else

58 {

60 *__r++ = *__b.second++;

61 }

62 return __r;

63 }

65 template<typename _IIter,

66 typename _OutputIterator,

67 typename _Compare>

68 struct __symmetric_difference_func

69 {

71 typedef typename _TraitsType::difference_type _DifferenceType;

74 __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}

76 _Compare _M_comp;

78 _OutputIterator

79 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,

80 _OutputIterator __r) const

81 {

82 while (__a != __b && __c != __d)

83 {

84 if (_M_comp(*__a, *__c))

85 {

86 *__r = *__a;

87 ++__a;

88 ++__r;

89 }

90 else if (_M_comp(*__c, *__a))

91 {

92 *__r = *__c;

93 ++__c;

94 ++__r;

95 }

96 else

97 {

98 ++__a;

99 ++__c;

100 }

101 }

102 return std::copy(__c, __d, std::copy(__a, __b, __r));

103 }

104

105 _DifferenceType

106 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const

107 {

108 _DifferenceType __counter = 0;

109

110 while (__a != __b && __c != __d)

111 {

112 if (_M_comp(*__a, *__c))

113 {

114 ++__a;

115 ++__counter;

116 }

117 else if (_M_comp(*__c, *__a))

118 {

119 ++__c;

120 ++__counter;

121 }

122 else

123 {

124 ++__a;

125 ++__c;

126 }

127 }

128

129 return __counter + (__b - __a) + (__d - __c);

130 }

131

132 _OutputIterator

133 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const

134 { return std::copy(__c, __d, __out); }

135

136 _OutputIterator

137 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const

138 { return std::copy(__a, __b, __out); }

139 };

140

141

142 template<typename _IIter,

143 typename _OutputIterator,

144 typename _Compare>

145 struct __difference_func

146 {

148 typedef typename _TraitsType::difference_type _DifferenceType;

150

151 __difference_func(_Compare __comp) : _M_comp(__comp) {}

152

153 _Compare _M_comp;

154

155 _OutputIterator

156 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,

157 _OutputIterator __r) const

158 {

159 while (__a != __b && __c != __d)

160 {

161 if (_M_comp(*__a, *__c))

162 {

163 *__r = *__a;

164 ++__a;

165 ++__r;

166 }

167 else if (_M_comp(*__c, *__a))

168 { ++__c; }

169 else

170 {

171 ++__a;

172 ++__c;

173 }

174 }

175 return std::copy(__a, __b, __r);

176 }

177

178 _DifferenceType

179 __count(_IIter __a, _IIter __b,

180 _IIter __c, _IIter __d) const

181 {

182 _DifferenceType __counter = 0;

183

184 while (__a != __b && __c != __d)

185 {

186 if (_M_comp(*__a, *__c))

187 {

188 ++__a;

189 ++__counter;

190 }

191 else if (_M_comp(*__c, *__a))

192 { ++__c; }

193 else

194 { ++__a; ++__c; }

195 }

196

197 return __counter + (__b - __a);

198 }

199

200 _OutputIterator

201 __first_empty(_IIter, _IIter, _OutputIterator __out) const

202 { return __out; }

203

204 _OutputIterator

205 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const

206 { return std::copy(__a, __b, __out); }

207 };

208

209

210 template<typename _IIter,

211 typename _OutputIterator,

212 typename _Compare>

213 struct __intersection_func

214 {

216 typedef typename _TraitsType::difference_type _DifferenceType;

218

219 __intersection_func(_Compare __comp) : _M_comp(__comp) {}

220

221 _Compare _M_comp;

222

223 _OutputIterator

224 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,

225 _OutputIterator __r) const

226 {

227 while (__a != __b && __c != __d)

228 {

229 if (_M_comp(*__a, *__c))

230 { ++__a; }

231 else if (_M_comp(*__c, *__a))

232 { ++__c; }

233 else

234 {

235 *__r = *__a;

236 ++__a;

237 ++__c;

238 ++__r;

239 }

240 }

241

242 return __r;

243 }

244

245 _DifferenceType

246 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const

247 {

248 _DifferenceType __counter = 0;

249

250 while (__a != __b && __c != __d)

251 {

252 if (_M_comp(*__a, *__c))

253 { ++__a; }

254 else if (_M_comp(*__c, *__a))

255 { ++__c; }

256 else

257 {

258 ++__a;

259 ++__c;

260 ++__counter;

261 }

262 }

263

264 return __counter;

265 }

266

267 _OutputIterator

268 __first_empty(_IIter, _IIter, _OutputIterator __out) const

269 { return __out; }

270

271 _OutputIterator

272 __second_empty(_IIter, _IIter, _OutputIterator __out) const

273 { return __out; }

274 };

275

276 template<class _IIter, class _OutputIterator, class _Compare>

277 struct __union_func

278 {

280 _DifferenceType;

281

282 __union_func(_Compare __comp) : _M_comp(__comp) {}

283

284 _Compare _M_comp;

285

286 _OutputIterator

287 _M_invoke(_IIter __a, const _IIter __b, _IIter __c,

288 const _IIter __d, _OutputIterator __r) const

289 {

290 while (__a != __b && __c != __d)

291 {

292 if (_M_comp(*__a, *__c))

293 {

294 *__r = *__a;

295 ++__a;

296 }

297 else if (_M_comp(*__c, *__a))

298 {

299 *__r = *__c;

300 ++__c;

301 }

302 else

303 {

304 *__r = *__a;

305 ++__a;

306 ++__c;

307 }

308 ++__r;

309 }

310 return std::copy(__c, __d, std::copy(__a, __b, __r));

311 }

312

313 _DifferenceType

314 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const

315 {

316 _DifferenceType __counter = 0;

317

318 while (__a != __b && __c != __d)

319 {

320 if (_M_comp(*__a, *__c))

321 { ++__a; }

322 else if (_M_comp(*__c, *__a))

323 { ++__c; }

324 else

325 {

326 ++__a;

327 ++__c;

328 }

329 ++__counter;

330 }

331

332 __counter += (__b - __a);

333 __counter += (__d - __c);

334 return __counter;

335 }

336

337 _OutputIterator

338 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const

339 { return std::copy(__c, __d, __out); }

340

341 _OutputIterator

342 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const

343 { return std::copy(__a, __b, __out); }

344 };

345

346 template<typename _IIter,

347 typename _OutputIterator,

348 typename _Operation>

349 _OutputIterator

350 __parallel_set_operation(_IIter __begin1, _IIter __end1,

351 _IIter __begin2, _IIter __end2,

352 _OutputIterator __result, _Operation __op)

353 {

354 _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))

355

357 typedef typename _TraitsType::difference_type _DifferenceType;

359

360 if (__begin1 == __end1)

361 return __op.__first_empty(__begin2, __end2, __result);

362

363 if (__begin2 == __end2)

364 return __op.__second_empty(__begin1, __end1, __result);

365

366 const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);

367

368 const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),

369 std::make_pair(__begin2, __end2) };

370 _OutputIterator __return_value = __result;

371 _DifferenceType *__borders;

372 _IteratorPair *__block_begins;

373 _DifferenceType* __lengths;

374

376 std::min<_DifferenceType>(__get_max_threads(),

377 std::min(__end1 - __begin1, __end2 - __begin2));

378

379# pragma omp parallel num_threads(__num_threads)

380 {

381# pragma omp single

382 {

383 __num_threads = omp_get_num_threads();

384

385 __borders = new _DifferenceType[__num_threads + 2];

387 __block_begins = new _IteratorPair[__num_threads + 1];

388

389 __block_begins[0] = std::make_pair(__begin1, __begin2);

390 __lengths = new _DifferenceType[__num_threads];

391 }

392

394

395

396 _IIter __offset[2];

397 const _DifferenceType __rank = __borders[__iam + 1];

398

400 __rank, __offset, __op._M_comp);

401

402

403

404

405 if (__offset[ 0 ] != __begin1 && __offset[1] != __end2

406 && !__op._M_comp(*(__offset[0] - 1), *__offset[1])

407 && !__op._M_comp(*__offset[1], *(__offset[0] - 1)))

408 {

409

410

411 --__offset[0];

412 }

413

414 _IteratorPair __block_end = __block_begins[__iam + 1] =

415 _IteratorPair(__offset[0], __offset[1]);

416

417

418# pragma omp barrier

419

420 _IteratorPair __block_begin = __block_begins[__iam];

421

422

423

424 if (__iam == 0)

425 {

426

427 __lengths[ __iam ] =

428 __op._M_invoke(__block_begin.first, __block_end.first,

429 __block_begin.second, __block_end.second,

430 __result) - __result;

431 }

432 else

433 {

434 __lengths[ __iam ] =

435 __op.__count(__block_begin.first, __block_end.first,

436 __block_begin.second, __block_end.second);

437 }

438

439

440# pragma omp barrier

441

442 _OutputIterator __r = __result;

443

444 if (__iam == 0)

445 {

446

447 for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)

448 __r += __lengths[__i];

449

450 __block_begin = __block_begins[__num_threads];

451

452

453 __return_value =

454 __op._M_invoke(__block_begin.first, __end1,

455 __block_begin.second, __end2, __r);

456

457 }

458 else

459 {

460 for (_ThreadIndex __i = 0; __i < __iam; ++__i)

461 __r += __lengths[ __i ];

462

463

464 __op._M_invoke(__block_begin.first, __block_end.first,

465 __block_begin.second, __block_end.second, __r);

466 }

467 }

468 return __return_value;

469 }

470

471 template<typename _IIter,

472 typename _OutputIterator,

473 typename _Compare>

474 inline _OutputIterator

475 __parallel_set_union(_IIter __begin1, _IIter __end1,

476 _IIter __begin2, _IIter __end2,

477 _OutputIterator __result, _Compare __comp)

478 {

479 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

480 __result,

481 __union_func< _IIter, _OutputIterator,

482 _Compare>(__comp));

483 }

484

485 template<typename _IIter,

486 typename _OutputIterator,

487 typename _Compare>

488 inline _OutputIterator

489 __parallel_set_intersection(_IIter __begin1, _IIter __end1,

490 _IIter __begin2, _IIter __end2,

491 _OutputIterator __result, _Compare __comp)

492 {

493 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

494 __result,

495 __intersection_func<_IIter,

496 _OutputIterator, _Compare>(__comp));

497 }

498

499 template<typename _IIter,

500 typename _OutputIterator,

501 typename _Compare>

502 inline _OutputIterator

503 __parallel_set_difference(_IIter __begin1, _IIter __end1,

504 _IIter __begin2, _IIter __end2,

505 _OutputIterator __result, _Compare __comp)

506 {

507 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

508 __result,

509 __difference_func<_IIter,

510 _OutputIterator, _Compare>(__comp));

511 }

512

513 template<typename _IIter,

514 typename _OutputIterator,

515 typename _Compare>

516 inline _OutputIterator

517 __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,

518 _IIter __begin2, _IIter __end2,

519 _OutputIterator __result,

520 _Compare __comp)

521 {

522 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

523 __result,

524 __symmetric_difference_func<_IIter,

525 _OutputIterator, _Compare>(__comp));

526 }

527}

528

529#endif

#define _GLIBCXX_CALL(__n)

Macro to produce log message when entering a function.

Functions to find elements of a certain global __rank in multiple sorted sequences....

Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms.

constexpr const _Tp & min(const _Tp &, const _Tp &)

This does what you think it does.

GNU parallel code for public use.

uint16_t _ThreadIndex

Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...

_OutputIterator __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)

function to split a sequence into parts of almost equal size.

void multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >())

Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each s...

Traits class for iterators.

Struct holding two objects of arbitrary type.

_T1 first

The first member.

_T2 second

The second member.