jdk

1
/*
2
 * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
3
 * Copyright (c) 2020, SAP and/or its affiliates.
4
 *
5
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6
 *
7
 * This code is free software; you can redistribute it and/or modify it
8
 * under the terms of the GNU General Public License version 2 only, as
9
 * published by the Free Software Foundation.
10
 *
11
 * This code is distributed in the hope that it will be useful, but WITHOUT
12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
 * version 2 for more details (a copy is included in the LICENSE file that
15
 * accompanied this code).
16
 *
17
 * You should have received a copy of the GNU General Public License version
18
 * 2 along with this work; if not, write to the Free Software Foundation,
19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20
 *
21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22
 * or visit www.oracle.com if you need additional information or have any
23
 * questions.
24
 */
25

26
#include "precompiled.hpp"
27
#include "memory/allocation.hpp"
28
#include "runtime/os.hpp"
29
#include "utilities/bitMap.inline.hpp"
30
#include "utilities/ostream.hpp"
31
#include "unittest.hpp"
32

33
// A simple stupid bitmap to mimic BitMap operations.
34
class SimpleFakeBitmap {
35

36
  const int _size;
37
  char* _buffer;
38

39
public:
40

41
  SimpleFakeBitmap(int size) : _size(size), _buffer(NEW_C_HEAP_ARRAY(char, size, mtInternal)) {
42
    clear();
43
  }
44

45
  ~SimpleFakeBitmap() {
46
    FREE_C_HEAP_ARRAY(char, _buffer);
47
  }
48

49
  // Set or clear the specified bit.
50
  void set_range(int beg, int end) { ::memset(_buffer + beg, 'X', end - beg); }
51
  void clear_range(int beg, int end) { ::memset(_buffer + beg, ' ', end - beg); }
52
  void clear() { clear_range(0, _size); }
53

54
  bool at(int idx) const { return _buffer[idx] == 'X'; }
55

56
  unsigned popcnt(int beg, int end) const {
57
    int sum = 0;
58
    for (int i = beg; i < end; i ++) {
59
      if (at(i)) {
60
        sum ++;
61
      }
62
    }
63
    return sum;
64
  }
65

66
  unsigned popcnt() const { return popcnt(0, _size); }
67

68
};
69

70
#define ASSERT_POPCNT_ALL(bm, expected) \
71
  ASSERT_EQ(bm.count_one_bits(), (BitMap::idx_t)(expected));
72

73
#define ASSERT_POPCNT_RANGE(bm, beg, end, expected) \
74
  ASSERT_EQ(bm.count_one_bits(beg, end), (BitMap::idx_t)(expected));
75

76
#define ASSERT_POPCNT_ALL_CMP(bm, fake_bm) \
77
  ASSERT_EQ(bm.count_one_bits(), fake_bm.popcnt());
78

79
#define ASSERT_POPCNT_RANGE_CMP(bm, beg, end, fake_bm) \
80
  ASSERT_EQ(bm.count_one_bits(beg, end), fake_bm.popcnt(beg, end));
81

82
static void set_or_clear_random_range(BitMap& bm, SimpleFakeBitmap& fbm, int beg, int end) {
83
  int range = end - beg;
84
  if (range > 0) {
85
    int from = os::random() % range;
86
    int to = os::random() % range;
87
    if (from > to) {
88
      int s = from;
89
      from = to;
90
      to = s;
91
    }
92
    from += beg;
93
    to += beg;
94
    if ((os::random() % 10) > 5) {
95
      bm.set_range(from, to);
96
      fbm.set_range(from, to);
97
    } else {
98
      bm.clear_range(from, to);
99
      fbm.clear_range(from, to);
100
    }
101
  }
102
}
103

104
static void test_bitmap_popcnt(int bitsize) {
105
  CHeapBitMap bm(bitsize, mtTest);
106
  SimpleFakeBitmap fbm(bitsize);
107

108
  ASSERT_POPCNT_ALL(bm, 0);
109
  ASSERT_POPCNT_RANGE(bm, 0, 0, 0);
110
  ASSERT_POPCNT_RANGE(bm, 0, bitsize, 0);
111

112
  const int stepsize = bitsize > 64 ? 5 : 1;
113

114
  for (int beg = 0; beg < bitsize; beg += stepsize) {
115
    for (int end = beg; end < bitsize; end += stepsize) {
116

117
      bm.clear();
118
      bm.set_range(beg, end);
119

120
      fbm.clear();
121
      fbm.set_range(beg, end);
122

123
      ASSERT_POPCNT_ALL_CMP(bm, fbm);
124

125
      for (int beg_query_range = 0; beg_query_range < bitsize; beg_query_range += stepsize) {
126
        for (int end_query_range = beg_query_range; end_query_range < bitsize; end_query_range += stepsize) {
127
          ASSERT_POPCNT_RANGE_CMP(bm, beg_query_range, end_query_range, fbm);
128

129
          // Clear some random ranges and retest
130
          for (int n = 0; n < 3; n ++) {
131
            set_or_clear_random_range(bm, fbm, beg, end);
132
            ASSERT_POPCNT_RANGE_CMP(bm, beg_query_range, end_query_range, fbm);
133
          }
134

135
        }
136
      }
137
    }
138
  }
139

140
}
141

142
TEST_VM(BitMap, popcnt_1)   { test_bitmap_popcnt(1); }
143
TEST_VM(BitMap, popcnt_8)   { test_bitmap_popcnt(8); }
144
TEST_VM(BitMap, popcnt_15)  { test_bitmap_popcnt(15); }
145
TEST_VM(BitMap, popcnt_19)  { test_bitmap_popcnt(17); }
146
TEST_VM(BitMap, popcnt_63)  { test_bitmap_popcnt(63); }
147
TEST_VM(BitMap, popcnt_300) { test_bitmap_popcnt(300); }
148

149
TEST_VM(BitMap, popcnt_large) {
150

151
  CHeapBitMap bm(64 * K, mtTest);
152

153
  ASSERT_POPCNT_ALL(bm, 0);
154
  ASSERT_POPCNT_RANGE(bm, 0, 64 * K, 0);
155
  ASSERT_POPCNT_RANGE(bm, 47, 199, 0);
156

157
  bm.set_bit(100);
158

159
  ASSERT_POPCNT_ALL(bm, 1);
160
  ASSERT_POPCNT_RANGE(bm, 0, 64 * K, 1);
161
  ASSERT_POPCNT_RANGE(bm, 47, 199, 1);
162
  ASSERT_POPCNT_RANGE(bm, 199, 299, 0 );
163

164
  bm.set_range(0, 64 * K);
165

166
  ASSERT_POPCNT_ALL(bm, 64 * K);
167
  ASSERT_POPCNT_RANGE(bm, 0, 64 * K, 64 * K);
168
  ASSERT_POPCNT_RANGE(bm, 47, 199, 152);
169
  ASSERT_POPCNT_RANGE(bm, 199, 299, 100);
170

171
}
172