hphp/util/bitset-view.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 namespace HPHP {
  20
  21 /*
  22  * Bitset view
  23  *
  24  * This is a utility class to view a region of memory as a vector of bits.
  25  *
  26  * It is the user of this class's responsibility to ensure that the memory used
  27  * to construct the view is large enough to contain all the bits that get
  28  * addressed through operator[]--this class does not perform any allocation or
  29  * bounds checking.
  30  */
  31 template <bool is_const>
  32 struct BitsetView {
  33   using char_t = typename std::conditional<is_const,
  34                                            const unsigned char,
  35                                            unsigned char>::type;
  36
  37   /*
  38    * A reference wrapper for a particular bit in the bitset--note that this is
  39    * larger than a typical pointer since it's a pointer to the byte and a mask
  40    * to select the particular bit of interest.
  41    */
  42   struct bit_reference {
  43     bit_reference(char_t* ptr, char_t mask)
  44       : m_ptr(ptr)
  45       , m_mask(mask) {}
  46
  47     bit_reference(const bit_reference& o)
  48       : m_ptr(o.m_ptr)
  49       , m_mask(o.m_mask) {}
  50
  51     bool operator=(bool b) {
  52       *m_ptr = (*m_ptr & ~m_mask) | (b ? m_mask : 0);
  53       return *this;
  54     }
  55
  56     operator bool() const {
  57       return *m_ptr & m_mask;
  58     }
  59
  60     bool operator!() const {
  61       return !(static_cast<bool>(*this));
  62     }
  63
  64   private:
  65     char_t* m_ptr;
  66     char_t m_mask;
  67   };
  68
  69   /*
  70    * A forward iterator for the bits in a view
  71    *
  72    * As with the view itself, no bounds-checking is performed--it's the callers
  73    * responsibility to make sure that every iterator that is dereferenced
  74    * points to valid memory
  75    */
  76   struct iterator {
  77     iterator(char_t* ptr, char_t mask)
  78       : m_ptr(ptr)
  79       , m_mask(mask) {}
  80
  81     using value_type = bit_reference;
  82     using reference = bit_reference;
  83     using pointer = void;
  84     using difference_type = void;
  85     using iterator_category = std::forward_iterator_tag;
  86
  87     bool operator==(const iterator& o) {
  88       return m_ptr == o.m_ptr && m_mask == o.m_mask;
  89     }
  90
  91     bool operator!=(const iterator& o) {
  92       return !(*this == o);
  93     }
  94
  95     bit_reference operator*() const {
  96       return bit_reference{m_ptr, m_mask};
  97     }
  98
  99     bit_reference operator->() const {
 100       return *(*this);
 101     }
 102
 103     iterator& operator++() {
 104       const auto carry = m_mask >> (sizeof(char_t) * 8 - 1);
 105       m_ptr += carry;
 106       m_mask = (m_mask << 1) | carry;
 107       return *this;
 108     }
 109
 110     iterator operator++(int) {
 111       auto const ret = *this;
 112       ++(*this);
 113       return ret;
 114     }
 115
 116   private:
 117     char_t* m_ptr;
 118     typename std::remove_const<char_t>::type m_mask;
 119   };
 120
 121   /*
 122    * Construct a BitsetView starting at the given byte
 123    */
 124   explicit BitsetView(char_t* buf) : m_buf(buf) {}
 125
 126   /*
 127    * Return the size (in bytes) for a bitset of the given length
 128    */
 129   static size_t sizeFor(size_t len) {
 130     return (len + CHAR_BIT - 1) / CHAR_BIT;
 131   }
 132
 133   /*
 134    * Access the bit at the given index in the set
 135    */
 136   bit_reference operator[](size_t idx) {
 137     auto const chunk = idx / CHAR_BIT;
 138     auto const mask = static_cast<char_t>(1 << (idx % CHAR_BIT));
 139     return bit_reference{m_buf + chunk, mask};
 140   }
 141
 142   iterator iteratorAt(size_t off) {
 143     return iterator{m_buf + off / CHAR_BIT,
 144                     static_cast<char_t>(1 << (off %  CHAR_BIT))};
 145   }
 146
 147   /*
 148    * Access the memory being viewed as a bitset
 149    */
 150   char_t* buffer() { return m_buf; }
 151   const char_t* buffer() const { return m_buf; }
 152
 153 private:
 154   char_t* m_buf;
 155 };
 156
 157 }
 158
 159
 160