bitmap.c 3.5 KB

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