src/BitVector.h

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2009-2011 aMule Team ( admin@amule.org / http://www.amule.org )
   5 // Copyright (c) 2009-2011 Stu Redman ( sturedman@amule.org )
   6 //
   7 // Any parts of this program derived from the xMule, lMule or eMule project,
   8 // or contributed by third-party developers are copyrighted by their
   9 // respective authors.
  10 //
  11 // This program is free software; you can redistribute it and/or modify
  12 // it under the terms of the GNU General Public License as published by
  13 // the Free Software Foundation; either version 2 of the License, or
  14 // (at your option) any later version.
  15 //
  16 // This program is distributed in the hope that it will be useful,
  17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 // GNU General Public License for more details.
  20 //
  21 // You should have received a copy of the GNU General Public License
  22 // along with this program; if not, write to the Free Software
  23 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  24 //
  25
  26 #ifndef BITVECTOR_H
  27 #define BITVECTOR_H
  28
  29 //
  30 // Packed bit vector
  31 //
  32 class BitVector {
  33 public:
  34         BitVector()
  35         {
  36                 m_bits  = 0;
  37                 m_bytes = 0;
  38                 m_allTrue = 0;
  39                 m_vector = NULL;
  40         }
  41
  42         ~BitVector() { clear(); }
  43
  44         // number of bits
  45         uint32 size() const     { return m_bits; }
  46
  47         // is it empty?
  48         bool empty() const { return m_bits == 0; }
  49
  50         // get bit at index
  51         bool get(uint32 idx) const
  52         {
  53                 if (idx >= m_bits) {
  54                         wxFAIL;
  55                         return false;
  56                 }
  57                 return (m_vector[idx / 8] & s_posMask[idx & 7]) != 0;
  58         }
  59
  60         // set bit at index
  61         void set(uint32 idx, bool value)
  62         {
  63                 if (idx >= m_bits) {
  64                         wxFAIL;
  65                         return;
  66                 }
  67                 uint32 bidx = idx / 8;
  68                 if (value) {
  69                         m_vector[bidx] = m_vector[bidx] | s_posMask[idx & 7];
  70                         // If it was not all true before, then we don't know now.
  71                         if (m_allTrue == 0) {
  72                                 m_allTrue = 2;
  73                         }
  74                 } else {
  75                         m_vector[bidx] = m_vector[bidx] & s_negMask[idx & 7];
  76                         m_allTrue = 0;
  77                 }
  78         }
  79
  80         // set number of bits to zero and free memory
  81         void clear()
  82         {
  83                 m_bits  = 0;
  84                 m_bytes = 0;
  85                 m_allTrue = 0;
  86                 delete[] m_vector;
  87                 m_vector = NULL;
  88         }
  89
  90         // set number of bits and initialize them with value
  91         void setsize(uint32 newsize, bool value)
  92         {
  93                 if (newsize == 0) {
  94                         clear();
  95                         return;
  96                 }
  97                 m_bits = newsize;
  98                 m_bytes = newsize / 8;
  99                 if (newsize & 7) {
 100                         m_bytes++;
 101                 }
 102                 delete[] m_vector;
 103                 m_vector = new uint8[m_bytes];
 104                 memset(m_vector, value ? 0xFF : 0, m_bytes);
 105                 m_allTrue = value ? 1 : 0;
 106         }
 107
 108         // are all bits true ?
 109         bool AllTrue() const
 110         {
 111                 if (m_allTrue == 2) {
 112                         // don't know, have to check
 113                         bool foundFalse = false;
 114                         uint32 lastByte = m_bytes;
 115                         if (m_bits & 7) {
 116                                 // uneven: check bits of last byte individually
 117                                 lastByte--;
 118                                 for (uint32 i = m_bits & 0xfffffff8; !foundFalse && i < m_bits; i++) {
 119                                         foundFalse = !get(i);
 120                                 }
 121                         }
 122                         // check bytewise
 123                         for (uint32 i = 0; !foundFalse && i < lastByte; i++) {
 124                                 foundFalse = m_vector[i] != 0xff;
 125                         }
 126                         // This is really just a caching of information,
 127                         // so m_allTrue is mutable and AllTrue() still const.
 128                         m_allTrue = foundFalse ? 0 : 1;
 129                 }
 130                 return m_allTrue == 1;
 131         }
 132
 133         // set all bits to true
 134         void SetAllTrue() { if (m_bytes) { memset(m_vector, 0xFF, m_bytes); } }
 135
 136         // handling of the internal buffer (for EC)
 137         // get size
 138         uint32 SizeBuffer() const { return m_bytes; }
 139         // get buffer
 140         const void* GetBuffer() const { return m_vector; }
 141         // set buffer
 142         void SetBuffer(const void* src) { memcpy(m_vector, src, m_bytes); m_allTrue = 2; }
 143
 144 private:
 145         uint32  m_bits;                 // number of bits
 146         uint32  m_bytes;                // number of bytes in the vector
 147         uint8 * m_vector;               // the storage
 148         mutable uint8 m_allTrue;// All true ? 0: no  1: yes  2: don't know
 149         static const uint8 s_posMask[]; // = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; implemented in OtherFunctions.cpp
 150         static const uint8 s_negMask[]; // = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F};
 151 };
 152
 153 #endif