Some enhancements to ImmutableSet and FoldingSet

I needed these for some work I'm doing in clang...

set.patch (1.88 KB)

Looks good to me. I'll apply these.

Yes sir! At least this message was informative. One thing:

+ int size() const {
+ int n = 0;
+ for(iterator i = begin() ; i != end() ; ++n, ++i)
+ ;
+ return n;
+ }
+ bool empty() const {
+ return size() == 0;
+ }

empty() here isn't a constant-time method. Can you make it's time
complexity O(1)?

-bw

Ben,

This patch doesn't apply. Can you update to TOT LLVM first and regenerate the patch?

Ted

Bill’s right; empty can be made constant time. e.g., “return Root == 0”;

Actually, neither of these methods are needed for ImmutableSet. ImmutableSet already has an ‘isEmpty()’ method and I have never really seen a case where “size()” needs to be explicitly calculated. If you need size() itself, however, this seems like a perfectly valid addition.

Minor nit:

--- include/llvm/ADT/FoldingSet.h (revision 63488)
+++ include/llvm/ADT/FoldingSet.h (working copy)
@@ -225,6 +225,7 @@
    void AddInteger(unsigned long I);
    void AddInteger(long long I);
    void AddInteger(unsigned long long I);
+ void AddBoolean(bool B);
    void AddString(const std::string &String);
    void AddString(const char* String);

Index: lib/Support/FoldingSet.cpp

I agree, "size" should also return 'unsigned' not int.

-Chris

Bill Wendling wrote:

I needed these for some work I'm doing in clang...

Yes sir! At least this message was informative. One thing:

+ int size() const {
+ int n = 0;
+ for(iterator i = begin() ; i != end() ; ++n, ++i)
+ ;

Please only call end() once. We use this pattern a lot in LLVM:

for (iterator i = begin(), e = end(); i != e; ++n, ++i)
   ;

But really I think you should just have:
   return std::distance(begin(), end());

Nick

I need to check for size() == 1 (in order to test whether a range set
has a single possible value).

Ah. If that is the case, we can implement a 'isSingleton()' method with constant time performance (i.e., check if we have a root, and check that the root has no children). Would that work?

Sure would!

Hi Ben,

I think this should work:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090209/073634.html

If you find it isn't doing the right thing just let me know.

Ted