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 #pragma once
  18
  19 #include <bitset>
  20 #include "hphp/util/assertions.h"
  21
  22 namespace HPHP {
  23
  24 // Return the index of the first set bit in a bitset, or bitset.size() if none.
  25 template <size_t N>
  26 inline size_t bitset_find_first(const std::bitset<N>& bitset) {
  27 #if defined(__GNUC__) && !defined(__APPLE__)
  28   // GNU provides non-standard (its a hold over from the original SGI
  29   // implementation) _Find_first(), which efficiently returns the index of the
  30   // first set bit.
  31   return bitset._Find_first();
  32 #else
  33   for (size_t i = 0; i < bitset.size(); ++i) {
  34     if (bitset[i]) return i;
  35   }
  36   return bitset.size();
  37 #endif
  38 }
  39
  40 // Return the index of the first set bit in a bitset after the given index, or
  41 // bitset.size() if none.
  42 template <size_t N>
  43 inline size_t bitset_find_next(const std::bitset<N>& bitset, size_t prev) {
  44   assertx(prev < bitset.size());
  45 #if defined(__GNUC__) && !defined(__APPLE__)
  46   // GNU provides non-standard (its a hold over from the original SGI
  47   // implementation) _Find_next(), which given an index, efficiently returns
  48   // the index of the first set bit after the index.
  49   return bitset._Find_next(prev);
  50 #else
  51   for (size_t i = prev+1; i < bitset.size(); ++i) {
  52     if (bitset[i]) return i;
  53   }
  54   return bitset.size();
  55 #endif
  56 }
  57
  58 // Invoke the given callable on the indices of all the set bits in a bitset.
  59 template <typename F, size_t N>
  60 inline void bitset_for_each_set(const std::bitset<N>& bitset, F f) {
  61   for (auto i = bitset_find_first(bitset);
  62        i < bitset.size();
  63        i = bitset_find_next(bitset, i)) {
  64     f(i);
  65   }
  66 }
  67
  68 template <size_t N>
  69 inline size_t findFirst1(const std::bitset<N>& bitset) {
  70   return bitset_find_first(bitset);
  71 }
  72
  73 // range from [s, e), if not found, return e
  74 template <size_t N>
  75 inline size_t findFirst1(const std::bitset<N>& bitset, size_t s, size_t e) {
  76   assert(s <= e);
  77   assert(e <= bitset.size());
  78   for (size_t i = s; i < e; ++i) {
  79     if (bitset[i]) return i;
  80   }
  81   return e;
  82 }
  83
  84 template <size_t N>
  85 inline size_t findFirst0(const std::bitset<N>& bitset) {
  86   for (size_t i = 0; i < bitset.size(); ++i) {
  87     if (!bitset[i]) return i;
  88   }
  89   return bitset.size();
  90 }
  91
  92 // range from [s, e), if not found, return e; if s == e, return e
  93 template <size_t N>
  94 inline size_t findFirst0(const std::bitset<N>& bitset, size_t s, size_t e) {
  95   assert(s <= e);
  96   assert(e <= bitset.size());
  97   for (size_t i = s; i < e; ++i) {
  98     if (!bitset[i]) return i;
  99   }
 100   return e;
 101 }
 102
 103 template <size_t N>
 104 inline size_t findLast1(const std::bitset<N>& bitset) {
 105   for (size_t i = bitset.size(); i-- > 0;) {
 106     if (bitset[i]) return i;
 107   }
 108   return bitset.size();
 109 }
 110
 111 // range from [s, e), if not found, return e; if s == e, return e
 112 template <size_t N>
 113 inline size_t findLast1(const std::bitset<N>& bitset, size_t s, size_t e) {
 114   assert(s <= e);
 115   assert(e <= bitset.size());
 116   for (size_t i = e; i-- > s;) {
 117     if (bitset[i]) return i;
 118   }
 119   return e;
 120 }
 121
 122 template <size_t N>
 123 inline size_t findLast0(const std::bitset<N>& bitset) {
 124   for (size_t i = bitset.size(); i-- > 0;) {
 125     if (!bitset[i]) return i;
 126   }
 127   return bitset.size();
 128 }
 129
 130 // range from [s, e), if not found, return e; if s == e, return e
 131 template <size_t N>
 132 inline size_t findLast0(const std::bitset<N>& bitset, size_t s, size_t e) {
 133   assert(s <= e);
 134   assert(e <= bitset.size());
 135   for (size_t i = e; i-- > s;) {
 136     if (!bitset[i]) return i;
 137   }
 138   return e;
 139 }
 140
 141
 142 template <size_t N>
 143 inline std::bitset<N>& fill1(std::bitset<N>& bitset) {
 144   return bitset.set();
 145 }
 146
 147 // range from [s, e)
 148 template <size_t N>
 149 inline std::bitset<N>& fill1(std::bitset<N>& bitset,
 150                       size_t s, size_t e) {
 151   assert(s < e);
 152   assert(e <= bitset.size());
 153   for(size_t i = s; i < e; ++i){
 154     bitset.set(i);
 155   }
 156   return bitset;
 157 }
 158
 159 template <size_t N>
 160 inline std::bitset<N>& fill0(std::bitset<N>& bitset) {
 161   return bitset.reset();
 162 }
 163
 164 // range from [s, e)
 165 template <size_t N>
 166 inline std::bitset<N>& fill0(std::bitset<N>& bitset,
 167                       size_t s, size_t e) {
 168   assert(s < e);
 169   assert(e <= bitset.size());
 170   for(size_t i = s; i < e; ++i){
 171     bitset.reset(i);
 172   }
 173   return bitset;
 174 }
 175
 176 } // HPHP
 177