Array.hpp

/*******************************************************************************
 * Copyright (c) 2000, 2019 IBM Corp. and others
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at http://eclipse.org/legal/epl-2.0
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] http://openjdk.java.net/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0 WITH Classpath-exception-2.0 OR LicenseRef-GPL-2.0 WITH Assembly-exception
 *******************************************************************************/

#ifndef ARRAY_INCL
#define ARRAY_INCL

#include <limits.h>
#include <stdint.h>
#include <string.h>
#include "env/TRMemory.hpp"
#include "infra/Assert.hpp"

// TR_Array implements a dynamic array of objects
//
// The objects in the array must be assignable using memcpy
// (eg T must not be a class type with virtual functions)
//
// An object of type TR_Array<T> can be copy constructed and
// assigned.
//
template<class T> class TR_Array
   {
public:
   friend class TR_DebugExt;
   TR_ALLOC(TR_Memory::Array);


   TR_Array() : _nextIndex(0), _internalSize(0), _allocationKind(heapAlloc), _zeroInit(false), _trMemory(0), _trPersistentMemory(0), _array (NULL) { }

   TR_Array(TR_Memory * m, uint32_t initialSize = 8, bool zeroInit = true, TR_AllocationKind allocKind = heapAlloc)
     {
     init(m, m->trPersistentMemory(), initialSize, zeroInit, allocKind);
     }

   TR_Array(TR_Memory * m, TR_AllocationKind allocKind, uint32_t initialSize = 8, bool zeroInit = true)
     {
     init(m, m->trPersistentMemory(), initialSize, zeroInit, allocKind);
     }

   TR_Array(TR_PersistentMemory * pm, uint32_t initialSize = 8, bool zeroInit = true)
     {
     init(0, pm, initialSize, zeroInit, persistentAlloc);
     }

   void init(TR_Memory * m, uint32_t initialSize = 8, bool zeroInit = true, TR_AllocationKind allocKind = heapAlloc)
         {
         init(m, m->trPersistentMemory(), initialSize, zeroInit, allocKind);
         }

   void init(TR_Memory * m, TR_PersistentMemory * pm, uint32_t initialSize = 8, bool zeroInit = true, TR_AllocationKind allocKind = heapAlloc)
      {
      _nextIndex = 0;
      _internalSize = initialSize;
      _allocationKind = allocKind;
      _zeroInit = zeroInit;
      _trMemory = m;
      _trPersistentMemory = pm;
      if (m)
         _array = (T*)m->allocateMemory(initialSize * sizeof(T), _allocationKind, TR_MemoryBase::Array);
      else if (pm)
         _array = (T*)pm->allocatePersistentMemory(initialSize * sizeof(T));
      else
         TR_ASSERT(false, "Attempting to allocate an array without a memory object");
      if (zeroInit)
         memset(_array, 0, initialSize * sizeof(T));
      }

   TR_Array(const TR_Array<T>& other) { copy(other); }

   TR_Array<T>& operator=(const TR_Array<T>& other) { copy(other); return *this; }

   uint32_t size() const   { return _nextIndex; }
   uint32_t internalSize() { return _internalSize; }

   TR_Memory * trMemory() { return _trMemory; }
   TR_AllocationKind allocationKind() { return _allocationKind; }

   void setSize(uint32_t s)
      {
      if (s > _internalSize)
         growTo(s + _internalSize);
      else
         if (_nextIndex > s && _zeroInit) memset(_array + s, 0, (_nextIndex - s) * sizeof(T));
      _nextIndex = s;
      }

   int32_t lastIndex() { return size() - 1; }

   /**
    * @brief Copies the provided object into the first unused element at the end of the array and returns the index to the newly created element.  This may require growing the backing array.
    * @param t The object to be copied into the array.
    * @return The index of the newly created element.
    */
   uint32_t add(T t)
      {
      if (_nextIndex == _internalSize) { TR_ASSERT(_internalSize < UINT_MAX/2, "Array trying to grow bigger than UINT_MAX\n"); growTo(_internalSize*2); }
      _array[_nextIndex] = t;
      return _nextIndex++;
      }

   void insert(T t, uint32_t index)
      {
      if (_nextIndex <= index)
         add(t);
      else
         {
         if (_nextIndex == _internalSize) growTo(_internalSize*2);
         for (uint32_t i = _nextIndex; i > index; --i)
            _array[i] = _array[i-1];
         _array[index] = t;
         _nextIndex++;
         }
      }

   void append(const TR_Array<T>& other)
      {
      for (uint32_t i = 0; i < other._nextIndex; i++)
         add(other[i]);
      }


   void remove(uint32_t index)
      {
      TR_ASSERT(index < _nextIndex, "TR_Array::remove, index >= _nextIndex");
      for (uint32_t i = index+1; i < _nextIndex; ++i)
         _array[i-1] = _array[i];
      --_nextIndex;
      }

   // element can be used to return an existing element
   //
   T& element(uint32_t index)
      {
      TR_ASSERT(index < _nextIndex, "TR_Array::element, Invalid array index %d while size is %d", index, _nextIndex);
      return _array[index];
      }

   // operator[] can be used to return an existing element or to create
   // space for a new element
   //
   T& operator[](uint32_t index)
      {
      if (index >= _nextIndex)
         {
         if (index >= _internalSize)
            growTo(index + _internalSize);
         _nextIndex = index + 1;
         }

      return _array[index];
      }

   const T& operator[] (uint32_t index) const
      {
      TR_ASSERT(index < _nextIndex, "TR_Array::operator[] const, Invalid array index %d while size is %d", index, _nextIndex);
      return _array[index];
      }


   bool isEmpty() const { return _nextIndex == 0; }

   void clear()
      {
      if (_zeroInit)
         {
         memset(_array, 0, _internalSize * sizeof(T));
         }
      _nextIndex = 0;
      }

   bool contains(T t)
      {
      for (uint32_t i = 0; i < _nextIndex; ++i)
         {
         if (_array[i] == t)
            {
            return true;
            }
         }
      return false;
      }

   void free() { return freeMemory(); }
   void freeMemory()
      {
      if (_allocationKind == persistentAlloc)
         jitPersistentFree(_array);
      }

protected:

   void copy(const TR_Array<T>& other)
      {
      _nextIndex = other._nextIndex;
      _internalSize = other._internalSize;
      _allocationKind = other._allocationKind;
      _trMemory = other._trMemory;
      _trPersistentMemory = other._trPersistentMemory;
      _zeroInit = other._zeroInit;
      if (_trMemory)
         _array = (T*)_trMemory->allocateMemory(_internalSize * sizeof(T), _allocationKind, TR_MemoryBase::Array);
      else if (_trPersistentMemory)
         _array = (T*)_trPersistentMemory->allocatePersistentMemory(_internalSize * sizeof(T));
      uint32_t copySize = _zeroInit ? _internalSize : _nextIndex;
      memcpy(_array, other._array, copySize * sizeof(T));
      }

   void growTo(uint32_t size)
      {
      uint32_t prevSize = _nextIndex * sizeof(T);
      uint32_t newSize = size * sizeof(T);

      char * tmpArray;
      if (_trMemory)
         tmpArray = (char*)_trMemory->allocateMemory(newSize, _allocationKind, TR_MemoryBase::Array);
      else if (_trPersistentMemory)
         tmpArray = (char*)_trPersistentMemory->allocatePersistentMemory(newSize);
      else
         TR_ASSERT(false, "Cannot allocate memory for array with no TR_Memory or TR_PersistentMemory.");
      memcpy(tmpArray, _array, prevSize);
      if (_allocationKind == persistentAlloc) _trPersistentMemory->freePersistentMemory(_array);
      if (_zeroInit) memset(tmpArray + prevSize, 0, newSize - prevSize);

      _internalSize = size;
      _array = (T*)tmpArray;
      }

   T *                    _array;
   uint32_t               _nextIndex;
   uint32_t               _internalSize;
   TR_Memory *            _trMemory;
   TR_PersistentMemory*   _trPersistentMemory;
   bool                   _zeroInit;
   TR_AllocationKind      _allocationKind;
   };

template<class T> class TR_PersistentArray : public TR_Array<T>
   {
public:
   TR_ALLOC(TR_Memory::Array);
   TR_PersistentArray(TR_Memory * m,           uint32_t initialSize = 8, bool zeroInit = true) : TR_Array<T>(m, initialSize, zeroInit, persistentAlloc) { }
   TR_PersistentArray(TR_PersistentMemory * m, uint32_t initialSize = 8, bool zeroInit = true) : TR_Array<T>(m, initialSize, zeroInit) { }
   };

// Use to traverse non-null entries of a TR_Array<T *>
// Note the difference between the the template types for the iter, vs. the array
//
template <class T> class TR_ArrayIterator
   {
   private:
   uint32_t       _cursor;
   TR_Array<T *> *_array;

   public:
   TR_ALLOC(TR_Memory::Array)

   TR_ArrayIterator()                 : _array(0), _cursor(-1) {}
   TR_ArrayIterator(TR_Array<T *> *p) : _array(p), _cursor(-1) {}

   void set(TR_Array<T *> *p) { _array = p; _cursor = -1; }
   void reset() { _cursor = -1; }

   T *getFirst()   { _cursor = -1; return getNext(); }
   T *getNext()
         {
         T *elem = NULL;
         while (++_cursor < _array->size() &&
                (elem =_array->element(_cursor)) == NULL)
            ;
         return elem;
         }
   bool atEnd()   { return (_cursor >= _array->size()-1); }
   bool pastEnd() { return (_cursor >= _array->size()); }
   };

#endif