path: root/src/inc/clr_std/vector

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

//
// clr_std/vector
//
// Copy of some key Standard Template Library functionality
//

#ifdef _MSC_VER
#pragma once
#endif

#ifdef USE_STL
#include <vector>
#else
#ifndef __clr_std_vector_h__
#define __clr_std_vector_h__

// This is defined in the debugmacrosext.h header, but don't take a dependency on that.
#ifndef INDEBUG
#ifdef _DEBUG
#define INDEBUG(x)          x
#else
#define INDEBUG(x)
#endif
#endif // !def INDEBUG

namespace std
{
    template <class T>
    class vector
    {
        public:
            class const_iterator;

            class iterator
            {
                friend class std::vector<T>::const_iterator;
            public:
                typedef T         value_type;
                typedef ptrdiff_t difference_type;
                typedef T*        pointer;
                typedef T&        reference;
                
                typedef class vector<T>::iterator _MyIter;
                
                _MyIter &operator++()
                {
                    m_ptr++;
                    return *this;
                }

                _MyIter operator++(int)
                {
                    // post-increment ++
                    _MyIter myiter(m_ptr);
                    m_ptr++;
                    return myiter;
                }

                _MyIter &operator--()
                {
                    m_ptr--;
                    return *this;
                }

                _MyIter operator--(int)
                {
                    // post-decrement --
                    _MyIter myiter(m_ptr);
                    m_ptr--;
                    return myiter;
                }

                _MyIter operator- (ptrdiff_t n)
                {
                    _MyIter myiter(m_ptr);
                    myiter.m_ptr -= n;
                    return myiter;
                }

                ptrdiff_t operator- (_MyIter right)
                {
                    _MyIter myiter(m_ptr);
                    return myiter.m_ptr - right.m_ptr;
                }

                _MyIter operator+ (ptrdiff_t n)
                {
                    _MyIter myiter(m_ptr);
                    myiter.m_ptr += n;
                    return myiter;
                }

                T* operator->() const
                {
                    return m_ptr;
                }

                T & operator*() const
                {
                    return *m_ptr;
                }

                bool operator==(const _MyIter& _Right) const
                {
                    bool equals = this->m_ptr == _Right.m_ptr;
                    return equals;
                }

                bool operator!=(const _MyIter& _Right) const
                {
                    bool equals = this->m_ptr == _Right.m_ptr;
                    return !equals;
                }

                bool operator<(const _MyIter& _Right) const
                {
                    return this->m_ptr < _Right.m_ptr;
                }

                bool operator>(const _MyIter& _Right) const
                {
                    return this->m_ptr > _Right.m_ptr;
                }
            public:
                explicit iterator(T* ptr)
                {
                    m_ptr = ptr;
                }

                private:
                    T* m_ptr;
            }; // class iterator

            class const_iterator
            {
            public:
                typedef class vector<T>::const_iterator _MyIter;
                typedef class vector<T>::iterator _MyNonConstIter;
                
                _MyIter &operator++()
                {
                    m_ptr++;
                    return *this;
                }

                _MyIter operator++(int)
                {
                    // post-increment ++
                    _MyIter myiter(m_ptr);
                    m_ptr++;
                    return myiter;
                }

                const T* operator->() const
                {
                    return m_ptr;
                }

                const T & operator*() const
                {
                    return *m_ptr;
                }

                bool operator==(const _MyIter& _Right) const
                {
                    bool equals = this->m_ptr == _Right.m_ptr;
                    return equals;
                }

                bool operator!=(const _MyIter& _Right) const
                {
                    bool equals = this->m_ptr == _Right.m_ptr;
                    return !equals;
                }

            public:
                explicit const_iterator(T* ptr)
                {
                    m_ptr = ptr;
                }
                const_iterator(const _MyNonConstIter &nonConstIterator)
                {
                    m_ptr = nonConstIterator.m_ptr;
                }

            private:
                T* m_ptr;
            }; // class const iterator


        public:
            explicit vector(size_t n = 0)
            {
                m_size = 0;
                m_capacity = 0;
                m_pelements = NULL;
                m_isBufferOwner = true;
                resize(n);
            }

            ~vector()
            {
                if (m_isBufferOwner)
                {
                    erase(m_pelements, 0, m_size);
                    delete [] (BYTE*)m_pelements; // cast to BYTE* as we don't want this delete to invoke T's dtor
                }
                else
                {
                    m_size = 0;
                    m_capacity = 0;
                }
            }


            size_t size() const
            {
                return m_size;
            }

            T & operator[](size_t iIndex)
            {
                assert(iIndex < m_size);
                return m_pelements[iIndex];
            }

            T & operator[](size_t iIndex) const
            {
                assert(iIndex < m_size);
                return m_pelements[iIndex];
            }

            void resize(size_t newsize)
            {
                assert(m_isBufferOwner);
                size_t oldsize = this->size();
                resize_noinit(newsize);
                if (newsize > oldsize)
                {
                    fill_uninitialized_with_default_value(m_pelements, oldsize, newsize);
                }
            }

            void clear()
            {
                assert(m_isBufferOwner);
                resize(0);
            }

            void resize(size_t newsize, T c)
            {
                assert(m_isBufferOwner);
                size_t oldsize = this->size();
                resize_noinit(newsize);
                if (newsize > oldsize)
                {
                    for (size_t i = oldsize; i < newsize; i++)
                    {
                        m_pelements[i] = c;
                    }
                }
            }

            void wrap(size_t numElements, T* pElements)
            {
                m_size = numElements;
                m_pelements = pElements;
                m_isBufferOwner = false;
            }

            void resize_noinit(size_t newsize)
            {
                assert(m_isBufferOwner);
                size_t oldsize = this->size();
                if (newsize < oldsize)
                {
                    // Shrink
                    erase(m_pelements, newsize, oldsize);
                }
                else if (newsize > oldsize)
                {
                    // Grow
                    reserve(newsize);
                }
                m_size = newsize;
            }

            void push_back(const T & val)
            {
                assert(m_isBufferOwner);
                if (m_size + 1 < m_size)
                {
                    assert("push_back: overflow");
                    // @todo: how to throw.
                }
                resize(m_size + 1, val);
            }

            void reserve(size_t newcapacity)
            {
                assert(m_isBufferOwner);
                if (newcapacity > m_capacity)
                {
                    // To avoid resizing for every element that gets added to a vector, we
                    // allocate at least twice the old capacity, or 16 elements, whichever is greater.
                    newcapacity = max(newcapacity, max(m_capacity * 2, 16));

                    size_t bytesNeeded = newcapacity * sizeof(T);
                    if (bytesNeeded / sizeof(T) != newcapacity)
                    {
                        assert("resize: overflow");
                        // @todo: how to throw something here?
                    }


                    T *pelements = (T*)(new BYTE[bytesNeeded]);  // Allocate as BYTE array to avoid automatic construction
                    INDEBUG(memset(pelements, 0xcc, bytesNeeded));
                    for (size_t i = 0; i < m_size; i++)
                    {
                        pelements[i] = m_pelements[i];
                    }

                    erase(m_pelements, 0, m_size);
                    delete [] (BYTE*)m_pelements; // cast to BYTE* as we don't want this delete to invoke T's dtor

                    m_pelements = pelements;
                    m_capacity = newcapacity;
                }
            }

            iterator begin()
            {
                return iterator(m_pelements);
            }

            iterator end()
            {
                return iterator(m_pelements + m_size);
            }

            const_iterator cbegin() const
            {
                return const_iterator(m_pelements);
            }

            const_iterator cend() const
            {
                return const_iterator(m_pelements + m_size);
            }

            iterator erase(iterator position)
            {
                assert(m_isBufferOwner);
                assert((position > begin() || position == begin()) && position < end());
                ptrdiff_t index = position - begin();
                erase(m_pelements, index, index + 1);
                memcpy(&m_pelements[index], &m_pelements[index + 1], sizeof(T) * (m_size - index - 1));
                --m_size;
                return iterator(m_pelements + (position - begin()));
            }

            iterator erase(iterator position, iterator positionEnd)
            {
                assert(m_isBufferOwner);
                assert((position > begin() || position == begin()) && position < end());
                ptrdiff_t index = position - begin();
                ptrdiff_t elements = positionEnd - position;
                erase(m_pelements, index, index + elements);
                memcpy(&m_pelements[index], &m_pelements[index + elements], sizeof(T) * (m_size - index - elements));
                m_size -= elements;
                return iterator(m_pelements + (position - begin()));
            }

            const T* data() const
            {
                return m_pelements;
            }

         private:
            // Transition a subset of the array from uninitialized to initialized with default value for T.
            static void fill_uninitialized_with_default_value(T* pelements, size_t startIdx, size_t endIdx)
            {
                assert(startIdx <= endIdx);
                assert(pelements != NULL || startIdx == endIdx);
                for (size_t i = startIdx; i < endIdx; i++)
                {
                    INDEBUG(assert(0xcc == *((BYTE*)&pelements[i])));
                    pelements[i] = T();
                }
            }

            // Transition a subset of the array from a valid value of T to uninitialized.
            static void erase(T* pelements, size_t startIdx, size_t endIdx)
            {
                assert(startIdx <= endIdx);
                assert(pelements != NULL || startIdx == endIdx);
                for (size_t i = startIdx; i < endIdx; i++)
                {
                    pelements[i].~T();
                }

                INDEBUG(memset(&pelements[startIdx], 0xcc, (endIdx - startIdx) * sizeof(T)));
            }

         private:
            size_t    m_size;       //# of elements
            size_t    m_capacity;   //# of elements allocated 
            T        *m_pelements;  //actual array
                                    //  invariants:
                                    //    dimensions == m_capacity
                                    //    elements 0 thru m_size-1 always contain constructed T values.
                                    //    elements from m_size thru m_capacity - 1 contain memory garbage (0xcc in DEBUG).
            bool    m_isBufferOwner; // indicate if this vector creates its own buffer, or wraps an existing buffer.




    };  // class vector

}; // namespace std
 
#endif /* __clr_std_vector_h__ */

#endif // !USE_STL

// Help the VIM editor figure out what kind of file this no-extension file is.
// vim: filetype=cpp