1 /*
   2  * Copyright (c) 2000, 2016, 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 #ifndef SHARE_VM_UTILITIES_ARRAY_HPP
  26 #define SHARE_VM_UTILITIES_ARRAY_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "memory/metaspace.hpp"
  31 #include "runtime/orderAccess.hpp"
  32 
  33 // correct linkage required to compile w/o warnings
  34 // (must be on file level - cannot be local)
  35 extern "C" { typedef int (*ftype)(const void*, const void*); }
  36 
  37 
  38 class ResourceArray: public ResourceObj {
  39  protected:
  40   int   _length;                                 // the number of array elements
  41   void* _data;                                   // the array memory
  42 #ifdef ASSERT
  43   int   _nesting;                                // the resource area nesting level
  44 #endif
  45 
  46   // creation
  47   ResourceArray() {
  48     _length  = 0;
  49     _data    = NULL;
  50     DEBUG_ONLY(init_nesting();)
  51     // client may call initialize, at most once
  52   }
  53 
  54 
  55   ResourceArray(size_t esize, int length) {
  56     DEBUG_ONLY(_data = NULL);
  57     initialize(esize, length);
  58   }
  59 
  60   void initialize(size_t esize, int length) {
  61     assert(length >= 0, "illegal length");
  62     assert(StressRewriter || _data == NULL, "must be new object");
  63     _length  = length;
  64     _data    = resource_allocate_bytes(esize * length);
  65     DEBUG_ONLY(init_nesting();)
  66   }
  67 
  68 #ifdef ASSERT
  69   void init_nesting();
  70 #endif
  71 
  72   // helper functions
  73   void sort     (size_t esize, ftype f);         // sort the array
  74   void expand   (size_t esize, int i, int& size);// expand the array to include slot i
  75   void remove_at(size_t esize, int i);           // remove the element in slot i
  76 
  77  public:
  78   // standard operations
  79   int  length() const                            { return _length; }
  80   bool is_empty() const                          { return length() == 0; }
  81 };
  82 
  83 
  84 template <MEMFLAGS F>class CHeapArray: public CHeapObj<F> {
  85  protected:
  86   int   _length;                                 // the number of array elements
  87   void* _data;                                   // the array memory
  88 
  89   // creation
  90   CHeapArray() {
  91     _length  = 0;
  92     _data    = NULL;
  93   }
  94 
  95 
  96   CHeapArray(size_t esize, int length) {
  97     assert(length >= 0, "illegal length");
  98     _length  = length;
  99     _data    = (void*) NEW_C_HEAP_ARRAY(char *, esize * length, F);
 100   }
 101 
 102   void initialize(size_t esize, int length) {
 103     // In debug set array to 0?
 104   }
 105 
 106 #ifdef ASSERT
 107   void init_nesting();
 108 #endif
 109 
 110   // helper functions
 111   void sort     (size_t esize, ftype f);         // sort the array
 112   void expand   (size_t esize, int i, int& size);// expand the array to include slot i
 113   void remove_at(size_t esize, int i);           // remove the element in slot i
 114 
 115  public:
 116   // standard operations
 117   int  length() const                            { return _length; }
 118   bool is_empty() const                          { return length() == 0; }
 119 };
 120 
 121 #define define_generic_array(array_name,element_type, base_class)                        \
 122   class array_name: public base_class {                                                  \
 123    protected:                                                                            \
 124     typedef element_type etype;                                                          \
 125     enum { esize = sizeof(etype) };                                                      \
 126                                                                                          \
 127     void base_remove_at(size_t size, int i) { base_class::remove_at(size, i); }          \
 128                                                                                          \
 129    public:                                                                               \
 130     /* creation */                                                                       \
 131     array_name() : base_class()                       {}                                 \
 132     explicit array_name(const int length) : base_class(esize, length) {}                          \
 133     array_name(const int length, const etype fx)      { initialize(length, fx); }        \
 134     void initialize(const int length)     { base_class::initialize(esize, length); }     \
 135     void initialize(const int length, const etype fx) {                                  \
 136       initialize(length);                                                                \
 137       for (int i = 0; i < length; i++) ((etype*)_data)[i] = fx;                          \
 138     }                                                                                    \
 139                                                                                          \
 140     /* standard operations */                                                            \
 141     etype& operator [] (const int i) const {                                             \
 142       assert(0 <= i && i < length(), "index out of bounds");                             \
 143       return ((etype*)_data)[i];                                                         \
 144     }                                                                                    \
 145                                                                                          \
 146     int index_of(const etype x) const {                                                  \
 147       int i = length();                                                                  \
 148       while (i-- > 0 && ((etype*)_data)[i] != x) ;                                       \
 149       /* i < 0 || ((etype*)_data)_data[i] == x */                                        \
 150       return i;                                                                          \
 151     }                                                                                    \
 152                                                                                          \
 153     void sort(int f(etype*, etype*))             { base_class::sort(esize, (ftype)f); }  \
 154     bool contains(const etype x) const           { return index_of(x) >= 0; }            \
 155                                                                                          \
 156     /* deprecated operations - for compatibility with GrowableArray only */              \
 157     etype  at(const int i) const                 { return (*this)[i]; }                  \
 158     void   at_put(const int i, const etype x)    { (*this)[i] = x; }                     \
 159     etype* adr_at(const int i)                   { return &(*this)[i]; }                 \
 160     int    find(const etype x)                   { return index_of(x); }                 \
 161   };                                                                                     \
 162 
 163 
 164 #define define_array(array_name,element_type)                                            \
 165   define_generic_array(array_name, element_type, ResourceArray)
 166 
 167 
 168 #define define_stack(stack_name,array_name)                                              \
 169   class stack_name: public array_name {                                                  \
 170    protected:                                                                            \
 171     int _size;                                                                           \
 172                                                                                          \
 173     void grow(const int i, const etype fx) {                                             \
 174       assert(i >= length(), "index too small");                                          \
 175       if (i >= size()) expand(esize, i, _size);                                          \
 176       for (int j = length(); j <= i; j++) ((etype*)_data)[j] = fx;                       \
 177       _length = i+1;                                                                     \
 178     }                                                                                    \
 179                                                                                          \
 180    public:                                                                               \
 181     /* creation */                                                                       \
 182     stack_name() : array_name()                     { _size = 0; }                       \
 183     stack_name(const int size)                      { initialize(size); }                \
 184     stack_name(const int size, const etype fx)      { initialize(size, fx); }            \
 185     void initialize(const int size, const etype fx) {                                    \
 186       _size = size;                                                                      \
 187       array_name::initialize(size, fx);                                                  \
 188       /* _length == size, allocation and size are the same */                            \
 189     }                                                                                    \
 190     void initialize(const int size) {                                                    \
 191       _size = size;                                                                      \
 192       array_name::initialize(size);                                                      \
 193       _length = 0;          /* reset length to zero; _size records the allocation */     \
 194     }                                                                                    \
 195                                                                                          \
 196     /* standard operations */                                                            \
 197     int size() const                             { return _size; }                       \
 198                                                                                          \
 199     int push(const etype x) {                                                            \
 200       int len = length();                                                                \
 201       if (len >= size()) expand(esize, len, _size);                                      \
 202       ((etype*)_data)[len] = x;                                                          \
 203       _length = len+1;                                                                   \
 204       return len;                                                                        \
 205     }                                                                                    \
 206                                                                                          \
 207     etype pop() {                                                                        \
 208       assert(!is_empty(), "stack is empty");                                             \
 209       return ((etype*)_data)[--_length];                                                 \
 210     }                                                                                    \
 211                                                                                          \
 212     etype top() const {                                                                  \
 213       assert(!is_empty(), "stack is empty");                                             \
 214       return ((etype*)_data)[length() - 1];                                              \
 215     }                                                                                    \
 216                                                                                          \
 217     void push_all(const stack_name* stack) {                                             \
 218       const int l = stack->length();                                                     \
 219       for (int i = 0; i < l; i++) push(((etype*)(stack->_data))[i]);                     \
 220     }                                                                                    \
 221                                                                                          \
 222     etype at_grow(const int i, const etype fx) {                                         \
 223       if (i >= length()) grow(i, fx);                                                    \
 224       return ((etype*)_data)[i];                                                         \
 225     }                                                                                    \
 226                                                                                          \
 227     void at_put_grow(const int i, const etype x, const etype fx) {                       \
 228       if (i >= length()) grow(i, fx);                                                    \
 229       ((etype*)_data)[i] = x;                                                            \
 230     }                                                                                    \
 231                                                                                          \
 232     void truncate(const int length) {                                                    \
 233       assert(0 <= length && length <= this->length(), "illegal length");                 \
 234       _length = length;                                                                  \
 235     }                                                                                    \
 236                                                                                          \
 237     void remove_at(int i)                        { base_remove_at(esize, i); }           \
 238     void remove(etype x)                         { remove_at(index_of(x)); }             \
 239                                                                                          \
 240     /* inserts the given element before the element at index i */                        \
 241     void insert_before(const int i, const etype el)  {                                   \
 242       int len = length();                                                                \
 243       int new_length = len + 1;                                                          \
 244       if (new_length >= size()) expand(esize, new_length, _size);                        \
 245       for (int j = len - 1; j >= i; j--) {                                               \
 246         ((etype*)_data)[j + 1] = ((etype*)_data)[j];                                     \
 247       }                                                                                  \
 248       _length = new_length;                                                              \
 249       at_put(i, el);                                                                     \
 250     }                                                                                    \
 251                                                                                          \
 252     /* inserts contents of the given stack before the element at index i */              \
 253     void insert_before(const int i, const stack_name *st) {                              \
 254       if (st->length() == 0) return;                                                     \
 255       int len = length();                                                                \
 256       int st_len = st->length();                                                         \
 257       int new_length = len + st_len;                                                     \
 258       if (new_length >= size()) expand(esize, new_length, _size);                        \
 259       int j;                                                                             \
 260       for (j = len - 1; j >= i; j--) {                                                   \
 261         ((etype*)_data)[j + st_len] = ((etype*)_data)[j];                                \
 262       }                                                                                  \
 263       for (j = 0; j < st_len; j++) {                                                     \
 264         ((etype*)_data)[i + j] = ((etype*)st->_data)[j];                                 \
 265       }                                                                                  \
 266       _length = new_length;                                                              \
 267     }                                                                                    \
 268                                                                                          \
 269     /* deprecated operations - for compatibility with GrowableArray only */              \
 270     int  capacity() const                        { return size(); }                      \
 271     void clear()                                 { truncate(0); }                        \
 272     void trunc_to(const int length)              { truncate(length); }                   \
 273     int  append(const etype x)                   { return push(x); }                     \
 274     void appendAll(const stack_name* stack)      { push_all(stack); }                    \
 275     etype last() const                           { return top(); }                       \
 276   };                                                                                     \
 277 
 278 
 279 #define define_resource_list(element_type)                                               \
 280   define_generic_array(element_type##Array, element_type, ResourceArray)                 \
 281   define_stack(element_type##List, element_type##Array)
 282 
 283 #define define_resource_pointer_list(element_type)                                       \
 284   define_generic_array(element_type##Array, element_type *, ResourceArray)               \
 285   define_stack(element_type##List, element_type##Array)
 286 
 287 #define define_c_heap_list(element_type)                                                 \
 288   define_generic_array(element_type##Array, element_type, CHeapArray)                    \
 289   define_stack(element_type##List, element_type##Array)
 290 
 291 #define define_c_heap_pointer_list(element_type)                                         \
 292   define_generic_array(element_type##Array, element_type *, CHeapArray)                  \
 293   define_stack(element_type##List, element_type##Array)
 294 
 295 // Arrays for basic types
 296 typedef GrowableArray<int> intArray;
 297 typedef GrowableArray<int> intStack;
 298 typedef GrowableArray<bool> boolArray;
 299 typedef GrowableArray<bool> boolStack;
 300 
 301 // Array for metadata allocation
 302 
 303 template <typename T>
 304 class Array: public MetaspaceObj {
 305   friend class MetadataFactory;
 306   friend class VMStructs;
 307   friend class JVMCIVMStructs;
 308   friend class MethodHandleCompiler;           // special case
 309   friend class WhiteBox;
 310 protected:
 311   int _length;                                 // the number of array elements
 312   T   _data[1];                                // the array memory
 313 
 314   void initialize(int length) {
 315     _length = length;
 316   }
 317 
 318  private:
 319   // Turn off copy constructor and assignment operator.
 320   Array(const Array<T>&);
 321   void operator=(const Array<T>&);
 322 
 323   void* operator new(size_t size, ClassLoaderData* loader_data, int length, bool read_only, TRAPS) throw() {
 324     size_t word_size = Array::size(length);
 325     return (void*) Metaspace::allocate(loader_data, word_size, read_only,
 326                                        MetaspaceObj::array_type(sizeof(T)), THREAD);
 327   }
 328 
 329   static size_t byte_sizeof(int length) { return sizeof(Array<T>) + MAX2(length - 1, 0) * sizeof(T); }
 330 
 331   // WhiteBox API helper.
 332   // Can't distinguish between array of length 0 and length 1,
 333   // will always return 0 in those cases.
 334   static int bytes_to_length(size_t bytes)       {
 335     assert(is_size_aligned(bytes, BytesPerWord), "Must be, for now");
 336 
 337     if (sizeof(Array<T>) >= bytes) {
 338       return 0;
 339     }
 340 
 341     size_t left = bytes - sizeof(Array<T>);
 342     assert(is_size_aligned(left, sizeof(T)), "Must be");
 343 
 344     size_t elements = left / sizeof(T);
 345     assert(elements <= (size_t)INT_MAX, "number of elements " SIZE_FORMAT "doesn't fit into an int.", elements);
 346 
 347     int length = (int)elements;
 348 
 349     assert((size_t)size(length) * BytesPerWord == bytes,
 350            "Expected: " SIZE_FORMAT " got: " SIZE_FORMAT,
 351            bytes, (size_t)size(length) * BytesPerWord);
 352 
 353     return length;
 354   }
 355 
 356   explicit Array(int length) : _length(length) {
 357     assert(length >= 0, "illegal length");
 358   }
 359 
 360   Array(int length, T init) : _length(length) {
 361     assert(length >= 0, "illegal length");
 362     for (int i = 0; i < length; i++) {
 363       _data[i] = init;
 364     }
 365   }
 366 
 367  public:
 368 
 369   // standard operations
 370   int  length() const                 { return _length; }
 371   T* data()                           { return _data; }
 372   bool is_empty() const               { return length() == 0; }
 373 
 374   int index_of(const T& x) const {
 375     int i = length();
 376     while (i-- > 0 && _data[i] != x) ;
 377 
 378     return i;
 379   }
 380 
 381   // sort the array.
 382   bool contains(const T& x) const      { return index_of(x) >= 0; }
 383 
 384   T    at(int i) const                 { assert(i >= 0 && i< _length, "oob: 0 <= %d < %d", i, _length); return _data[i]; }
 385   void at_put(const int i, const T& x) { assert(i >= 0 && i< _length, "oob: 0 <= %d < %d", i, _length); _data[i] = x; }
 386   T*   adr_at(const int i)             { assert(i >= 0 && i< _length, "oob: 0 <= %d < %d", i, _length); return &_data[i]; }
 387   int  find(const T& x)                { return index_of(x); }
 388 
 389   T at_acquire(const int which)              { return OrderAccess::load_acquire(adr_at(which)); }
 390   void release_at_put(int which, T contents) { OrderAccess::release_store(adr_at(which), contents); }
 391 
 392   static int size(int length) {
 393     return align_size_up(byte_sizeof(length), BytesPerWord) / BytesPerWord;
 394   }
 395 
 396   int size() {
 397     return size(_length);
 398   }
 399 
 400   static int length_offset_in_bytes() { return (int) (offset_of(Array<T>, _length)); }
 401   // Note, this offset don't have to be wordSize aligned.
 402   static int base_offset_in_bytes() { return (int) (offset_of(Array<T>, _data)); };
 403 
 404   // FIXME: How to handle this?
 405   void print_value_on(outputStream* st) const {
 406     st->print("Array<T>(" INTPTR_FORMAT ")", p2i(this));
 407   }
 408 
 409 #ifndef PRODUCT
 410   void print(outputStream* st) {
 411      for (int i = 0; i< _length; i++) {
 412        st->print_cr("%d: " INTPTR_FORMAT, i, (intptr_t)at(i));
 413      }
 414   }
 415   void print() { print(tty); }
 416 #endif // PRODUCT
 417 };
 418 
 419 
 420 #endif // SHARE_VM_UTILITIES_ARRAY_HPP