#include "test/jemalloc_test.h"

#include "test/nbits.h"

static void
test_bitmap_initializer_body(const bitmap_info_t *binfo, size_t nbits) {
       bitmap_info_t binfo_dyn;
       bitmap_info_init(&binfo_dyn, nbits);

       expect_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn),
           "Unexpected difference between static and dynamic initialization, "
           "nbits=%zu", nbits);
       expect_zu_eq(binfo->nbits, binfo_dyn.nbits,
           "Unexpected difference between static and dynamic initialization, "
           "nbits=%zu", nbits);
#ifdef BITMAP_USE_TREE
       expect_u_eq(binfo->nlevels, binfo_dyn.nlevels,
           "Unexpected difference between static and dynamic initialization, "
           "nbits=%zu", nbits);
       {
               unsigned i;

               for (i = 0; i < binfo->nlevels; i++) {
                       expect_zu_eq(binfo->levels[i].group_offset,
                           binfo_dyn.levels[i].group_offset,
                           "Unexpected difference between static and dynamic "
                           "initialization, nbits=%zu, level=%u", nbits, i);
               }
       }
#else
       expect_zu_eq(binfo->ngroups, binfo_dyn.ngroups,
           "Unexpected difference between static and dynamic initialization");
#endif
}

TEST_BEGIN(test_bitmap_initializer) {
#define NB(nbits) {                                                     \
               if (nbits <= BITMAP_MAXBITS) {                          \
                       bitmap_info_t binfo =                           \
                           BITMAP_INFO_INITIALIZER(nbits);             \
                       test_bitmap_initializer_body(&binfo, nbits);    \
               }                                                       \
       }
       NBITS_TAB
#undef NB
}
TEST_END

static size_t
test_bitmap_size_body(const bitmap_info_t *binfo, size_t nbits,
   size_t prev_size) {
       size_t size = bitmap_size(binfo);
       expect_zu_ge(size, (nbits >> 3),
           "Bitmap size is smaller than expected");
       expect_zu_ge(size, prev_size, "Bitmap size is smaller than expected");
       return size;
}

TEST_BEGIN(test_bitmap_size) {
       size_t nbits, prev_size;

       prev_size = 0;
       for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
               bitmap_info_t binfo;
               bitmap_info_init(&binfo, nbits);
               prev_size = test_bitmap_size_body(&binfo, nbits, prev_size);
       }
#define NB(nbits) {                                                     \
               bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits);   \
               prev_size = test_bitmap_size_body(&binfo, nbits,        \
                   prev_size);                                         \
       }
       prev_size = 0;
       NBITS_TAB
#undef NB
}
TEST_END

static void
test_bitmap_init_body(const bitmap_info_t *binfo, size_t nbits) {
       size_t i;
       bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
       expect_ptr_not_null(bitmap, "Unexpected malloc() failure");

       bitmap_init(bitmap, binfo, false);
       for (i = 0; i < nbits; i++) {
               expect_false(bitmap_get(bitmap, binfo, i),
                   "Bit should be unset");
       }

       bitmap_init(bitmap, binfo, true);
       for (i = 0; i < nbits; i++) {
               expect_true(bitmap_get(bitmap, binfo, i), "Bit should be set");
       }

       free(bitmap);
}

TEST_BEGIN(test_bitmap_init) {
       size_t nbits;

       for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
               bitmap_info_t binfo;
               bitmap_info_init(&binfo, nbits);
               test_bitmap_init_body(&binfo, nbits);
       }
#define NB(nbits) {                                                     \
               bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits);   \
               test_bitmap_init_body(&binfo, nbits);                   \
       }
       NBITS_TAB
#undef NB
}
TEST_END

static void
test_bitmap_set_body(const bitmap_info_t *binfo, size_t nbits) {
       size_t i;
       bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
       expect_ptr_not_null(bitmap, "Unexpected malloc() failure");
       bitmap_init(bitmap, binfo, false);

       for (i = 0; i < nbits; i++) {
               bitmap_set(bitmap, binfo, i);
       }
       expect_true(bitmap_full(bitmap, binfo), "All bits should be set");
       free(bitmap);
}

TEST_BEGIN(test_bitmap_set) {
       size_t nbits;

       for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
               bitmap_info_t binfo;
               bitmap_info_init(&binfo, nbits);
               test_bitmap_set_body(&binfo, nbits);
       }
#define NB(nbits) {                                                     \
               bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits);   \
               test_bitmap_set_body(&binfo, nbits);                    \
       }
       NBITS_TAB
#undef NB
}
TEST_END

static void
test_bitmap_unset_body(const bitmap_info_t *binfo, size_t nbits) {
       size_t i;
       bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
       expect_ptr_not_null(bitmap, "Unexpected malloc() failure");
       bitmap_init(bitmap, binfo, false);

       for (i = 0; i < nbits; i++) {
               bitmap_set(bitmap, binfo, i);
       }
       expect_true(bitmap_full(bitmap, binfo), "All bits should be set");
       for (i = 0; i < nbits; i++) {
               bitmap_unset(bitmap, binfo, i);
       }
       for (i = 0; i < nbits; i++) {
               bitmap_set(bitmap, binfo, i);
       }
       expect_true(bitmap_full(bitmap, binfo), "All bits should be set");
       free(bitmap);
}

TEST_BEGIN(test_bitmap_unset) {
       size_t nbits;

       for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
               bitmap_info_t binfo;
               bitmap_info_init(&binfo, nbits);
               test_bitmap_unset_body(&binfo, nbits);
       }
#define NB(nbits) {                                                     \
               bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits);   \
               test_bitmap_unset_body(&binfo, nbits);                  \
       }
       NBITS_TAB
#undef NB
}
TEST_END

static void
test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) {
       bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
       expect_ptr_not_null(bitmap, "Unexpected malloc() failure");
       bitmap_init(bitmap, binfo, false);

       /* Iteratively set bits starting at the beginning. */
       for (size_t i = 0; i < nbits; i++) {
               expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i,
                   "First unset bit should be just after previous first unset "
                   "bit");
               expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i,
                   "First unset bit should be just after previous first unset "
                   "bit");
               expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
                   "First unset bit should be just after previous first unset "
                   "bit");
               expect_zu_eq(bitmap_sfu(bitmap, binfo), i,
                   "First unset bit should be just after previous first unset "
                   "bit");
       }
       expect_true(bitmap_full(bitmap, binfo), "All bits should be set");

       /*
        * Iteratively unset bits starting at the end, and verify that
        * bitmap_sfu() reaches the unset bits.
        */
       for (size_t i = nbits - 1; i < nbits; i--) { /* (nbits..0] */
               bitmap_unset(bitmap, binfo, i);
               expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i,
                   "First unset bit should the bit previously unset");
               expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i,
                   "First unset bit should the bit previously unset");
               expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
                   "First unset bit should the bit previously unset");
               expect_zu_eq(bitmap_sfu(bitmap, binfo), i,
                   "First unset bit should the bit previously unset");
               bitmap_unset(bitmap, binfo, i);
       }
       expect_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset");

       /*
        * Iteratively set bits starting at the beginning, and verify that
        * bitmap_sfu() looks past them.
        */
       for (size_t i = 1; i < nbits; i++) {
               bitmap_set(bitmap, binfo, i - 1);
               expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i,
                   "First unset bit should be just after the bit previously "
                   "set");
               expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i,
                   "First unset bit should be just after the bit previously "
                   "set");
               expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
                   "First unset bit should be just after the bit previously "
                   "set");
               expect_zu_eq(bitmap_sfu(bitmap, binfo), i,
                   "First unset bit should be just after the bit previously "
                   "set");
               bitmap_unset(bitmap, binfo, i);
       }
       expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), nbits - 1,
           "First unset bit should be the last bit");
       expect_zu_eq(bitmap_ffu(bitmap, binfo, (nbits > 1) ? nbits-2 : nbits-1),
           nbits - 1, "First unset bit should be the last bit");
       expect_zu_eq(bitmap_ffu(bitmap, binfo, nbits - 1), nbits - 1,
           "First unset bit should be the last bit");
       expect_zu_eq(bitmap_sfu(bitmap, binfo), nbits - 1,
           "First unset bit should be the last bit");
       expect_true(bitmap_full(bitmap, binfo), "All bits should be set");

       /*
        * Bubble a "usu" pattern through the bitmap and verify that
        * bitmap_ffu() finds the correct bit for all five min_bit cases.
        */
       if (nbits >= 3) {
               for (size_t i = 0; i < nbits-2; i++) {
                       bitmap_unset(bitmap, binfo, i);
                       bitmap_unset(bitmap, binfo, i+2);
                       if (i > 0) {
                               expect_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i,
                                   "Unexpected first unset bit");
                       }
                       expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
                           "Unexpected first unset bit");
                       expect_zu_eq(bitmap_ffu(bitmap, binfo, i+1), i+2,
                           "Unexpected first unset bit");
                       expect_zu_eq(bitmap_ffu(bitmap, binfo, i+2), i+2,
                           "Unexpected first unset bit");
                       if (i + 3 < nbits) {
                               expect_zu_eq(bitmap_ffu(bitmap, binfo, i+3),
                                   nbits, "Unexpected first unset bit");
                       }
                       expect_zu_eq(bitmap_sfu(bitmap, binfo), i,
                           "Unexpected first unset bit");
                       expect_zu_eq(bitmap_sfu(bitmap, binfo), i+2,
                           "Unexpected first unset bit");
               }
       }

       /*
        * Unset the last bit, bubble another unset bit through the bitmap, and
        * verify that bitmap_ffu() finds the correct bit for all four min_bit
        * cases.
        */
       if (nbits >= 3) {
               bitmap_unset(bitmap, binfo, nbits-1);
               for (size_t i = 0; i < nbits-1; i++) {
                       bitmap_unset(bitmap, binfo, i);
                       if (i > 0) {
                               expect_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i,
                                   "Unexpected first unset bit");
                       }
                       expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
                           "Unexpected first unset bit");
                       expect_zu_eq(bitmap_ffu(bitmap, binfo, i+1), nbits-1,
                           "Unexpected first unset bit");
                       expect_zu_eq(bitmap_ffu(bitmap, binfo, nbits-1),
                           nbits-1, "Unexpected first unset bit");

                       expect_zu_eq(bitmap_sfu(bitmap, binfo), i,
                           "Unexpected first unset bit");
               }
               expect_zu_eq(bitmap_sfu(bitmap, binfo), nbits-1,
                   "Unexpected first unset bit");
       }

       free(bitmap);
}

TEST_BEGIN(test_bitmap_xfu) {
       size_t nbits, nbits_max;

       /* The test is O(n^2); large page sizes may slow down too much. */
       nbits_max = BITMAP_MAXBITS > 512 ? 512 : BITMAP_MAXBITS;
       for (nbits = 1; nbits <= nbits_max; nbits++) {
               bitmap_info_t binfo;
               bitmap_info_init(&binfo, nbits);
               test_bitmap_xfu_body(&binfo, nbits);
       }
#define NB(nbits) {                                                     \
               bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits);   \
               test_bitmap_xfu_body(&binfo, nbits);                    \
       }
       NBITS_TAB
#undef NB
}
TEST_END

int
main(void) {
       return test(
           test_bitmap_initializer,
           test_bitmap_size,
           test_bitmap_init,
           test_bitmap_set,
           test_bitmap_unset,
           test_bitmap_xfu);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.