1 /*++ 2 Copyright (c) 2006 Microsoft Corporation 3 4 Module Name: 5 6 tst_bitvector.cpp 7 8 Abstract: 9 10 Test bitvector module 11 12 Author: 13 14 Leonardo de Moura (leonardo) 2006-10-03. 15 16 Revision History: 17 18 --*/ 19 #include<cstdlib> 20 #include<iostream> 21 #include "util/bit_vector.h" 22 #include "util/vector.h" 23 tst1()24static void tst1() { 25 bit_vector v1; 26 bool_vector v2; 27 unsigned n = rand()%10000; 28 for (unsigned i = 0; i < n; i++) { 29 int op = rand()%6; 30 if (op <= 1) { 31 bool val = (rand()%2) != 0; 32 v1.push_back(val); 33 v2.push_back(val); 34 ENSURE(v1.size() == v2.size()); 35 } 36 else if (op <= 3) { 37 ENSURE(v1.size() == v2.size()); 38 if (!v1.empty()) { 39 bool val = (rand()%2) != 0; 40 unsigned idx = rand()%v1.size(); 41 ENSURE(v1.get(idx) == v2[idx]); 42 v1.set(idx, val); 43 v2[idx] = val; 44 ENSURE(v1.get(idx) == v2[idx]); 45 } 46 } 47 else if (op <= 4) { 48 ENSURE(v1.size() == v2.size()); 49 if (!v1.empty()) { 50 unsigned idx = rand()%v1.size(); 51 VERIFY(v1.get(idx) == v2[idx]); 52 } 53 } 54 else if (op <= 5) { 55 ENSURE(v1.size() == v2.size()); 56 for (unsigned j = 0; j < v1.size(); j++) { 57 ENSURE(v1.get(j) == v2[j]); 58 } 59 } 60 } 61 } 62 tst2()63static void tst2() { 64 bit_vector b; 65 b.push_back(true); 66 b.push_back(false); 67 b.push_back(true); 68 b.resize(30); 69 ENSURE(b.get(0) == true); 70 ENSURE(b.get(1) == false); 71 ENSURE(b.get(2) == true); 72 ENSURE(b.get(3) == false); 73 ENSURE(b.get(29) == false); 74 } 75 tst_shift()76static void tst_shift() { 77 bit_vector b; 78 b.resize(111); 79 b.set(105); 80 b.set(99); 81 b.set(98); 82 b.set(90); 83 b.set(80); 84 b.set(75); 85 b.set(33); 86 b.set(32); 87 b.set(31); 88 b.set(30); 89 b.set(10); 90 std::cout << "b: " << b << "\n"; 91 b.shift_right(16); 92 std::cout << "b: " << b << "\n"; 93 b.shift_right(1); 94 std::cout << "b: " << b << "\n"; 95 b.shift_right(32); 96 std::cout << "b: " << b << "\n"; 97 b.shift_right(42); 98 std::cout << "b: " << b << "\n"; 99 b.shift_right(16); 100 std::cout << "b: " << b << "\n"; 101 b.shift_right(63); 102 std::cout << "b: " << b << "\n"; 103 } 104 tst_or()105static void tst_or() { 106 { 107 bit_vector b1; 108 bit_vector b2; 109 b1.resize(5); 110 b2.resize(10); 111 b1.set(4); 112 b2.set(8); 113 b2.set(3); 114 b2.set(2); 115 b2.set(1); 116 std::cout << b1 << "\n"; 117 std::cout << b2 << "\n"; 118 b1 |= b2; 119 ENSURE(b1.size() == 10); 120 std::cout << b1 << "\n"; 121 ENSURE(b1 != b2); 122 ENSURE(b1 != b2); 123 b1.unset(4); 124 ENSURE(b1 == b2); 125 b1.unset(3); 126 ENSURE(b1 != b2); 127 } 128 { 129 bit_vector b1; 130 bit_vector b2; 131 b1.resize(2); 132 b2.resize(5); 133 b1.set(0); 134 b2.set(4); 135 b1 |= b2; 136 ENSURE(b1 != b2); 137 b2.set(0); 138 ENSURE(b1 == b2); 139 std::cout << "-----\n"; 140 std::cout << b1 << "\n"; 141 } 142 { 143 bit_vector b1; 144 bit_vector b2; 145 b1.resize(10); 146 b2.resize(10); 147 b1.set(5); 148 b2.set(8); 149 b2.set(3); 150 b2.resize(5); 151 b1 |= b2; 152 ENSURE(!b1.get(8)); 153 ENSURE(b1.get(5)); 154 ENSURE(b1.get(3)); 155 } 156 { 157 bit_vector b1; 158 bit_vector b2; 159 b1.resize(123); 160 b2.resize(126); 161 b2.set(124); 162 b1.set(122); 163 b1.set(100); 164 b2.set(100); 165 b1.set(80); 166 b2.set(80); 167 b1.set(4); 168 b2.set(4); 169 ENSURE(b1!=b2); 170 b2.resize(123); 171 ENSURE(b1!=b2); 172 b1.resize(120); 173 b2.resize(120); 174 ENSURE(b1==b2); 175 b1.unset(80); 176 b1.unset(100); 177 ENSURE(b1!=b2); 178 b1 |= b2; 179 ENSURE(b1 == b2); 180 } 181 { 182 bit_vector b1; 183 bit_vector b2; 184 b1.resize(5); 185 b2.resize(10); 186 b2.set(8); 187 b1.set(4); 188 b2.set(1); 189 b1.set(0); 190 b1 |= b2; 191 ENSURE(b1.size() == 10); 192 ENSURE(b1.get(8) && b1.get(4) && b1.get(1) && b1.get(0) && !b1.get(9)); 193 } 194 { 195 bit_vector b1; 196 bit_vector b2; 197 b1.resize(32); 198 b2.resize(32); 199 b1.set(1); 200 b1.set(5); 201 b2.set(8); 202 b2.set(0); 203 b1 |= b2; 204 ENSURE(b1.get(1) && b1.get(5) && b1.get(8) && b1.get(0) && !b1.get(11)); 205 std::cout << "b1(size32): " << b1 << "\n"; 206 } 207 } 208 tst_and()209static void tst_and() { 210 { 211 bit_vector b1; 212 bit_vector b2; 213 b1.resize(5); 214 b2.resize(3); 215 b2.set(2); 216 b1.set(2); 217 b1.set(4); 218 std::cout << "------\nb1: " << b1 << "\n"; 219 b1 &= b2; 220 std::cout << "------\nb1: " << b1 << "\n"; 221 ENSURE(!b1.get(4)); 222 ENSURE(b1.get(2)); 223 } 224 { 225 bit_vector b1; 226 bit_vector b2; 227 b1.resize(241); 228 b2.resize(128); 229 b1.set(240); 230 b1.set(232); 231 b1.set(127); 232 b1.set(128); 233 b1.set(8); 234 b2.set(127); 235 b2.set(5); 236 b1 &= b2; 237 ENSURE(!b1.get(240) && !b1.get(232) && !b1.get(128) && b1.get(127) && !b1.get(8) && !b1.get(5)); 238 } 239 } 240 tst_crash()241static void tst_crash() { 242 { 243 bit_vector b; 244 b.push_back(true); 245 b.resize(64); 246 ENSURE(!b.get(63)); 247 ENSURE(b.get(0)); 248 ENSURE(!b.get(1)); 249 } 250 { 251 bit_vector b; 252 b.push_back(false); 253 b.resize(64, true); 254 ENSURE(b.get(63)); 255 ENSURE(!b.get(0)); 256 ENSURE(b.get(1)); 257 } 258 } 259 tst_bv_reset()260static void tst_bv_reset() { 261 bit_vector b; 262 bool bit = true; 263 for (unsigned sz = 1; sz < 84; ++sz) { 264 b.reset(); 265 b.resize(sz, bit); 266 for (unsigned i = 0; i < sz; ++i) { 267 ENSURE(bit == b.get(i)); 268 } 269 for (unsigned sz2 = sz; sz2 < sz+10; ++sz2) { 270 b.resize(sz2, !bit); 271 for (unsigned i = sz; i < sz2; ++i) { 272 ENSURE(bit != b.get(i)); 273 } 274 } 275 bit = !bit; 276 } 277 } 278 tst_eq()279static void tst_eq() { 280 bit_vector b1, b2, b3; 281 b1.resize(32); 282 b2.resize(32); 283 b3.resize(32); 284 285 b1.set(3, true); 286 ENSURE(b1 != b2); 287 ENSURE(!(b1 == b2)); 288 ENSURE(b2 == b3); 289 290 b3.set(3, true); 291 ENSURE(b1 == b3); 292 ENSURE(!(b1 != b3)); 293 294 b2.set(31, true); 295 b3.set(31); 296 b3.unset(3); 297 ENSURE(b2 == b3); 298 ENSURE(!(b2 != b3)); 299 } 300 tst_bit_vector()301void tst_bit_vector() { 302 tst_crash(); 303 tst_shift(); 304 tst_or(); 305 tst_and(); 306 tst_bv_reset(); 307 tst_eq(); 308 return; 309 tst2(); 310 for (unsigned i = 0; i < 20; i++) { 311 std::cerr << i << std::endl; 312 tst1(); 313 } 314 } 315