SparseMultiSet.h Source File (original) (raw)

21#ifndef LLVM_ADT_SPARSEMULTISET_H

22#define LLVM_ADT_SPARSEMULTISET_H

27#include

28#include

29#include

30#include

31#include

32#include

34namespace llvm {

84template <typename ValueT, typename KeyT = unsigned,

85 typename KeyFunctorT = identity, typename SparseT = uint8_t>

87 static_assert(std::is_unsigned_v,

88 "SparseT must be an unsigned integer type");

96 struct SMSNode {

97 static constexpr unsigned INVALID = ~0U;

100 unsigned Prev;

101 unsigned Next;

102

103 SMSNode(ValueT D, unsigned P, unsigned N) : Data(D), Prev(P), Next(N) {}

104

105

106 bool isTail() const { return Next == INVALID; }

107

108

109 bool isTombstone() const { return Prev == INVALID; }

110

111

112

114 };

115

117 DenseT Dense;

118 SparseT *Sparse = nullptr;

119 unsigned Universe = 0;

120 KeyFunctorT KeyIndexOf;

122

123

124

125

126 unsigned FreelistIdx = SMSNode::INVALID;

127 unsigned NumFree = 0;

128

129 unsigned sparseIndex(const ValueT &Val) const {

130 assert(ValIndexOf(Val) < Universe &&

131 "Invalid key in set. Did object mutate?");

132 return ValIndexOf(Val);

133 }

134 unsigned sparseIndex(const SMSNode &N) const { return sparseIndex(N.Data); }

135

136

137

138

139 bool isHead(const SMSNode &D) const {

140 assert(D.isValid() && "Invalid node for head");

141 return Dense[D.Prev].isTail();

142 }

143

144

145

146 bool isSingleton(const SMSNode &N) const {

147 assert(N.isValid() && "Invalid node for singleton");

148

149 return &Dense[N.Prev] == &N;

150 }

151

152

153

154 unsigned addValue(const ValueT &V, unsigned Prev, unsigned Next) {

155 if (NumFree == 0) {

156 Dense.push_back(SMSNode(V, Prev, Next));

157 return Dense.size() - 1;

158 }

159

160

161 unsigned Idx = FreelistIdx;

162 unsigned NextFree = Dense[Idx].Next;

163 assert(Dense[Idx].isTombstone() && "Non-tombstone free?");

164

165 Dense[Idx] = SMSNode(V, Prev, Next);

166 FreelistIdx = NextFree;

167 --NumFree;

168 return Idx;

169 }

170

171

172 void makeTombstone(unsigned Idx) {

173 Dense[Idx].Prev = SMSNode::INVALID;

174 Dense[Idx].Next = FreelistIdx;

175 FreelistIdx = Idx;

176 ++NumFree;

177 }

178

179public:

186

191

192

193

194

195

196

198

199

200 assert(empty() && "Can only resize universe on an empty map");

201

202 if (U >= Universe / 4 && U <= Universe)

203 return;

204 free(Sparse);

205

206

207

208 Sparse = static_cast<SparseT *>(safe_calloc(U, sizeof(SparseT)));

209 Universe = U;

210 }

211

212

213

214 template class iterator_base {

216

217 public:

223

224 private:

225 SMSPtrTy SMS;

226 unsigned Idx;

227 unsigned SparseIdx;

228

229 iterator_base(SMSPtrTy P, unsigned I, unsigned SI)

230 : SMS(P), Idx(I), SparseIdx(SI) {}

231

232

233 bool isEnd() const {

234 if (Idx == SMSNode::INVALID)

235 return true;

236

237 assert(Idx < SMS->Dense.size() && "Out of range, non-INVALID Idx?");

238 return false;

239 }

240

241

242 bool isKeyed() const { return SparseIdx < SMS->Universe; }

243

244 unsigned Prev() const { return SMS->Dense[Idx].Prev; }

245 unsigned Next() const { return SMS->Dense[Idx].Next; }

246

247 void setPrev(unsigned P) { SMS->Dense[Idx].Prev = P; }

248 void setNext(unsigned N) { SMS->Dense[Idx].Next = N; }

249

250 public:

252 assert(isKeyed() && SMS->sparseIndex(SMS->Dense[Idx].Data) == SparseIdx &&

253 "Dereferencing iterator of invalid key or index");

254

255 return SMS->Dense[Idx].Data;

256 }

258

259

261

262 if (SMS == RHS.SMS && Idx == RHS.Idx) {

263 assert((isEnd() || SparseIdx == RHS.SparseIdx) &&

264 "Same dense entry, but different keys?");

265 return true;

266 }

267

268 return false;

269 }

270

272

273

274 iterator_base &operator--() {

275 assert(isKeyed() && "Decrementing an invalid iterator");

276 assert((isEnd() || !SMS->isHead(SMS->Dense[Idx])) &&

277 "Decrementing head of list");

278

279

280 if (isEnd())

281 Idx = SMS->findIndex(SparseIdx).Prev();

282 else

283 Idx = Prev();

284

285 return *this;

286 }

287 iterator_base &operator++() {

288 assert(!isEnd() && isKeyed() && "Incrementing an invalid/end iterator");

289 Idx = Next();

290 return *this;

291 }

293 iterator_base I(*this);

294 --*this;

295 return I;

296 }

298 iterator_base I(*this);

299 ++*this;

300 return I;

301 }

302 };

303

306

307

308 using RangePair = std::pair<iterator, iterator>;

309

310

311

314 return const_iterator(this, SMSNode::INVALID, SMSNode::INVALID);

315 }

316

317

318

319

320

322

323

324

325

326

327

329 assert(NumFree <= Dense.size() && "Out-of-bounds free entries");

330 return Dense.size() - NumFree;

331 }

332

333

334

336

337 Dense.clear();

338 NumFree = 0;

339 FreelistIdx = SMSNode::INVALID;

340 }

341

342

343

344

345

346

348 assert(Idx < Universe && "Key out of range");

349 const unsigned Stride = std::numeric_limits::max() + 1u;

350 for (unsigned i = Sparse[Idx], e = Dense.size(); i < e; i += Stride) {

351 const unsigned FoundIdx = sparseIndex(Dense[i]);

352

353

354 if (Idx == FoundIdx && Dense[i].isValid() && isHead(Dense[i]))

355 return iterator(this, i, Idx);

356

357 if (!Stride)

358 break;

359 }

360 return end();

361 }

362

363

364

365

366

367

369

374

375

376

378 unsigned Ret = 0;

380 ++Ret;

381

382 return Ret;

383 }

384

385

387

388

392 if (I != end())

394 return I;

395 }

396

397

398

399

405

406

407

409 unsigned Idx = sparseIndex(Val);

411

412 unsigned NodeIdx = addValue(Val, SMSNode::INVALID, SMSNode::INVALID);

413

414 if (I == end()) {

415

416 Sparse[Idx] = NodeIdx;

417 Dense[NodeIdx].Prev = NodeIdx;

418 return iterator(this, NodeIdx, Idx);

419 }

420

421

422 unsigned HeadIdx = I.Idx;

423 unsigned TailIdx = I.Prev();

424 Dense[TailIdx].Next = NodeIdx;

425 Dense[HeadIdx].Prev = NodeIdx;

426 Dense[NodeIdx].Prev = TailIdx;

427

428 return iterator(this, NodeIdx, Idx);

429 }

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

456 assert(I.isKeyed() && .isEnd() && !Dense[I.Idx].isTombstone() &&

457 "erasing invalid/end/tombstone iterator");

458

459

460

461 iterator NextI = unlink(Dense[I.Idx]);

462

463

464 makeTombstone(I.Idx);

465

466 return NextI;

467 }

468

469

470

475

476private:

477

478 iterator unlink(const SMSNode &N) {

479 if (isSingleton(N)) {

480

481 assert(N.Next == SMSNode::INVALID && "Singleton has next?");

482 return iterator(this, SMSNode::INVALID, ValIndexOf(N.Data));

483 }

484

485 if (isHead(N)) {

486

487 Sparse[sparseIndex(N)] = N.Next;

488 Dense[N.Next].Prev = N.Prev;

489 return iterator(this, N.Next, ValIndexOf(N.Data));

490 }

491

492 if (N.isTail()) {

493

494 findIndex(sparseIndex(N)).setPrev(N.Prev);

495 Dense[N.Prev].Next = N.Next;

496

497

498 iterator I(this, N.Prev, ValIndexOf(N.Data));

499 return ++I;

500 }

501

502

503 Dense[N.Next].Prev = N.Prev;

504 Dense[N.Prev].Next = N.Next;

505 return iterator(this, N.Next, ValIndexOf(N.Data));

506 }

507};

508

509}

510

511#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static bool isValid(const char C)

Returns true if C is a valid mangled character: <0-9a-zA-Z_>.

This file contains library features backported from future STL versions.

This file defines the SmallVector class.

This file defines the SparseSet class derived from the version described in Briggs,...

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Our iterators are iterators over the collection of objects that share a key.

Definition SparseMultiSet.h:214

std::ptrdiff_t difference_type

Definition SparseMultiSet.h:220

friend class SparseMultiSet

Definition SparseMultiSet.h:215

iterator_base & operator++()

Definition SparseMultiSet.h:287

iterator_base & operator--()

Increment and decrement operators.

Definition SparseMultiSet.h:274

value_type & reference

Definition SparseMultiSet.h:222

bool operator!=(const iterator_base &RHS) const

Definition SparseMultiSet.h:271

iterator_base operator--(int)

Definition SparseMultiSet.h:292

reference operator*() const

Definition SparseMultiSet.h:251

ValueT value_type

Definition SparseMultiSet.h:219

std::bidirectional_iterator_tag iterator_category

Definition SparseMultiSet.h:218

value_type * pointer

Definition SparseMultiSet.h:221

pointer operator->() const

Definition SparseMultiSet.h:257

bool operator==(const iterator_base &RHS) const

Comparison operators.

Definition SparseMultiSet.h:260

iterator_base operator++(int)

Definition SparseMultiSet.h:297

ValueT * pointer

Definition SparseMultiSet.h:183

void clear()

Clears the set.

Definition SparseMultiSet.h:335

iterator end()

Returns an iterator past this container.

Definition SparseMultiSet.h:312

const_iterator end() const

Definition SparseMultiSet.h:313

iterator find(const KeyT &Key)

Find an element by its key.

Definition SparseMultiSet.h:368

bool contains(const KeyT &Key) const

Returns true if this set contains an element identified by Key.

Definition SparseMultiSet.h:386

iterator getTail(const KeyT &Key)

Definition SparseMultiSet.h:390

RangePair equal_range(const KeyT &K)

The bounds of the range of items sharing Key K.

Definition SparseMultiSet.h:400

const ValueT & const_reference

Definition SparseMultiSet.h:182

iterator findIndex(unsigned Idx)

Find an element by its index.

Definition SparseMultiSet.h:347

iterator erase(iterator I)

Erases an existing element identified by a valid iterator.

Definition SparseMultiSet.h:455

bool empty() const

Returns true if the set is empty.

Definition SparseMultiSet.h:321

iterator insert(const ValueT &Val)

Insert a new element at the tail of the subset list.

Definition SparseMultiSet.h:408

const_iterator find(const KeyT &Key) const

Definition SparseMultiSet.h:370

void setUniverse(unsigned U)

Set the universe size which determines the largest key the set can hold.

Definition SparseMultiSet.h:197

SparseMultiSet & operator=(const SparseMultiSet &)=delete

iterator_base< const SparseMultiSet * > const_iterator

Definition SparseMultiSet.h:305

unsigned size_type

Definition SparseMultiSet.h:185

size_type size() const

Returns the number of elements in the set.

Definition SparseMultiSet.h:328

void eraseAll(const KeyT &K)

Erase all elements with the given key.

Definition SparseMultiSet.h:471

ValueT & reference

Definition SparseMultiSet.h:181

size_type count(const KeyT &Key) const

Returns the number of elements identified by Key.

Definition SparseMultiSet.h:377

std::pair< iterator, iterator > RangePair

Definition SparseMultiSet.h:308

iterator_base< SparseMultiSet * > iterator

Definition SparseMultiSet.h:304

~SparseMultiSet()

Definition SparseMultiSet.h:190

ValueT value_type

Definition SparseMultiSet.h:180

const ValueT * const_pointer

Definition SparseMultiSet.h:184

SparseMultiSet(const SparseMultiSet &)=delete

iterator getHead(const KeyT &Key)

Return the head and tail of the subset's list, otherwise returns end().

Definition SparseMultiSet.h:389

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

FunctionAddr VTableAddr uintptr_t uintptr_t Data

FunctionAddr VTableAddr Next

SparseSetValFunctor - Helper class for getting a value's index.