]>
Commit | Line | Data |
---|---|---|
f831a472 K |
1 | /* |
2 | * Copyright (c) 2014 Kmindg <kmindg@gmail.com> | |
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 <config.h> | |
18 | #include "bitmap.h" | |
19 | #include "ovstest.h" | |
20 | #include "timeval.h" | |
21 | #include "command-line.h" | |
22 | ||
23 | #undef NDEBUG | |
24 | #include <assert.h> | |
25 | ||
26 | enum { MAX_BITS = 20 * BITMAP_ULONG_BITS }; | |
27 | ||
28 | static int | |
29 | elapsed(const struct timeval *start) | |
30 | { | |
31 | struct timeval end; | |
32 | ||
33 | xgettimeofday(&end); | |
34 | return timeval_to_msec(&end) - timeval_to_msec(start); | |
35 | } | |
36 | ||
37 | /* Tests bitmap_equal. */ | |
38 | static void | |
39 | test_bitmap_equal(void) | |
40 | { | |
41 | unsigned long *a, *b; | |
42 | ||
43 | a = bitmap_allocate(MAX_BITS); | |
44 | b = bitmap_allocate(MAX_BITS); | |
45 | ||
46 | /* equal test */ | |
47 | assert(bitmap_equal(a, b, MAX_BITS)); | |
48 | assert(bitmap_equal(a, b, MAX_BITS - 1)); | |
49 | assert(bitmap_equal(a, b, MAX_BITS - (BITMAP_ULONG_BITS - 1))); | |
50 | ||
51 | bitmap_set_multiple(a, 10 * BITMAP_ULONG_BITS, BITMAP_ULONG_BITS, true); | |
52 | assert(bitmap_equal(a, b, 10 * BITMAP_ULONG_BITS)); | |
53 | ||
54 | /* non-equal test */ | |
55 | assert(!bitmap_equal(a, b, 11 * BITMAP_ULONG_BITS)); | |
56 | assert(!bitmap_equal(a, b, 11 * BITMAP_ULONG_BITS - 1)); | |
57 | assert(!bitmap_equal(a, b, | |
58 | 11 * BITMAP_ULONG_BITS - (BITMAP_ULONG_BITS - 1))); | |
c44a2a6d TG |
59 | |
60 | free(b); | |
61 | free(a); | |
f831a472 K |
62 | } |
63 | ||
64 | /* Tests bitmap_scan. */ | |
65 | static void | |
66 | test_bitmap_scan(void) | |
67 | { | |
68 | unsigned long *a; | |
69 | ||
70 | a = bitmap_allocate(MAX_BITS); | |
71 | ||
72 | /* scan for 1 */ | |
73 | assert(bitmap_scan(a, true, 1, BITMAP_ULONG_BITS) == BITMAP_ULONG_BITS); | |
74 | assert(bitmap_scan(a, true, BITMAP_ULONG_BITS - 1, BITMAP_ULONG_BITS) | |
75 | == BITMAP_ULONG_BITS); | |
76 | assert(bitmap_scan(a, true, 0, BITMAP_ULONG_BITS) == BITMAP_ULONG_BITS); | |
77 | assert(bitmap_scan(a, true, 0, BITMAP_ULONG_BITS + 1) | |
78 | == BITMAP_ULONG_BITS + 1); | |
79 | assert(bitmap_scan(a, true, 0, 2 * BITMAP_ULONG_BITS - 1) | |
80 | == 2 * BITMAP_ULONG_BITS - 1); | |
81 | ||
82 | bitmap_set1(a, MAX_BITS - 1); | |
83 | assert(bitmap_scan(a, true, 0, MAX_BITS) == MAX_BITS - 1); | |
84 | bitmap_set1(a, MAX_BITS - BITMAP_ULONG_BITS + 1); | |
85 | assert(bitmap_scan(a, true, 0, MAX_BITS - 1) | |
86 | == MAX_BITS - BITMAP_ULONG_BITS + 1); | |
87 | bitmap_set1(a, BITMAP_ULONG_BITS - 1); | |
88 | assert(bitmap_scan(a, true, 0, MAX_BITS - 1) == BITMAP_ULONG_BITS - 1); | |
89 | bitmap_set1(a, 0); | |
90 | assert(bitmap_scan(a, true, 0, MAX_BITS - 1) == 0); | |
91 | ||
92 | bitmap_set_multiple(a, 0, MAX_BITS, true); | |
93 | ||
94 | /* scan for 0 */ | |
95 | assert(bitmap_scan(a, false, 1, BITMAP_ULONG_BITS) == BITMAP_ULONG_BITS); | |
96 | assert(bitmap_scan(a, false, BITMAP_ULONG_BITS - 1, BITMAP_ULONG_BITS) | |
97 | == BITMAP_ULONG_BITS); | |
98 | assert(bitmap_scan(a, false, 0, BITMAP_ULONG_BITS) == BITMAP_ULONG_BITS); | |
99 | assert(bitmap_scan(a, false, 0, BITMAP_ULONG_BITS + 1) | |
100 | == BITMAP_ULONG_BITS + 1); | |
101 | assert(bitmap_scan(a, false, 0, 2 * BITMAP_ULONG_BITS - 1) | |
102 | == 2 * BITMAP_ULONG_BITS - 1); | |
103 | ||
104 | bitmap_set0(a, MAX_BITS - 1); | |
105 | assert(bitmap_scan(a, false, 0, MAX_BITS) == MAX_BITS - 1); | |
106 | bitmap_set0(a, MAX_BITS - BITMAP_ULONG_BITS + 1); | |
107 | assert(bitmap_scan(a, false, 0, MAX_BITS - 1) | |
108 | == MAX_BITS - BITMAP_ULONG_BITS + 1); | |
109 | bitmap_set0(a, BITMAP_ULONG_BITS - 1); | |
110 | assert(bitmap_scan(a, false, 0, MAX_BITS - 1) == BITMAP_ULONG_BITS - 1); | |
111 | bitmap_set0(a, 0); | |
112 | assert(bitmap_scan(a, false, 0, MAX_BITS - 1) == 0); | |
c44a2a6d TG |
113 | |
114 | free(a); | |
f831a472 K |
115 | } |
116 | ||
117 | static void | |
118 | run_test(void (*function)(void)) | |
119 | { | |
120 | function(); | |
121 | printf("."); | |
122 | } | |
123 | ||
124 | static void | |
125 | run_tests(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
126 | { | |
127 | run_test(test_bitmap_equal); | |
128 | run_test(test_bitmap_scan); | |
129 | printf("\n"); | |
130 | } | |
131 | ||
132 | static void | |
133 | run_benchmarks(int argc OVS_UNUSED, char *argv[]) | |
134 | { | |
135 | int n_iter = strtol(argv[1], NULL, 10); | |
136 | struct timeval start; | |
137 | ||
138 | xgettimeofday(&start); | |
139 | for (int i = 0; i < n_iter; i++) { | |
140 | test_bitmap_equal(); | |
141 | } | |
142 | printf("bitmap equal: %5d ms\n", elapsed(&start)); | |
143 | ||
144 | xgettimeofday(&start); | |
145 | for (int i = 0; i < n_iter; i++) { | |
146 | test_bitmap_scan(); | |
147 | } | |
148 | printf("bitmap scan: %5d ms\n", elapsed(&start)); | |
149 | printf("\n"); | |
150 | } | |
151 | ||
152 | static const struct command commands[] = { | |
153 | {"check", 0, 0, run_tests}, | |
154 | {"benchmark", 1, 1, run_benchmarks}, | |
155 | {NULL, 0, 0, NULL}, | |
156 | }; | |
157 | ||
158 | static void | |
159 | test_bitmap_main(int argc, char *argv[]) | |
160 | { | |
161 | set_program_name(argv[0]); | |
162 | run_command(argc - 1, argv + 1, commands); | |
163 | } | |
164 | ||
165 | OVSTEST_REGISTER("test-bitmap", test_bitmap_main); |