unsigned count() for ADT

[yaron.keren]

Summary

The count() function for STL datatypes returns unsigned, even where it's only 1/0 result like std::set. Some of the LLVM ADT already return unsigned count(), while others still return bool count().

In continuation to r197879, this patch modifies DenseMap, DenseSet, ScopedHashTable, ValueMap:: count() to return unsigned instead of bool, 1 instead of true and 0 instead of false.

Updated upatch to ToT, fixed comments and two warnings.

[yaron.keren]

From the list discussion, Richard Smith:

If we want our container-like types to be containers, count should return size_type. I suspect that size_type == size_t is probably the best choice (for performance and code size), but I really doubt this makes much difference. I don't think there are many cases where we'd want to support containers of more than 4Gi elements. (In short, I don't think this really matters, but each container should be internally consistent.)

[yaron.keren]

Updated count() and size() type to class-local size_type.

[yaron.keren]

Typo fix in SmallPtrSet.

[dblaikie]

lib/CodeGen/AsmPrinter/WinCodeViewLineTables.cpp

311

It's common to write a "does this container contain this thing" as simply boolean testing the result of 'count':

assert(FnDebugInfo.count(GV));

Personally this is easier for me to read because I don't have to worry about "is this container a multimap and are they testing that there's /exactly/ one element" (and writing it as "> 0" when it's a single map is also a little confusing, even though it's semantically equivalent to the non-zero count test above)

Not a requirement, just a though - maybe others feel more strongly.

lib/IR/Metadata.cpp

666

same here, though I guess this is a bit more interesting as in this case the bool on the LHS would be converted to an int and compared... but you're == 1, so it is the same whether it's a multimap or not (ie: it's only true if there's exactly one thing)... not sure how I'd prefer to write this one.

[yaron.keren]

Fixed first test per comment. The second test is trickier, comparing a bool to count() results in VC complaining:

..\..\..\lib\IR\Metadata.cpp(667): warning C4805: '==' : unsafe mix of type 'bool' and type

I modified it to read count() > 0, so the comparison will be between bools.

[yaron.keren]

Is this good to commit?

[dblaikie]

Looks fine to me. I'd probably have written that last one as "!= 0" rather than "> 0", but either seems acceptable.

[yaron.keren]

r211350

[yaron.keren]

I modified size_type for BitVector back from size_t to unsigned.
The code caused a compile building failure on LP64 systems where sizeof(size_t)==sizeof(long) with template deduction in line 560. The failure could be fixed otherwise but anyhow I don't think that we have the need to store that many bits.

Rereading BitVector.h, if size were unsigned long instead of unsigned then members Size, Capacity should also be unsigned long.

[yaron.keren]

Richard, I reverted size_type to unsigned since size are counts are usually assumed in LLVM code to be unsigned.
We don't really need to 64 bit-sized containers (yet?) so better be safe rather than introduce possibly subtle bugs.

include/llvm/ADT/BitVector.h

   unsigned Capacity;     // Size of allocated memory in BitWord.
 
 public:
+  typedef size_t size_type;
   // Encapsulation of a single bit.
   class reference {
     friend class BitVector;

   bool empty() const { return Size == 0; }
 
   /// size - Returns the number of bits in this bitvector.
-  unsigned size() const { return Size; }
+  size_type size() const { return Size; }
 
   /// count - Returns the number of bits which are set.
-  unsigned count() const {
+  size_type count() const {
     unsigned NumBits = 0;
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       if (sizeof(BitWord) == 4)

include/llvm/ADT/DenseMap.h

   typedef std::pair<KeyT, ValueT> BucketT;
 
 public:
+  typedef size_t size_type;
   typedef KeyT key_type;
   typedef ValueT mapped_type;
   typedef BucketT value_type;

   unsigned size() const { return getNumEntries(); }
 
   /// Grow the densemap so that it has at least Size buckets. Does not shrink
-  void resize(size_t Size) {
+  void resize(size_type Size) {
     if (Size > getNumBuckets())
       grow(Size);
   }

     setNumTombstones(0);
   }
 
-  /// count - Return true if the specified key is in the map.
-  bool count(const KeyT &Val) const {
+  /// Return 1 if the specified key is in the map, 0 otherwise.
+  size_type count(const KeyT &Val) const {
     const BucketT *TheBucket;
-    return LookupBucketFor(Val, TheBucket);
+    return LookupBucketFor(Val, TheBucket) ? 1 : 0;
   }
 
   iterator find(const KeyT &Val) {

include/llvm/ADT/DenseSet.h

 public:
   typedef ValueT key_type;
   typedef ValueT value_type;
+  typedef size_t size_type;
 
   explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
 
   bool empty() const { return TheMap.empty(); }
-  unsigned size() const { return TheMap.size(); }
+  size_type size() const { return TheMap.size(); }
   size_t getMemorySize() const { return TheMap.getMemorySize(); }
 
   /// Grow the DenseSet so that it has at least Size buckets. Will not shrink

     TheMap.clear();
   }
 
-  bool count(const ValueT &V) const {
+  /// Return 1 if the specified key is in the set, 0 otherwise.
+  size_type count(const ValueT &V) const {
     return TheMap.count(V);
   }
 

include/llvm/ADT/MapVector.h

          typename MapType = llvm::DenseMap<KeyT, unsigned>,
          typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
 class MapVector {
-  typedef typename VectorType::size_type SizeType;
+  typedef typename VectorType::size_type size_type;
 
   MapType Map;
   VectorType Vector;

   typedef typename VectorType::iterator iterator;
   typedef typename VectorType::const_iterator const_iterator;
 
-  SizeType size() const {
+  size_type size() const {
     return Vector.size();
   }
 

     return std::make_pair(begin() + I, false);
   }
 
-  unsigned count(const KeyT &Key) const {
+  size_type count(const KeyT &Key) const {
     typename MapType::const_iterator Pos = Map.find(Key);
     return Pos == Map.end()? 0 : 1;
   }

include/llvm/ADT/ScopedHashTable.h

   /// ScopeTy - This is a helpful typedef that allows clients to get easy access
   /// to the name of the scope for this hash table.
   typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy;
+  typedef size_t size_type;
 private:
   typedef ScopedHashTableVal<K, V> ValTy;
   DenseMap<K, ValTy*, KInfo> TopLevelMap;

   AllocatorTy &getAllocator() { return Allocator; }
   const AllocatorTy &getAllocator() const { return Allocator; }
 
-  bool count(const K &Key) const {
+  /// Return 1 if the specified key is in the table, 0 otherwise.
+  size_type count(const K &Key) const {
     return TopLevelMap.count(Key);
   }
 

include/llvm/ADT/SmallBitVector.h

   };
 
 public:
+  typedef size_t size_type;
   // Encapsulation of a single bit.
   class reference {
     SmallBitVector &TheVector;

   }
 
   /// size - Returns the number of bits in this bitvector.
-  size_t size() const {
+  size_type size() const {
     return isSmall() ? getSmallSize() : getPointer()->size();
   }
 
   /// count - Returns the number of bits which are set.
-  unsigned count() const {
+  size_type count() const {
     if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       if (NumBaseBits == 32)

include/llvm/ADT/SmallPtrSet.h

   ~SmallPtrSetImplBase();
 
 public:
+  typedef size_t size_type;
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; }
-  unsigned size() const { return NumElements; }
+  size_type size() const { return NumElements; }
 
   void clear() {
     // If the capacity of the array is huge, and the # elements used is small,

   }
 
   /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
-  unsigned count(PtrType Ptr) const {
+  size_type count(PtrType Ptr) const {
     return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
   }
 

include/llvm/ADT/SmallSet.h

   typedef typename SmallVector<T, N>::const_iterator VIterator;
   typedef typename SmallVector<T, N>::iterator mutable_iterator;
 public:
+  typedef size_t size_type;
   SmallSet() {}
 
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {

     return Vector.empty() && Set.empty();
   }
 
-  unsigned size() const {
+  size_type size() const {
     return isSmall() ? Vector.size() : Set.size();
   }
 
   /// count - Return 1 if the element is in the set, 0 otherwise.
-  unsigned count(const T &V) const {
+  size_type count(const T &V) const {
     if (isSmall()) {
       // Since the collection is small, just do a linear search.
       return vfind(V) == Vector.end() ? 0 : 1;

include/llvm/ADT/SparseBitVector.h

   : public ilist_node<SparseBitVectorElement<ElementSize> > {
 public:
   typedef unsigned long BitWord;
+  typedef size_t size_type;
   enum {
     BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,

     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
   }
 
-  unsigned count() const {
+  size_type count() const {
     unsigned NumBits = 0;
     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
       if (sizeof(BitWord) == 4)

include/llvm/ADT/SparseMultiSet.h

   typedef const ValueT &const_reference;
   typedef ValueT *pointer;
   typedef const ValueT *const_pointer;
+  typedef size_t size_type;
 
   SparseMultiSet()
     : Sparse(nullptr), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) {}

   /// This is not the same as BitVector::size() which returns the size of the
   /// universe.
   ///
-  unsigned size() const {
+  size_type size() const {
     assert(NumFree <= Dense.size() && "Out-of-bounds free entries");
     return Dense.size() - NumFree;
   }

 
   /// Returns the number of elements identified by Key. This will be linear in
   /// the number of elements of that key.
-  unsigned count(const KeyT &Key) const {
+  size_type count(const KeyT &Key) const {
     unsigned Ret = 0;
     for (const_iterator It = find(Key); It != end(); ++It)
       ++Ret;

include/llvm/ADT/SparseSet.h

 
   typedef typename KeyFunctorT::argument_type KeyT;
   typedef SmallVector<ValueT, 8> DenseT;
+  typedef size_t size_type;
   DenseT Dense;
   SparseT *Sparse;
   unsigned Universe;

   /// This is not the same as BitVector::size() which returns the size of the
   /// universe.
   ///
-  unsigned size() const { return Dense.size(); }
+  size_type size() const { return Dense.size(); }
 
   /// clear - Clears the set.  This is a very fast constant time operation.
   ///

   /// count - Returns 1 if this set contains an element identified by Key,
   /// 0 otherwise.
   ///
-  unsigned count(const KeyT &Key) const {
+  size_type count(const KeyT &Key) const {
     return find(Key) == end() ? 0 : 1;
   }
 

include/llvm/IR/ValueMap.h

   typedef KeyT key_type;
   typedef ValueT mapped_type;
   typedef std::pair<KeyT, ValueT> value_type;
+  typedef size_t size_type;
 
   explicit ValueMap(unsigned NumInitBuckets = 64)
     : Map(NumInitBuckets), Data() {}

   inline const_iterator end() const { return const_iterator(Map.end()); }
 
   bool empty() const { return Map.empty(); }
-  unsigned size() const { return Map.size(); }
+  size_type size() const { return Map.size(); }
 
   /// Grow the map so that it has at least Size buckets. Does not shrink
   void resize(size_t Size) { Map.resize(Size); }

 
   void clear() { Map.clear(); }
 
-  /// count - Return true if the specified key is in the map.
-  bool count(const KeyT &Val) const {
-    return Map.find_as(Val) != Map.end();
+  /// Return 1 if the specified key is in the map, 0 otherwise.
+  size_type count(const KeyT &Val) const {
+    return Map.find_as(Val) == Map.end() ? 0 : 1;
   }
 
   iterator find(const KeyT &Val) {

lib/CodeGen/AsmPrinter/WinCodeViewLineTables.cpp

     return;
 
   const Function *GV = MF->getFunction();
-  assert(FnDebugInfo.count(GV) == true);
+  assert(FnDebugInfo.count(GV));
   assert(CurFn == &FnDebugInfo[GV]);
 
   if (CurFn->Instrs.empty()) {

lib/IR/Metadata.cpp

 
   // Otherwise, we're removing metadata from an instruction.
   assert((hasMetadataHashEntry() ==
-          getContext().pImpl->MetadataStore.count(this)) &&
+          (getContext().pImpl->MetadataStore.count(this) > 0)) &&
          "HasMetadata bit out of date!");
   if (!hasMetadataHashEntry())
     return;  // Nothing to remove!