llvm dev - Feb 2009 - [LLVMdev] Some enhancements to ImmutableSet and FoldingSet

I needed these for some work I'm doing in clang...
-------------- next part --------------
A non-text attachment was scrubbed...
Name: set.patch
Type: application/octet-stream
Size: 1925 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090211/82192816/attachment.obj>

On Feb 11, 2009, at 10:36 AM, Ben Laurie wrote:
> I needed these for some work I'm doing in clang...
> <set.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Looks good to me.  I'll apply these.

On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <benl at google.com>
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)
+      ;
+    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

On Feb 11, 2009, at 10:36 AM, Ben Laurie wrote:
> I needed these for some work I'm doing in clang...
> <set.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Feb 11, 2009, at 10:54 AM, Bill Wendling wrote:
> On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <benl at google.com>
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)
> +      ;
> +    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
Bill's right; empty can be made constant time.  e.g.,  "return Root ==
0";
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090211/c57eec74/attachment.html>

On Feb 11, 2009, at 10:36 AM, Ben Laurie wrote:
> I needed these for some work I'm doing in clang...
> <set.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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
==================================================================---
lib/Support/FoldingSet.cpp	(revision 63488)
+++ lib/Support/FoldingSet.cpp	(working copy)
@@ -61,6 +61,9 @@
    if ((uint64_t)(int)I != I)
      Bits.push_back(unsigned(I >> 32));
  }
+void FoldingSetNodeID::AddBoolean(bool B) {
+  AddInteger(B ? 1 : 0);
+}

"AddBoolean()" can just be defined inline, since it is so simple.

I've committed this change:

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

Bill Wendling wrote:
> On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <benl at google.com>
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
> +    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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>