tests/test-bitmap.c

   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)));
  59
  60     free(b);
  61     free(a);
  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);
 113
 114     free(a);
 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);