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

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>

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.

On Feb 11, 2009, at 10:57 AM, Ted Kremenek wrote:
>
> 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/5b2664b8/attachment.html>

On Feb 11, 2009, at 12:24 PM, Ted Kremenek wrote:
> 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.
I agree, "size" should also return 'unsigned' not int.

-Chris

On Wed, Feb 11, 2009 at 8:24 PM, Ted Kremenek <kremenek at apple.com>
wrote:
> 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.
I need to check for size() == 1 (in order to test whether a range set
has a single possible value).