182 lines · cpp
1//===-- sanitizer_bitvector_test.cpp --------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of Sanitizer runtime.10// Tests for sanitizer_bitvector.h.11//12//===----------------------------------------------------------------------===//13#include "sanitizer_common/sanitizer_bitvector.h"14 15#include "sanitizer_test_utils.h"16 17#include "gtest/gtest.h"18 19#include <algorithm>20#include <vector>21#include <random>22#include <set>23 24using namespace __sanitizer;25using namespace std;26 27 28// Check the 'bv' == 's' and that the indexes go in increasing order.29// Also check the BV::Iterator30template <class BV>31static void CheckBV(const BV &bv, const set<uptr> &s) {32 BV t;33 t.copyFrom(bv);34 set<uptr> t_s(s);35 uptr last_idx = bv.size();36 uptr count = 0;37 for (typename BV::Iterator it(bv); it.hasNext();) {38 uptr idx = it.next();39 count++;40 if (last_idx != bv.size())41 EXPECT_LT(last_idx, idx);42 last_idx = idx;43 EXPECT_TRUE(s.count(idx));44 }45 EXPECT_EQ(count, s.size());46 47 last_idx = bv.size();48 while (!t.empty()) {49 uptr idx = t.getAndClearFirstOne();50 if (last_idx != bv.size())51 EXPECT_LT(last_idx, idx);52 last_idx = idx;53 EXPECT_TRUE(t_s.erase(idx));54 }55 EXPECT_TRUE(t_s.empty());56}57 58template <class BV>59void Print(const BV &bv) {60 BV t;61 t.copyFrom(bv);62 while (!t.empty()) {63 uptr idx = t.getAndClearFirstOne();64 fprintf(stderr, "%lu ", idx);65 }66 fprintf(stderr, "\n");67}68 69void Print(const set<uptr> &s) {70 for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) {71#if defined(_WIN64)72 fprintf(stderr, "%llu ", *it);73#else74 fprintf(stderr, "%lu ", (unsigned long)*it);75#endif76 }77 fprintf(stderr, "\n");78}79 80template <class BV>81void TestBitVector(uptr expected_size) {82 std::mt19937 r;83 BV bv, bv1, t_bv;84 EXPECT_EQ(expected_size, BV::kSize);85 bv.clear();86 EXPECT_TRUE(bv.empty());87 bv.setBit(5);88 EXPECT_FALSE(bv.empty());89 EXPECT_FALSE(bv.getBit(4));90 EXPECT_FALSE(bv.getBit(6));91 EXPECT_TRUE(bv.getBit(5));92 bv.clearBit(5);93 EXPECT_FALSE(bv.getBit(5));94 95 // test random bits96 bv.clear();97 set<uptr> s;98 for (uptr it = 0; it < 1000; it++) {99 uptr bit = ((uptr)my_rand() % bv.size());100 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);101 switch (my_rand() % 2) {102 case 0:103 EXPECT_EQ(bv.setBit(bit), s.insert(bit).second);104 break;105 case 1:106 size_t old_size = s.size();107 s.erase(bit);108 EXPECT_EQ(bv.clearBit(bit), old_size > s.size());109 break;110 }111 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);112 }113 114 vector<uptr>bits(bv.size());115 // Test setUnion, setIntersection, setDifference,116 // intersectsWith, and getAndClearFirstOne.117 for (uptr it = 0; it < 30; it++) {118 // iota119 for (size_t j = 0; j < bits.size(); j++) bits[j] = j;120 std::shuffle(bits.begin(), bits.end(), r);121 set<uptr> s, s1, t_s;122 bv.clear();123 bv1.clear();124 uptr n_bits = ((uptr)my_rand() % bv.size()) + 1;125 uptr n_bits1 = (uptr)my_rand() % (bv.size() / 2);126 EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size());127 EXPECT_TRUE(n_bits1 < bv.size() / 2);128 for (uptr i = 0; i < n_bits; i++) {129 bv.setBit(bits[i]);130 s.insert(bits[i]);131 }132 CheckBV(bv, s);133 for (uptr i = 0; i < n_bits1; i++) {134 bv1.setBit(bits[bv.size() / 2 + i]);135 s1.insert(bits[bv.size() / 2 + i]);136 }137 CheckBV(bv1, s1);138 139 vector<uptr> vec;140 set_intersection(s.begin(), s.end(), s1.begin(), s1.end(),141 back_insert_iterator<vector<uptr> >(vec));142 EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty());143 144 // setUnion145 t_s = s;146 t_bv.copyFrom(bv);147 t_s.insert(s1.begin(), s1.end());148 EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size());149 CheckBV(t_bv, t_s);150 151 // setIntersection152 t_s = set<uptr>(vec.begin(), vec.end());153 t_bv.copyFrom(bv);154 EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size());155 CheckBV(t_bv, t_s);156 157 // setDifference158 vec.clear();159 set_difference(s.begin(), s.end(), s1.begin(), s1.end(),160 back_insert_iterator<vector<uptr> >(vec));161 t_s = set<uptr>(vec.begin(), vec.end());162 t_bv.copyFrom(bv);163 EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size());164 CheckBV(t_bv, t_s);165 }166}167 168TEST(SanitizerCommon, BasicBitVector) {169 TestBitVector<BasicBitVector<u8> >(8);170 TestBitVector<BasicBitVector<u16> >(16);171 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE);172}173 174TEST(SanitizerCommon, TwoLevelBitVector) {175 uptr ws = SANITIZER_WORDSIZE;176 TestBitVector<TwoLevelBitVector<1, BasicBitVector<u8> > >(8 * 8);177 TestBitVector<TwoLevelBitVector<> >(ws * ws);178 TestBitVector<TwoLevelBitVector<2> >(ws * ws * 2);179 TestBitVector<TwoLevelBitVector<3> >(ws * ws * 3);180 TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >(16 * 16 * 3);181}182