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: BitVector()34 BitVector() 35 { 36 m_bits = 0; 37 m_bytes = 0; 38 m_allTrue = 0; 39 m_vector = NULL; 40 } 41 ~BitVector()42 ~BitVector() { clear(); } 43 44 // number of bits size()45 uint32 size() const { return m_bits; } 46 47 // is it empty? empty()48 bool empty() const { return m_bits == 0; } 49 50 // get bit at index get(uint32 idx)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 set(uint32 idx,bool value)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 clear()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 setsize(uint32 newsize,bool 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 ? AllTrue()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 SetAllTrue()134 void SetAllTrue() { if (m_bytes) { memset(m_vector, 0xFF, m_bytes); } } 135 136 // handling of the internal buffer (for EC) 137 // get size SizeBuffer()138 uint32 SizeBuffer() const { return m_bytes; } 139 // get buffer GetBuffer()140 const void* GetBuffer() const { return m_vector; } 141 // set buffer SetBuffer(const void * src)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 154