CoalescingBitVector.h Source File (original) (raw)

39 static_assert(std::is_unsigned::value,

40 "Index must be an unsigned integer.");

47 using UnderlyingIterator = typename MapT::const_iterator;

49 using IntervalT = std::pair<IndexT, IndexT>;

51public:

57 : Alloc(&Alloc), Intervals(Alloc) {}

63 : Alloc(Other.Alloc), Intervals(*Other.Alloc) {

65 }

79 void clear() { Intervals.clear(); }

82 bool empty() const { return Intervals.empty(); }

86 unsigned Bits = 0;

87 for (auto It = Intervals.begin(), End = Intervals.end(); It != End; ++It)

88 Bits += 1 + It.stop() - It.start();

89 return Bits;

90 }

97 void set(IndexT Index) {

98 assert( test (Index) && "Setting already-set bits not supported/efficient, "

99 "IntervalMap will assert");

100 insert(Index, Index);

101 }

102

103

104

105

106

108 for (auto It = Other.Intervals.begin(), End = Other.Intervals.end();

109 It != End; ++It)

110 insert(It.start(), It.stop());

111 }

112

113

114 void set(std::initializer_list Indices) {

115 for (IndexT Index : Indices)

116 set(Index);

117 }

118

119

120 bool test(IndexT Index) const {

121 const auto It = Intervals.find(Index);

122 if (It == Intervals.end())

123 return false;

124 assert(It.stop() >= Index && "Interval must end after Index");

125 return It.start() <= Index;

126 }

127

128

130 if ( test (Index))

131 set(Index);

132 }

133

134

136 auto It = Intervals.find(Index);

137 if (It == Intervals.end())

138 return;

139

140

141

142

143

144 IndexT Start = It.start();

145 if (Index < Start)

146

147 return;

148 IndexT Stop = It.stop();

149 assert(Index <= Stop && "Wrong interval for index");

150 It.erase();

151 if (Start < Index)

152 insert(Start, Index - 1);

153 if (Index < Stop)

154 insert(Index + 1, Stop);

155 }

156

157

158

160

162 getOverlaps(RHS, Overlaps);

163

164

165 for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end();

166 It != End; ++It) {

167 IndexT Start = It.start();

168 IndexT Stop = It.stop();

170 getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);

171 for (IntervalT AdditivePortion : NonOverlappingParts)

172 insert(AdditivePortion.first, AdditivePortion.second);

173 }

174 }

175

176

178

180 getOverlaps(RHS, Overlaps);

181

183 for (IntervalT Overlap : Overlaps)

184 insert(Overlap.first, Overlap.second);

185 }

186

187

190 if (!getOverlaps(Other, Overlaps)) {

191

192 return;

193 }

194

195

196

197 for (auto [OlapStart, OlapStop] : Overlaps) {

198 auto It = Intervals.find(OlapStart);

199 IndexT CurrStart = It.start();

200 IndexT CurrStop = It.stop();

201 assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&

202 "Expected some intersection!");

203

204

205

206

207

208 It.erase();

209 if (CurrStart < OlapStart)

210 insert(CurrStart, OlapStart - 1);

211 if (OlapStop < CurrStop)

212 insert(OlapStop + 1, CurrStop);

213 }

214 }

215

217

218

219

220 auto ItL = Intervals.begin();

221 auto ItR = RHS.Intervals.begin();

222 while (ItL != Intervals.end() && ItR != RHS.Intervals.end() &&

223 ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {

224 ++ItL;

225 ++ItR;

226 }

227 return ItL == Intervals.end() && ItR == RHS.Intervals.end();

228 }

229

231

232 class const_iterator {

234

235 public:

241

242 private:

243

244

245 static constexpr unsigned kIteratorAtTheEndOffset = ~0u;

246

247 UnderlyingIterator MapIterator;

248 unsigned OffsetIntoMapIterator = 0;

249

250

251

252 IndexT CachedStart = IndexT();

253 IndexT CachedStop = IndexT();

254

255 void setToEnd() {

256 OffsetIntoMapIterator = kIteratorAtTheEndOffset;

257 CachedStart = IndexT();

258 CachedStop = IndexT();

259 }

260

261

262

263 void resetCache() {

264 if (MapIterator.valid()) {

265 OffsetIntoMapIterator = 0;

266 CachedStart = MapIterator.start();

267 CachedStop = MapIterator.stop();

268 } else {

269 setToEnd();

270 }

271 }

272

273

274

275

276 void advanceTo(IndexT Index) {

277 assert(Index <= CachedStop && "Cannot advance to OOB index");

278 if (Index < CachedStart)

279

280 return;

281 OffsetIntoMapIterator = Index - CachedStart;

282 }

283

284 const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) {

285 resetCache();

286 }

287

288 public:

290

292

293

294 return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==

295 std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart,

296 RHS.CachedStop);

297 }

298

302

303 IndexT operator*() const { return CachedStart + OffsetIntoMapIterator; }

304

305 const_iterator &operator++() {

306 if (CachedStart + OffsetIntoMapIterator < CachedStop) {

307

308 ++OffsetIntoMapIterator;

309 } else {

310

311 ++MapIterator;

312 resetCache();

313 }

314 return *this;

315 }

316

317 const_iterator operator++(int) {

318 const_iterator tmp = *this;

320 return tmp;

321 }

322

323

324

325

326

328 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)

329 return;

330

331

332 while (Index > CachedStop) {

333 ++MapIterator;

334 resetCache();

335 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)

336 return;

337 }

338

339 advanceTo(Index);

340 }

341 };

342

344

346

347

348

349

350

352 auto UnderlyingIt = Intervals.find(Index);

353 if (UnderlyingIt == Intervals.end())

354 return end();

356 It.advanceTo(Index);

357 return It;

358 }

359

360

361

363 IndexT End) const {

364 assert(Start < End && "Not a valid range");

365 auto StartIt = find(Start);

366 if (StartIt == end() || *StartIt >= End)

367 return {end(), end()};

368 auto EndIt = StartIt;

369 EndIt.advanceToLowerBound(End);

370 return {StartIt, EndIt};

371 }

372

374 OS << "{";

375 for (auto It = Intervals.begin(), End = Intervals.end(); It != End;

376 ++It) {

377 OS << "[" << It.start();

378 if (It.start() != It.stop())

379 OS << ", " << It.stop();

380 OS << "]";

381 }

382 OS << "}";

383 }

384

385#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

387

388

389 dbgs() << "\n";

391 dbgs() << "\n";

392 }

393#endif

394

395private:

396 void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }

397

398

399

400 bool getOverlaps(const ThisT &Other,

401 SmallVectorImpl &Overlaps) const {

402 for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);

403 I.valid(); ++I)

404 Overlaps.emplace_back(I.start(), I.stop());

406 [](IntervalT LHS, IntervalT RHS) {

407 return LHS.second < RHS.first;

408 }) &&

409 "Overlaps must be sorted");

410 return !Overlaps.empty();

411 }

412

413

414

415

416 void getNonOverlappingParts(IndexT Start, IndexT Stop,

417 const SmallVectorImpl &Overlaps,

418 SmallVectorImpl &NonOverlappingParts) {

419 IndexT NextUncoveredBit = Start;

420 for (auto [OlapStart, OlapStop] : Overlaps) {

421

422

423 bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;

424 if (!DoesOverlap)

425 continue;

426

427

428

429 if (NextUncoveredBit < OlapStart)

430 NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);

431 NextUncoveredBit = OlapStop + 1;

432 if (NextUncoveredBit > Stop)

433 break;

434 }

435 if (NextUncoveredBit <= Stop)

436 NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);

437 }

438

440 MapT Intervals;

441};