src/jemalloc/test/unit/bitmap.c

   1 #include "test/jemalloc_test.h"
   2
   3 TEST_BEGIN(test_bitmap_size)
   4 {
   5         size_t i, prev_size;
   6
   7         prev_size = 0;
   8         for (i = 1; i <= BITMAP_MAXBITS; i++) {
   9                 bitmap_info_t binfo;
  10                 size_t size;
  11
  12                 bitmap_info_init(&binfo, i);
  13                 size = bitmap_size(&binfo);
  14                 assert_true(size >= prev_size,
  15                     "Bitmap size is smaller than expected");
  16                 prev_size = size;
  17         }
  18 }
  19 TEST_END
  20
  21 TEST_BEGIN(test_bitmap_init)
  22 {
  23         size_t i;
  24
  25         for (i = 1; i <= BITMAP_MAXBITS; i++) {
  26                 bitmap_info_t binfo;
  27                 bitmap_info_init(&binfo, i);
  28                 {
  29                         size_t j;
  30                         bitmap_t *bitmap = (bitmap_t *)malloc(
  31                             bitmap_size(&binfo));
  32                         bitmap_init(bitmap, &binfo);
  33
  34                         for (j = 0; j < i; j++) {
  35                                 assert_false(bitmap_get(bitmap, &binfo, j),
  36                                     "Bit should be unset");
  37                         }
  38                         free(bitmap);
  39                 }
  40         }
  41 }
  42 TEST_END
  43
  44 TEST_BEGIN(test_bitmap_set)
  45 {
  46         size_t i;
  47
  48         for (i = 1; i <= BITMAP_MAXBITS; i++) {
  49                 bitmap_info_t binfo;
  50                 bitmap_info_init(&binfo, i);
  51                 {
  52                         size_t j;
  53                         bitmap_t *bitmap = (bitmap_t *)malloc(
  54                             bitmap_size(&binfo));
  55                         bitmap_init(bitmap, &binfo);
  56
  57                         for (j = 0; j < i; j++)
  58                                 bitmap_set(bitmap, &binfo, j);
  59                         assert_true(bitmap_full(bitmap, &binfo),
  60                             "All bits should be set");
  61                         free(bitmap);
  62                 }
  63         }
  64 }
  65 TEST_END
  66
  67 TEST_BEGIN(test_bitmap_unset)
  68 {
  69         size_t i;
  70
  71         for (i = 1; i <= BITMAP_MAXBITS; i++) {
  72                 bitmap_info_t binfo;
  73                 bitmap_info_init(&binfo, i);
  74                 {
  75                         size_t j;
  76                         bitmap_t *bitmap = (bitmap_t *)malloc(
  77                             bitmap_size(&binfo));
  78                         bitmap_init(bitmap, &binfo);
  79
  80                         for (j = 0; j < i; j++)
  81                                 bitmap_set(bitmap, &binfo, j);
  82                         assert_true(bitmap_full(bitmap, &binfo),
  83                             "All bits should be set");
  84                         for (j = 0; j < i; j++)
  85                                 bitmap_unset(bitmap, &binfo, j);
  86                         for (j = 0; j < i; j++)
  87                                 bitmap_set(bitmap, &binfo, j);
  88                         assert_true(bitmap_full(bitmap, &binfo),
  89                             "All bits should be set");
  90                         free(bitmap);
  91                 }
  92         }
  93 }
  94 TEST_END
  95
  96 TEST_BEGIN(test_bitmap_sfu)
  97 {
  98         size_t i;
  99
 100         for (i = 1; i <= BITMAP_MAXBITS; i++) {
 101                 bitmap_info_t binfo;
 102                 bitmap_info_init(&binfo, i);
 103                 {
 104                         ssize_t j;
 105                         bitmap_t *bitmap = (bitmap_t *)malloc(
 106                             bitmap_size(&binfo));
 107                         bitmap_init(bitmap, &binfo);
 108
 109                         /* Iteratively set bits starting at the beginning. */
 110                         for (j = 0; j < i; j++) {
 111                                 assert_zd_eq(bitmap_sfu(bitmap, &binfo), j,
 112                                     "First unset bit should be just after "
 113                                     "previous first unset bit");
 114                         }
 115                         assert_true(bitmap_full(bitmap, &binfo),
 116                             "All bits should be set");
 117
 118                         /*
 119                          * Iteratively unset bits starting at the end, and
 120                          * verify that bitmap_sfu() reaches the unset bits.
 121                          */
 122                         for (j = i - 1; j >= 0; j--) {
 123                                 bitmap_unset(bitmap, &binfo, j);
 124                                 assert_zd_eq(bitmap_sfu(bitmap, &binfo), j,
 125                                     "First unset bit should the bit previously "
 126                                     "unset");
 127                                 bitmap_unset(bitmap, &binfo, j);
 128                         }
 129                         assert_false(bitmap_get(bitmap, &binfo, 0),
 130                             "Bit should be unset");
 131
 132                         /*
 133                          * Iteratively set bits starting at the beginning, and
 134                          * verify that bitmap_sfu() looks past them.
 135                          */
 136                         for (j = 1; j < i; j++) {
 137                                 bitmap_set(bitmap, &binfo, j - 1);
 138                                 assert_zd_eq(bitmap_sfu(bitmap, &binfo), j,
 139                                     "First unset bit should be just after the "
 140                                     "bit previously set");
 141                                 bitmap_unset(bitmap, &binfo, j);
 142                         }
 143                         assert_zd_eq(bitmap_sfu(bitmap, &binfo), i - 1,
 144                             "First unset bit should be the last bit");
 145                         assert_true(bitmap_full(bitmap, &binfo),
 146                             "All bits should be set");
 147                         free(bitmap);
 148                 }
 149         }
 150 }
 151 TEST_END
 152
 153 int
 154 main(void)
 155 {
 156
 157         return (test(
 158             test_bitmap_size,
 159             test_bitmap_init,
 160             test_bitmap_set,
 161             test_bitmap_unset,
 162             test_bitmap_sfu));
 163 }