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