1 | /* |
2 | * Copyright 2015-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #include <folly/container/SparseByteSet.h> |
18 | |
19 | #include <cstdint> |
20 | #include <limits> |
21 | #include <random> |
22 | #include <set> |
23 | |
24 | #include <folly/portability/GTest.h> |
25 | |
26 | using namespace std; |
27 | using namespace folly; |
28 | |
29 | namespace { |
30 | |
31 | class SparseByteSetTest : public testing::Test { |
32 | protected: |
33 | using lims = numeric_limits<uint8_t>; |
34 | SparseByteSet s; |
35 | }; |
36 | |
37 | } // namespace |
38 | |
39 | TEST_F(SparseByteSetTest, empty) { |
40 | for (auto c = lims::min(); c < lims::max(); ++c) { |
41 | EXPECT_FALSE(s.contains(c)); |
42 | } |
43 | } |
44 | |
45 | TEST_F(SparseByteSetTest, each) { |
46 | for (auto c = lims::min(); c < lims::max(); ++c) { |
47 | EXPECT_TRUE(s.add(c)); |
48 | EXPECT_TRUE(s.contains(c)); |
49 | } |
50 | for (auto c = lims::min(); c < lims::max(); ++c) { |
51 | EXPECT_FALSE(s.add(c)); |
52 | EXPECT_TRUE(s.contains(c)); |
53 | } |
54 | } |
55 | |
56 | TEST_F(SparseByteSetTest, each_random) { |
57 | mt19937 rng; |
58 | uniform_int_distribution<uint16_t> dist{lims::min(), lims::max()}; |
59 | set<uint8_t> added; |
60 | while (added.size() <= lims::max()) { |
61 | auto c = uint8_t(dist(rng)); |
62 | EXPECT_EQ(added.count(c), s.contains(c)); |
63 | EXPECT_EQ(!added.count(c), s.add(c)); |
64 | added.insert(c); |
65 | EXPECT_TRUE(added.count(c)); // sanity |
66 | EXPECT_TRUE(s.contains(c)); |
67 | } |
68 | } |
69 | |