1 // Copyright 2023 The RE2 Authors. All Rights Reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 #include "re2/bitmap256.h" 6 7 #include <stdint.h> 8 9 #include "absl/base/macros.h" 10 #include "util/logging.h" 11 12 namespace re2 { 13 FindNextSetBit(int c) const14int Bitmap256::FindNextSetBit(int c) const { 15 DCHECK_GE(c, 0); 16 DCHECK_LE(c, 255); 17 18 // Check the word that contains the bit. Mask out any lower bits. 19 int i = c / 64; 20 uint64_t word = words_[i] & (~uint64_t{0} << (c % 64)); 21 if (word != 0) 22 return (i * 64) + FindLSBSet(word); 23 24 // Check any following words. 25 i++; 26 switch (i) { 27 case 1: 28 if (words_[1] != 0) 29 return (1 * 64) + FindLSBSet(words_[1]); 30 ABSL_FALLTHROUGH_INTENDED; 31 case 2: 32 if (words_[2] != 0) 33 return (2 * 64) + FindLSBSet(words_[2]); 34 ABSL_FALLTHROUGH_INTENDED; 35 case 3: 36 if (words_[3] != 0) 37 return (3 * 64) + FindLSBSet(words_[3]); 38 ABSL_FALLTHROUGH_INTENDED; 39 default: 40 return -1; 41 } 42 } 43 44 } // namespace re2 45