5 #include "../lib/lfsr.h"
6 #include "../lib/axmap.h"
8 static int test_regular(uint64_t size, int seed)
14 printf("Using %llu entries...", (unsigned long long) size);
17 lfsr_init(&lfsr, size, seed, seed & 0xF);
18 map = axmap_new(size);
24 if (lfsr_next(&lfsr, &val)) {
25 printf("lfsr: short loop\n");
29 if (axmap_isset(map, val)) {
30 printf("bit already set\n");
35 if (!axmap_isset(map, val)) {
36 printf("bit not set\n");
50 static int check_next_free(struct axmap *map, uint64_t start, uint64_t expected)
55 ff = axmap_next_free(map, start);
57 printf("axmap_next_free broken: Expected %llu, got %llu\n",
58 (unsigned long long)expected, (unsigned long long) ff);
64 static int test_next_free(uint64_t size, int seed)
69 uint64_t ff, lastfree;
72 printf("Test next_free %llu entries...", (unsigned long long) size);
75 map = axmap_new(size);
79 /* Empty map. Next free after 0 should be 1. */
80 if (check_next_free(map, 0, 1))
83 /* Empty map. Next free after 63 should be 64. */
84 if (check_next_free(map, 63, 64))
87 /* Empty map. Next free after size - 2 should be size - 1 */
88 if (check_next_free(map, size - 2, size - 1))
91 /* Empty map. Next free after size - 1 should be 0 */
92 if (check_next_free(map, size - 1, 0))
95 /* Empty map. Next free after 63 should be 64. */
96 if (check_next_free(map, 63, 64))
100 /* Bit 63 set. Next free after 62 should be 64. */
102 if (check_next_free(map, 62, 64))
105 /* Last bit set. Next free after size - 2 should be 0. */
106 axmap_set(map, size - 1);
107 if (check_next_free(map, size - 2, 0))
110 /* Last bit set. Next free after size - 1 should be 0. */
111 if (check_next_free(map, size - 1, 0))
114 /* Last 64 bits set. Next free after size - 66 or size - 65 should be 0. */
115 for (i=size - 65; i < size; i++)
117 if (check_next_free(map, size - 66, 0))
119 if (check_next_free(map, size - 65, 0))
122 /* Last 64 bits set. Next free after size - 67 should be size - 66. */
123 if (check_next_free(map, size - 67, size - 66))
128 /* Start with a fresh map and mostly fill it up */
129 lfsr_init(&lfsr, size, seed, seed & 0xF);
130 map = axmap_new(size);
133 /* Leave 1 entry free */
138 if (lfsr_next(&lfsr, &val)) {
139 printf("lfsr: short loop\n");
143 if (axmap_isset(map, val)) {
144 printf("bit already set\n");
149 if (!axmap_isset(map, val)) {
150 printf("bit not set\n");
156 /* Get last free bit */
157 lastfree = axmap_next_free(map, 0);
158 if (lastfree == -1ULL) {
159 printf("axmap_next_free broken: Couldn't find last free bit\n");
163 /* Start with last free bit and test wrap-around */
164 ff = axmap_next_free(map, lastfree);
165 if (ff != lastfree) {
166 printf("axmap_next_free broken: wrap-around test #1 failed\n");
170 /* Start with last bit and test wrap-around */
171 ff = axmap_next_free(map, osize - 1);
172 if (ff != lastfree) {
173 printf("axmap_next_free broken: wrap-around test #2 failed\n");
177 /* Set last free bit */
178 axmap_set(map, lastfree);
179 ff = axmap_next_free(map, 0);
181 printf("axmap_next_free broken: Expected -1 from full map\n");
185 ff = axmap_next_free(map, osize);
187 printf("axmap_next_free broken: Expected -1 from out of bounds request\n");
199 static int test_multi(uint64_t size, unsigned int bit_off)
201 unsigned int map_size = size;
203 uint64_t val = bit_off;
206 printf("Test multi %llu entries %u offset...", (unsigned long long) size, bit_off);
209 map = axmap_new(map_size);
210 while (val + 128 <= map_size) {
212 for (i = val; i < val + 128; i++) {
213 if (axmap_isset(map, val + i)) {
214 printf("bit already set\n");
223 err = axmap_set_nr(map, val, 128);
225 printf("only set %u bits\n", err);
230 for (i = 0; i < 128; i++) {
231 if (!axmap_isset(map, val + i)) {
232 printf("bit not set: %llu\n", (unsigned long long) val + i);
250 struct overlap_test {
256 static int test_overlap(void)
258 struct overlap_test tests[] = {
364 int entries, i, ret, err = 0;
367 for (i = 0; tests[i].start != -1U; i++) {
368 unsigned int this = tests[i].start + tests[i].nr;
374 printf("Test overlaps...\n");
377 map = axmap_new(entries);
379 for (i = 0; tests[i].start != -1U; i++) {
380 struct overlap_test *t = &tests[i];
382 printf("\tstart=%6u, nr=%3u: ", t->start, t->nr);
383 ret = axmap_set_nr(map, t->start, t->nr);
385 printf("%3d (FAIL, wanted %d)\n", ret, t->ret);
389 printf("%3d (PASS)\n", ret);
396 int main(int argc, char *argv[])
398 uint64_t size = (1ULL << 23) - 200;
402 size = strtoul(argv[1], NULL, 10);
404 seed = strtoul(argv[2], NULL, 10);
407 if (test_regular(size, seed))
409 if (test_multi(size, 0))
411 if (test_multi(size, 17))
415 if (test_next_free(size, seed))
418 /* Test 3 levels, all full: 64*64*64 */
419 if (test_next_free(64*64*64, seed))
422 /* Test 4 levels, with 2 inner levels not full */
423 if (test_next_free(((((64*64)-63)*64)-63)*64*12, seed))