duke@435: /*
iklam@5208:  * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
duke@435:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435:  *
duke@435:  * This code is free software; you can redistribute it and/or modify it
duke@435:  * under the terms of the GNU General Public License version 2 only, as
duke@435:  * published by the Free Software Foundation.
duke@435:  *
duke@435:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@435:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@435:  * version 2 for more details (a copy is included in the LICENSE file that
duke@435:  * accompanied this code).
duke@435:  *
duke@435:  * You should have received a copy of the GNU General Public License version
duke@435:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@435:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435:  *
trims@1907:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@1907:  * or visit www.oracle.com if you need additional information or have any
trims@1907:  * questions.
duke@435:  *
duke@435:  */
duke@435: 
stefank@2314: #ifndef SHARE_VM_UTILITIES_ARRAY_HPP
stefank@2314: #define SHARE_VM_UTILITIES_ARRAY_HPP
stefank@2314: 
stefank@2314: #include "memory/allocation.hpp"
stefank@2314: #include "memory/allocation.inline.hpp"
coleenp@4037: #include "memory/metaspace.hpp"
stefank@2314: 
duke@435: // correct linkage required to compile w/o warnings
duke@435: // (must be on file level - cannot be local)
duke@435: extern "C" { typedef int (*ftype)(const void*, const void*); }
duke@435: 
duke@435: 
duke@435: class ResourceArray: public ResourceObj {
duke@435:  protected:
duke@435:   int   _length;                                 // the number of array elements
duke@435:   void* _data;                                   // the array memory
duke@435: #ifdef ASSERT
duke@435:   int   _nesting;                                // the resource area nesting level
duke@435: #endif
duke@435: 
duke@435:   // creation
duke@435:   ResourceArray() {
duke@435:     _length  = 0;
duke@435:     _data    = NULL;
duke@435:     DEBUG_ONLY(init_nesting();)
jrose@867:     // client may call initialize, at most once
duke@435:   }
duke@435: 
duke@435: 
duke@435:   ResourceArray(size_t esize, int length) {
jrose@867:     DEBUG_ONLY(_data = NULL);
jrose@867:     initialize(esize, length);
jrose@867:   }
jrose@867: 
jrose@867:   void initialize(size_t esize, int length) {
duke@435:     assert(length >= 0, "illegal length");
jrose@867:     assert(_data == NULL, "must be new object");
duke@435:     _length  = length;
duke@435:     _data    = resource_allocate_bytes(esize * length);
duke@435:     DEBUG_ONLY(init_nesting();)
duke@435:   }
duke@435: 
duke@435: #ifdef ASSERT
duke@435:   void init_nesting();
duke@435: #endif
duke@435: 
duke@435:   // helper functions
duke@435:   void sort     (size_t esize, ftype f);         // sort the array
duke@435:   void expand   (size_t esize, int i, int& size);// expand the array to include slot i
duke@435:   void remove_at(size_t esize, int i);           // remove the element in slot i
duke@435: 
duke@435:  public:
duke@435:   // standard operations
duke@435:   int  length() const                            { return _length; }
duke@435:   bool is_empty() const                          { return length() == 0; }
duke@435: };
duke@435: 
duke@435: 
zgu@3900: template <MEMFLAGS F>class CHeapArray: public CHeapObj<F> {
duke@435:  protected:
duke@435:   int   _length;                                 // the number of array elements
duke@435:   void* _data;                                   // the array memory
duke@435: 
duke@435:   // creation
duke@435:   CHeapArray() {
duke@435:     _length  = 0;
duke@435:     _data    = NULL;
duke@435:   }
duke@435: 
duke@435: 
duke@435:   CHeapArray(size_t esize, int length) {
duke@435:     assert(length >= 0, "illegal length");
duke@435:     _length  = length;
zgu@3900:     _data    = (void*) NEW_C_HEAP_ARRAY(char *, esize * length, F);
duke@435:   }
duke@435: 
coleenp@4037:   void initialize(size_t esize, int length) {
coleenp@4037:     // In debug set array to 0?
coleenp@4037:   }
coleenp@4037: 
duke@435: #ifdef ASSERT
duke@435:   void init_nesting();
duke@435: #endif
duke@435: 
duke@435:   // helper functions
duke@435:   void sort     (size_t esize, ftype f);         // sort the array
duke@435:   void expand   (size_t esize, int i, int& size);// expand the array to include slot i
duke@435:   void remove_at(size_t esize, int i);           // remove the element in slot i
duke@435: 
duke@435:  public:
duke@435:   // standard operations
duke@435:   int  length() const                            { return _length; }
duke@435:   bool is_empty() const                          { return length() == 0; }
duke@435: };
duke@435: 
duke@435: #define define_generic_array(array_name,element_type, base_class)                        \
duke@435:   class array_name: public base_class {                                                  \
duke@435:    protected:                                                                            \
duke@435:     typedef element_type etype;                                                          \
duke@435:     enum { esize = sizeof(etype) };                                                      \
duke@435:                                                                                          \
duke@435:     void base_remove_at(size_t size, int i) { base_class::remove_at(size, i); }          \
duke@435:                                                                                          \
duke@435:    public:                                                                               \
duke@435:     /* creation */                                                                       \
duke@435:     array_name() : base_class()                       {}                                 \
coleenp@4037:     explicit array_name(const int length) : base_class(esize, length) {}                          \
jrose@867:     array_name(const int length, const etype fx)      { initialize(length, fx); }        \
jrose@867:     void initialize(const int length)     { base_class::initialize(esize, length); }     \
jrose@867:     void initialize(const int length, const etype fx) {                                  \
jrose@867:       initialize(length);                                                                \
duke@435:       for (int i = 0; i < length; i++) ((etype*)_data)[i] = fx;                          \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     /* standard operations */                                                            \
duke@435:     etype& operator [] (const int i) const {                                             \
duke@435:       assert(0 <= i && i < length(), "index out of bounds");                             \
duke@435:       return ((etype*)_data)[i];                                                         \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     int index_of(const etype x) const {                                                  \
duke@435:       int i = length();                                                                  \
duke@435:       while (i-- > 0 && ((etype*)_data)[i] != x) ;                                       \
duke@435:       /* i < 0 || ((etype*)_data)_data[i] == x */                                        \
duke@435:       return i;                                                                          \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     void sort(int f(etype*, etype*))             { base_class::sort(esize, (ftype)f); }  \
duke@435:     bool contains(const etype x) const           { return index_of(x) >= 0; }            \
duke@435:                                                                                          \
duke@435:     /* deprecated operations - for compatibility with GrowableArray only */              \
duke@435:     etype  at(const int i) const                 { return (*this)[i]; }                  \
duke@435:     void   at_put(const int i, const etype x)    { (*this)[i] = x; }                     \
duke@435:     etype* adr_at(const int i)                   { return &(*this)[i]; }                 \
duke@435:     int    find(const etype x)                   { return index_of(x); }                 \
duke@435:   };                                                                                     \
duke@435: 
duke@435: 
duke@435: #define define_array(array_name,element_type)                                            \
duke@435:   define_generic_array(array_name, element_type, ResourceArray)
duke@435: 
duke@435: 
duke@435: #define define_stack(stack_name,array_name)                                              \
duke@435:   class stack_name: public array_name {                                                  \
duke@435:    protected:                                                                            \
duke@435:     int _size;                                                                           \
duke@435:                                                                                          \
duke@435:     void grow(const int i, const etype fx) {                                             \
duke@435:       assert(i >= length(), "index too small");                                          \
duke@435:       if (i >= size()) expand(esize, i, _size);                                          \
duke@435:       for (int j = length(); j <= i; j++) ((etype*)_data)[j] = fx;                       \
duke@435:       _length = i+1;                                                                     \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:    public:                                                                               \
duke@435:     /* creation */                                                                       \
jrose@867:     stack_name() : array_name()                     { _size = 0; }                       \
jrose@867:     stack_name(const int size)                      { initialize(size); }                \
jrose@867:     stack_name(const int size, const etype fx)      { initialize(size, fx); }            \
jrose@867:     void initialize(const int size, const etype fx) {                                    \
jrose@867:       _size = size;                                                                      \
jrose@867:       array_name::initialize(size, fx);                                                  \
jrose@867:       /* _length == size, allocation and size are the same */                            \
jrose@867:     }                                                                                    \
jrose@867:     void initialize(const int size) {                                                    \
jrose@867:       _size = size;                                                                      \
jrose@867:       array_name::initialize(size);                                                      \
jrose@867:       _length = 0;          /* reset length to zero; _size records the allocation */     \
jrose@867:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     /* standard operations */                                                            \
duke@435:     int size() const                             { return _size; }                       \
duke@435:                                                                                          \
jrose@867:     int push(const etype x) {                                                            \
jrose@867:       int len = length();                                                                \
jrose@867:       if (len >= size()) expand(esize, len, _size);                                      \
jrose@867:       ((etype*)_data)[len] = x;                                                          \
jrose@867:       _length = len+1;                                                                   \
jrose@867:       return len;                                                                        \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     etype pop() {                                                                        \
duke@435:       assert(!is_empty(), "stack is empty");                                             \
duke@435:       return ((etype*)_data)[--_length];                                                 \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     etype top() const {                                                                  \
duke@435:       assert(!is_empty(), "stack is empty");                                             \
duke@435:       return ((etype*)_data)[length() - 1];                                              \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     void push_all(const stack_name* stack) {                                             \
duke@435:       const int l = stack->length();                                                     \
duke@435:       for (int i = 0; i < l; i++) push(((etype*)(stack->_data))[i]);                     \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     etype at_grow(const int i, const etype fx) {                                         \
duke@435:       if (i >= length()) grow(i, fx);                                                    \
duke@435:       return ((etype*)_data)[i];                                                         \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     void at_put_grow(const int i, const etype x, const etype fx) {                       \
duke@435:       if (i >= length()) grow(i, fx);                                                    \
duke@435:       ((etype*)_data)[i] = x;                                                            \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     void truncate(const int length) {                                                    \
duke@435:       assert(0 <= length && length <= this->length(), "illegal length");                 \
duke@435:       _length = length;                                                                  \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     void remove_at(int i)                        { base_remove_at(esize, i); }           \
duke@435:     void remove(etype x)                         { remove_at(index_of(x)); }             \
duke@435:                                                                                          \
duke@435:     /* inserts the given element before the element at index i */                        \
duke@435:     void insert_before(const int i, const etype el)  {                                   \
duke@435:       int len = length();                                                                \
duke@435:       int new_length = len + 1;                                                          \
duke@435:       if (new_length >= size()) expand(esize, new_length, _size);                        \
duke@435:       for (int j = len - 1; j >= i; j--) {                                               \
duke@435:         ((etype*)_data)[j + 1] = ((etype*)_data)[j];                                     \
duke@435:       }                                                                                  \
duke@435:       _length = new_length;                                                              \
duke@435:       at_put(i, el);                                                                     \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     /* inserts contents of the given stack before the element at index i */              \
duke@435:     void insert_before(const int i, const stack_name *st) {                              \
duke@435:       if (st->length() == 0) return;                                                     \
duke@435:       int len = length();                                                                \
duke@435:       int st_len = st->length();                                                         \
duke@435:       int new_length = len + st_len;                                                     \
duke@435:       if (new_length >= size()) expand(esize, new_length, _size);                        \
duke@435:       int j;                                                                             \
duke@435:       for (j = len - 1; j >= i; j--) {                                                   \
duke@435:         ((etype*)_data)[j + st_len] = ((etype*)_data)[j];                                \
duke@435:       }                                                                                  \
duke@435:       for (j = 0; j < st_len; j++) {                                                     \
duke@435:         ((etype*)_data)[i + j] = ((etype*)st->_data)[j];                                 \
duke@435:       }                                                                                  \
duke@435:       _length = new_length;                                                              \
duke@435:     }                                                                                    \
duke@435:                                                                                          \
duke@435:     /* deprecated operations - for compatibility with GrowableArray only */              \
duke@435:     int  capacity() const                        { return size(); }                      \
duke@435:     void clear()                                 { truncate(0); }                        \
duke@435:     void trunc_to(const int length)              { truncate(length); }                   \
jrose@867:     int  append(const etype x)                   { return push(x); }                     \
duke@435:     void appendAll(const stack_name* stack)      { push_all(stack); }                    \
duke@435:     etype last() const                           { return top(); }                       \
duke@435:   };                                                                                     \
duke@435: 
duke@435: 
duke@435: #define define_resource_list(element_type)                                               \
duke@435:   define_generic_array(element_type##Array, element_type, ResourceArray)                 \
duke@435:   define_stack(element_type##List, element_type##Array)
duke@435: 
duke@435: #define define_resource_pointer_list(element_type)                                       \
duke@435:   define_generic_array(element_type##Array, element_type *, ResourceArray)               \
duke@435:   define_stack(element_type##List, element_type##Array)
duke@435: 
duke@435: #define define_c_heap_list(element_type)                                                 \
duke@435:   define_generic_array(element_type##Array, element_type, CHeapArray)                    \
duke@435:   define_stack(element_type##List, element_type##Array)
duke@435: 
duke@435: #define define_c_heap_pointer_list(element_type)                                         \
duke@435:   define_generic_array(element_type##Array, element_type *, CHeapArray)                  \
duke@435:   define_stack(element_type##List, element_type##Array)
duke@435: 
duke@435: 
duke@435: // Arrays for basic types
duke@435: 
duke@435: define_array(boolArray, bool)          define_stack(boolStack, boolArray)
duke@435: define_array(intArray , int )          define_stack(intStack , intArray )
stefank@2314: 
coleenp@4037: // Array for metadata allocation
coleenp@4037: 
coleenp@4037: template <typename T>
coleenp@4037: class Array: public MetaspaceObj {
coleenp@4037:   friend class MetadataFactory;
coleenp@4037:   friend class VMStructs;
coleenp@4037:   friend class MethodHandleCompiler;           // special case
coleenp@4037: protected:
coleenp@4037:   int _length;                                 // the number of array elements
coleenp@4037:   T   _data[1];                                // the array memory
coleenp@4037: 
coleenp@4037:   void initialize(int length) {
coleenp@4037:     _length = length;
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:  private:
coleenp@4037:   // Turn off copy constructor and assignment operator.
coleenp@4037:   Array(const Array<T>&);
coleenp@4037:   void operator=(const Array<T>&);
coleenp@4037: 
coleenp@5614:   void* operator new(size_t size, ClassLoaderData* loader_data, int length, bool read_only, TRAPS) throw() {
coleenp@4037:     size_t word_size = Array::size(length);
coleenp@4037:     return (void*) Metaspace::allocate(loader_data, word_size, read_only,
iklam@5208:                                        MetaspaceObj::array_type(sizeof(T)), CHECK_NULL);
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:   static size_t byte_sizeof(int length) { return sizeof(Array<T>) + MAX2(length - 1, 0) * sizeof(T); }
coleenp@4037: 
coleenp@4037:   explicit Array(int length) : _length(length) {
coleenp@4037:     assert(length >= 0, "illegal length");
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:   Array(int length, T init) : _length(length) {
coleenp@4037:     assert(length >= 0, "illegal length");
coleenp@4037:     for (int i = 0; i < length; i++) {
coleenp@4037:       _data[i] = init;
coleenp@4037:     }
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:  public:
coleenp@4037: 
coleenp@4037:   // standard operations
coleenp@4037:   int  length() const                 { return _length; }
coleenp@4037:   T* data()                           { return _data; }
coleenp@4037:   bool is_empty() const               { return length() == 0; }
coleenp@4037: 
coleenp@4037:   int index_of(const T& x) const {
coleenp@4037:     int i = length();
coleenp@4037:     while (i-- > 0 && _data[i] != x) ;
coleenp@4037: 
coleenp@4037:     return i;
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:   // sort the array.
coleenp@4037:   bool contains(const T& x) const      { return index_of(x) >= 0; }
coleenp@4037: 
minqi@4267:   T    at(int i) const                 { assert(i >= 0 && i< _length, err_msg_res("oob: 0 <= %d < %d", i, _length)); return _data[i]; }
minqi@4267:   void at_put(const int i, const T& x) { assert(i >= 0 && i< _length, err_msg_res("oob: 0 <= %d < %d", i, _length)); _data[i] = x; }
minqi@4267:   T*   adr_at(const int i)             { assert(i >= 0 && i< _length, err_msg_res("oob: 0 <= %d < %d", i, _length)); return &_data[i]; }
coleenp@4037:   int  find(const T& x)                { return index_of(x); }
coleenp@4037: 
coleenp@4037:   T at_acquire(const int which)              { return OrderAccess::load_acquire(adr_at(which)); }
coleenp@4037:   void release_at_put(int which, T contents) { OrderAccess::release_store(adr_at(which), contents); }
coleenp@4037: 
coleenp@4037:   static int size(int length) {
coleenp@4037:     return align_size_up(byte_sizeof(length), BytesPerWord) / BytesPerWord;
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:   int size() {
coleenp@4037:     return size(_length);
coleenp@4037:   }
coleenp@4037: 
coleenp@4037:   static int length_offset_in_bytes() { return (int) (offset_of(Array<T>, _length)); }
coleenp@4037:   // Note, this offset don't have to be wordSize aligned.
coleenp@4037:   static int base_offset_in_bytes() { return (int) (offset_of(Array<T>, _data)); };
coleenp@4037: 
coleenp@4037:   // FIXME: How to handle this?
coleenp@4037:   void print_value_on(outputStream* st) const {
coleenp@4037:     st->print("Array<T>(" INTPTR_FORMAT ")", this);
coleenp@4037:   }
coleenp@4037: 
coleenp@4037: #ifndef PRODUCT
coleenp@4037:   void print(outputStream* st) {
coleenp@4037:      for (int i = 0; i< _length; i++) {
coleenp@4037:        st->print_cr("%d: " INTPTR_FORMAT, i, (intptr_t)at(i));
coleenp@4037:      }
coleenp@4037:   }
coleenp@4037:   void print() { print(tty); }
coleenp@4037: #endif // PRODUCT
coleenp@4037: };
coleenp@4037: 
coleenp@4037: 
stefank@2314: #endif // SHARE_VM_UTILITIES_ARRAY_HPP