include/libtorrent/bitfield.hpp

   1 /*
   2
   3 Copyright (c) 2008, Arvid Norberg
   4 All rights reserved.
   5
   6 Redistribution and use in source and binary forms, with or without
   7 modification, are permitted provided that the following conditions
   8 are met:
   9
  10     * Redistributions of source code must retain the above copyright
  11       notice, this list of conditions and the following disclaimer.
  12     * Redistributions in binary form must reproduce the above copyright
  13       notice, this list of conditions and the following disclaimer in
  14       the documentation and/or other materials provided with the distribution.
  15     * Neither the name of the author nor the names of its
  16       contributors may be used to endorse or promote products derived
  17       from this software without specific prior written permission.
  18
  19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29 POSSIBILITY OF SUCH DAMAGE.
  30
  31 */
  32
  33 #ifndef TORRENT_BITFIELD_HPP_INCLUDED
  34 #define TORRENT_BITFIELD_HPP_INCLUDED
  35
  36 #include "libtorrent/assert.hpp"
  37 #include "libtorrent/config.hpp"
  38
  39 namespace libtorrent
  40 {
  41         struct TORRENT_EXPORT bitfield
  42         {
  43                 bitfield(): m_bytes(0), m_size(0), m_own(false) {}
  44                 bitfield(int bits): m_bytes(0), m_size(0)
  45                 { resize(bits); }
  46                 bitfield(int bits, bool val): m_bytes(0), m_size(0)
  47                 { resize(bits, val); }
  48                 bitfield(char const* bytes, int bits): m_bytes(0), m_size(0)
  49                 { assign(bytes, bits); }
  50                 bitfield(bitfield const& rhs): m_bytes(0), m_size(0), m_own(false)
  51                 { assign(rhs.bytes(), rhs.size()); }
  52
  53                 void borrow_bytes(char* bytes, int bits)
  54                 {
  55                         dealloc();
  56                         m_bytes = (unsigned char*)bytes;
  57                         m_size = bits;
  58                         m_own = false;
  59                 }
  60                 ~bitfield() { dealloc(); }
  61
  62                 void assign(char const* bytes, int bits)
  63                 { resize(bits); memcpy(m_bytes, bytes, (bits + 7) / 8); }
  64
  65                 bool operator[](int index) const
  66                 { return get_bit(index); }
  67
  68                 bool get_bit(int index) const
  69                 {
  70                         TORRENT_ASSERT(index >= 0);
  71                         TORRENT_ASSERT(index < m_size);
  72                         return m_bytes[index / 8] & (0x80 >> (index & 7));
  73                 }
  74
  75                 void clear_bit(int index)
  76                 {
  77                         TORRENT_ASSERT(index >= 0);
  78                         TORRENT_ASSERT(index < m_size);
  79                         m_bytes[index / 8] &= ~(0x80 >> (index & 7));
  80                 }
  81
  82                 void set_bit(int index)
  83                 {
  84                         TORRENT_ASSERT(index >= 0);
  85                         TORRENT_ASSERT(index < m_size);
  86                         m_bytes[index / 8] |= (0x80 >> (index & 7));
  87                 }
  88
  89                 std::size_t size() const { return m_size; }
  90                 bool empty() const { return m_size == 0; }
  91
  92                 char const* bytes() const { return (char*)m_bytes; }
  93
  94                 bitfield& operator=(bitfield const& rhs)
  95                 {
  96                         assign(rhs.bytes(), rhs.size());
  97                         return *this;
  98                 }
  99
 100                 int count() const
 101                 {
 102                         // 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
 103                         // 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
 104                         const static char num_bits[] =
 105                         {
 106                                 0, 1, 1, 2, 1, 2, 2, 3,
 107                                 1, 2, 2, 3, 2, 3, 3, 4
 108                         };
 109
 110                         int ret = 0;
 111                         const int num_bytes = m_size / 8;
 112                         for (int i = 0; i < num_bytes; ++i)
 113                         {
 114                                 ret += num_bits[m_bytes[i] & 0xf] + num_bits[m_bytes[i] >> 4];
 115                         }
 116
 117                         int rest = m_size - num_bytes * 8;
 118                         for (int i = 0; i < rest; ++i)
 119                         {
 120                                 ret += (m_bytes[num_bytes] >> (7-i)) & 1;
 121                         }
 122                         TORRENT_ASSERT(ret <= m_size);
 123                         TORRENT_ASSERT(ret >= 0);
 124                         return ret;
 125                 }
 126
 127                 struct const_iterator
 128                 {
 129                 friend struct bitfield;
 130
 131                         typedef bool value_type;
 132                         typedef ptrdiff_t difference_type;
 133                         typedef bool const* pointer;
 134                         typedef bool& reference;
 135                         typedef std::forward_iterator_tag iterator_category;
 136
 137                         bool operator*() { return *byte & bit; }
 138                         const_iterator& operator++() { inc(); return *this; }
 139                         const_iterator operator++(int)
 140                         { const_iterator ret(*this); inc(); return ret; }
 141                         const_iterator& operator--() { dec(); return *this; }
 142                         const_iterator operator--(int)
 143                         { const_iterator ret(*this); dec(); return ret; }
 144
 145                         const_iterator(): byte(0), bit(0x80) {}
 146                         bool operator==(const_iterator const& rhs) const
 147                         { return byte == rhs.byte && bit == rhs.bit; }
 148
 149                         bool operator!=(const_iterator const& rhs) const
 150                         { return byte != rhs.byte || bit != rhs.bit; }
 151
 152                 private:
 153                         void inc()
 154                         {
 155                                 TORRENT_ASSERT(byte);
 156                                 if (bit == 0x01)
 157                                 {
 158                                         bit = 0x80;
 159                                         ++byte;
 160                                 }
 161                                 else
 162                                 {
 163                                         bit >>= 1;
 164                                 }
 165                         }
 166                         void dec()
 167                         {
 168                                 TORRENT_ASSERT(byte);
 169                                 if (bit == 0x80)
 170                                 {
 171                                         bit = 0x01;
 172                                         --byte;
 173                                 }
 174                                 else
 175                                 {
 176                                         bit <<= 1;
 177                                 }
 178                         }
 179                         const_iterator(unsigned char const* ptr, int offset)
 180                                 : byte(ptr), bit(0x80 >> offset) {}
 181                         unsigned char const* byte;
 182                         int bit;
 183                 };
 184
 185                 const_iterator begin() const { return const_iterator(m_bytes, 0); }
 186                 const_iterator end() const { return const_iterator(m_bytes + m_size / 8, m_size & 7); }
 187
 188                 void resize(int bits, bool val)
 189                 {
 190                         resize(bits);
 191                         if (val) set_all(); else clear_all();
 192                 }
 193
 194                 void set_all()
 195                 {
 196                         memset(m_bytes, 0xff, (m_size + 7) / 8);
 197                 }
 198
 199                 void clear_all()
 200                 {
 201                         memset(m_bytes, 0x00, (m_size + 7) / 8);
 202                 }
 203
 204                 void resize(int bits)
 205                 {
 206                         const int bytes = (bits + 7) / 8;
 207                         if (m_bytes)
 208                         {
 209                                 if (m_own)
 210                                 {
 211                                         m_bytes = (unsigned char*)realloc(m_bytes, bytes);
 212                                         m_own = true;
 213                                 }
 214                                 else if (bits > m_size)
 215                                 {
 216                                         unsigned char* tmp = (unsigned char*)malloc(bytes);
 217                                         memcpy(tmp, m_bytes, (std::min)((m_size + 7)/ 8, bytes));
 218                                         m_bytes = tmp;
 219                                         m_own = true;
 220                                 }
 221                         }
 222                         else
 223                         {
 224                                 m_bytes = (unsigned char*)malloc(bytes);
 225                                 m_own = true;
 226                         }
 227                         m_size = bits;
 228                 }
 229
 230         private:
 231
 232                 void dealloc() { if (m_own) free(m_bytes); m_bytes = 0; }
 233                 unsigned char* m_bytes;
 234                 int m_size; // in bits
 235                 bool m_own;
 236         };
 237
 238 }
 239
 240 #endif // TORRENT_BITFIELD_HPP_INCLUDED
 241