Repository: llvm/llvm-project
File: llvm/include/llvm/ADT/EquivalenceClasses.h (C/C++)

Code before:
      if (I->isLeader()) ++NC;
    return NC;
  }

  //===--------------------------------------------------------------------===//
  // Mutation methods

  /// insert - Insert a new value into the union/find set, ignoring the request
  /// if the value already exists.
  iterator insert(const ElemTy &Data) {
    return TheMapping.insert(ECValue(Data)).first;
  }

  /// findLeader - Given a value in the set, return a member iterator for the
  /// equivalence class it is in.  This does the path-compression part that
  /// makes union-find "union findy".  This returns an end iterator if the value
  /// is not in the equivalence class.
  member_iterator findLeader(iterator I) const {
    if (I == TheMapping.end()) return member_end();
    return member_iterator(I->getLeader());
  }
  member_iterator findLeader(const ElemTy &V) const {
    return findLeader(TheMapping.find(V));
  }

  /// Erase the class containing \p V.
  void eraseClass(const ElemTy &V) {
    if (TheMapping.find(V) == TheMapping.end())
      return;
    auto LeaderI = findValue(getLeaderValue(V));
    for (auto MI = member_begin(LeaderI), ME = member_end(); MI != ME;) {
      const auto &ToErase = *MI;
      ++MI;
      TheMapping.erase(ToErase);
    }
  }

  /// union - Merge the two equivalence sets for the specified values, inserting
  /// them if they do not already exist in the equivalence set.
  member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
    iterator V1I = insert(V1), V2I = insert(V2);
    return unionSets(findLeader(V1I), findLeader(V2I));
  }
  member_iterator unionSets(member_iterator L1, member_iterator L2) {
    assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
    if (L1 == L2) return L1;   // Unifying the same two sets, noop.

    // Otherwise, this is a real union operation.  Set the end of the L1 list to
    // point to the L2 leader node.
    const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
    L1LV.getEndOfList()->setNext(&L2LV);

Review comment (suggestion):
The comment could be clearer what "erasing" a class means. Reading the code, it removes all its members from the set.


Code after:
        ++NC;
    return NC;
  }

  //===--------------------------------------------------------------------===//
  // Mutation methods

  /// insert - Insert a new value into the union/find set, ignoring the request
  /// if the value already exists.
  const ECValue &insert(const ElemTy &Data) {
    auto [I, Inserted] = TheMapping.try_emplace(Data);
    if (!Inserted)
      return *I->second;

    auto *ECV = new (ECValueAllocator) ECValue(Data);
    I->second = ECV;
    Members.push_back(ECV);
    return *ECV;
  }

  /// erase - Erase a value from the union/find set, return "true" if erase
  /// succeeded, or "false" when the value was not found.
  bool erase(const ElemTy &V) {
    if (!TheMapping.contains(V))
      return false;
    const ECValue *Cur = TheMapping[V];
    const ECValue *Next = Cur->getNext();
    // If the current element is the leader and has a successor element,
    // update the successor element's 'Leader' field to be the last element,
    // set the successor element's stolen bit, and set the 'Leader' field of
    // all other elements in same class to be the successor element.
    if (Cur->isLeader() && Next) {
      Next->Leader = Cur->Leader;
      Next->Next = reinterpret_cast<const ECValue *>(
          reinterpret_cast<intptr_t>(Next->Next) | static_cast<intptr_t>(1));

      const ECValue *NewLeader = Next;
      while ((Next = Next->getNext())) {
        Next->Leader = NewLeader;
      }
    } else if (!Cur->isLeader()) {
      const ECValue *Leader = findLeader(V).Node;
      const ECValue *Pre = Leader;
      while (Pre->getNext() != Cur) {
        Pre = Pre->getNext();
      }
      if (!Next) {
        // If the current element is the last element(not leader), set the
        // successor of the current element's predecessor to null while
        // preserving the leader bit, and set the 'Leader' field of the class
        // leader to the predecessor element.