deps/jemalloc/test/bitmap.c

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