1fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka/* 2fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * Copyright (C) 2017 The Android Open Source Project 3fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * 4fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * Licensed under the Apache License, Version 2.0 (the "License"); 5fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * you may not use this file except in compliance with the License. 6fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * You may obtain a copy of the License at 7fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * 8fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * http://www.apache.org/licenses/LICENSE-2.0 9fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * 10fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * Unless required by applicable law or agreed to in writing, software 11fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * distributed under the License is distributed on an "AS IS" BASIS, 12fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * See the License for the specific language governing permissions and 14fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka * limitations under the License. 15fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka */ 16fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 17fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka#include <random> 18fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 19fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka#include <gtest/gtest.h> 20fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka#include <minikin/SparseBitSet.h> 21fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 22fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonakanamespace minikin { 23fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 24fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo NonakaTEST(SparseBitSetTest, randomTest) { 25fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka const uint32_t kTestRangeNum = 4096; 26fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 27fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka std::mt19937 mt; // Fix seeds to be able to reproduce the result. 28fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka std::uniform_int_distribution<uint16_t> distribution(1, 512); 29fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 30fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka std::vector<uint32_t> range { distribution(mt) }; 31fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (size_t i = 1; i < kTestRangeNum * 2; ++i) { 32fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka range.push_back((range.back() - 1) + distribution(mt)); 33fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 34fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 35db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet bitset(range.data(), range.size() / 2); 36fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 37fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka uint32_t ch = 0; 38fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (size_t i = 0; i < range.size() / 2; ++i) { 39fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka uint32_t start = range[i * 2]; 40fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka uint32_t end = range[i * 2 + 1]; 41fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 42fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (; ch < start; ch++) { 43fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka ASSERT_FALSE(bitset.get(ch)) << std::hex << ch; 44fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 45fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (; ch < end; ch++) { 46fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka ASSERT_TRUE(bitset.get(ch)) << std::hex << ch; 47fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 48fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 49fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (; ch < 0x1FFFFFF; ++ch) { 50fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka ASSERT_FALSE(bitset.get(ch)) << std::hex << ch; 51fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 52fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka} 53fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 54fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka} // namespace minikin 55