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