hphp/util/multibitset.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_UTIL_MULTIBITSET_H_
  18 #define incl_HPHP_UTIL_MULTIBITSET_H_
  19
  20 #include <cstddef>
  21 #include <cstdint>
  22 #include <limits>
  23 #include <unordered_map>
  24
  25 namespace HPHP {
  26
  27 ///////////////////////////////////////////////////////////////////////////////
  28
  29 /*
  30  * Like a bitset, but we have N bits at each position instead of 1.
  31  */
  32 template<size_t N>
  33 struct multibitset {
  34   /*
  35    * Create an empty multibitset with no bits allocated.
  36    */
  37   multibitset();
  38
  39   /*
  40    * Allocate a multibitset with room for `nelms' N-bits, and zero it.
  41    */
  42   explicit multibitset(size_t nelms);
  43
  44   /*
  45    * Free the allocated bits.
  46    */
  47   ~multibitset();
  48
  49   /*
  50    * Make room for `nelms' N-bits in the set, shrinking it if `nelms' is
  51    * smaller than the current size.
  52    */
  53   void resize(size_t nelms);
  54
  55   /*
  56    * Set all N-bits to zero.
  57    */
  58   void reset();
  59
  60   /////////////////////////////////////////////////////////////////////////////
  61
  62   /*
  63    * Reference to an N-bit.
  64    *
  65    * Behaves analogously to std::bitset::reference.
  66    */
  67   struct reference {
  68     /* implicit */ operator uint64_t() const;
  69     reference& operator=(uint64_t);
  70
  71     friend struct multibitset<N>;
  72
  73    private:
  74     reference(multibitset<N>& mbs, size_t pos);
  75
  76    private:
  77     multibitset<N>& m_mbs;
  78     size_t m_word;
  79     uint8_t m_bit;
  80   };
  81
  82   static constexpr size_t npos = std::numeric_limits<uint64_t>::max();
  83
  84   /////////////////////////////////////////////////////////////////////////////
  85
  86   /*
  87    * Access a specific N-bit.
  88    *
  89    * This asserts that `pos <= N'; as such, we do not implement a test().
  90    */
  91   uint64_t operator[](size_t pos) const;
  92   reference operator[](size_t pos);
  93
  94   /*
  95    * Returns the number of N-bits the multibitset can hold.
  96    */
  97   size_t size() const;
  98
  99   /*
 100    * Find the position of the first or last N-bit set to a nonzero value,
 101    * starting at `pos'.  Note that `pos' is an inclusive bound, so `pos' itself
 102    * may be returned.
 103    *
 104    * Returns `npos' if no set N-bit is found.
 105    */
 106   size_t ffs(size_t pos = 0) const;
 107   size_t fls(size_t pos = npos) const;
 108
 109   /////////////////////////////////////////////////////////////////////////////
 110
 111 private:
 112   static_assert(N > 0 && N < 64, "must have 0 < N < 64");
 113
 114 private:
 115   uint64_t* m_bits{nullptr};
 116   size_t m_size{0};
 117   size_t m_nwords{0};
 118 };
 119
 120 template<size_t N>
 121 constexpr size_t multibitset<N>::npos;
 122
 123 ///////////////////////////////////////////////////////////////////////////////
 124
 125 /*
 126  * An alternate multibitset interface intended for use patterns with sparse
 127  * clusters of marked bits.
 128  *
 129  * Has roughly the same interface as multibitset, with exceptions noted.
 130  */
 131 template<size_t N>
 132 struct chunked_multibitset {
 133   /*
 134    * Create an empty multibitset.
 135    *
 136    * chunked_multibitset automatically expands storage as bits are set.  Thus,
 137    * it does not accept a size restriction; instead, it takes a chunk size.
 138    */
 139   explicit chunked_multibitset(size_t chunk_sz);
 140
 141   /////////////////////////////////////////////////////////////////////////////
 142
 143   struct reference {
 144     /* implicit */ operator uint64_t() const;
 145     reference& operator=(uint64_t);
 146
 147     friend struct chunked_multibitset<N>;
 148
 149    private:
 150     reference(chunked_multibitset<N>& cmbs, size_t pos);
 151
 152    private:
 153     chunked_multibitset<N>& m_cmbs;
 154     size_t m_pos;
 155   };
 156
 157   static constexpr size_t npos = std::numeric_limits<uint64_t>::max();
 158
 159   /////////////////////////////////////////////////////////////////////////////
 160
 161   void reset();
 162
 163   /*
 164    * Return a reference to an N-bit.
 165    *
 166    * Setting an N-bit may cause new chunks to be allocated.
 167    */
 168   uint64_t operator[](size_t pos) const;
 169   reference operator[](size_t pos);
 170
 171   /*
 172    * Find set bit; see multibitset::f{f,l}s().
 173    *
 174    * The time complexity of these routines is linearly bounded by the number of
 175    * chunks in which bits have been touched during the lifetime of the object.
 176    * No other guarantees are made.
 177    */
 178   size_t ffs(size_t pos = 0) const;
 179   size_t fls(size_t pos = npos) const;
 180
 181   /////////////////////////////////////////////////////////////////////////////
 182
 183 private:
 184   static_assert(N > 0 && N <= 64, "must have 0 < N <= 64");
 185
 186   multibitset<N>& chunk_for(size_t pos);
 187
 188 private:
 189   std::unordered_map<size_t,multibitset<N>> m_chunks;
 190   const size_t m_chunk_sz;
 191   size_t m_highwater{0};
 192   size_t m_lowwater{npos};
 193 };
 194
 195 template<size_t N>
 196 constexpr size_t chunked_multibitset<N>::npos;
 197
 198 ///////////////////////////////////////////////////////////////////////////////
 199
 200 }
 201
 202 #include "hphp/util/multibitset-inl.h"
 203
 204 #endif