deps/jemalloc/test/bitmap.c

   1 #define JEMALLOC_MANGLE
   2 #include "jemalloc_test.h"
   3
   4 /*
   5  * Avoid using the assert() from jemalloc_internal.h, since it requires
   6  * internal libjemalloc functionality.
   7  * */
   8 #include <assert.h>
   9
  10 /*
  11  * Directly include the bitmap code, since it isn't exposed outside
  12  * libjemalloc.
  13  */
  14 #include "../src/bitmap.c"
  15
  16 #if (LG_BITMAP_MAXBITS > 12)
  17 #  define MAXBITS       4500
  18 #else
  19 #  define MAXBITS       (1U << LG_BITMAP_MAXBITS)
  20 #endif
  21
  22 static void
  23 test_bitmap_size(void)
  24 {
  25         size_t i, prev_size;
  26
  27         prev_size = 0;
  28         for (i = 1; i <= MAXBITS; i++) {
  29                 size_t size = bitmap_size(i);
  30                 assert(size >= prev_size);
  31                 prev_size = size;
  32         }
  33 }
  34
  35 static void
  36 test_bitmap_init(void)
  37 {
  38         size_t i;
  39
  40         for (i = 1; i <= MAXBITS; i++) {
  41                 bitmap_info_t binfo;
  42                 bitmap_info_init(&binfo, i);
  43                 {
  44                         size_t j;
  45                         bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
  46                         bitmap_init(bitmap, &binfo);
  47
  48                         for (j = 0; j < i; j++)
  49                                 assert(bitmap_get(bitmap, &binfo, j) == false);
  50
  51                 }
  52         }
  53 }
  54
  55 static void
  56 test_bitmap_set(void)
  57 {
  58         size_t i;
  59
  60         for (i = 1; i <= MAXBITS; i++) {
  61                 bitmap_info_t binfo;
  62                 bitmap_info_init(&binfo, i);
  63                 {
  64                         size_t j;
  65                         bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
  66                         bitmap_init(bitmap, &binfo);
  67
  68                         for (j = 0; j < i; j++)
  69                                 bitmap_set(bitmap, &binfo, j);
  70                         assert(bitmap_full(bitmap, &binfo));
  71                 }
  72         }
  73 }
  74
  75 static void
  76 test_bitmap_unset(void)
  77 {
  78         size_t i;
  79
  80         for (i = 1; i <= MAXBITS; i++) {
  81                 bitmap_info_t binfo;
  82                 bitmap_info_init(&binfo, i);
  83                 {
  84                         size_t j;
  85                         bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
  86                         bitmap_init(bitmap, &binfo);
  87
  88                         for (j = 0; j < i; j++)
  89                                 bitmap_set(bitmap, &binfo, j);
  90                         assert(bitmap_full(bitmap, &binfo));
  91                         for (j = 0; j < i; j++)
  92                                 bitmap_unset(bitmap, &binfo, j);
  93                         for (j = 0; j < i; j++)
  94                                 bitmap_set(bitmap, &binfo, j);
  95                         assert(bitmap_full(bitmap, &binfo));
  96                 }
  97         }
  98 }
  99
 100 static void
 101 test_bitmap_sfu(void)
 102 {
 103         size_t i;
 104
 105         for (i = 1; i <= MAXBITS; i++) {
 106                 bitmap_info_t binfo;
 107                 bitmap_info_init(&binfo, i);
 108                 {
 109                         ssize_t j;
 110                         bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
 111                         bitmap_init(bitmap, &binfo);
 112
 113                         /* Iteratively set bits starting at the beginning. */
 114                         for (j = 0; j < i; j++)
 115                                 assert(bitmap_sfu(bitmap, &binfo) == j);
 116                         assert(bitmap_full(bitmap, &binfo));
 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(bitmap_sfu(bitmap, &binfo) == j);
 125                                 bitmap_unset(bitmap, &binfo, j);
 126                         }
 127                         assert(bitmap_get(bitmap, &binfo, 0) == false);
 128
 129                         /*
 130                          * Iteratively set bits starting at the beginning, and
 131                          * verify that bitmap_sfu() looks past them.
 132                          */
 133                         for (j = 1; j < i; j++) {
 134                                 bitmap_set(bitmap, &binfo, j - 1);
 135                                 assert(bitmap_sfu(bitmap, &binfo) == j);
 136                                 bitmap_unset(bitmap, &binfo, j);
 137                         }
 138                         assert(bitmap_sfu(bitmap, &binfo) == i - 1);
 139                         assert(bitmap_full(bitmap, &binfo));
 140                 }
 141         }
 142 }
 143
 144 int
 145 main(void)
 146 {
 147         fprintf(stderr, "Test begin\n");
 148
 149         test_bitmap_size();
 150         test_bitmap_init();
 151         test_bitmap_set();
 152         test_bitmap_unset();
 153         test_bitmap_sfu();
 154
 155         fprintf(stderr, "Test end\n");
 156         return (0);
 157 }