jdk

1
/*
2
 * Copyright (c) 2020, 2022, 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
#include "precompiled.hpp"
25
#include "memory/resourceArea.hpp"
26
#include "utilities/growableArray.hpp"
27
#include "unittest.hpp"
28

29
struct WithEmbeddedArray {
30
  // Array embedded in another class
31
  GrowableArray<int> _a;
32

33
  // Resource allocated data array
34
  WithEmbeddedArray(int initial_max) : _a(initial_max) {}
35
  // Arena allocated data array
36
  WithEmbeddedArray(Arena* arena, int initial_max) : _a(arena, initial_max, 0, 0) {}
37
  // CHeap allocated data array
38
  WithEmbeddedArray(int initial_max, MEMFLAGS memflags) : _a(initial_max, memflags) {
39
    assert(memflags != mtNone, "test requirement");
40
  }
41
  WithEmbeddedArray(const GrowableArray<int>& other) : _a(other) {}
42
};
43

44
// Test fixture to work with TEST_VM_F
45
class GrowableArrayTest : public ::testing::Test {
46
protected:
47
  // friend -> private accessors
48
  template <typename E>
49
  static bool elements_on_C_heap(const GrowableArray<E>* array) {
50
    return array->on_C_heap();
51
  }
52
  template <typename E>
53
  static bool elements_on_resource_area(const GrowableArray<E>* array) {
54
    return array->on_resource_area();
55
  }
56
  template <typename E>
57
  static bool elements_on_arena(const GrowableArray<E>* array) {
58
    return array->on_arena();
59
  }
60

61
  template <typename ArrayClass>
62
  static void test_append(ArrayClass* a) {
63
    // Add elements
64
    for (int i = 0; i < 10; i++) {
65
      a->append(i);
66
    }
67

68
    // Check size
69
    ASSERT_EQ(a->length(), 10);
70

71
    // Check elements
72
    for (int i = 0; i < 10; i++) {
73
      EXPECT_EQ(a->at(i), i);
74
    }
75
  }
76

77
  template <typename ArrayClass>
78
  static void test_clear(ArrayClass* a) {
79
    // Add elements
80
    for (int i = 0; i < 10; i++) {
81
      a->append(i);
82
    }
83

84
    // Check size
85
    ASSERT_EQ(a->length(), 10);
86
    ASSERT_EQ(a->is_empty(), false);
87

88
    // Clear elements
89
    a->clear();
90

91
    // Check size
92
    ASSERT_EQ(a->length(), 0);
93
    ASSERT_EQ(a->is_empty(), true);
94

95
    // Add element
96
    a->append(11);
97

98
    // Check size
99
    ASSERT_EQ(a->length(), 1);
100
    ASSERT_EQ(a->is_empty(), false);
101

102
    // Clear elements
103
    a->clear();
104

105
    // Check size
106
    ASSERT_EQ(a->length(), 0);
107
    ASSERT_EQ(a->is_empty(), true);
108
  }
109

110
  template <typename ArrayClass>
111
  static void test_iterator(ArrayClass* a) {
112
    // Add elements
113
    for (int i = 0; i < 10; i++) {
114
      a->append(i);
115
    }
116

117
    // Iterate
118
    int counter = 0;
119
    for (GrowableArrayIterator<int> i = a->begin(); i != a->end(); ++i) {
120
      ASSERT_EQ(*i, counter++);
121
    }
122

123
    // Check count
124
    ASSERT_EQ(counter, 10);
125
  }
126

127
  template <typename ArrayClass>
128
  static void test_capacity(ArrayClass* a) {
129
    ASSERT_EQ(a->length(), 0);
130
    a->reserve(50);
131
    ASSERT_EQ(a->length(), 0);
132
    ASSERT_EQ(a->capacity(), 50);
133
    for (int i = 0; i < 50; ++i) {
134
      a->append(i);
135
    }
136
    ASSERT_EQ(a->length(), 50);
137
    ASSERT_EQ(a->capacity(), 50);
138
    a->append(50);
139
    ASSERT_EQ(a->length(), 51);
140
    int capacity = a->capacity();
141
    ASSERT_GE(capacity, 51);
142
    for (int i = 0; i < 30; ++i) {
143
      a->pop();
144
    }
145
    ASSERT_EQ(a->length(), 21);
146
    ASSERT_EQ(a->capacity(), capacity);
147
    a->shrink_to_fit();
148
    ASSERT_EQ(a->length(), 21);
149
    ASSERT_EQ(a->capacity(), 21);
150

151
    a->reserve(50);
152
    ASSERT_EQ(a->length(), 21);
153
    ASSERT_EQ(a->capacity(), 50);
154

155
    a->clear();
156
    ASSERT_EQ(a->length(), 0);
157
    ASSERT_EQ(a->capacity(), 50);
158

159
    a->shrink_to_fit();
160
    ASSERT_EQ(a->length(), 0);
161
    ASSERT_EQ(a->capacity(), 0);
162
  }
163

164
  template <typename ArrayClass>
165
  static void test_copy1(ArrayClass* a) {
166
    ASSERT_EQ(a->length(), 1);
167
    ASSERT_EQ(a->at(0), 1);
168

169
    // Only allowed to copy to stack and embedded ResourceObjs
170

171
    // Copy to stack
172
    {
173
      GrowableArray<int> c(*a);
174

175
      ASSERT_EQ(c.length(), 1);
176
      ASSERT_EQ(c.at(0), 1);
177
    }
178

179
    // Copy to embedded
180
    {
181
      WithEmbeddedArray c(*a);
182

183
      ASSERT_EQ(c._a.length(), 1);
184
      ASSERT_EQ(c._a.at(0), 1);
185
    }
186
  }
187

188
  template <typename ArrayClass>
189
  static void test_assignment1(ArrayClass* a) {
190
    ASSERT_EQ(a->length(), 1);
191
    ASSERT_EQ(a->at(0), 1);
192

193
    // Only allowed to assign to stack and embedded ResourceObjs
194

195
    // Copy to embedded/resource
196
    {
197
      ResourceMark rm;
198
      GrowableArray<int> c(1);
199
      c = *a;
200

201
      ASSERT_EQ(c.length(), 1);
202
      ASSERT_EQ(c.at(0), 1);
203
    }
204

205
    // Copy to embedded/arena
206
    {
207
      Arena arena(mtTest);
208
      GrowableArray<int> c(&arena, 1, 0, 0);
209
      c = *a;
210

211
      ASSERT_EQ(c.length(), 1);
212
      ASSERT_EQ(c.at(0), 1);
213
    }
214

215
    // Copy to embedded/resource
216
    {
217
      ResourceMark rm;
218
      WithEmbeddedArray c(1);
219
      c._a = *a;
220

221
      ASSERT_EQ(c._a.length(), 1);
222
      ASSERT_EQ(c._a.at(0), 1);
223
    }
224

225
    // Copy to embedded/arena
226
    {
227
      Arena arena(mtTest);
228
      WithEmbeddedArray c(&arena, 1);
229
      c._a = *a;
230

231
      ASSERT_EQ(c._a.length(), 1);
232
      ASSERT_EQ(c._a.at(0), 1);
233
    }
234
  }
235

236
  // Supported by all GrowableArrays
237
  enum TestEnum {
238
    Append,
239
    Clear,
240
    Capacity,
241
    Iterator
242
  };
243

244
  template <typename ArrayClass>
245
  static void do_test(ArrayClass* a, TestEnum test) {
246
    switch (test) {
247
      case Append:
248
        test_append(a);
249
        break;
250

251
      case Clear:
252
        test_clear(a);
253
        break;
254

255
      case Capacity:
256
        test_capacity(a);
257
        break;
258

259
      case Iterator:
260
        test_iterator(a);
261
        break;
262

263
      default:
264
        fatal("Missing dispatch");
265
        break;
266
    }
267
  }
268

269
  // Only supported by GrowableArrays without CHeap data arrays
270
  enum TestNoCHeapEnum {
271
    Copy1,
272
    Assignment1,
273
  };
274

275
  template <typename ArrayClass>
276
  static void do_test(ArrayClass* a, TestNoCHeapEnum test) {
277
    switch (test) {
278
      case Copy1:
279
        test_copy1(a);
280
        break;
281

282
      case Assignment1:
283
        test_assignment1(a);
284
        break;
285

286
      default:
287
        fatal("Missing dispatch");
288
        break;
289
    }
290
  }
291

292
  enum ModifyEnum {
293
    Append1,
294
    Append1Clear,
295
    Append1ClearAndDeallocate,
296
    NoModify
297
  };
298

299
  template <typename ArrayClass>
300
  static void do_modify(ArrayClass* a, ModifyEnum modify) {
301
    switch (modify) {
302
      case Append1:
303
        a->append(1);
304
        break;
305

306
      case Append1Clear:
307
        a->append(1);
308
        a->clear();
309
        break;
310

311
      case Append1ClearAndDeallocate:
312
        a->append(1);
313
        a->clear_and_deallocate();
314
        break;
315

316
      case NoModify:
317
        // Nothing to do
318
        break;
319

320
      default:
321
        fatal("Missing dispatch");
322
        break;
323
    }
324
  }
325

326
  static const int Max0 = 0;
327
  static const int Max1 = 1;
328

329
  template <typename ArrayClass, typename T>
330
  static void modify_and_test(ArrayClass* array, ModifyEnum modify, T test) {
331
    do_modify(array, modify);
332
    do_test(array, test);
333
  }
334

335
  template <typename T>
336
  static void with_no_cheap_array(int max, ModifyEnum modify, T test) {
337
    // Resource/Resource allocated
338
    {
339
      ResourceMark rm;
340
      GrowableArray<int>* a = new GrowableArray<int>(max);
341
      modify_and_test(a, modify, test);
342
    }
343

344
    // Resource/Arena allocated
345
    //  Combination not supported
346

347
    // CHeap/Resource allocated
348
    //  Combination not supported
349

350
    // CHeap/Arena allocated
351
    //  Combination not supported
352

353
    // Stack/Resource allocated
354
    {
355
      ResourceMark rm;
356
      GrowableArray<int> a(max);
357
      modify_and_test(&a, modify, test);
358
    }
359

360
    // Stack/Arena allocated
361
    {
362
      Arena arena(mtTest);
363
      GrowableArray<int> a(&arena, max, 0, 0);
364
      modify_and_test(&a, modify, test);
365
    }
366

367
    // Embedded/Resource allocated
368
    {
369
      ResourceMark rm;
370
      WithEmbeddedArray w(max);
371
      modify_and_test(&w._a, modify, test);
372
    }
373

374
    // Embedded/Arena allocated
375
    {
376
      Arena arena(mtTest);
377
      WithEmbeddedArray w(&arena, max);
378
      modify_and_test(&w._a, modify, test);
379
    }
380
  }
381

382
  static void with_cheap_array(int max, ModifyEnum modify, TestEnum test) {
383
    // Resource/CHeap allocated
384
    //  Combination not supported
385

386
    // CHeap/CHeap allocated
387
    {
388
      GrowableArray<int>* a = new (mtTest) GrowableArray<int>(max, mtTest);
389
      modify_and_test(a, modify, test);
390
      delete a;
391
    }
392

393
    // Stack/CHeap allocated
394
    {
395
      GrowableArray<int> a(max, mtTest);
396
      modify_and_test(&a, modify, test);
397
    }
398

399
    // Embedded/CHeap allocated
400
    {
401
      WithEmbeddedArray w(max, mtTest);
402
      modify_and_test(&w._a, modify, test);
403
    }
404
  }
405

406
  static void with_all_types(int max, ModifyEnum modify, TestEnum test) {
407
    with_no_cheap_array(max, modify, test);
408
    with_cheap_array(max, modify, test);
409
  }
410

411
  static void with_all_types_empty(TestEnum test) {
412
    with_all_types(Max0, NoModify, test);
413
  }
414

415
  static void with_all_types_max_set(TestEnum test) {
416
    with_all_types(Max1, NoModify, test);
417
  }
418

419
  static void with_all_types_cleared(TestEnum test) {
420
    with_all_types(Max1, Append1Clear, test);
421
  }
422

423
  static void with_all_types_clear_and_deallocated(TestEnum test) {
424
    with_all_types(Max1, Append1ClearAndDeallocate, test);
425
  }
426

427
  static void with_all_types_all_0(TestEnum test) {
428
    with_all_types_empty(test);
429
    with_all_types_max_set(test);
430
    with_all_types_cleared(test);
431
    with_all_types_clear_and_deallocated(test);
432
  }
433

434
  static void with_no_cheap_array_append1(TestNoCHeapEnum test) {
435
    with_no_cheap_array(Max0, Append1, test);
436
  }
437
};
438

439
TEST_VM_F(GrowableArrayTest, append) {
440
  with_all_types_all_0(Append);
441
}
442

443
TEST_VM_F(GrowableArrayTest, clear) {
444
  with_all_types_all_0(Clear);
445
}
446

447
TEST_VM_F(GrowableArrayTest, capacity) {
448
  with_all_types_all_0(Capacity);
449
}
450

451
TEST_VM_F(GrowableArrayTest, iterator) {
452
  with_all_types_all_0(Iterator);
453
}
454

455
TEST_VM_F(GrowableArrayTest, copy) {
456
  with_no_cheap_array_append1(Copy1);
457
}
458

459
TEST_VM_F(GrowableArrayTest, assignment) {
460
  with_no_cheap_array_append1(Assignment1);
461
}
462

463
#ifdef ASSERT
464
TEST_VM_F(GrowableArrayTest, where) {
465
  WithEmbeddedArray s(1, mtTest);
466
  ASSERT_FALSE(s._a.allocated_on_C_heap());
467
  ASSERT_TRUE(elements_on_C_heap(&s._a));
468

469
  // Resource/Resource allocated
470
  {
471
    ResourceMark rm;
472
    GrowableArray<int>* a = new GrowableArray<int>();
473
    ASSERT_TRUE(a->allocated_on_res_area());
474
    ASSERT_TRUE(elements_on_resource_area(a));
475
  }
476

477
  // Resource/CHeap allocated
478
  //  Combination not supported
479

480
  // Resource/Arena allocated
481
  //  Combination not supported
482

483
  // CHeap/Resource allocated
484
  //  Combination not supported
485

486
  // CHeap/CHeap allocated
487
  {
488
    GrowableArray<int>* a = new (mtTest) GrowableArray<int>(0, mtTest);
489
    ASSERT_TRUE(a->allocated_on_C_heap());
490
    ASSERT_TRUE(elements_on_C_heap(a));
491
    delete a;
492
  }
493

494
  // CHeap/Arena allocated
495
  //  Combination not supported
496

497
  // Stack/Resource allocated
498
  {
499
    ResourceMark rm;
500
    GrowableArray<int> a(0);
501
    ASSERT_TRUE(a.allocated_on_stack_or_embedded());
502
    ASSERT_TRUE(elements_on_resource_area(&a));
503
  }
504

505
  // Stack/CHeap allocated
506
  {
507
    GrowableArray<int> a(0, mtTest);
508
    ASSERT_TRUE(a.allocated_on_stack_or_embedded());
509
    ASSERT_TRUE(elements_on_C_heap(&a));
510
  }
511

512
  // Stack/Arena allocated
513
  {
514
    Arena arena(mtTest);
515
    GrowableArray<int> a(&arena, 0, 0, 0);
516
    ASSERT_TRUE(a.allocated_on_stack_or_embedded());
517
    ASSERT_TRUE(elements_on_arena(&a));
518
  }
519

520
  // Embedded/Resource allocated
521
  {
522
    ResourceMark rm;
523
    WithEmbeddedArray w(0);
524
    ASSERT_TRUE(w._a.allocated_on_stack_or_embedded());
525
    ASSERT_TRUE(elements_on_resource_area(&w._a));
526
  }
527

528
  // Embedded/CHeap allocated
529
  {
530
    WithEmbeddedArray w(0, mtTest);
531
    ASSERT_TRUE(w._a.allocated_on_stack_or_embedded());
532
    ASSERT_TRUE(elements_on_C_heap(&w._a));
533
  }
534

535
  // Embedded/Arena allocated
536
  {
537
    Arena arena(mtTest);
538
    WithEmbeddedArray w(&arena, 0);
539
    ASSERT_TRUE(w._a.allocated_on_stack_or_embedded());
540
    ASSERT_TRUE(elements_on_arena(&w._a));
541
  }
542
}
543

544
TEST_VM_ASSERT_MSG(GrowableArrayAssertingTest, copy_with_embedded_cheap,
545
    "assert.!on_C_heap... failed: Copying of CHeap arrays not supported") {
546
  WithEmbeddedArray s(1, mtTest);
547
  // Intentionally asserts that copy of CHeap arrays are not allowed
548
  WithEmbeddedArray c(s);
549
}
550

551
TEST_VM_ASSERT_MSG(GrowableArrayAssertingTest, assignment_with_embedded_cheap,
552
    "assert.!on_C_heap... failed: Assignment of CHeap arrays not supported") {
553
  WithEmbeddedArray s(1, mtTest);
554
  WithEmbeddedArray c(1, mtTest);
555

556
  // Intentionally asserts that assignment of CHeap arrays are not allowed
557
  c = s;
558
}
559

560
#endif
561

562
TEST(GrowableArrayCHeap, sanity) {
563
  // Stack/CHeap
564
  {
565
    GrowableArrayCHeap<int, mtTest> a(0);
566
#ifdef ASSERT
567
    ASSERT_TRUE(a.allocated_on_stack_or_embedded());
568
#endif
569
    ASSERT_TRUE(a.is_empty());
570

571
    a.append(1);
572
    ASSERT_FALSE(a.is_empty());
573
    ASSERT_EQ(a.at(0), 1);
574
  }
575

576
  // CHeap/CHeap
577
  {
578
    GrowableArrayCHeap<int, mtTest>* a = new GrowableArrayCHeap<int, mtTest>(0);
579
#ifdef ASSERT
580
    ASSERT_TRUE(a->allocated_on_C_heap());
581
#endif
582
    ASSERT_TRUE(a->is_empty());
583

584
    a->append(1);
585
    ASSERT_FALSE(a->is_empty());
586
    ASSERT_EQ(a->at(0), 1);
587
    delete a;
588
  }
589

590
  // CHeap/CHeap - nothrow new operator
591
  {
592
    GrowableArrayCHeap<int, mtTest>* a = new (std::nothrow) GrowableArrayCHeap<int, mtTest>(0);
593
#ifdef ASSERT
594
    ASSERT_TRUE(a->allocated_on_C_heap());
595
#endif
596
    ASSERT_TRUE(a->is_empty());
597

598
    a->append(1);
599
    ASSERT_FALSE(a->is_empty());
600
    ASSERT_EQ(a->at(0), 1);
601
    delete a;
602
  }
603
}
604

605
TEST(GrowableArrayCHeap, find_if) {
606
  struct Element {
607
    int value;
608
  };
609
  GrowableArrayCHeap<Element, mtTest> array;
610
  array.push({1});
611
  array.push({2});
612
  array.push({3});
613

614
  {
615
    int index = array.find_if([&](const Element& elem) {
616
      return elem.value == 1;
617
    });
618
    ASSERT_EQ(index, 0);
619
  }
620

621
  {
622
    int index = array.find_if([&](const Element& elem) {
623
      return elem.value > 1;
624
    });
625
    ASSERT_EQ(index, 1);
626
  }
627

628
  {
629
    int index = array.find_if([&](const Element& elem) {
630
      return elem.value == 4;
631
    });
632
    ASSERT_EQ(index, -1);
633
  }
634
}
635

636
TEST(GrowableArrayCHeap, find_from_end_if) {
637
  struct Element {
638
    int value;
639
  };
640
  GrowableArrayCHeap<Element, mtTest> array;
641
  array.push({1});
642
  array.push({2});
643
  array.push({3});
644

645
  {
646
    int index = array.find_from_end_if([&](const Element& elem) {
647
      return elem.value == 1;
648
    });
649
    ASSERT_EQ(index, 0);
650
  }
651

652
  {
653
    int index = array.find_from_end_if([&](const Element& elem) {
654
      return elem.value > 1;
655
    });
656
    ASSERT_EQ(index, 2);
657
  }
658

659
  {
660
    int index = array.find_from_end_if([&](const Element& elem) {
661
      return elem.value == 4;
662
    });
663
    ASSERT_EQ(index, -1);
664
  }
665
}
666

667
TEST(GrowableArrayCHeap, returning_references_works_as_expected) {
668
  GrowableArrayCHeap<int, mtTest> arr(8, 8, -1); // Pre-fill with 8 -1s
669
  int& x = arr.at_grow(9, -1);
670
  EXPECT_EQ(-1, arr.at(9));
671
  EXPECT_EQ(-1, x);
672
  x = 2;
673
  EXPECT_EQ(2, arr.at(9));
674
  int& x2 = arr.top();
675
  EXPECT_EQ(2, arr.at(9));
676
  x2 = 5;
677
  EXPECT_EQ(5, arr.at(9));
678

679
  int y = arr.at_grow(10, -1);
680
  EXPECT_EQ(-1, arr.at(10));
681
  y = arr.top();
682
  EXPECT_EQ(-1, arr.at(10));
683

684
  GrowableArrayCHeap<int, mtTest> arr2(1, 1, -1);
685
  int& first = arr2.first();
686
  int& last = arr2.last();
687
  EXPECT_EQ(-1, first);
688
  EXPECT_EQ(-1, last);
689
  first = 5;
690
  EXPECT_EQ(5, first);
691
  EXPECT_EQ(5, last);
692
}
693