Changeset View
Changeset View
Standalone View
Standalone View
src/util/bitset.cpp
Context not available. | |||||
24 | namespace bt | 24 | namespace bt | ||
---|---|---|---|---|---|
25 | { | 25 | { | ||
26 | BitSet BitSet::null; | 26 | BitSet BitSet::null; | ||
27 | | ||||
28 | // Fast lookup table to see how many bits are there in a byte | | |||
29 | static const Uint8 BitCount[] = | | |||
30 | { | | |||
31 | 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, | | |||
32 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | | |||
33 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | | |||
34 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | | |||
35 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | | |||
36 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | | |||
37 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | | |||
38 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | | |||
39 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | | |||
40 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | | |||
41 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | | |||
42 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | | |||
43 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | | |||
44 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | | |||
45 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | | |||
46 | 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 | | |||
47 | }; | | |||
48 | 27 | | |||
49 | 28 | | |||
50 | BitSet::BitSet(Uint32 num_bits) : num_bits(num_bits),data(0) | 29 | BitSet::BitSet(Uint32 num_bits) : num_bits(num_bits),data(0) | ||
51 | { | 30 | { | ||
52 | num_bytes = (num_bits / 8) + ((num_bits % 8 > 0) ? 1 : 0); | 31 | num_bytes = (num_bits >> 3) + (((num_bits & 7) > 0) ? 1 : 0); | ||
53 | data = new Uint8[num_bytes]; | 32 | data = new Uint8[num_bytes]; | ||
54 | std::fill(data,data+num_bytes,0x00); | 33 | std::fill(data,data+num_bytes,0x00); | ||
55 | num_on = 0; | 34 | num_on = 0; | ||
Context not available. | |||||
57 | 36 | | |||
58 | BitSet::BitSet(const Uint8* d,Uint32 num_bits) : num_bits(num_bits),data(0) | 37 | BitSet::BitSet(const Uint8* d,Uint32 num_bits) : num_bits(num_bits),data(0) | ||
59 | { | 38 | { | ||
60 | num_bytes = (num_bits / 8) + ((num_bits % 8 > 0) ? 1 : 0); | 39 | num_bytes = (num_bits >> 3) + (((num_bits & 7) > 0) ? 1 : 0); | ||
61 | data = new Uint8[num_bytes]; | 40 | data = new Uint8[num_bytes]; | ||
62 | memcpy(data,d,num_bytes); | 41 | memcpy(data,d,num_bytes); | ||
63 | num_on = 0; | 42 | num_on = 0; | ||
64 | Uint32 i = 0; | 43 | updateNumOnBits(); | ||
65 | while (i < num_bits) | | |||
66 | { | | |||
67 | if (get(i)) | | |||
68 | num_on++; | | |||
69 | i++; | | |||
70 | } | | |||
71 | } | 44 | } | ||
72 | 45 | | |||
73 | BitSet::BitSet(const BitSet & bs) : num_bits(bs.num_bits),num_bytes(bs.num_bytes),data(0),num_on(bs.num_on) | 46 | BitSet::BitSet(const BitSet & bs) : num_bits(bs.num_bits),num_bytes(bs.num_bytes),data(0),num_on(bs.num_on) | ||
Context not available. | |||||
103 | return *this; | 76 | return *this; | ||
104 | } | 77 | } | ||
105 | 78 | | |||
79 | const Uint8 tail_mask_lookup[8] = {0xFF, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F}; | ||||
80 | | ||||
106 | void BitSet::invert() | 81 | void BitSet::invert() | ||
107 | { | 82 | { | ||
83 | if (num_bytes <= 0) return; | ||||
84 | | ||||
85 | num_on = 0; | ||||
108 | Uint32 i = 0; | 86 | Uint32 i = 0; | ||
109 | while (i < num_bits) | 87 | while (i < num_bytes - 1) | ||
110 | { | 88 | { | ||
111 | set(i,!get(i)); | 89 | data[i] = ~data[i]; | ||
90 | num_on += BitCount[data[i]]; | ||||
112 | i++; | 91 | i++; | ||
113 | } | 92 | } | ||
93 | // i == num_bytes-1 | ||||
94 | data[i] = ~data[i] & tail_mask_lookup[num_bits & 7]; | ||||
95 | num_on += BitCount[data[i]]; | ||||
114 | } | 96 | } | ||
115 | 97 | | |||
116 | BitSet & BitSet::operator -= (const BitSet & bs) | 98 | BitSet & BitSet::operator -= (const BitSet & bs) | ||
117 | { | 99 | { | ||
118 | Uint32 i = 0; | 100 | num_on = 0; | ||
119 | while (i < num_bits) | 101 | for (Uint32 i = 0; i < num_bytes; i++) | ||
120 | { | 102 | { | ||
121 | if (get(i) && bs.get(i)) | 103 | data[i] &= ~(data[i] & bs.data[i]); | ||
122 | set(i,false); | 104 | num_on += BitCount[data[i]]; | ||
123 | i++; | | |||
124 | } | 105 | } | ||
125 | return *this; | 106 | return *this; | ||
126 | } | 107 | } | ||
Context not available. | |||||
142 | } | 123 | } | ||
143 | 124 | | |||
144 | void BitSet::orBitSet(const BitSet & other) | 125 | void BitSet::orBitSet(const BitSet & other) | ||
145 | { | 126 | { | ||
146 | Uint32 i = 0; | | |||
147 | num_on = 0; | 127 | num_on = 0; | ||
148 | while (i < num_bytes) | 128 | | ||
149 | { | 129 | if (num_bits == other.num_bits) { | ||
150 | Uint8 od = 0; | 130 | // best case | ||
151 | if (i < other.num_bytes) | 131 | for (Uint32 i = 0; i < num_bytes; i++) { | ||
152 | od = other.data[i]; | 132 | data[i] |= other.data[i]; | ||
153 | data[i] |= od; | 133 | num_on += BitCount[data[i]]; | ||
134 | } | ||||
135 | return; | ||||
136 | } | ||||
137 | | ||||
138 | // process till the end of other data or last-1 byte in our data | ||||
139 | // whatether comes first | ||||
140 | for (Uint32 i = 0; i < qMin(num_bytes - 1, other.num_bytes); i++) { | ||||
141 | data[i] |= other.data[i]; | ||||
142 | num_on += BitCount[data[i]]; | ||||
143 | } | ||||
144 | | ||||
145 | // if last-1 not reached yet then the end of other data is reached | ||||
146 | // so just add BitCount till last-1 byte | ||||
147 | for (Uint32 i = other.num_bytes; i < num_bytes - 1; i++) { | ||||
154 | num_on += BitCount[data[i]]; | 148 | num_on += BitCount[data[i]]; | ||
155 | i++; | | |||
156 | } | 149 | } | ||
150 | | ||||
151 | // if other has matching byte for our last byte - OR it with proper mask | ||||
152 | if (other.num_bytes >= num_bytes) { | ||||
153 | data[num_bytes-1] = (data[num_bytes-1] | other.data[num_bytes-1]) & tail_mask_lookup[num_bytes & 7]; | ||||
154 | } | ||||
155 | | ||||
156 | // count bits set in last byte | ||||
157 | num_on += BitCount[data[num_bytes-1]]; | ||||
157 | } | 158 | } | ||
158 | 159 | | |||
159 | void BitSet::andBitSet(const BitSet & other) | 160 | void BitSet::andBitSet(const BitSet & other) | ||
160 | { | 161 | { | ||
161 | Uint32 i = 0; | | |||
162 | num_on = 0; | 162 | num_on = 0; | ||
163 | while (i < num_bytes) | 163 | | ||
164 | { | 164 | if (num_bits == other.num_bits) { | ||
165 | Uint8 od = 0; | 165 | // best case | ||
166 | if (i < other.num_bytes) | 166 | for (Uint32 i = 0; i < num_bytes; i++) { | ||
167 | od = other.data[i]; | 167 | data[i] &= other.data[i]; | ||
168 | data[i] &= od; | 168 | num_on += BitCount[data[i]]; | ||
169 | } | ||||
170 | return; | ||||
171 | } | ||||
172 | | ||||
173 | // we expect 0's at the tail of last byte (if any) | ||||
174 | // so just AND matching bytes and clear the others | ||||
175 | // no need to worry about mask for last byte | ||||
176 | for (Uint32 i = 0; i < qMin(num_bytes, other.num_bytes); i++) { | ||||
177 | data[i] &= other.data[i]; | ||||
169 | num_on += BitCount[data[i]]; | 178 | num_on += BitCount[data[i]]; | ||
170 | i++; | | |||
171 | } | 179 | } | ||
180 | | ||||
181 | if (num_bytes > other.num_bytes) { | ||||
182 | memset(data+other.num_bytes, 0, num_bytes - other.num_bytes); | ||||
183 | } | ||||
184 | | ||||
172 | } | 185 | } | ||
173 | 186 | | |||
174 | bool BitSet::includesBitSet(const BitSet & other) | 187 | bool BitSet::includesBitSet(const BitSet & other) const | ||
175 | { | 188 | { | ||
176 | Uint32 i = 0; | 189 | | ||
177 | while (i < num_bits) | 190 | if (num_bits == other.num_bits) { | ||
178 | { | 191 | // best case | ||
179 | if (other.get(i) && !get(i)) | 192 | for (Uint32 i = 0; i < num_bytes; i++) { | ||
193 | if ( (data[i] | other.data[i]) != data[i]) { | ||||
194 | return false; | ||||
195 | } | ||||
196 | } | ||||
197 | return true; | ||||
198 | } | ||||
199 | | ||||
200 | // process till the end of other data or last-1 byte in our data | ||||
201 | // whatether comes first | ||||
202 | for (Uint32 i = 0; i < qMin(num_bytes - 1, other.num_bytes); i++) { | ||||
203 | if ( (data[i] | other.data[i]) != data[i]) { | ||||
180 | return false; | 204 | return false; | ||
181 | i++; | 205 | } | ||
182 | } | 206 | } | ||
207 | | ||||
208 | // if other has matching byte for our last byte - OR it with proper mask | ||||
209 | if (other.num_bytes >= num_bytes) { | ||||
210 | const Uint8 d = data[num_bytes-1]; | ||||
211 | if ( ( (d | other.data[num_bytes-1]) & tail_mask_lookup[num_bytes & 7]) != d) { | ||||
212 | return false; | ||||
213 | } | ||||
214 | } | ||||
215 | | ||||
183 | return true; | 216 | return true; | ||
184 | } | 217 | } | ||
185 | 218 | | |||
Context not available. |