[LLVMdev] EquivalenceClasses: findValue vs. findLeader

[Chris Lattner]

On Fri, 15 Jun 2007, David A. Greene wrote:
> Given an object o of ElemType in an instance of EquivalenceClasses, I need
> to get a list of all members of the equivalence class that o is in.  For
> various reasons, it is easiest if I could get an EquivalenceClasses::iterator
> that I can pass to member_begin and member_end.

ok

> So naturally, I did something like this (pseudo-C++):
>
> EquivalenceClasses::iterator i = equiv.findValue(o);
> for(equiv.member_begin(i); member_end(i); ++i) {
>   // Do stuff
> }
>
> Unfortunately, this doesn't seem to work.  findValue returns an iterator that
> is not end(), but the member set of the equivalence class is empty.

Right.  Conceptually, the range of elements in a set consist of [leader, 
end).  You want something like this:

  EquivalenceClasses::iterator i = equiv.findValue(o);
  i = equiv.getleaderfor(i);
  for(equiv.member_begin(i); member_end(i); ++i) {
    // Do stuff
  }

> Strangly, when I just iterate through the EquivalenceClasses object like this:
...

> I get something like this:
>
> ### New set:
> ### New set:
> ### New set:
> ### New set:
> ### New set:
> ### New set:
> a
> b
> ### New set:
> ### New set:
> c
> Why all the empty sets?  Is this an artifact of the path compression?

This is an artifact of member_begin:

   /// member_* Iterate over the members of an equivalence class.
   ///
   class member_iterator;
   member_iterator member_begin(iterator I) const {
     // Only leaders provide anything to iterate over.
     return member_iterator(I->isLeader() ? &*I : 0);
   }

member_begin only works on leaders.

> What does findLeader do?  Does it return a member iterator that is at the
> beginning of the list of equivalence class members?

Yep.

> The Doxygen
> documentation seems to indicate that it does not, but returns a
> member_iterator pointing to o.  But then what is a "Leader" and why do
> I care?

You care a lot, you need it to get the start of the member range of the 
subset.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/