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 171d461589869ee5b7102f96271b0ef0a776ab513cSeigo Nonaka#include "minikin/SparseBitSet.h" 181d461589869ee5b7102f96271b0ef0a776ab513cSeigo Nonaka 19fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka#include <random> 20fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 21fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka#include <gtest/gtest.h> 22fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 23fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonakanamespace minikin { 24fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 25fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo NonakaTEST(SparseBitSetTest, randomTest) { 26fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka const uint32_t kTestRangeNum = 4096; 27fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 28fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka std::mt19937 mt; // Fix seeds to be able to reproduce the result. 29fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka std::uniform_int_distribution<uint16_t> distribution(1, 512); 30fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 316c8722e217ff5238f0b849152d7936959a728103Seigo Nonaka std::vector<uint32_t> range{distribution(mt)}; 32fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (size_t i = 1; i < kTestRangeNum * 2; ++i) { 33fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka range.push_back((range.back() - 1) + distribution(mt)); 34fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 35fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 36db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet bitset(range.data(), range.size() / 2); 37fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 38fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka uint32_t ch = 0; 39fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (size_t i = 0; i < range.size() / 2; ++i) { 40fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka uint32_t start = range[i * 2]; 41fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka uint32_t end = range[i * 2 + 1]; 42fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 43fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (; ch < start; ch++) { 44fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka ASSERT_FALSE(bitset.get(ch)) << std::hex << ch; 45fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 46fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (; ch < end; ch++) { 47fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka ASSERT_TRUE(bitset.get(ch)) << std::hex << ch; 48fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 49fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 50fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka for (; ch < 0x1FFFFFF; ++ch) { 51fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka ASSERT_FALSE(bitset.get(ch)) << std::hex << ch; 52fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka } 53fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka} 54fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 55fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka} // namespace minikin 56