1#include "test/jemalloc_test.h"
2
3#if (LG_BITMAP_MAXBITS > 12)
4#  define MAXBITS	4500
5#else
6#  define MAXBITS	(1U << LG_BITMAP_MAXBITS)
7#endif
8
9TEST_BEGIN(test_bitmap_size)
10{
11	size_t i, prev_size;
12
13	prev_size = 0;
14	for (i = 1; i <= MAXBITS; i++) {
15		size_t size = bitmap_size(i);
16		assert_true(size >= prev_size,
17		    "Bitmap size is smaller than expected");
18		prev_size = size;
19	}
20}
21TEST_END
22
23TEST_BEGIN(test_bitmap_init)
24{
25	size_t i;
26
27	for (i = 1; i <= MAXBITS; i++) {
28		bitmap_info_t binfo;
29		bitmap_info_init(&binfo, i);
30		{
31			size_t j;
32			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
33				bitmap_info_ngroups(&binfo));
34			bitmap_init(bitmap, &binfo);
35
36			for (j = 0; j < i; j++) {
37				assert_false(bitmap_get(bitmap, &binfo, j),
38				    "Bit should be unset");
39			}
40			free(bitmap);
41		}
42	}
43}
44TEST_END
45
46TEST_BEGIN(test_bitmap_set)
47{
48	size_t i;
49
50	for (i = 1; i <= MAXBITS; i++) {
51		bitmap_info_t binfo;
52		bitmap_info_init(&binfo, i);
53		{
54			size_t j;
55			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
56				bitmap_info_ngroups(&binfo));
57			bitmap_init(bitmap, &binfo);
58
59			for (j = 0; j < i; j++)
60				bitmap_set(bitmap, &binfo, j);
61			assert_true(bitmap_full(bitmap, &binfo),
62			    "All bits should be set");
63			free(bitmap);
64		}
65	}
66}
67TEST_END
68
69TEST_BEGIN(test_bitmap_unset)
70{
71	size_t i;
72
73	for (i = 1; i <= MAXBITS; i++) {
74		bitmap_info_t binfo;
75		bitmap_info_init(&binfo, i);
76		{
77			size_t j;
78			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
79				bitmap_info_ngroups(&binfo));
80			bitmap_init(bitmap, &binfo);
81
82			for (j = 0; j < i; j++)
83				bitmap_set(bitmap, &binfo, j);
84			assert_true(bitmap_full(bitmap, &binfo),
85			    "All bits should be set");
86			for (j = 0; j < i; j++)
87				bitmap_unset(bitmap, &binfo, j);
88			for (j = 0; j < i; j++)
89				bitmap_set(bitmap, &binfo, j);
90			assert_true(bitmap_full(bitmap, &binfo),
91			    "All bits should be set");
92			free(bitmap);
93		}
94	}
95}
96TEST_END
97
98TEST_BEGIN(test_bitmap_sfu)
99{
100	size_t i;
101
102	for (i = 1; i <= MAXBITS; i++) {
103		bitmap_info_t binfo;
104		bitmap_info_init(&binfo, i);
105		{
106			ssize_t j;
107			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
108				bitmap_info_ngroups(&binfo));
109			bitmap_init(bitmap, &binfo);
110
111			/* Iteratively set bits starting at the beginning. */
112			for (j = 0; j < i; j++) {
113				assert_zd_eq(bitmap_sfu(bitmap, &binfo), j,
114				    "First unset bit should be just after "
115				    "previous first unset bit");
116			}
117			assert_true(bitmap_full(bitmap, &binfo),
118			    "All bits should be set");
119
120			/*
121			 * Iteratively unset bits starting at the end, and
122			 * verify that bitmap_sfu() reaches the unset bits.
123			 */
124			for (j = i - 1; j >= 0; j--) {
125				bitmap_unset(bitmap, &binfo, j);
126				assert_zd_eq(bitmap_sfu(bitmap, &binfo), j,
127				    "First unset bit should the bit previously "
128				    "unset");
129				bitmap_unset(bitmap, &binfo, j);
130			}
131			assert_false(bitmap_get(bitmap, &binfo, 0),
132			    "Bit should be unset");
133
134			/*
135			 * Iteratively set bits starting at the beginning, and
136			 * verify that bitmap_sfu() looks past them.
137			 */
138			for (j = 1; j < i; j++) {
139				bitmap_set(bitmap, &binfo, j - 1);
140				assert_zd_eq(bitmap_sfu(bitmap, &binfo), j,
141				    "First unset bit should be just after the "
142				    "bit previously set");
143				bitmap_unset(bitmap, &binfo, j);
144			}
145			assert_zd_eq(bitmap_sfu(bitmap, &binfo), i - 1,
146			    "First unset bit should be the last bit");
147			assert_true(bitmap_full(bitmap, &binfo),
148			    "All bits should be set");
149			free(bitmap);
150		}
151	}
152}
153TEST_END
154
155int
156main(void)
157{
158
159	return (test(
160	    test_bitmap_size,
161	    test_bitmap_init,
162	    test_bitmap_set,
163	    test_bitmap_unset,
164	    test_bitmap_sfu));
165}
166