jdk

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

25
#include "precompiled.hpp"
26
#include "utilities/align.hpp"
27
#include "utilities/bitMap.inline.hpp"
28
#include "utilities/debug.hpp"
29
#include "utilities/globalDefinitions.hpp"
30
#include "unittest.hpp"
31

32
using idx_t = BitMap::idx_t;
33
using bm_word_t = BitMap::bm_word_t;
34

35
static const idx_t BITMAP_SIZE = 1024;
36
static const idx_t BITMAP_WORD_SIZE = align_up(BITMAP_SIZE, BitsPerWord) / BitsPerWord;
37

38

39
static void test_iterate_step(const BitMap& map,
40
                              idx_t index,
41
                              const idx_t* positions,
42
                              size_t positions_index,
43
                              size_t positions_size) {
44
  ASSERT_LT(positions_index, positions_size);
45
  ASSERT_EQ(index, positions[positions_index]);
46
  ASSERT_TRUE(map.at(index));
47
}
48

49
// Test lambda returning void.
50
static void test_iterate_lambda(const BitMap& map,
51
                                const idx_t* positions,
52
                                size_t positions_size) {
53
  SCOPED_TRACE("iterate with lambda");
54
  size_t positions_index = 0;
55
  auto f = [&](idx_t i) {
56
    test_iterate_step(map, i, positions, positions_index++, positions_size);
57
  };
58
  ASSERT_TRUE(map.iterate(f));
59
  ASSERT_EQ(positions_index, positions_size);
60
}
61

62
static void test_reverse_iterate_lambda(const BitMap& map,
63
                                        const idx_t* positions,
64
                                        size_t positions_size) {
65
  SCOPED_TRACE("reverse iterate with lambda");
66
  size_t positions_index = positions_size;
67
  auto f = [&](idx_t i) {
68
    test_iterate_step(map, i, positions, --positions_index, positions_size);
69
  };
70
  ASSERT_TRUE(map.reverse_iterate(f));
71
  ASSERT_EQ(positions_index, 0u);
72
}
73

74

75
struct TestBitMapIterationData {
76
  const BitMap& _map;
77
  const idx_t* _positions;
78
  size_t _positions_index;
79
  size_t _positions_size;
80

81
  TestBitMapIterationData(const BitMap& map,
82
                          const idx_t* positions,
83
                          size_t positions_index,
84
                          size_t positions_size)
85
    : _map(map),
86
      _positions(positions),
87
      _positions_index(positions_index),
88
      _positions_size(positions_size)
89
  {}
90

91
  void test(idx_t index) const {
92
    test_iterate_step(_map, index, _positions, _positions_index, _positions_size);
93
  }
94
};
95

96
// Test closure returning bool.  Also tests lambda returning bool.
97
static void test_iterate_closure(const BitMap& map,
98
                                 const idx_t* positions,
99
                                 size_t positions_size) {
100
  SCOPED_TRACE("iterate with BitMapClosure");
101
  struct Closure : public BitMapClosure {
102
    TestBitMapIterationData _data;
103

104
    Closure(const BitMap& map, const idx_t* positions, size_t positions_size)
105
      : _data(map, positions, 0, positions_size)
106
    {}
107

108
    bool do_bit(idx_t i) override {
109
      _data.test(i);
110
      _data._positions_index += 1;
111
      return true;
112
    }
113
  } closure{map, positions, positions_size};
114
  ASSERT_TRUE(map.iterate(&closure));
115
  ASSERT_EQ(closure._data._positions_index, positions_size);
116
}
117

118
static void test_reverse_iterate_closure(const BitMap& map,
119
                                         const idx_t* positions,
120
                                         size_t positions_size) {
121
  SCOPED_TRACE("reverse iterate with BitMapClosure");
122
  struct Closure : public BitMapClosure {
123
    TestBitMapIterationData _data;
124

125
    Closure(const BitMap& map, const idx_t* positions, size_t positions_size)
126
      : _data(map, positions, positions_size, positions_size)
127
    {}
128

129
    bool do_bit(idx_t i) override {
130
      _data._positions_index -= 1;
131
      _data.test(i);
132
      return true;
133
    }
134
  } closure{map, positions, positions_size};
135
  ASSERT_TRUE(map.reverse_iterate(&closure));
136
  ASSERT_EQ(closure._data._positions_index, 0u);
137
}
138

139
// Test closure returning void.  Also tests lambda returning bool.
140
static void test_iterate_non_closure(const BitMap& map,
141
                                     const idx_t* positions,
142
                                     size_t positions_size) {
143
  SCOPED_TRACE("iterate with non-BitMapClosure");
144
  struct Closure {
145
    TestBitMapIterationData _data;
146
    Closure(const BitMap& map, const idx_t* positions, size_t positions_size)
147
      : _data(map, positions, 0, positions_size)
148
    {}
149

150
    void do_bit(idx_t i) {
151
      _data.test(i);
152
      _data._positions_index += 1;
153
    }
154
  } closure{map, positions, positions_size};
155
  ASSERT_TRUE(map.iterate(&closure));
156
  ASSERT_EQ(closure._data._positions_index, positions_size);
157
}
158

159
static void test_reverse_iterate_non_closure(const BitMap& map,
160
                                             const idx_t* positions,
161
                                             size_t positions_size) {
162
  SCOPED_TRACE("reverse iterate with non-BitMapClosure");
163
  struct Closure {
164
    TestBitMapIterationData _data;
165
    Closure(const BitMap& map, const idx_t* positions, size_t positions_size)
166
      : _data(map, positions, positions_size, positions_size)
167
    {}
168

169
    void do_bit(idx_t i) {
170
      _data._positions_index -= 1;
171
      _data.test(i);
172
    }
173
  } closure{map, positions, positions_size};
174
  ASSERT_TRUE(map.reverse_iterate(&closure));
175
  ASSERT_EQ(closure._data._positions_index, 0u);
176
}
177

178
static void test_iterator(const BitMap& map,
179
                          const idx_t* positions,
180
                          size_t positions_size) {
181
  SCOPED_TRACE("iterate with Iterator");
182
  size_t positions_index = 0;
183
  for (BitMap::Iterator it{map}; !it.is_empty(); it.step()) {
184
    test_iterate_step(map, it.index(), positions, positions_index++, positions_size);
185
  }
186
  ASSERT_EQ(positions_index, positions_size);
187
}
188

189
static void test_reverse_iterator(const BitMap& map,
190
                                  const idx_t* positions,
191
                                  size_t positions_size) {
192
  SCOPED_TRACE("reverse iterate with Iterator");
193
  size_t positions_index = positions_size;
194
  for (BitMap::ReverseIterator it{map}; !it.is_empty(); it.step()) {
195
    test_iterate_step(map, it.index(), positions, --positions_index, positions_size);
196
  }
197
  ASSERT_EQ(positions_index, 0u);
198
}
199

200
static void test_for_loop_iterator(const BitMap& map,
201
                                   const idx_t* positions,
202
                                   size_t positions_size) {
203
  SCOPED_TRACE("iterate with range-based for loop");
204
  size_t positions_index = 0;
205
  for (idx_t index : BitMap::Iterator(map)) {
206
    test_iterate_step(map, index, positions, positions_index++, positions_size);
207
  }
208
  ASSERT_EQ(positions_index, positions_size);
209
}
210

211
static void test_for_loop_reverse_iterator(const BitMap& map,
212
                                           const idx_t* positions,
213
                                           size_t positions_size) {
214
  SCOPED_TRACE("reverse iterate with range-based for loop");
215
  size_t positions_index = positions_size;
216
  for (idx_t index : BitMap::ReverseIterator(map)) {
217
    test_iterate_step(map, index, positions, --positions_index, positions_size);
218
  }
219
  ASSERT_EQ(positions_index, 0u);
220
}
221

222
static void fill_iterate_map(BitMap& map,
223
                             const idx_t* positions,
224
                             size_t positions_size) {
225
  map.clear_range(0, map.size());
226
  for (size_t i = 0; i < positions_size; ++i) {
227
    map.set_bit(positions[i]);
228
  }
229
}
230

231
static void test_iterate(BitMap& map,
232
                         const idx_t* positions,
233
                         size_t positions_size) {
234
  fill_iterate_map(map, positions, positions_size);
235

236
  test_iterate_lambda(map, positions, positions_size);
237
  test_iterate_closure(map, positions, positions_size);
238
  test_iterate_non_closure(map, positions, positions_size);
239

240
  test_reverse_iterate_lambda(map, positions, positions_size);
241
  test_reverse_iterate_closure(map, positions, positions_size);
242
  test_reverse_iterate_non_closure(map, positions, positions_size);
243

244
  test_iterator(map, positions, positions_size);
245
  test_reverse_iterator(map, positions, positions_size);
246

247
  test_for_loop_iterator(map, positions, positions_size);
248
  test_for_loop_reverse_iterator(map, positions, positions_size);
249
}
250

251
TEST(BitMap, iterate_empty) {
252
  bm_word_t test_data[BITMAP_WORD_SIZE];
253
  BitMapView test_map{test_data, BITMAP_SIZE};
254
  idx_t positions[1] = {};
255
  test_iterate(test_map, positions, 0);
256
}
257

258
TEST(BitMap, iterate_with_endpoints) {
259
  bm_word_t test_data[BITMAP_WORD_SIZE];
260
  BitMapView test_map{test_data, BITMAP_SIZE};
261
  idx_t positions[] = { 0, 2, 6, 31, 61, 131, 247, 578, BITMAP_SIZE - 1 };
262
  test_iterate(test_map, positions, ARRAY_SIZE(positions));
263
}
264

265
TEST(BitMap, iterate_without_endpoints) {
266
  bm_word_t test_data[BITMAP_WORD_SIZE];
267
  BitMapView test_map{test_data, BITMAP_SIZE};
268
  idx_t positions[] = { 1, 2, 6, 31, 61, 131, 247, 578, BITMAP_SIZE - 2 };
269
  test_iterate(test_map, positions, ARRAY_SIZE(positions));
270
}
271

272
TEST(BitMap, iterate_full) {
273
  bm_word_t test_data[BITMAP_WORD_SIZE];
274
  BitMapView test_map{test_data, BITMAP_SIZE};
275
  static idx_t positions[BITMAP_SIZE]; // static to avoid large stack allocation.
276
  for (idx_t i = 0; i < BITMAP_SIZE; ++i) {
277
    positions[i] = i;
278
  }
279
  test_iterate(test_map, positions, ARRAY_SIZE(positions));
280
}
281

282
TEST(BitMap, iterate_early_termination) {
283
  bm_word_t test_data[BITMAP_WORD_SIZE];
284
  BitMapView test_map{test_data, BITMAP_SIZE};
285
  idx_t positions[] = { 1, 2, 6, 31, 61, 131, 247, 578, BITMAP_SIZE - 2 };
286
  size_t positions_size = ARRAY_SIZE(positions);
287
  size_t positions_index = 0;
288
  fill_iterate_map(test_map, positions, positions_size);
289
  idx_t stop_at = 131;
290
  auto f = [&](idx_t i) {
291
    test_iterate_step(test_map, i, positions, positions_index, positions_size);
292
    if (positions[positions_index] == stop_at) {
293
      return false;
294
    } else {
295
      positions_index += 1;
296
      return true;
297
    }
298
  };
299
  ASSERT_FALSE(test_map.iterate(f));
300
  ASSERT_LT(positions_index, positions_size);
301
  ASSERT_EQ(positions[positions_index], stop_at);
302

303
  struct Closure : public BitMapClosure {
304
    const BitMap& _map;
305
    const idx_t* _positions;
306
    size_t _positions_index;
307
    size_t _positions_size;
308
    idx_t _stop_at;
309

310
    Closure(const BitMap& map, const idx_t* positions, size_t positions_size, idx_t stop_at)
311
      : _map(map),
312
        _positions(positions),
313
        _positions_index(0),
314
        _positions_size(positions_size),
315
        _stop_at(stop_at)
316
    {}
317

318
    bool do_bit(idx_t i) override {
319
      test_iterate_step(_map, i, _positions, _positions_index, _positions_size);
320
      if (_positions[_positions_index] == _stop_at) {
321
        return false;
322
      } else {
323
        _positions_index += 1;
324
        return true;
325
      }
326
    }
327
  } closure{test_map, positions, positions_size, stop_at};
328
  ASSERT_FALSE(test_map.iterate(&closure));
329
  ASSERT_LT(closure._positions_index, positions_size);
330
  ASSERT_EQ(positions[closure._positions_index], stop_at);
331
}
332