9 #ifndef LLVM_ADT_STRATIFIEDSETS_H
10 #define LLVM_ADT_STRATIFIEDSETS_H
19 #include <type_traits>
90 std::vector<StratifiedLink> Links)
93 std::optional<StratifiedInfo>
find(
const T &Elem)
const {
94 auto Iter = Values.find(Elem);
95 if (Iter == Values.end())
107 std::vector<StratifiedLink> Links;
183 bool hasAbove()
const {
185 return Link.hasAbove();
188 bool hasBelow()
const {
190 return Link.hasBelow();
267 void finalizeSets(std::vector<StratifiedLink> &StratLinks) {
269 for (
auto &
Link : Links) {
270 if (
Link.isRemapped())
275 StratLinks.push_back(
Link.getLink());
278 for (
auto &
Link : StratLinks) {
279 if (
Link.hasAbove()) {
280 auto &Above = linksAt(
Link.Above);
281 auto Iter = Remaps.
find(Above.Number);
283 Link.Above = Iter->second;
286 if (
Link.hasBelow()) {
287 auto &Below = linksAt(
Link.Below);
288 auto Iter = Remaps.
find(Below.Number);
290 Link.Below = Iter->second;
294 for (
auto &Pair : Values) {
295 auto &
Info = Pair.second;
297 auto Iter = Remaps.
find(
Link.Number);
299 Info.Index = Iter->second;
305 static void propagateAttrs(std::vector<StratifiedLink> &Links) {
307 const auto *
Link = &Links[Idx];
308 while (
Link->hasAbove()) {
316 for (
unsigned I = 0,
E = Links.size();
I <
E; ++
I) {
317 auto CurrentIndex = getHighestParentAbove(
I);
318 if (!Visited.
insert(CurrentIndex).second)
321 while (Links[CurrentIndex].hasBelow()) {
322 auto &CurrentBits = Links[CurrentIndex].Attrs;
323 auto NextIndex = Links[CurrentIndex].Below;
324 auto &NextBits = Links[NextIndex].Attrs;
325 NextBits |= CurrentBits;
326 CurrentIndex = NextIndex;
335 std::vector<StratifiedLink> StratLinks;
336 finalizeSets(StratLinks);
337 propagateAttrs(StratLinks);
342 bool has(
const T &Elem)
const {
return get(Elem).has_value(); }
348 auto NewIndex = getNewUnlinkedIndex();
349 return addAtMerging(Main, NewIndex);
357 auto Index = *indexOf(Main);
358 if (!linksAt(
Index).hasAbove())
361 auto Above = linksAt(
Index).getAbove();
362 return addAtMerging(ToAdd, Above);
370 auto Index = *indexOf(Main);
371 if (!linksAt(
Index).hasBelow())
374 auto Below = linksAt(
Index).getBelow();
375 return addAtMerging(ToAdd, Below);
380 auto MainIndex = *indexOf(Main);
381 return addAtMerging(ToAdd, MainIndex);
386 auto *
Info = *get(Main);
388 Link.setAttrs(NewAttrs);
393 std::vector<BuilderLink> Links;
398 auto Pair = Values.
insert(std::make_pair(ToAdd,
Info));
402 auto &Iter = Pair.first;
403 auto &IterSet = linksAt(Iter->second.Index);
404 auto &ReqSet = linksAt(
Index);
407 if (&IterSet != &ReqSet)
408 merge(IterSet.Number, ReqSet.Number);
416 auto *Start = &Links[
Index];
417 if (!Start->isRemapped())
420 auto *Current = Start;
421 while (Current->isRemapped())
422 Current = &Links[Current->getRemapIndex()];
424 auto NewRemap = Current->Number;
429 while (Current->isRemapped()) {
430 auto *Next = &Links[Current->getRemapIndex()];
431 Current->updateRemap(NewRemap);
441 assert(inbounds(Idx1) && inbounds(Idx2));
442 assert(&linksAt(Idx1) != &linksAt(Idx2) &&
443 "Merging a set into itself is not allowed");
448 if (tryMergeUpwards(Idx1, Idx2))
451 if (tryMergeUpwards(Idx2, Idx1))
456 mergeDirect(Idx1, Idx2);
462 assert(inbounds(Idx1) && inbounds(Idx2));
464 auto *LinksInto = &linksAt(Idx1);
465 auto *LinksFrom = &linksAt(Idx2);
468 while (LinksInto->hasAbove() && LinksFrom->hasAbove()) {
469 LinksInto = &linksAt(LinksInto->getAbove());
470 LinksFrom = &linksAt(LinksFrom->getAbove());
473 if (LinksFrom->hasAbove()) {
474 LinksInto->setAbove(LinksFrom->getAbove());
475 auto &NewAbove = linksAt(LinksInto->getAbove());
476 NewAbove.setBelow(LinksInto->Number);
485 while (LinksInto->hasBelow() && LinksFrom->hasBelow()) {
486 auto FromAttrs = LinksFrom->getAttrs();
487 LinksInto->setAttrs(FromAttrs);
491 auto *NewLinksFrom = &linksAt(LinksFrom->getBelow());
492 LinksFrom->remapTo(LinksInto->Number);
493 LinksFrom = NewLinksFrom;
494 LinksInto = &linksAt(LinksInto->getBelow());
497 if (LinksFrom->hasBelow()) {
498 LinksInto->setBelow(LinksFrom->getBelow());
499 auto &NewBelow = linksAt(LinksInto->getBelow());
500 NewBelow.setAbove(LinksInto->Number);
503 LinksInto->setAttrs(LinksFrom->getAttrs());
504 LinksFrom->remapTo(LinksInto->Number);
511 assert(inbounds(LowerIndex) && inbounds(UpperIndex));
512 auto *
Lower = &linksAt(LowerIndex);
513 auto *
Upper = &linksAt(UpperIndex);
517 SmallVector<BuilderLink *, 8> Found;
518 auto *Current =
Lower;
519 auto Attrs = Current->getAttrs();
520 while (Current->hasAbove() && Current != Upper) {
521 Found.push_back(Current);
522 Attrs |= Current->getAttrs();
523 Current = &linksAt(Current->getAbove());
526 if (Current != Upper)
531 if (
Lower->hasBelow()) {
532 auto NewBelowIndex =
Lower->getBelow();
533 Upper->setBelow(NewBelowIndex);
534 auto &NewBelow = linksAt(NewBelowIndex);
535 NewBelow.setAbove(UpperIndex);
540 for (
const auto &
Ptr : Found)
546 std::optional<const StratifiedInfo *> get(
const T &Val)
const {
548 if (Result == Values.
end())
553 std::optional<StratifiedInfo *> get(
const T &Val) {
555 if (Result == Values.
end())
560 std::optional<StratifiedIndex> indexOf(
const T &Val) {
561 auto MaybeVal = get(Val);
564 auto *
Info = *MaybeVal;
570 auto At = addLinks();
571 Links[Set].setBelow(At);
572 Links[At].setAbove(Set);
577 auto At = addLinks();
578 Links[At].setBelow(Set);
579 Links[Set].setAbove(At);
586 auto Link = Links.size();
587 Links.push_back(BuilderLink(
Link));
595 #endif // LLVM_ADT_STRATIFIEDSETS_H