1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/memory/jemalloc/src/test/bitmap.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,153 @@
1.4 +#define JEMALLOC_MANGLE
1.5 +#include "jemalloc_test.h"
1.6 +
1.7 +#if (LG_BITMAP_MAXBITS > 12)
1.8 +# define MAXBITS 4500
1.9 +#else
1.10 +# define MAXBITS (1U << LG_BITMAP_MAXBITS)
1.11 +#endif
1.12 +
1.13 +static void
1.14 +test_bitmap_size(void)
1.15 +{
1.16 + size_t i, prev_size;
1.17 +
1.18 + prev_size = 0;
1.19 + for (i = 1; i <= MAXBITS; i++) {
1.20 + size_t size = bitmap_size(i);
1.21 + assert(size >= prev_size);
1.22 + prev_size = size;
1.23 + }
1.24 +}
1.25 +
1.26 +static void
1.27 +test_bitmap_init(void)
1.28 +{
1.29 + size_t i;
1.30 +
1.31 + for (i = 1; i <= MAXBITS; i++) {
1.32 + bitmap_info_t binfo;
1.33 + bitmap_info_init(&binfo, i);
1.34 + {
1.35 + size_t j;
1.36 + bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
1.37 + bitmap_info_ngroups(&binfo));
1.38 + bitmap_init(bitmap, &binfo);
1.39 +
1.40 + for (j = 0; j < i; j++)
1.41 + assert(bitmap_get(bitmap, &binfo, j) == false);
1.42 + free(bitmap);
1.43 +
1.44 + }
1.45 + }
1.46 +}
1.47 +
1.48 +static void
1.49 +test_bitmap_set(void)
1.50 +{
1.51 + size_t i;
1.52 +
1.53 + for (i = 1; i <= MAXBITS; i++) {
1.54 + bitmap_info_t binfo;
1.55 + bitmap_info_init(&binfo, i);
1.56 + {
1.57 + size_t j;
1.58 + bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
1.59 + bitmap_info_ngroups(&binfo));
1.60 + bitmap_init(bitmap, &binfo);
1.61 +
1.62 + for (j = 0; j < i; j++)
1.63 + bitmap_set(bitmap, &binfo, j);
1.64 + assert(bitmap_full(bitmap, &binfo));
1.65 + free(bitmap);
1.66 + }
1.67 + }
1.68 +}
1.69 +
1.70 +static void
1.71 +test_bitmap_unset(void)
1.72 +{
1.73 + size_t i;
1.74 +
1.75 + for (i = 1; i <= MAXBITS; i++) {
1.76 + bitmap_info_t binfo;
1.77 + bitmap_info_init(&binfo, i);
1.78 + {
1.79 + size_t j;
1.80 + bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
1.81 + bitmap_info_ngroups(&binfo));
1.82 + bitmap_init(bitmap, &binfo);
1.83 +
1.84 + for (j = 0; j < i; j++)
1.85 + bitmap_set(bitmap, &binfo, j);
1.86 + assert(bitmap_full(bitmap, &binfo));
1.87 + for (j = 0; j < i; j++)
1.88 + bitmap_unset(bitmap, &binfo, j);
1.89 + for (j = 0; j < i; j++)
1.90 + bitmap_set(bitmap, &binfo, j);
1.91 + assert(bitmap_full(bitmap, &binfo));
1.92 + free(bitmap);
1.93 + }
1.94 + }
1.95 +}
1.96 +
1.97 +static void
1.98 +test_bitmap_sfu(void)
1.99 +{
1.100 + size_t i;
1.101 +
1.102 + for (i = 1; i <= MAXBITS; i++) {
1.103 + bitmap_info_t binfo;
1.104 + bitmap_info_init(&binfo, i);
1.105 + {
1.106 + ssize_t j;
1.107 + bitmap_t *bitmap = malloc(sizeof(bitmap_t) *
1.108 + bitmap_info_ngroups(&binfo));
1.109 + bitmap_init(bitmap, &binfo);
1.110 +
1.111 + /* Iteratively set bits starting at the beginning. */
1.112 + for (j = 0; j < i; j++)
1.113 + assert(bitmap_sfu(bitmap, &binfo) == j);
1.114 + assert(bitmap_full(bitmap, &binfo));
1.115 +
1.116 + /*
1.117 + * Iteratively unset bits starting at the end, and
1.118 + * verify that bitmap_sfu() reaches the unset bits.
1.119 + */
1.120 + for (j = i - 1; j >= 0; j--) {
1.121 + bitmap_unset(bitmap, &binfo, j);
1.122 + assert(bitmap_sfu(bitmap, &binfo) == j);
1.123 + bitmap_unset(bitmap, &binfo, j);
1.124 + }
1.125 + assert(bitmap_get(bitmap, &binfo, 0) == false);
1.126 +
1.127 + /*
1.128 + * Iteratively set bits starting at the beginning, and
1.129 + * verify that bitmap_sfu() looks past them.
1.130 + */
1.131 + for (j = 1; j < i; j++) {
1.132 + bitmap_set(bitmap, &binfo, j - 1);
1.133 + assert(bitmap_sfu(bitmap, &binfo) == j);
1.134 + bitmap_unset(bitmap, &binfo, j);
1.135 + }
1.136 + assert(bitmap_sfu(bitmap, &binfo) == i - 1);
1.137 + assert(bitmap_full(bitmap, &binfo));
1.138 + free(bitmap);
1.139 + }
1.140 + }
1.141 +}
1.142 +
1.143 +int
1.144 +main(void)
1.145 +{
1.146 + malloc_printf("Test begin\n");
1.147 +
1.148 + test_bitmap_size();
1.149 + test_bitmap_init();
1.150 + test_bitmap_set();
1.151 + test_bitmap_unset();
1.152 + test_bitmap_sfu();
1.153 +
1.154 + malloc_printf("Test end\n");
1.155 + return (0);
1.156 +}
