1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
/*
* Copyright © 2025 Valve Corporation
*
* SPDX-License-Identifier: MIT
*/
#include <gtest/gtest.h>
#include "util/sparse_bitset.h"
TEST(sparse_bitset, tree)
{
struct u_sparse_bitset set;
u_sparse_bitset_init(&set, 1048577, NULL);
u_sparse_bitset_set(&set, 65535);
u_sparse_bitset_set(&set, 1048576);
unsigned num_nodes = 0;
rb_tree_foreach(struct u_sparse_bitset_node, _, &set.tree, node) {
++num_nodes;
}
EXPECT_EQ(num_nodes, 2);
u_sparse_bitset_free(&set);
}
TEST(sparse_bitset, set_clear)
{
struct u_sparse_bitset set;
u_sparse_bitset_init(&set, 1048577, NULL);
u_sparse_bitset_set(&set, 65535);
u_sparse_bitset_set(&set, 1048576);
u_sparse_bitset_set(&set, 16383);
EXPECT_EQ(u_sparse_bitset_test(&set, 128), false);
EXPECT_EQ(u_sparse_bitset_test(&set, 65535), true);
EXPECT_EQ(u_sparse_bitset_test(&set, 16383), true);
u_sparse_bitset_clear(&set, 1236749);
u_sparse_bitset_clear(&set, 65535);
EXPECT_EQ(u_sparse_bitset_test(&set, 65535), false);
u_sparse_bitset_free(&set);
}
TEST(sparse_bitset, set_dup)
{
struct u_sparse_bitset set;
u_sparse_bitset_init(&set, 1048577, NULL);
u_sparse_bitset_set(&set, 65535);
u_sparse_bitset_set(&set, 1048576);
struct u_sparse_bitset set2;
u_sparse_bitset_dup(&set2, &set);
u_sparse_bitset_clear(&set, 65535);
EXPECT_EQ(u_sparse_bitset_test(&set2, 128), false);
EXPECT_EQ(u_sparse_bitset_test(&set2, 65535), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 1048576), true);
u_sparse_bitset_free(&set);
u_sparse_bitset_free(&set2);
}
TEST(sparse_bitset, set_merge)
{
struct u_sparse_bitset set;
u_sparse_bitset_init(&set, 1048577, NULL);
u_sparse_bitset_set(&set, 65535);
u_sparse_bitset_set(&set, 1048576);
struct u_sparse_bitset set2;
u_sparse_bitset_init(&set2, 1048577, NULL);
u_sparse_bitset_set(&set2, 128);
u_sparse_bitset_set(&set2, 16383);
EXPECT_EQ(u_sparse_bitset_merge(&set2, &set), true);
u_sparse_bitset_clear(&set, 65535);
EXPECT_EQ(u_sparse_bitset_test(&set2, 128), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 16383), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 65535), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 1048576), true);
EXPECT_EQ(u_sparse_bitset_merge(&set2, &set), false);
EXPECT_EQ(u_sparse_bitset_test(&set2, 128), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 16383), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 65535), true);
EXPECT_EQ(u_sparse_bitset_test(&set2, 1048576), true);
u_sparse_bitset_free(&set);
u_sparse_bitset_free(&set2);
}
TEST(sparse_bitset, set_foreach)
{
struct u_sparse_bitset set;
u_sparse_bitset_init(&set, 1048577, NULL);
u_sparse_bitset_set(&set, 65535);
u_sparse_bitset_set(&set, 1048576);
u_sparse_bitset_set(&set, 16383);
u_sparse_bitset_set(&set, 19);
u_sparse_bitset_set(&set, 422);
u_sparse_bitset_set(&set, 65539);
uint32_t arr[] = {19, 422, 16383, 65535, 65539, 1048576};
unsigned i = 0;
U_SPARSE_BITSET_FOREACH_SET(&set, it) {
EXPECT_LE(i, ARRAY_SIZE(arr));
EXPECT_EQ(it, arr[i]);
++i;
}
EXPECT_EQ(i, ARRAY_SIZE(arr));
u_sparse_bitset_free(&set);
}
|
