bitmap.c revision 86abd0dcd8e478759fe409d338d11558c4cec427 
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
9static void
10test_bitmap_size(void)
11{
12	size_t i, prev_size;
13
14	prev_size = 0;
15	for (i = 1; i <= MAXBITS; i++) {
16		size_t size = bitmap_size(i);
17		assert(size >= prev_size);
18		prev_size = size;
19	}
20}
21
22static void
23test_bitmap_init(void)
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(bitmap_get(bitmap, &binfo, j) == false);
38			free(bitmap);
39		}
40	}
41}
42
43static void
44test_bitmap_set(void)
45{
46	size_t i;
47
48	for (i = 1; i <= MAXBITS; i++) {
49		bitmap_info_t binfo;
50		bitmap_info_init(&binfo, i);
51		{
52			size_t j;
53			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
54				bitmap_info_ngroups(&binfo));
55			bitmap_init(bitmap, &binfo);
56
57			for (j = 0; j < i; j++)
58				bitmap_set(bitmap, &binfo, j);
59			assert(bitmap_full(bitmap, &binfo));
60			free(bitmap);
61		}
62	}
63}
64
65static void
66test_bitmap_unset(void)
67{
68	size_t i;
69
70	for (i = 1; i <= MAXBITS; i++) {
71		bitmap_info_t binfo;
72		bitmap_info_init(&binfo, i);
73		{
74			size_t j;
75			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
76				bitmap_info_ngroups(&binfo));
77			bitmap_init(bitmap, &binfo);
78
79			for (j = 0; j < i; j++)
80				bitmap_set(bitmap, &binfo, j);
81			assert(bitmap_full(bitmap, &binfo));
82			for (j = 0; j < i; j++)
83				bitmap_unset(bitmap, &binfo, j);
84			for (j = 0; j < i; j++)
85				bitmap_set(bitmap, &binfo, j);
86			assert(bitmap_full(bitmap, &binfo));
87			free(bitmap);
88		}
89	}
90}
91
92static void
93test_bitmap_sfu(void)
94{
95	size_t i;
96
97	for (i = 1; i <= MAXBITS; i++) {
98		bitmap_info_t binfo;
99		bitmap_info_init(&binfo, i);
100		{
101			ssize_t j;
102			bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
103				bitmap_info_ngroups(&binfo));
104			bitmap_init(bitmap, &binfo);
105
106			/* Iteratively set bits starting at the beginning. */
107			for (j = 0; j < i; j++)
108				assert(bitmap_sfu(bitmap, &binfo) == j);
109			assert(bitmap_full(bitmap, &binfo));
110
111			/*
112			 * Iteratively unset bits starting at the end, and
113			 * verify that bitmap_sfu() reaches the unset bits.
114			 */
115			for (j = i - 1; j >= 0; j--) {
116				bitmap_unset(bitmap, &binfo, j);
117				assert(bitmap_sfu(bitmap, &binfo) == j);
118				bitmap_unset(bitmap, &binfo, j);
119			}
120			assert(bitmap_get(bitmap, &binfo, 0) == false);
121
122			/*
123			 * Iteratively set bits starting at the beginning, and
124			 * verify that bitmap_sfu() looks past them.
125			 */
126			for (j = 1; j < i; j++) {
127				bitmap_set(bitmap, &binfo, j - 1);
128				assert(bitmap_sfu(bitmap, &binfo) == j);
129				bitmap_unset(bitmap, &binfo, j);
130			}
131			assert(bitmap_sfu(bitmap, &binfo) == i - 1);
132			assert(bitmap_full(bitmap, &binfo));
133			free(bitmap);
134		}
135	}
136}
137
138int
139main(void)
140{
141	malloc_printf("Test begin\n");
142
143	test_bitmap_size();
144	test_bitmap_init();
145	test_bitmap_set();
146	test_bitmap_unset();
147	test_bitmap_sfu();
148
149	malloc_printf("Test end\n");
150	return (0);
151}
152