Improve the performance of bit set searches with a compiler intrinsic.

runtime/vm/bit_set.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_BIT_SET_H_
 #define VM_BIT_SET_H_
 
+#include "platform/utils.h"
 #include "vm/globals.h"
 
 namespace dart {
 
 // Just like its namesake in the STL, a BitSet object contains a fixed
 // length sequence of bits.
 template<intptr_t N>
 class BitSet {
  public:
   BitSet() {
@@ skipping 11 matching lines @@
     }
   }
 
   bool Test(intptr_t i) {
     ASSERT(i >= 0);
     ASSERT(i < N);
     uword mask = (static_cast<uword>(1) << (i % kBitsPerWord));
     return (data_[i / kBitsPerWord] & mask) != 0;
   }
 
+  intptr_t Next(intptr_t i) {
+    ASSERT(i >= 0);
+    ASSERT(i < N);
+    intptr_t w = i / kBitsPerWord;
+    uword mask = ~static_cast<uword>(0) << i;
+    if ((data_[w] & mask) != 0) {
+      uword tz = Utils::CountTrailingZeros(data_[w] & mask);
+      return kBitsPerWord*w + tz;
+    }
+    while (++w < (1 + ((N - 1) / kBitsPerWord))) {
+      if (data_[w] != 0) {
+        return kBitsPerWord*w + Utils::CountTrailingZeros(data_[w]);
+      }
+    }
+    return -1;
+  }
+
   void Reset() {
     memset(data_, 0, sizeof(data_));
   }
 
   intptr_t Size() const {
     return N;
   }
 
  private:
   uword data_[1 + ((N - 1) / kBitsPerWord)];
 };
 
 }  // namespace dart
 
 #endif  // VM_BIT_SET_H_