hphp/util/bitset-utils.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_BITSET_UTILS_H_
  18 #define incl_HPHP_BITSET_UTILS_H_
  19
  20 #include <bitset>
  21 #include "hphp/util/assertions.h"
  22
  23 namespace HPHP {
  24
  25 // Return the index of the first set bit in a bitset, or bitset.size() if none.
  26 template <size_t N>
  27 inline size_t bitset_find_first(const std::bitset<N>& bitset) {
  28 #if defined(__GNUC__) && !defined(__APPLE__)
  29   // GNU provides non-standard (its a hold over from the original SGI
  30   // implementation) _Find_first(), which efficiently returns the index of the
  31   // first set bit.
  32   return bitset._Find_first();
  33 #else
  34   for (size_t i = 0; i < bitset.size(); ++i) {
  35     if (bitset[i]) return i;
  36   }
  37   return bitset.size();
  38 #endif
  39 }
  40
  41 // Return the index of the first set bit in a bitset after the given index, or
  42 // bitset.size() if none.
  43 template <size_t N>
  44 inline size_t bitset_find_next(const std::bitset<N>& bitset, size_t prev) {
  45   assertx(prev < bitset.size());
  46 #if defined(__GNUC__) && !defined(__APPLE__)
  47   // GNU provides non-standard (its a hold over from the original SGI
  48   // implementation) _Find_next(), which given an index, efficiently returns
  49   // the index of the first set bit after the index.
  50   return bitset._Find_next(prev);
  51 #else
  52   for (size_t i = prev+1; i < bitset.size(); ++i) {
  53     if (bitset[i]) return i;
  54   }
  55   return bitset.size();
  56 #endif
  57 }
  58
  59 // Invoke the given callable on the indices of all the set bits in a bitset.
  60 template <typename F, size_t N>
  61 inline void bitset_for_each_set(const std::bitset<N>& bitset, F f) {
  62   for (auto i = bitset_find_first(bitset);
  63        i < bitset.size();
  64        i = bitset_find_next(bitset, i)) {
  65     f(i);
  66   }
  67 }
  68
  69 template <size_t N>
  70 inline size_t findFirst1(const std::bitset<N>& bitset) {
  71   return bitset_find_first(bitset);
  72 }
  73
  74 // range from [s, e), if not found, return e
  75 template <size_t N>
  76 inline size_t findFirst1(const std::bitset<N>& bitset, size_t s, size_t e) {
  77   assert(s <= e);
  78   assert(e <= bitset.size());
  79   for (size_t i = s; i < e; ++i) {
  80     if (bitset[i]) return i;
  81   }
  82   return e;
  83 }
  84
  85 template <size_t N>
  86 inline size_t findFirst0(const std::bitset<N>& bitset) {
  87   for (size_t i = 0; i < bitset.size(); ++i) {
  88     if (!bitset[i]) return i;
  89   }
  90   return bitset.size();
  91 }
  92
  93 // range from [s, e), if not found, return e; if s == e, return e
  94 template <size_t N>
  95 inline size_t findFirst0(const std::bitset<N>& bitset, size_t s, size_t e) {
  96   assert(s <= e);
  97   assert(e <= bitset.size());
  98   for (size_t i = s; i < e; ++i) {
  99     if (!bitset[i]) return i;
 100   }
 101   return e;
 102 }
 103
 104 template <size_t N>
 105 inline size_t findLast1(const std::bitset<N>& bitset) {
 106   for (size_t i = bitset.size(); i-- > 0;) {
 107     if (bitset[i]) return i;
 108   }
 109   return bitset.size();
 110 }
 111
 112 // range from [s, e), if not found, return e; if s == e, return e
 113 template <size_t N>
 114 inline size_t findLast1(const std::bitset<N>& bitset, size_t s, size_t e) {
 115   assert(s <= e);
 116   assert(e <= bitset.size());
 117   for (size_t i = e; i-- > s;) {
 118     if (bitset[i]) return i;
 119   }
 120   return e;
 121 }
 122
 123 template <size_t N>
 124 inline size_t findLast0(const std::bitset<N>& bitset) {
 125   for (size_t i = bitset.size(); i-- > 0;) {
 126     if (!bitset[i]) return i;
 127   }
 128   return bitset.size();
 129 }
 130
 131 // range from [s, e), if not found, return e; if s == e, return e
 132 template <size_t N>
 133 inline size_t findLast0(const std::bitset<N>& bitset, size_t s, size_t e) {
 134   assert(s <= e);
 135   assert(e <= bitset.size());
 136   for (size_t i = e; i-- > s;) {
 137     if (!bitset[i]) return i;
 138   }
 139   return e;
 140 }
 141
 142
 143 template <size_t N>
 144 inline std::bitset<N>& fill1(std::bitset<N>& bitset) {
 145   return bitset.set();
 146 }
 147
 148 // range from [s, e)
 149 template <size_t N>
 150 inline std::bitset<N>& fill1(std::bitset<N>& bitset,
 151                       size_t s, size_t e) {
 152   assert(s < e);
 153   assert(e <= bitset.size());
 154   for(size_t i = s; i < e; ++i){
 155     bitset.set(i);
 156   }
 157   return bitset;
 158 }
 159
 160 template <size_t N>
 161 inline std::bitset<N>& fill0(std::bitset<N>& bitset) {
 162   return bitset.reset();
 163 }
 164
 165 // range from [s, e)
 166 template <size_t N>
 167 inline std::bitset<N>& fill0(std::bitset<N>& bitset,
 168                       size_t s, size_t e) {
 169   assert(s < e);
 170   assert(e <= bitset.size());
 171   for(size_t i = s; i < e; ++i){
 172     bitset.reset(i);
 173   }
 174   return bitset;
 175 }
 176
 177 } // HPHP
 178
 179 #endif