1 /*
   2  * Copyright (c) 2018, 2020, Oracle and/or its affiliates. All rights reserved.
   3  * Copyright (c) 2018, 2020 SAP SE. All rights reserved.
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * This code is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License version 2 only, as
   8  * published by the Free Software Foundation.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  *
  24  */
  25 
  26 #ifndef GTEST_METASPACE_SPARSEARRAY_HPP
  27 #define GTEST_METASPACE_SPARSEARRAY_HPP
  28 
  29 #include "memory/allocation.hpp"
  30 #include "runtime/os.hpp"
  31 #include "metaspace/metaspaceTestsCommon.hpp"
  32 #include "metaspace/metaspace_rangehelpers.hpp"
  33 
  34 
  35 /////// SparseArray<T> ////////////////
  36 
  37 // Throughout these tests we need to keep track of allocated items (ranges of metaspace memory, metachunks, ..)
  38 //  and be able to random-access them. Makes sense to have a helper for that.
  39 template <class T>
  40 class SparseArray : public StackObj {
  41 
  42   T* const _slots;
  43   const int _num;
  44 
  45   // For convenience: a range covering all possible slot indices.
  46   const IntRange _index_range;
  47 
  48   bool contains(int index) const {
  49     return _index_range.contains(index);
  50   }
  51 
  52   // Check slot intex for oob
  53   void check_index(int i) const {
  54     assert(contains(i), "Sanity");
  55   }
  56 
  57   // Swap the content of two slots.
  58   void swap(int i1, int i2) {
  59     check_index(i1);
  60     check_index(i2);
  61     T tmp = _slots[i1];
  62     _slots[i1] = _slots[i2];
  63     _slots[i2] = tmp;
  64   }
  65 
  66   enum condition_t { cond_null = 0, cond_non_null = 1, cond_dontcare = 2 };
  67 
  68   // Helper for next_matching_slot
  69   bool slot_matches(int slot, condition_t c) const {
  70     switch(c) {
  71     case cond_null:     return _slots[slot] == NULL;
  72     case cond_non_null: return _slots[slot] != NULL;
  73     case cond_dontcare: return true;
  74     }
  75     ShouldNotReachHere();
  76     return false;
  77   }
  78 
  79   // Starting at (including) index, find the next matching slot. Returns index or -1 if none found.
  80   int next_matching_slot(int slot, condition_t c) const {
  81     while(slot < _num) {
  82       if (slot_matches(slot, c)) {
  83         return slot;
  84       }
  85       slot ++;
  86     }
  87     return -1;
  88   }
  89 
  90 public:
  91 
  92   SparseArray(int num)
  93     : _slots(NEW_C_HEAP_ARRAY(T, num, mtInternal)),
  94       _num(num),
  95       _index_range(num)
  96   {
  97     for (int i = 0; i < _num; i ++) {
  98       _slots[i] = NULL;
  99     }
 100   }
 101 
 102   T at(int i)              { return _slots[i]; }
 103   const T at(int i) const  { return _slots[i]; }
 104   void set_at(int i, T e)  { _slots[i] = e; }
 105 
 106   int size() const         { return _num; }
 107 
 108   bool slot_is_null(int i) const                      { check_index(i); return _slots[i] == NULL; }
 109 
 110   DEBUG_ONLY(void check_slot_is_null(int i) const     { assert(slot_is_null(i), "Slot %d is not null", i); })
 111   DEBUG_ONLY(void check_slot_is_not_null(int i) const { assert(!slot_is_null(i), "Slot %d is null", i); })
 112 
 113   // Shuffle all elements randomly
 114   void shuffle() {
 115     for (int i = 0; i < _num; i ++) {
 116       swap(i, random_slot_index());
 117     }
 118   }
 119 
 120   // Reverse elements
 121   void reverse() {
 122     for (int i = 0; i < _num / 2; i ++) {
 123       swap(i, _num - i);
 124     }
 125   }
 126 
 127   int first_slot() const            { return 0; }
 128   int next_slot(int index) const    { return index == _index_range.highest() ? -1 : index + 1; }
 129 
 130   int first_non_null_slot() const         { return next_matching_slot(0, cond_non_null); }
 131   int next_non_null_slot(int index) const { return next_matching_slot(index + 1, cond_non_null); }
 132 
 133   int first_null_slot() const             { return next_matching_slot(0, cond_null); }
 134   int next_null_slot(int index) const     { return next_matching_slot(index + 1, cond_null); }
 135 
 136   // Return a random slot index.
 137   int random_slot_index() const {
 138     return _index_range.random_value();
 139   }
 140 
 141   int random_non_null_slot_index() const {
 142     int i = next_non_null_slot(_index_range.random_value());
 143     if (i == -1) {
 144       i = first_non_null_slot();
 145     }
 146     return i;
 147   }
 148 
 149   int random_null_slot_index() const {
 150     int i = next_null_slot(_index_range.random_value());
 151     if (i == -1) {
 152       i = first_null_slot();
 153     }
 154     return i;
 155   }
 156 
 157   IntRange random_slot_range() const {
 158     return _index_range.random_subrange();
 159   }
 160 
 161 };
 162 
 163 
 164 #endif // GTEST_METASPACE_SPARSEARRAY_HPP
 165 
 166