File indexing completed on 2024-03-24 04:38:44
0001 /* This file is part of kdev-pg-qt 0002 Copyright (C) 2010 Jonathan Schmidt-Dominé <devel@the-user.org> 0003 0004 This library is free software; you can redistribute it and/or 0005 modify it under the terms of the GNU Library General Public 0006 License as published by the Free Software Foundation; either 0007 version 2 of the License, or (at your option) any later version. 0008 0009 This library is distributed in the hope that it will be useful, 0010 but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 Library General Public License for more details. 0013 0014 You should have received a copy of the GNU Library General Public License 0015 along with this library; see the file COPYING.LIB. If not, write to 0016 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 Boston, MA 02110-1301, USA. 0018 */ 0019 0020 #ifndef KDEV_PG_BIT_ARRAY 0021 #define KDEV_PG_BIT_ARRAY 0022 0023 #include <iostream> 0024 #include <cstring> 0025 #include <unordered_set> 0026 0027 class BitArray 0028 { 0029 typedef std::size_t size_t; 0030 size_t mSize; 0031 union 0032 { 0033 unsigned char *mByte; 0034 size_t *mWord; 0035 }; 0036 friend struct ::std::hash<BitArray>; 0037 enum { BPW = sizeof(size_t) * 8 }; // Bits per word 0038 static inline size_t words(size_t n) 0039 { 0040 return (n + BPW - 1) / BPW; 0041 } 0042 inline size_t words() const 0043 { 0044 return words(mSize); 0045 } 0046 static inline size_t bytes(size_t n) 0047 { 0048 return words(n) * sizeof(size_t); 0049 } 0050 inline size_t bytes() const 0051 { 0052 return bytes(mSize); 0053 } 0054 inline void setZerosAtEnd() 0055 { 0056 mWord[words() - 1] &= ((~size_t(0)) << (BPW - mSize % BPW)); 0057 } 0058 public: 0059 struct BitRef 0060 { 0061 unsigned char &byte; 0062 unsigned char bit: 3; 0063 inline BitRef(unsigned char &byte, unsigned char bit) : byte(byte), bit(bit) 0064 {} 0065 inline operator bool() const 0066 { 0067 return (byte & (1 << bit)) == (1 << bit); 0068 } 0069 inline BitRef& operator=(bool val) 0070 { 0071 if(val) 0072 byte |= (1 << bit); 0073 else 0074 byte &= ~(1 << bit); 0075 return *this; 0076 } 0077 inline BitRef& operator=(const BitRef& val) 0078 { 0079 return *this = (bool)val; 0080 } 0081 }; 0082 inline BitArray(size_t size) : mSize(size), mByte(reinterpret_cast<unsigned char*>(malloc(bytes()))) 0083 { 0084 memset(mByte, 0, bytes()); 0085 setZerosAtEnd(); 0086 } 0087 inline BitArray() : mSize(0), mByte((unsigned char*)malloc(0)) 0088 { 0089 } 0090 inline BitArray(const BitArray& o) : mSize(o.mSize), mByte(reinterpret_cast<unsigned char*>(malloc(bytes()))) 0091 { 0092 for(size_t *i = mWord, *j = o.mWord; i != mWord + words(); ++i, ++j) 0093 *i = *j; 0094 } 0095 inline bool operator<(const BitArray& o) const 0096 { 0097 if(size() < o.size()) 0098 return true; 0099 if(o.size() < size()) 0100 return false; 0101 if(size() == 0) 0102 return false; 0103 size_t *i, *j; 0104 for(i = mWord, j = o.mWord; i != mWord + words(); ++i, ++j) 0105 { 0106 if(*i < *j) 0107 return true; 0108 if(*j < *i) 0109 return false; 0110 } 0111 return false; 0112 } 0113 inline ~BitArray() 0114 { 0115 free(mByte); 0116 } 0117 inline bool operator==(const BitArray& o) const 0118 { 0119 if(o.size() != size()) 0120 return false; 0121 if(size() == 0) 0122 return true; 0123 size_t *i, *j; 0124 for(i = mWord, j = o.mWord; i != mWord + words(); ++i, ++j) 0125 { 0126 if(*i != *j) 0127 return false; 0128 } 0129 return true; 0130 } 0131 inline BitArray& operator=(const BitArray& o) 0132 { 0133 if(&o != this) 0134 { 0135 this->~BitArray(); 0136 new (this)BitArray(o); 0137 } 0138 return *this; 0139 } 0140 inline bool operator[](size_t x) const 0141 { 0142 if(x > size()) 0143 cerr << "out of bounds" << endl; 0144 return (mByte[x >> 3] & (1 << (x & 7))) == (1 << (x & 7)); 0145 } 0146 inline BitRef operator[](size_t x) 0147 { 0148 if(x > size()) 0149 cerr << "out of bounds" << endl; 0150 return BitRef(mByte[x >> 3], x & 7); 0151 } 0152 inline void resize(size_t size) 0153 { 0154 mByte = reinterpret_cast<unsigned char*>(realloc(mByte, bytes(size))); 0155 if(size > mSize) 0156 { 0157 memset(mWord + words(), 0, bytes(size) - bytes()); 0158 } 0159 mSize = size; 0160 } 0161 inline size_t size() const 0162 { 0163 return mSize; 0164 } 0165 }; 0166 0167 namespace std 0168 { 0169 template<> struct hash<BitArray> 0170 { 0171 inline size_t operator()(const BitArray &x) const 0172 { 0173 size_t ret = 0; 0174 for(size_t *i = x.mWord; i != x.mWord + x.words(); ++i) 0175 { 0176 ret ^= *i; 0177 ret = (ret >> (sizeof(size_t)*8 - 17)) | (ret << 17); 0178 } 0179 return ret; 0180 } 0181 }; 0182 } 0183 0184 std::ostream& operator<<(std::ostream &o, const BitArray &a) 0185 { 0186 for(size_t i = 0; i != a.size(); ++i) 0187 { 0188 o << (int)a[i]; 0189 } 0190 return o; 0191 } 0192 0193 #endif