/****************************************************************************
**
** Copyright (C) 2008-2010 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation (developer.feedback@nokia.com)
**
** This file is part of the HbCore module of the UI Extensions for Mobile.
**
** GNU Lesser General Public License Usage
** This file may be used under the terms of the GNU Lesser General Public
** License version 2.1 as published by the Free Software Foundation and
** appearing in the file LICENSE.LGPL included in the packaging of this file.
** Please review the following information to ensure the GNU Lesser General
** Public License version 2.1 requirements will be met:
** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** In addition, as a special exception, Nokia gives you certain additional
** rights.  These rights are described in the Nokia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** If you have questions regarding the use of this file, please contact
** Nokia at developer.feedback@nokia.com.
**
****************************************************************************/

#ifndef HBVECTOR_P_H
#define HBVECTOR_P_H

#include <new>

#include <QAtomicInt>

#include "hbsmartoffset_p.h"
#include "hbsmartpointer_p.h"
#include "hbmemoryutils_p.h"

/**
* const iterator class of HbVector
*/
template <typename T, typename Pointer>
class  const_vector_iterator
{
public:
    typedef const T value_type;
    typedef value_type & reference;
    typedef int difference_type;

public :
    Pointer ptr() const { return mPtr; }
    const_vector_iterator()
        : mPtr(0)
    {}

    explicit const_vector_iterator(Pointer ptr)
        : mPtr(ptr)
    {}

    reference operator*() const
    { return *mPtr; }

    const value_type * operator->() const
    { return mPtr.get(); }

    reference operator[](difference_type offset) const
    { return mPtr[offset]; }

    const_vector_iterator & operator++()
    { ++mPtr;  return *this; }

    const_vector_iterator operator++(int)
    {
        Pointer tmp = mPtr;
        ++*this;
        return const_vector_iterator(tmp);
    }

    const_vector_iterator operator+ (int offset) const
    {  return const_vector_iterator(mPtr + offset); }

     int operator- (const_vector_iterator &other) const
    { return mPtr - other.mPtr; }

     const_vector_iterator & operator-- ()
    { --mPtr; return *this; }

    const_vector_iterator & operator--(int)
    { Pointer temp = mPtr; --*this; return const_vector_iterator(temp); }

    bool operator!= (const const_vector_iterator &other) const
    { return mPtr != other.mPtr;  }

    int operator- (Pointer right) const
    { return mPtr - right; }

    bool operator< (const_vector_iterator & other)  const
    { return mPtr < other.mPtr;  }

    bool operator<= (const_vector_iterator & other)  const
    {  return mPtr <= other.mPtr;  }

    bool operator> (const_vector_iterator & other)  const
    {  return mPtr > other.mPtr;  }

    bool operator>= (const_vector_iterator & other)  const
   {  return mPtr >= other.mPtr;  }

    bool operator== (const_vector_iterator &right) const
    { return mPtr == right.mPtr; }

protected :
    Pointer mPtr;
};

/**
* iterator class of HbVector
*/
template <typename T, typename Pointer>
class  vector_iterator
    : public const_vector_iterator<T, Pointer>
{
public:
    typedef T           value_type;
    typedef value_type &         reference;
    typedef int                         difference_type;
public:

    vector_iterator()
    {}

    explicit vector_iterator(Pointer ptr)
      : const_vector_iterator<T,Pointer>(ptr)
    {}

    reference operator*() const
    { return *this->mPtr;}

    value_type * operator->() const
    { return this->mPtr.get(); }

    reference operator[](difference_type offset) const
    { return this->mPtr[offset]; }

    //Increment / Decrement
    vector_iterator & operator++()  
    {
        ++this->mPtr;
        return *this;
    }

    vector_iterator operator++(int)
    {  
        Pointer tmp = this->mPtr;
        ++*this;
        return vector_iterator(tmp);
    }

    vector_iterator & operator--()
    { 
        --this->mPtr;
        return *this;
    }

    vector_iterator operator--(int)
    {
        vector_iterator temp = *this;
        --*this;
        return vector_iterator(temp);
    }

    vector_iterator operator+(difference_type offset) const
    {  return vector_iterator(this->mPtr+offset); }

    vector_iterator operator-(difference_type offset) const
   {  return vector_iterator(this->mPtr-offset); }

    difference_type operator-(const_vector_iterator<T,Pointer>& right) const
    {  return static_cast<const const_vector_iterator<T,Pointer>&>(*this) - right; }
};

/**
* HbVector class
* HbVector is templatized vector which can store its internal data either in shared memory or heap.
* The class was written specially for sharing the output of CSS parser for subsequent lookup usage
* across processes, to reduce the overall memory usage and to improve performance.
*
* In case of out of memory situation, the vector is restored to the state it was before the exception occurred. 
* 
* The class uses smart pointers (smart_ptr<T> class objects) which internally contains offsets from
* a certain base address (which can either be shared memory or heap) instead of directly containing
* the virtual addresses. This way, the smart pointers are usable across processes, as the base 
* virtual addresses of the specific shared memory chunk may be different in different processes.
* 
* For iterating through the HbVector, special iterator classes are also provided (const_vector_iterator
* and vector_iterator)
* Important Note: By default implicit sharing happens. For the scenarios when source vector is in 
* shared memory and destination vector is in heap (or does not have write access to shared memory),
* implicit sharing is done by keeping a pointer to the shared internal data of source container inside 
* destination container. Here we assume that source container will not destroy its data as long as
* destination container is using it. (We can assume it safely for css sharing usecase when we do not
* remove stylesheet from shared memory as long as it is being used by client processes).
* 
* However, in normal scenario (places where you don't need sharing stuff), it's recommended to still
* use normal QVector.
*/

template <typename T>
class  HbVector
{
    friend class TestHbVector;
public :
    typedef int                                 size_type;
    typedef smart_ptr<T>                        pointer;
    typedef T                                   value_type;
    typedef const value_type                    const_value_type;
    typedef value_type &                        reference;
    typedef const_value_type &                  const_reference;
    typedef vector_iterator<T,pointer>          iterator;
    typedef const_vector_iterator<T,pointer>    const_iterator;

public:
    //Owing to OOM condition, the ctor of HbVector can throw, the exception is 
    // propagated to the caller.
    HbVector(HbMemoryManager::MemoryType type = HbMemoryManager::HeapMemory)
       : mData(0,type),
         mMemoryType(type),
         mShared(false)
   {
       GET_MEMORY_MANAGER(type);
       HbSmartOffset smartOffset(manager->alloc(sizeof(HbVectorData)), type );
       mData = new((char*)manager->base() + smartOffset.get()) HbVectorData(type);
       smartOffset.release(); 
   }

    HbVector(const HbVector<T> &other)
    { 
       mMemoryType = other.mMemoryType;
       GET_MEMORY_MANAGER(other.mMemoryType)
       // Deep copy , if current vector is in client side and it copies data which is in shared memory.
       // else Do normal Implicit sharing.
       mData = other.mData;

       if(!manager->isWritable() || other.mShared == true){
           mShared = true;
           mMemoryType = HbMemoryManager::HeapMemory;
       } else {
           mShared = false;
           mData->mRef.ref();
       }
       Q_ASSERT(mMemoryType == HbMemoryManager::SharedMemory 
                || mMemoryType == HbMemoryManager::HeapMemory);
    }
    
    ~HbVector()
    {
       GET_MEMORY_MANAGER(mMemoryType);
       // if the memory where the vector is not writable it means it's client process, so do nothing
       if(!mData || !manager->isWritable()) 
           return;
       if(mShared != true && !mData->mRef.deref()) {
           destroyData();
       }
    
    }
    
    HbMemoryManager::MemoryType memoryType() const
    {
       return mMemoryType;
    }
    
    #ifdef CSS_PARSER_TRACES
    void print() const
    {
    //qDebug() <<"==============HbVector::Print():Begin [size = "<< count() <<"] ==================";
       if(count())
       {
           const_iterator iter = begin();
           while(iter != end()) {
               if(iter->supportsPrinting())
               iter->print();
               iter++;
           }
       }
       else
           qDebug() << "Empty HbVector::Nothing to print!";
     //qDebug() <<"==============HbVector::Print():End [size = "<< count() <<"] ==================";
    }
    
    #endif
    
    bool isEmpty() const
    { return mData->mSize == 0; }
    
    void append(const_reference value);
    void insert ( int i, const_reference value )
    {
       Q_ASSERT_X(i >= 0 && i <= mData->mSize,"HbVector<T>::insert()","index out of range");
       insert(constBegin() + i, (size_type)1, value); 
    }
    
    void insert ( int i, int count, const_reference value )
    {
       Q_ASSERT_X(i >= 0 && i <= mData->mSize,"HbVector<T>::insert()","index out of range");
       insert(constBegin() + i, (size_type)count, value);
    }
    
    iterator insert ( const_iterator before, const_reference value )
    { return insert(before, (size_type)1, value); }
    
    iterator insert ( const_iterator before, int count, const_reference value );
    
    const_iterator constEnd() const
    { return const_iterator(mData->mStart + mData->mSize); }
    
    iterator end() 
    {
        detach(); 
        return iterator(mData->mStart + mData->mSize); 
    }

    const_iterator end() const
    { return const_iterator(mData->mStart + mData->mSize); }

    const_iterator constBegin() const
    { return const_iterator(mData->mStart); }

    iterator begin() 
    { detach() ; return iterator(mData->mStart); }

    const_iterator begin() const
    { return const_iterator(mData->mStart); }

    reference first() const
    { Q_ASSERT(!isEmpty()); return *this->mData->mStart; }

    const_reference last() const
    { Q_ASSERT(!isEmpty()); return this->mData->mStart[this->mData->mSize - 1]; } 

    reference at(size_type position) const
    {
       Q_ASSERT_X(position >= 0 && position < this->mData->mSize,"HbVector<T>::at", "index out of range"); 
       return this->mData->mStart[position];
    }

    const T *constData() const
    { return (T*)mData->mStart.get(); }

    value_type value(int i) const
    {
       if(i < 0 || i >= mData->mSize) {
           return value_type();
       }
       return mData->mStart[i];
    }

    value_type value(int i, const_reference defaultValue) const
    {
       return ((i < 0 || i >= mData->mSize) ? defaultValue : mData->mStart[i]); 
    }

    void resize(int newSize)
    {
       Q_ASSERT(newSize > -1);
       int oldSize = mData->mSize;
       if(newSize < oldSize) {
           // Destroy the last remaining elements
           erase(const_iterator(mData->mStart + newSize), constEnd());
       } else {
           reserve(newSize);
           Inserter it(mData->mStart + mData->mSize, mData->mStart + newSize);
           while(it.canInsert()) {
               it.insert(T());
           }
           it.release();
       }
       mData->mSize = newSize;
    }

    // reserve() can throw owing to OOM
    void reserve(int newSize)
    {
        if( mShared || newSize > mData->mCapacity || mData->mRef != 1) {
            GET_MEMORY_MANAGER(mMemoryType);
            int offset = (char*)mData->mStart.get() - (char*)manager->base();
            int newOffset = -1;
            if(newSize > mData->mCapacity)
                newOffset = reAlloc(offset, newSize, mData->mSize);
            else
                newOffset = reAlloc(offset, mData->mCapacity, mData->mSize);
            mData->mStart.setOffset(newOffset);
            mData->mCapacity = newSize;
       }
    }

    iterator erase(const_iterator first, const_iterator last)
    {
        int firstDiff = first - mData->mStart;
        int lastDiff = last - mData->mStart;
        int diff = lastDiff - firstDiff;
        detach();
        if(QTypeInfo<value_type>::isComplex) {
            copy(mData->mStart + lastDiff, mData->mStart + mData->mSize, mData->mStart + firstDiff);
            pointer i = mData->mStart + mData->mSize;
            pointer b = mData->mStart + mData->mSize - diff;
            while(i != b) {
                --i;
                i.get()->~T();
            }
        } else {
            ::memmove(mData->mStart + firstDiff,
                        mData->mStart + lastDiff, 
                        sizeof(value_type) * (mData->mSize -lastDiff));
        }

        mData->mSize -= diff;
        return iterator(mData->mStart + firstDiff);
    }

    void remove(int i)
    {
       Q_ASSERT_X(i >= 0 && i < mData->mSize, "HbVector<T>::remove", "index out of range");
       erase(constBegin() + i , constBegin() + i + 1);
    }

    void remove(int i, int count)
    {
       Q_ASSERT_X(i >= 0 && i + count <= mData->mSize, "HbVector<T>::remove", "index out of range");
       erase(constBegin() + i , constBegin() + i + count);
    }

    void clear()
    {
       resize(0);
    }

    size_type count() const
    { return mData->mSize; } 

    size_type size() const
    { return count(); } 

    size_type capacity() const
    { return mData->mCapacity;}

    bool contains(const_reference value) const
    {
       pointer first = mData->mStart;
       pointer last = mData->mStart + mData->mSize;
       while( last != first ) {
           if( *--last == value) {
               return true;
           }
       }
      return false;
    }

    const_reference operator[](int position) const
    {
       Q_ASSERT_X(position >= 0 && position < this->mData->mSize,"HbVector<T>::at", "index out of range");
       return this->mData->mStart[position];
    }
    
    reference operator[](int position)
    {
       Q_ASSERT_X(position >= 0 && position < this->mData->mSize,"HbVector<T>::at", "index out of range");
       return this->mData->mStart[position];
    }

    bool operator!=(const HbVector<T> &other) const
    {
        return !(*this == other);
    }

    bool operator==(const HbVector<T> &other) const
    {
        if (size() != other.size())
            return false;
        pointer start = mData->mStart;
        pointer end = start + mData->mSize;
        pointer otherEnd  = other.mData->mStart + other.mData->mSize;
        while (end != start) {
            if (!(*--end == *--otherEnd)) {
                return false;
            }
        }
        return true;
    }

    HbVector<T> & operator+= (const HbVector<T>& other)
    {
        int newSize = mData->mSize + other.mData->mSize;
        reserve(newSize);
        Inserter it(mData->mStart + mData->mSize, mData->mStart + newSize);
        pointer otherFirst = other.mData->mStart;

        for(;it.canInsert(); ++otherFirst ) {
            it.insert(*otherFirst);
        }
        mData->mSize = newSize;
        it.release();
        return *this;
    }

    HbVector<T> & operator+= (const_reference value)
    {
        append(value); 
        return *this;
    }

    
    HbVector<T> & operator<< (const_reference value)
    {
        append(value); 
        return *this;
    }

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

    HbVector<T> & operator=(const HbVector<T> &other)
    {
        GET_MEMORY_MANAGER(mMemoryType);
        if(!manager->isWritable())
            Q_ASSERT(mMemoryType != HbMemoryManager::SharedMemory);
        
        // if the Current vector and other Vector memory type is not same then do Deep Copy.
        //To Do: mShared == true is just Quick fix for unit-test where the other vector is in heap but 
        // its data shared to shared memory also the current vector is same state. this needs to fix
        // and decision making is required very clear for all the scenarios.
        if (other.mMemoryType != mMemoryType || other.mShared == true || mShared == true ) 
        {
            if(mShared != true) {
                if(mData->mRef == 1) {
                    destroyData();
                }else {
                    mData->mRef.deref();
                }
            }
            mShared = true;
            // Here assumption is that two memory type will be different in
            // client side. so this code will not be execute in the server side so
            // memoryType will be heap but data still shared to Shared memory.
            mMemoryType = HbMemoryManager::HeapMemory;
        } else {
            if(!mData->mRef.deref() ) {
               destroyData();
            }
            other.mData->mRef.ref();
            mMemoryType = other.mMemoryType;
            mShared = other.mShared;
        }
        mData = other.mData;
        Q_ASSERT(mMemoryType == HbMemoryManager::SharedMemory || mMemoryType == HbMemoryManager::HeapMemory);
        return *this;
    }

    HbVector<T> & operator=(const QVector<T> &other)
    {
        Q_ASSERT(mMemoryType == HbMemoryManager::SharedMemory || mMemoryType == HbMemoryManager::HeapMemory);
        clear();
        foreach (T obj, other) {
            append(obj);
        }
        return *this;
    }

    operator QVector<T>() const
    {
        QVector<T> v;
        v += *this;
        return v;
    }

private:
    void detach()
    {
        if(mData->mRef != 1 || mShared == true) {
            copyData(size(), size());
            // Here assumption is the new copy of data is created in heap.
            // so disabling the shared flag.
            if(mShared)
                mShared = false;
        }
    }

    pointer copy(pointer begin, pointer end, pointer dest)
    {
        while(begin != end) {
            *dest++ = *begin++;
        }
        return dest;
    }    

// copy the Data , this will be called in Implicit sharing whenever vector State is going to change.
// mData is not freed, because it is assumed, that it is owned by another HbVector (mData->mRef > 1)
    void copyData(int newSize, int oldSize)
    {
        DataPointer tempData(mData);
        DataPointer newData(0, mMemoryType);
        GET_MEMORY_MANAGER(mMemoryType)
        HbSmartOffset offset(manager->alloc(sizeof(HbVectorData)), mMemoryType);
        qDebug() << tempData->mSize << "," << oldSize;
        newData = new ((char*)manager->base() + offset.get())
                        HbVectorData(mMemoryType, oldSize, newSize);
        mData = newData;
        offset.release();
        if(!mShared) {
            tempData->mRef.deref();
        }

        if(QTypeInfo<value_type>::isComplex) {
            Inserter it(mData->mStart, mData->mStart + oldSize);
            pointer sourceStart = tempData->mStart;
            for(;it.canInsert(); ++sourceStart) {
                it.insert(*sourceStart);
            }
            it.release();
        } else {
            ::memcpy(mData->mStart, tempData->mStart, oldSize * sizeof(T));
        }
    }

// reallocate the data with new size , in implicit sharing we have new copy of data.
// This function can throw because it calls a throwing function (manager->realloc),
// the exception is propagated to the caller
    int reAlloc(int oldOffset, int newSize , int oldSize)
    {   
        GET_MEMORY_MANAGER(mMemoryType);
        if(mData->mRef != 1 || mShared == true) {
            copyData( newSize, oldSize );
            // Here assumption is the new copy of data is created in heap.
            // so disabling the shared flag.
            if(mShared)
                mShared = false;
            return (char*)mData->mStart.get() - (char*)manager->base();
        } else {
            // this statement can throw
            int offset = manager->realloc(oldOffset, newSize * sizeof(T));
            return offset;
        }
   }

   void destroyData()
   {
       mData->~HbVectorData();
       deAllocateData();
   }

private : // Data
   void deAllocateData()
   {
       GET_MEMORY_MANAGER(mMemoryType);
       mData->deAllocateAll(mMemoryType);
       int dataOffset = (char*) mData.get() - (char*)manager->base();
       manager->free(dataOffset);
       mData = 0;
   }   
    struct HbVectorData
    {
        // The ctor of HbVectorData can throw owing to manager->alloc, we're not catching the exception
        // if any and simply allow to propagate it to caller.
        HbVectorData(HbMemoryManager::MemoryType type, unsigned int size=0, unsigned int capacity = 5)
            : mStart(0,type),
              mSize(size), 
              mCapacity(capacity),
              mRef(1)
        {
            GET_MEMORY_MANAGER(type);
            mStart = (T*) ((char*)manager->base() + manager->alloc(capacity*sizeof(T)));            
        }

        ~HbVectorData()
        { 
            destroyAll();
        }

        void deAllocateAll(HbMemoryManager::MemoryType type)
        {
            if(!mCapacity) return;
            GET_MEMORY_MANAGER(type);
            int offset = (char*)mStart.get() - (char*)manager->base();
            manager->free(offset);
            mStart = 0;
            mSize = 0;
            mCapacity = 0;
        }

        void destroyAll()
        {
            if(QTypeInfo<value_type>::isComplex) {
                pointer start(mStart);
                pointer last(start + mSize);
                
                while(last-- != start) {
                    last.get()->~value_type();
                }
            }
        }
        
        pointer mStart;
        size_type mSize;
        size_type mCapacity;
        QAtomicInt mRef;
    };

    struct Inserter {
        Inserter(pointer begin, pointer end) : begin(begin), it(begin), end(end) {

        }
        void release() {
            it = begin;
        }
        bool canInsert() const {
            return (it != end);
        }
        void insert(const T& obj) {
            new (it) T(obj);
            ++it;
        }

        ~Inserter() {
            if(QTypeInfo<value_type>::isComplex) {
                while(it != begin) {
                    begin.get()->~T();
                    ++begin;
                }
            }
        }
    private:
        pointer begin;
        pointer it;
        pointer end;
    };
    typedef smart_ptr<HbVectorData> DataPointer;
    DataPointer mData;
    HbMemoryManager::MemoryType mMemoryType;
    bool mShared;

};


template <typename T>
Q_TYPENAME HbVector<T>::iterator
HbVector<T>::insert(const_iterator before, int count, const_reference value)
{
    int offset = before - mData->mStart;
    if(count != 0) {
        if(mShared || mData->mRef !=1 || mData->mSize + count > mData->mCapacity) {
            GET_MEMORY_MANAGER(mMemoryType);
            int offset = (char*)mData->mStart.get() - (char*)manager->base();
            int newCapacity = mData->mSize + count;
            if(newCapacity < mData->mCapacity) {
                newCapacity = mData->mCapacity;
            }
            mData->mStart.setOffset(reAlloc(offset, newCapacity, mData->mSize));
            mData->mCapacity = newCapacity;
        }
        if(QTypeInfo<value_type>::isStatic) {
            pointer b = mData->mStart + mData->mSize;
            pointer i = b + count;
            while(i != b)
                new(--i) T(mMemoryType);
            i = mData->mStart + mData->mSize;
            pointer j = i + count;
            b = mData->mStart + offset;
            while( i != b )
                *--j = *--i;
            i = b + count;
            while( i != b )
                *--i = value;
        } else {
            pointer b = mData->mStart + offset;
            pointer i = b + count;
            ::memmove(i, b, (mData->mSize - offset) * sizeof(T));
            Inserter it(b, i);
            while(it.canInsert()) {
                it.insert(value);
            }
            it.release();
        }

        mData->mSize += count;
    }
    return iterator(mData->mStart + offset);
}

template <typename T>
void HbVector<T>::append(const value_type &value)
{
    if(!mShared && mData->mRef == 1 && mData->mSize < mData->mCapacity ) {
        //There is enough space, construct a new object at the end.
        if(QTypeInfo<value_type>::isComplex) {
            new ((void*)(mData->mStart + mData->mSize)) value_type(value);
        } else {
            mData->mStart[mData->mSize] = value;
        }
    } else {
        GET_MEMORY_MANAGER(mMemoryType);
        int offset = (char*)mData->mStart.get() - (char*)manager->base();
        int newOffset = reAlloc(offset, 2 * mData->mCapacity, mData->mSize);
        mData->mStart.setOffset(newOffset);
        mData->mCapacity *= 2;

        if(QTypeInfo<value_type>::isComplex) {
            Inserter it(mData->mStart + mData->mSize, mData->mStart + mData->mSize + 1);
            it.insert(value_type(value));
            it.release();
        } else {
            mData->mStart[mData->mSize] = value;
        }
    }
    ++mData->mSize;
}

template <typename T>
QVector<T>& operator += (QVector<T>& v1, const HbVector<T>& v2)
{
    v1.reserve(v1.size()+v2.size());
    typename HbVector<T>::const_iterator iter = v2.constBegin();
    typename HbVector<T>::const_iterator end = v2.constEnd();
    while(iter != end) {
        v1.append(*iter);
        ++iter;
    }
    return v1;
}

#endif // HBVECTOR_P_H
