OdArray.h

Go to the documentation of this file.

// Copyright (C) 2002-2017, Open Design Alliance (the "Alliance"). 
// All rights reserved. 
// 
// This software and its documentation and related materials are owned by 
// the Alliance. The software may only be incorporated into application 
// programs owned by members of the Alliance, subject to a signed 
// Membership Agreement and Supplemental Software License Agreement with the
// Alliance. The structure and organization of this software are the valuable  
// trade secrets of the Alliance and its suppliers. The software is also 
// protected by copyright law and international treaty provisions. Application  
// programs incorporating this software must include the following statement 
// with their copyright notices:
//   
//   This application incorporates Teigha(R) software pursuant to a license 
//   agreement with Open Design Alliance.
//   Teigha(R) Copyright (C) 2002-2017 by Open Design Alliance. 
//   All rights reserved.
//
// By use of this software, its documentation or related materials, you 
// acknowledge and accept the above terms.
 
 
 
 
#ifndef ODARRAY_H_INCLUDED
#define ODARRAY_H_INCLUDED
 
#include <new>
 
#include "TD_PackPush.h"
 
#include "OdArrayPreDef.h"
#include "OdHeap.h"
#include "OdMutex.h"
#include "OdError.h"
#include "RxSystemServices.h"
 
template <class T> class OdMemoryAllocator
{
public:
  typedef unsigned int size_type;
  static inline void copy(
    T* pDestination, 
    const T* pSource, 
    size_type numElements)
  {
    memcpy(pDestination, pSource, numElements * sizeof(T));
  }
  
  static inline void move(
    T* pDestination, 
    const T* pSource, 
    size_type numElements)
  {
    memmove(pDestination, pSource, numElements * sizeof(T));
  }
  static inline void construct(
    T* pElement, 
    const T& value = T())
  {
    *pElement = value;
  }
 
  static inline void constructn(
    T* pDestination, 
    size_type numElements, 
    const T& value)
  {
    while(numElements--)
    {
      pDestination[numElements] = value;
    }
  }
  
  static inline void constructn(
    T* pDestination, 
    const T* pSource, 
    size_type numElements)
  {
    copy(pDestination, pSource, numElements);
  }
  
  //FELIX_CHANGE_BEGIN
  // merged from ODA GIT, CORE-15248
  static inline void constructn(
    T* pDestination, 
    size_type numElements)
  {
    memset(pDestination, 0, numElements * sizeof(T));
  }
  //FELIX_CHANGE_END
  static inline void destroy(
    T*)
  {
    // DOES NOTHING
  }
  static inline void destroy(
    T*, 
    size_type )
  {
    // DOES NOTHING
  }
  static inline bool useRealloc()
  {
    return true;
  }
};
 
 
template <class T> class OdObjectsAllocator
{
public:
  typedef unsigned int size_type;
  
  static inline void copy(
    T* pDestination, 
    const T* pSource, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      *pDestination = *pSource;
      pDestination++;
      pSource++;
    }
  }
 
  static inline void move(
    T* pDestination, 
    const T* pSource, 
    size_type numObjects)
  {
    if (pDestination <= pSource || pDestination >= pSource + numObjects)
    {
      copy(pDestination, pSource, numObjects);
    }
    else
    {
      while(numObjects--)
      {
        pDestination[numObjects] = pSource[numObjects];
      }
    }
  }
  static inline void construct(
    T* pObject)
  {
#ifdef new
#undef new
#endif
    ::new (pObject) T;
  }
  static inline void construct(
     T* pObject, 
     const T& value)
  {
#ifdef new
#undef new
#endif
    ::new (pObject) T(value);
  }
  static inline void constructn(
    T* pDestination, 
    size_type numObjects, 
    const T& value)
  {
    while(numObjects--)
    {
      construct(pDestination+numObjects, value);
    }
  }
  static inline void constructn(
    T* pDestination, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      construct(pDestination+numObjects);
    }
  }
  static inline void constructn(
    T* pDestination, 
    const T* pSource, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      construct(pDestination, *pSource);
      pDestination++;
      pSource++;
    }
  }
  static inline void destroy(
    T* pObject)
  {
    pObject->~T();
    pObject = 0;
  }
  static inline void destroy(
    T* objects, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      destroy(objects + numObjects);
    }
  }
  static inline bool useRealloc()
  {
    return false;
  }
};
template <class T> class OdPlainObjectsAllocator
{
public:
  typedef unsigned int size_type;
  
  static inline void copy(
    T* pDestination, 
    const T* pSource, 
    size_type numObjects)
  {
    memcpy(pDestination, pSource, numObjects * sizeof(T));
  }
  
  static inline void move(
    T* pDestination, 
    const T* pSource, 
    size_type numObjects)
  {
    memmove(pDestination, pSource, numObjects * sizeof(T));
  }
  
  static inline void construct(
    T* pObject)
  {
#ifdef new
#undef new
#endif
    ::new (pObject) T;
  }
  static inline void construct(
    T* pObject, 
    const T& value)
  {
#ifdef new
#undef new
#endif
    ::new (pObject) T(value);
  }
  
  static inline void constructn(
    T* pDestination, 
    size_type numObjects, 
    const T& value)
  {
    while(numObjects--)
    {
      construct(pDestination+numObjects, value);
    }
  }
  static inline void constructn(
    T* pDestination, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      construct(pDestination+numObjects);
    }
  }
  static inline void constructn(
    T* pDestination, 
    const T* pSource, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      construct(pDestination, *pSource);
      pDestination++;
      pSource++;
    }
  }
  
  static inline void destroy(
    T* pObject)
  {
    pObject->~T();
    pObject = 0;
  }
  static inline void destroy(
    T* objects, 
    size_type numObjects)
  {
    while(numObjects--)
    {
      destroy(objects + numObjects);
    }
  }
  static inline bool useRealloc()
  {
    return true;
  }
};
 
struct FIRSTDLL_EXPORT OdArrayBuffer
{
  typedef unsigned int size_type;
 
  mutable OdRefCounter m_nRefCounter;
  int               m_nGrowBy;
  size_type         m_nAllocated;
  size_type         m_nLength;
 
  FIRSTDLL_EXPORT_STATIC static OdArrayBuffer g_empty_array_buffer;
};
 
 
 
template <class T, class A> class OdArray
{
public:
  typedef typename A::size_type size_type;
  typedef T* iterator;
  typedef const T* const_iterator;
  typedef T value_type;
  typedef const T& const_reference;
  typedef T& reference;
private:
  struct Buffer : OdArrayBuffer
  {
    T* data() const { return (T*)(this+1); }
 
    static Buffer* allocate(size_type nLength2Allocate, int nGrowBy)
    {
      size_type nBytes2Allocate = sizeof(Buffer) + nLength2Allocate * sizeof(T);
      ODA_ASSERT(nBytes2Allocate > nLength2Allocate); // size_type overflow
      if(nBytes2Allocate > nLength2Allocate)
      {
        Buffer* pBuffer = (Buffer*)::odrxAlloc(nBytes2Allocate);
        if (pBuffer)
        {
          pBuffer->m_nRefCounter = 1;
          pBuffer->m_nGrowBy     = nGrowBy;
          pBuffer->m_nAllocated  = nLength2Allocate;
          pBuffer->m_nLength     = 0;
          return pBuffer;
        }
      }
      throw OdError(eOutOfMemory);
    }
    static Buffer* _default()
    {
      return (Buffer*)&g_empty_array_buffer;
    }
    void release()
    {
      ODA_ASSERT(m_nRefCounter);
      if((--m_nRefCounter)==0 && this != _default())
      {
        A::destroy(data(), m_nLength);
        ::odrxFree(this);
      }
    }
    void addref() const { ++m_nRefCounter; }
  };
  class reallocator
  {
    bool _may_use_realloc;
    Buffer* m_pBuffer;
  public:
    inline reallocator( bool may_use_realloc = false ) : _may_use_realloc(may_use_realloc), m_pBuffer(NULL)
    {
      if ( !_may_use_realloc )
      {
        m_pBuffer = Buffer::_default();
        m_pBuffer->addref(); 
      }
    }
    inline void reallocate(OdArray* pArray, size_type nNewLen )
    {
      if(!pArray->referenced())
      {
        if(nNewLen > pArray->physicalLength())
        {
          if ( !_may_use_realloc )
          {
            m_pBuffer->release();
            m_pBuffer = pArray->buffer();
            m_pBuffer->addref(); // save buffer to ensure copy from itself would work (e.g insertAt)
          }
          pArray->copy_buffer(nNewLen, _may_use_realloc);
        }
      }
      else
      {
        pArray->copy_buffer(nNewLen);
      }
    }
    inline ~reallocator() 
    {
      if ( !_may_use_realloc ) m_pBuffer->release();
    }
  };
  friend class reallocator;
  const_iterator begin_const() const { return begin(); }
  iterator begin_non_const() { return begin(); }
  const_iterator end_const() { return end(); }
  iterator end_non_const() { return end(); }
  void copy_before_write(size_type len, bool may_use_realloc = false )
  {
    if( referenced() )
      copy_buffer(len);
    else if ( len > physicalLength() )
      copy_buffer( len, may_use_realloc );
  }
  void copy_if_referenced() { if(referenced()) { copy_buffer(physicalLength()); } }
  void copy_buffer( size_type len, bool may_use_realloc = false, bool force_size = false )
  {
    Buffer* pOldBuffer = buffer();
    int nGrowBy = pOldBuffer->m_nGrowBy;
    size_type len2 = len;
    if ( !force_size )
    {
      if(nGrowBy > 0)
      {
        len2 += nGrowBy;
        len2 = ((len2 - 1) / nGrowBy) * nGrowBy;
      }
      else
      {
        len2 = pOldBuffer->m_nLength;
        len2 = len2 + -nGrowBy * len2 / 100;
        if(len2 < len)
        {
          len2 = len;
        }
      }
    }
    if ( may_use_realloc && A::useRealloc() && !empty() )
    {
      Buffer* pNewBuffer = reinterpret_cast<Buffer*>( ::odrxRealloc( 
        pOldBuffer, len2 * sizeof(T) + sizeof(Buffer), pOldBuffer->m_nAllocated * sizeof(T) + sizeof(Buffer) ) );
      if (!pNewBuffer)
        throw OdError(eOutOfMemory);
      pNewBuffer->m_nAllocated = len2;
      pNewBuffer->m_nLength = odmin(pNewBuffer->m_nLength, len);
      m_pData = pNewBuffer->data();
    }
    else 
    {
      Buffer* pNewBuffer = Buffer::allocate(len2, nGrowBy);
      if (!pNewBuffer)
        throw OdError(eOutOfMemory);
      len = odmin(pOldBuffer->m_nLength, len);
      A::constructn(pNewBuffer->data(), pOldBuffer->data(), len);
      pNewBuffer->m_nLength = len;
      m_pData = pNewBuffer->data();
      pOldBuffer->release();
    }
  }
  inline void assertValid(size_type index) const
  { 
    if(!isValid(index)) 
    { 
      ODA_FAIL(); 
      throw OdError_InvalidIndex(); 
    } 
  }
  static inline void rise_error(OdResult e) 
  { 
    ODA_FAIL(); 
    throw OdError(e); 
  }
public:
  // STL-like interface
  
  iterator begin() 
  { 
    if(!empty()) 
    { 
      copy_if_referenced(); 
      return data(); 
    } 
    return 0;
  }
  const_iterator begin() const 
  { 
    if(!empty()) 
    { 
      return data(); 
    } 
    return 0; 
  }
 
  iterator end() 
  { 
    if(!empty()) 
    { 
      copy_if_referenced(); 
      return data() + length(); 
    } 
    return 0; 
  }
  const_iterator end() const 
  { 
    if(!empty()) 
    { 
      return data() + length(); 
    } 
    return 0; 
  }
  
  void insert(
    iterator before, 
    const_iterator first, 
    const_iterator afterLast)
  {
    size_type len = length();
    size_type index = (size_type)(before - begin_const());
    if(index <= len && afterLast>=first)
    {
      if(afterLast > first)
      {
        size_type num2copy = (size_type)(afterLast - first);
        reallocator r( first < begin() || first >= end() );
        r.reallocate(this, len + num2copy);
        A::constructn(m_pData + len, first, num2copy);
        buffer()->m_nLength = len + num2copy;
        T* pDestination = m_pData + index;
        if(index != len)
        {
          A::move(pDestination + num2copy, pDestination, len - index);
        }
        A::copy(pDestination, first, (size_type)(afterLast - first));
      }
    }
    else
    {
      rise_error(eInvalidInput);
    }
  }
  void resize( 
    size_type logicalLength, 
    const T& value )
  {
    size_type len = length();
    int d = logicalLength - len;
    if ( d > 0 )
    {
      reallocator r( m_pData > &value || &value > (m_pData + len) );
      r.reallocate(this, logicalLength);
      A::constructn(m_pData + len, d, value);
    }
    else if ( d < 0 )
    {
      d=-d;
      if(!referenced())
      {
        A::destroy(m_pData + logicalLength, d);
      }
      else
      {
        copy_buffer(logicalLength);
      }
    }
    buffer()->m_nLength = logicalLength;
  }
  
  void resize( 
    size_type logicalLength )
  {
    size_type len = length();
    int d = logicalLength - len;
    if ( d > 0 )
    {
      copy_before_write( len + d, true );
      A::constructn(m_pData + len, d);
    }
    else if ( d < 0 )
    {
      d = -d;
      if ( !referenced() )
      {
        A::destroy( m_pData + logicalLength, d );
      }
      else
      {
        copy_buffer(logicalLength);
      }
    }
    buffer()->m_nLength = logicalLength;
  }
  
  size_type size() const 
  { 
    return buffer()->m_nLength; 
  }
 
  bool empty() const 
  { 
    return size() == 0; 
  }
  
  size_type capacity() const 
  { 
    return buffer()->m_nAllocated; 
  }
 
  void reserve(
    size_type reserveLength) 
  { 
    if(physicalLength() < reserveLength) 
    { 
      setPhysicalLength(reserveLength); 
    } 
  }
 
  void assign(
    const_iterator first, 
    const_iterator afterLast)
  { 
    erase(begin_non_const(), end_non_const()); 
    insert(begin_non_const(), first, afterLast); 
  }
  
  iterator erase(
    iterator first, 
    iterator afterLast)
  {
    size_type i = (size_type)(first - begin_const());
    if(first != afterLast)
    {
      removeSubArray(i, (size_type)(afterLast-begin_const()-1));
    }
    return begin_non_const()+i;
  }
  iterator erase(
    iterator where)
  {
    size_type i = (size_type) (where - begin_const());
    removeAt(i);
    return begin_non_const()+i;
  }
  void clear()
  { 
    erase(begin_non_const(), end_non_const()); 
  }
 
  void push_back(
    const T& value) 
  { 
    insertAt(length(), value); 
  }
  
  iterator insert(
    iterator before, 
    size_type numElements, 
    const T& value)
  {
    size_type len = length();
    size_type index = (size_type)(before - begin_const());
    reallocator r( m_pData > &value || &value > (m_pData + len) );
    r.reallocate(this, len + numElements);
    A::constructn(m_pData + len, numElements, value);
    buffer()->m_nLength = len + numElements;
    T* pData = data();
    pData += index;
    if(index != len)
    {
      A::move(pData + numElements, pData, len - index);
    }
    while(numElements--)
    {
      pData[numElements] = value;
    }
    return begin_non_const()+index;
  }
  iterator insert(
    iterator before, 
    const T& value = T())
  {
    size_type index = (size_type)(before - begin_const());
    insertAt(index, value);
    return (begin_non_const() + index);
  }  
 
  bool contains(
    const T& value, 
    size_type start = 0) const
  { 
    size_type dummy; 
    return find(value, dummy, start); 
  }
 
  size_type length() const 
  { 
    return buffer()->m_nLength; 
  }
  
  bool isEmpty() const 
  { 
    return length() == 0; 
  }
  
  size_type logicalLength() const 
  { 
    return length(); 
  }
  
  size_type physicalLength() const 
  { 
    return buffer()->m_nAllocated; 
  }
  
  int growLength() const 
  { 
    return buffer()->m_nGrowBy; 
  }
  
  const T* asArrayPtr() const 
  { 
    return data(); 
  }
 
  const T* getPtr() const 
  { 
    return data(); 
  }
  
  T* asArrayPtr() 
  { 
    copy_if_referenced(); 
    return data(); 
  }
  
  const T& operator [](
    size_type index) const 
  { 
    assertValid(index); 
    return m_pData[index]; 
  }
  T& operator [](
    size_type index) 
  { 
    assertValid(index); 
    copy_if_referenced(); 
    return m_pData[index]; 
  }
 
  T& at(size_type arrayIndex) 
  { 
    assertValid(arrayIndex); 
    copy_if_referenced(); 
    return *(data() + arrayIndex); 
  }
  
  const T& at(size_type arrayIndex) const 
  { 
    assertValid(arrayIndex); 
    return *(data() + arrayIndex); 
  }
  
  OdArray& setAt(
    size_type arrayIndex, 
    const T& value)
  { 
    assertValid(arrayIndex); 
    copy_if_referenced(); 
    m_pData[arrayIndex] = value; 
    return *this; 
  }
 
  const T& getAt(
    size_type arrayIndex) const 
  { 
    assertValid(arrayIndex); 
    return *(data() + arrayIndex); 
  }
  
  T& first() 
  { 
    return *begin(); 
  }
  const T& first() const 
  { 
    return *begin(); 
  }
  
  T& last() 
  { 
    return at(length() - 1); 
  }
  const T& last() const 
  { 
    return at(length() - 1); 
  }
  
  size_type append(
    const T& value) 
  { 
    insertAt(length(), value); 
    return length() - 1; 
  }
  
  iterator append() 
  { 
    size_type i = append(T()); 
    return begin_non_const() + i;
  }
  
  OdArray& removeFirst() 
  { 
    return removeAt(0); 
  }
  
  OdArray& removeLast() 
  { 
    return removeAt(length() - 1); 
  }
  
  OdArray& setGrowLength(
    int growLength)
  {
    if (growLength != 0)
    {
      copy_if_referenced();
      buffer()->m_nGrowBy = growLength;
    }
    else
    {
      ODA_FAIL();
    }
    return *this;
  }
 
  explicit OdArray(
    size_type physicalLength, 
    int growLength = 8) : m_pData(0)
  {
    if (growLength == 0)
    {
      growLength = 8;
    }
    m_pData = Buffer::allocate(physicalLength, growLength)->data();
  }
  
  OdArray() : m_pData(Buffer::_default()->data()) 
  { 
    buffer()->addref(); 
  }
  
  OdArray(const OdArray& source) : m_pData((T*)source.data()) 
  { 
    buffer()->addref(); 
  }
  
  ~OdArray() 
  { 
    buffer()->release(); 
  }
  
  OdArray& operator =(
    const OdArray& source)
  {
    source.buffer()->addref();
    buffer()->release();
    m_pData = source.m_pData;
    return *this;
  }
  
  bool operator ==(
    const OdArray& array) const
  {
    if(length() == array.length())
    {
      for(size_type i = 0; i < length(); i++)
      {
        if(at(i) != array[i])
        {
          return false;
        }
      }
      return true;
    }
    return false;
  }
  
  OdArray& setAll(
    const T& value)
  {
    copy_if_referenced();
    T* pData = data();
    size_type n = length();
    while(n)
    {
      pData[--n] = value;
    }
    return *this;
  }
  OdArray& append(
    const OdArray& otherArray)
  {
    insert(end_non_const(), otherArray.begin(), otherArray.end());
    return *this;
  }
  
  OdArray& insertAt(
    size_type arrayIndex, 
    const T& value)
  {
    size_type len = length();
    if( arrayIndex == len )
    {
      resize( len + 1, value );
    }
    else if ( arrayIndex < len )
    {
      reallocator r( m_pData > &value || &value > (m_pData + len) );
      r.reallocate( this, len+1 );
      A::construct( m_pData + len );
      ++(buffer()->m_nLength);
      A::move(m_pData + arrayIndex + 1, m_pData + arrayIndex, len - arrayIndex);
      m_pData[arrayIndex] = value;
    }
    else
    {
      rise_error(eInvalidIndex);
    }
    return *this;
  }
  
  OdArray& removeAt(
    size_type arrayIndex)
  {
    assertValid(arrayIndex);
    size_type len = length();
    if(arrayIndex < --len)
    {
      copy_if_referenced();
      T* pData = data();
      A::move(pData + arrayIndex, pData + arrayIndex + 1, len - arrayIndex);
    }
    resize(len);
    return *this;
  }
  
  OdArray& removeSubArray(
    size_type startIndex, 
    size_type endIndex)
  {
    if(!isValid(startIndex) || startIndex > endIndex)
    {
      rise_error(eInvalidIndex);
    }
    size_type len = length();
    copy_if_referenced();
    T* pData = data();
    ++endIndex;
    size_type n2remove = endIndex - startIndex;
    A::move(pData + startIndex, pData + endIndex, len - endIndex);
    A::destroy(pData + len - n2remove, n2remove);
    buffer()->m_nLength -= n2remove;
    return *this;
  }
  
  bool find(
    const T& value, 
    size_type& findIndex, 
    size_type start=0) const
  {
    if(!empty())
    {
      assertValid(start);
      size_type len = length();
      const T* pData = data();
      for(size_type i = start; i<len; ++i)
      {
        if(pData[i] == value)
        {
          findIndex = i;
          return true;
        }
      }
    }
    return false;
  }
  
  OdArray& setLogicalLength(
    size_type logLength)
  {
    resize(logLength);
    return *this;
  }
  
  OdArray& setPhysicalLength(
    size_type physLength)
  {
    if(physLength==0)
    {
      *this = OdArray<T, A>();
    }
    else if(physLength != physicalLength())
    {
      copy_buffer(physLength, !referenced(), true);
    }
    return *this;
  }
  
  OdArray& reverse()
  {
    if(!empty())
    {
      copy_if_referenced();
      T tmp;
      iterator iter1 = begin_non_const();
      iterator iter2 = end_non_const();
      --iter2;
      while(iter1 < iter2)
      {
        tmp = *iter1;
        *iter1 = *iter2;
        *iter2 = tmp;
        ++iter1;
        --iter2;
      }
    }
    return *this;
  }
    
  OdArray& swap(
    size_type firstIndex, 
    size_type secondIndex)
  {
    if(!isValid(firstIndex) || !isValid(secondIndex))
    {
      rise_error(eInvalidIndex);
    }    
    if(firstIndex != secondIndex)
    {
      const T tmp = at(firstIndex);
      at(firstIndex) = at(secondIndex);
      at(secondIndex) = tmp;
    }
    return *this;
  }
  bool remove(
    const T& value, 
    size_type start = 0)
  {
    size_type i = 0;
    if(find(value, i, start))
    {
      removeAt(i);
      return true;
    }
    return false;
  }
private:
 
  T*    m_pData;
 
  bool isValid(size_type i) const 
  { 
    return (i < length());
  }
 
  T* data() 
  { 
    return (length() ? m_pData : 0); 
  }
 
  const T* data() const 
  { 
    return m_pData; 
  }
 
  Buffer* buffer() const
  {
    return (reinterpret_cast<Buffer*>(const_cast<OdArray*>(this)->m_pData) - 1);
  }
  bool referenced() const
  {
    return (buffer()->m_nRefCounter>1);
  }
};
 
template <class T, class A>
bool operator !=(
    const OdArray<T,A>& a,
    const OdArray<T, A>& b)
{
    return !( a.operator == (b) );
}
 
#include "TD_PackPop.h"
 
#endif // ODARRAY_H_INCLUDED