// 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.
 
//#define BUFFER_BUILDER_TRACING
 
using System.IO;
using System.Text;
using System.Diagnostics;
 
namespace Microsoft.Xml
{
    using System;
 
    //
    //  Buffer Builder
    //
    // BufferBuilder is a replacement for StringBuilder for cases when large strings can occur.
    // StringBuilder stores the string that is being built in one large chunk of memory. If it needs more memory,
    // it allocates a new chunk of double size and copies the data into it. This results in bad perf and
    // memory constumption in case the string is very large (>85kB). Large objects are allocated on Large Object 
    // Heap and are not freed by GC as fast as smaller objects.
    // 
    // BufferBuilder uses a StringBuilder as long as the stored string is smaller that 64kB. If the final string
    // should be bigger that that, it stores the data in a list of char[] arrays. A StringBuilder object still needs to be 
    // used in order to create the final string in ToString methods, but this is ok since at that point 
    // we already know the resulting string length and we can initialize the StringBuilder with the correct 
    // capacity. 
    //
    // The BufferBuilder is designed for reusing. The Clear method will clear the state of the builder. 
    // The next string built by BufferBuilder will reuse the string builder and the buffer chunks allocated 
    // in the previous uses. (The string builder it not reused when it was last used to create a string >64kB because
    // setting Length=0 on the string builder makes it allocate the big string again.)
    // When the buffer chunks are not in use, they are stored as WeakReferences so they can be freed by GC 
    // in case memory-pressure situation happens.
 
#if BUFFER_BUILDER_TRACING
    public class BufferBuilder {
#else
    internal class BufferBuilder
    {
#endif
        //
        // Private types
        //
        private struct Buffer
        {
            internal char[] buffer;
            internal WeakReference recycledBuffer;
        }
 
        //
        // Fields
        //
        private StringBuilder _stringBuilder;
 
        private Buffer[] _buffers;
        private int _buffersCount;
        private char[] _lastBuffer;
        private int _lastBufferIndex;
        private int _length;
 
#if BUFFER_BUILDER_TRACING
// 
// Tracing
// 
        public static TextWriter s_TraceOutput = null;
        static int minLength = int.MaxValue;
        static int maxLength;
        static int totalLength;
        static int toStringCount;
        static int totalAppendCount;
#endif
 
        //
        // Constants
        //
#if DEBUG
        // make it easier to catch buffer-related bugs on debug builds
        private const int BufferSize = 4 * 1024;
#else
        private const int BufferSize = 64 * 1024;
#endif
        private const int InitialBufferArrayLength = 4;
        private const int MaxStringBuilderLength = BufferSize;
        private const int DefaultSBCapacity = 16;
 
        //
        // Constructor
        //
        public BufferBuilder()
        {
#if BUFFER_BUILDER_TRACING
            if ( s_TraceOutput != null ) {
                s_TraceOutput.WriteLine( "----------------------------\r\nnew BufferBuilder()\r\n----------------------------" );
            }
#endif
        }
 
        //
        // Properties
        //
        public int Length
        {
            get
            {
                return _length;
            }
            set
            {
#if BUFFER_BUILDER_TRACING
                if ( s_TraceOutput != null ) {
                    s_TraceOutput.WriteLine( "BufferBuilder.Length = " + value );
                }
#endif
 
                if (value < 0 || value > _length)
                {
                    throw new ArgumentOutOfRangeException("value");
                }
                if (value == 0)
                {
                    Clear();
                }
                else
                {
                    SetLength(value);
                }
            }
        }
 
        //
        // Public methods
        //
 
        public void Append(char value)
        {
#if BUFFER_BUILDER_TRACING
            if ( s_TraceOutput != null ) {
                s_TraceOutput.WriteLine( "BufferBuilder.Append\tLength = 1\tchar '" + value.ToString() + "'" );
                totalAppendCount++;
            }
#endif
            if (_length + 1 <= MaxStringBuilderLength)
            {
                if (_stringBuilder == null)
                {
                    _stringBuilder = new StringBuilder();
                }
                _stringBuilder.Append(value);
            }
            else
            {
                if (_lastBuffer == null)
                {
                    CreateBuffers();
                }
                if (_lastBufferIndex == _lastBuffer.Length)
                {
                    AddBuffer();
                }
                _lastBuffer[_lastBufferIndex++] = value;
            }
            _length++;
        }
 
        public void Append(char[] value, int start, int count)
        {
#if BUFFER_BUILDER_TRACING
            if ( s_TraceOutput != null ) {
                s_TraceOutput.WriteLine( "BufferBuilder.Append\tLength = " + count + "\t char array \"" + new string( value, start, count ) + "\"" );
                totalAppendCount++;
            }
#endif
            if (value == null)
            {
                if (start == 0 && count == 0)
                {
                    return;
                }
                throw new ArgumentNullException("value");
            }
            if (count == 0)
            {
                return;
            }
            if (start < 0)
            {
                throw new ArgumentOutOfRangeException("start");
            }
            if (count < 0 || start + count > value.Length)
            {
                throw new ArgumentOutOfRangeException("count");
            }
 
            if (_length + count <= MaxStringBuilderLength)
            {
                if (_stringBuilder == null)
                {
                    _stringBuilder = new StringBuilder(count < DefaultSBCapacity ? DefaultSBCapacity : count);
                }
                _stringBuilder.Append(value, start, count);
                _length += count;
            }
            else
            {
                unsafe
                {
                    fixed (char* source = &value[start])
                    {
                        AppendHelper(source, count);
                    }
                }
            }
        }
 
        public void Append(string value)
        {
            Append(value, 0, value.Length);
        }
 
        public void Append(string value, int start, int count)
        {
#if BUFFER_BUILDER_TRACING
            if ( s_TraceOutput != null ) {
                s_TraceOutput.WriteLine( "BufferBuilder.Append\tLength = " + count + "\t string fragment \"" + value.Substring( start, count ) + "\"" );
                totalAppendCount++;
            }
#endif
            if (value == null)
            {
                if (start == 0 && count == 0)
                {
                    return;
                }
                throw new ArgumentNullException("value");
            }
            if (count == 0)
            {
                return;
            }
            if (start < 0)
            {
                throw new ArgumentOutOfRangeException("start");
            }
            if (count < 0 || start + count > value.Length)
            {
                throw new ArgumentOutOfRangeException("count");
            }
            if (_length + count <= MaxStringBuilderLength)
            {
                if (_stringBuilder == null)
                {
                    _stringBuilder = new StringBuilder(value, start, count, 0);
                }
                else
                {
                    _stringBuilder.Append(value, start, count);
                }
                _length += count;
            }
            else
            {
                unsafe
                {
                    fixed (char* source = value)
                    {
                        AppendHelper(source + start, count);
                    }
                }
            }
        }
 
        public void Clear()
        {
            if (_length <= MaxStringBuilderLength)
            {
                if (_stringBuilder != null)
                {
                    _stringBuilder.Length = 0;
                }
            }
            else
            {
                if (_lastBuffer != null)
                {
                    ClearBuffers();
                }
                // destroy the string builder because setting its Length or Capacity to 0 makes it allocate the last string again :-|
                _stringBuilder = null;
            }
            _length = 0;
        }
 
        internal void ClearBuffers()
        {
            if (_buffers != null)
            {
                // recycle all but the first the buffer
                for (int i = 0; i < _buffersCount; i++)
                {
                    Recycle(ref _buffers[i]);
                }
                _lastBuffer = null;
            }
            else
            {
                // just one buffer allocated with no buffers array -> no recycling
            }
            _lastBufferIndex = 0;
            _buffersCount = 0;
        }
 
        public override string ToString()
        {
            string returnString;
            if ((_length <= MaxStringBuilderLength) || (_buffersCount == 1 && _lastBufferIndex == 0))
            {
                returnString = (_stringBuilder != null) ? _stringBuilder.ToString() : string.Empty;
            }
            else
            {
                if (_stringBuilder == null)
                {
                    _stringBuilder = new StringBuilder(_length);
                }
                else
                {
                    _stringBuilder.Capacity = _length;
                }
                int charsLeft = _length - _stringBuilder.Length;
                for (int i = 0; i < _buffersCount - 1; i++)
                {
                    char[] buf = _buffers[i].buffer;
                    _stringBuilder.Append(buf, 0, buf.Length);
                    charsLeft -= buf.Length;
                }
                _stringBuilder.Append(_buffers[_buffersCount - 1].buffer, 0, charsLeft);
                ClearBuffers();
                returnString = _stringBuilder.ToString();
            }
#if BUFFER_BUILDER_TRACING
            if ( s_TraceOutput != null ) {
                s_TraceOutput.WriteLine( "BufferBuilder.ToString() Length == " + returnString.Length + "\t \"" + returnString + "\"" );
                toStringCount++;
                totalLength += returnString.Length;
                if ( minLength > returnString.Length ) {
                    minLength = returnString.Length;
                }
                if ( maxLength < returnString.Length ) {
                    maxLength = returnString.Length;
                }
            }
#endif
            return returnString;
        }
 
        public string ToString(int startIndex, int len)
        {
#if BUFFER_BUILDER_TRACING
            if ( s_TraceOutput != null ) {
                s_TraceOutput.WriteLine( "BufferBuilder.ToString( " + startIndex + ", " + len + " )" );
            }
#endif
            if (startIndex < 0 || startIndex >= _length)
            {
                throw new ArgumentOutOfRangeException("startIndex");
            }
            if (len < 0 || startIndex + len > _length)
            {
                throw new ArgumentOutOfRangeException("len");
            }
 
            if ((_length <= MaxStringBuilderLength) || (_buffersCount == 1 && _lastBufferIndex == 0))
            {
                return (_stringBuilder != null) ? _stringBuilder.ToString(startIndex, len) : string.Empty;
            }
            else
            {
                StringBuilder sb = new StringBuilder(len);
                if (_stringBuilder != null)
                {
                    if (startIndex < _stringBuilder.Length)
                    {
                        if (len < _stringBuilder.Length)
                        {
                            return _stringBuilder.ToString(startIndex, len);
                        }
                        else
                        {
                            sb.Append(_stringBuilder.ToString(startIndex, _stringBuilder.Length - startIndex));
                            len -= (_stringBuilder.Length - startIndex);
                            startIndex = 0;
                        }
                    }
                    else
                    {
                        startIndex -= _stringBuilder.Length;
                    }
                }
 
                int i;
                for (i = 0; i < _buffersCount; i++)
                {
                    if (startIndex < _buffers[i].buffer.Length)
                    {
                        break;
                    }
                    startIndex -= _buffers[i].buffer.Length;
                }
                if (i < _buffersCount)
                {
                    int charsLeft = len;
                    for (; i < _buffersCount && charsLeft > 0; i++)
                    {
                        char[] buf = _buffers[i].buffer;
                        int copyCount = (buf.Length < charsLeft) ? buf.Length : charsLeft;
                        sb.Append(buf, startIndex, copyCount);
                        startIndex = 0;
                        charsLeft -= copyCount;
                    }
                }
                return sb.ToString();
            }
        }
 
 
        //
        // Private implementation methods
        //
        private void CreateBuffers()
        {
            Debug.Assert(_lastBuffer == null);
            if (_buffers == null)
            {
                _lastBuffer = new char[BufferSize];
                _buffers = new Buffer[InitialBufferArrayLength];
                _buffers[0].buffer = _lastBuffer;
                _buffersCount = 1;
            }
            else
            {
                AddBuffer();
            }
        }
 
        unsafe private void AppendHelper(char* pSource, int count)
        {
            if (_lastBuffer == null)
            {
                CreateBuffers();
            }
            int copyCount = 0;
            while (count > 0)
            {
                if (_lastBufferIndex >= _lastBuffer.Length)
                {
                    AddBuffer();
                }
 
                copyCount = count;
                int free = _lastBuffer.Length - _lastBufferIndex;
                if (free < copyCount)
                {
                    copyCount = free;
                }
 
                fixed (char* pLastBuffer = &_lastBuffer[_lastBufferIndex])
                {
                    wstrcpy(pLastBuffer, pSource, copyCount);
                }
                pSource += copyCount;
                _length += copyCount;
                _lastBufferIndex += copyCount;
                count -= copyCount;
            }
        }
 
        private void AddBuffer()
        {
            Debug.Assert(_buffers != null);
 
            // check the buffers array it its big enough
            if (_buffersCount + 1 == _buffers.Length)
            {
                Buffer[] newBuffers = new Buffer[_buffers.Length * 2];
                Array.Copy(_buffers, 0, newBuffers, 0, _buffers.Length);
                _buffers = newBuffers;
            }
 
            // use the recycled buffer if we have one
            char[] newBuffer;
            if (_buffers[_buffersCount].recycledBuffer != null)
            {
                newBuffer = (char[])_buffers[_buffersCount].recycledBuffer.Target;
                if (newBuffer != null)
                {
                    _buffers[_buffersCount].recycledBuffer.Target = null;
                    goto End;
                }
            }
            newBuffer = new char[BufferSize];
        End:
            // add the buffer to the list
            _lastBuffer = newBuffer;
            _buffers[_buffersCount++].buffer = newBuffer;
            _lastBufferIndex = 0;
        }
 
        private void Recycle(ref Buffer buf)
        {
            // recycled buffers are kept as WeakReferences 
            if (buf.recycledBuffer == null)
            {
                buf.recycledBuffer = new WeakReference(buf.buffer);
            }
            else
            {
                buf.recycledBuffer.Target = buf.buffer;
            }
#if DEBUG
            for (int i = 0; i < buf.buffer.Length; i++)
            {
                buf.buffer[i] = (char)0xCC;
            }
#endif
            buf.buffer = null;
        }
 
        private void SetLength(int newLength)
        {
            Debug.Assert(newLength <= _length);
 
            if (newLength == _length)
            {
                return;
            }
 
            if (_length <= MaxStringBuilderLength)
            {
                _stringBuilder.Length = newLength;
            }
            else
            {
                int newLastIndex = newLength;
                int i;
                for (i = 0; i < _buffersCount; i++)
                {
                    if (newLastIndex < _buffers[i].buffer.Length)
                    {
                        break;
                    }
                    newLastIndex -= _buffers[i].buffer.Length;
                }
                if (i < _buffersCount)
                {
                    _lastBuffer = _buffers[i].buffer;
                    _lastBufferIndex = newLastIndex;
                    i++;
                    int newBuffersCount = i;
                    for (; i < _buffersCount; i++)
                    {
                        Recycle(ref _buffers[i]);
                    }
                    _buffersCount = newBuffersCount;
                }
            }
            _length = newLength;
        }
 
        internal static unsafe void wstrcpy(char* dmem, char* smem, int charCount)
        {
            if (charCount > 0)
            {
                if ((((int)dmem ^ (int)smem) & 3) == 0)
                {
                    while (((int)dmem & 3) != 0 && charCount > 0)
                    {
                        dmem[0] = smem[0];
                        dmem += 1;
                        smem += 1;
                        charCount -= 1;
                    }
                    if (charCount >= 8)
                    {
                        charCount -= 8;
                        do
                        {
                            ((uint*)dmem)[0] = ((uint*)smem)[0];
                            ((uint*)dmem)[1] = ((uint*)smem)[1];
                            ((uint*)dmem)[2] = ((uint*)smem)[2];
                            ((uint*)dmem)[3] = ((uint*)smem)[3];
                            dmem += 8;
                            smem += 8;
                            charCount -= 8;
                        } while (charCount >= 0);
                    }
                    if ((charCount & 4) != 0)
                    {
                        ((uint*)dmem)[0] = ((uint*)smem)[0];
                        ((uint*)dmem)[1] = ((uint*)smem)[1];
                        dmem += 4;
                        smem += 4;
                    }
                    if ((charCount & 2) != 0)
                    {
                        ((uint*)dmem)[0] = ((uint*)smem)[0];
                        dmem += 2;
                        smem += 2;
                    }
                }
                else
                {
                    if (charCount >= 8)
                    {
                        charCount -= 8;
                        do
                        {
                            dmem[0] = smem[0];
                            dmem[1] = smem[1];
                            dmem[2] = smem[2];
                            dmem[3] = smem[3];
                            dmem[4] = smem[4];
                            dmem[5] = smem[5];
                            dmem[6] = smem[6];
                            dmem[7] = smem[7];
                            dmem += 8;
                            smem += 8;
                            charCount -= 8;
                        }
                        while (charCount >= 0);
                    }
                    if ((charCount & 4) != 0)
                    {
                        dmem[0] = smem[0];
                        dmem[1] = smem[1];
                        dmem[2] = smem[2];
                        dmem[3] = smem[3];
                        dmem += 4;
                        smem += 4;
                    }
                    if ((charCount & 2) != 0)
                    {
                        dmem[0] = smem[0];
                        dmem[1] = smem[1];
                        dmem += 2;
                        smem += 2;
                    }
                }
 
                if ((charCount & 1) != 0)
                {
                    dmem[0] = smem[0];
                }
            }
        }
 
#if BUFFER_BUILDER_TRACING
        public static int ToStringCount { 
            get {
                return toStringCount;
            }
        }
 
        public static double AvgAppendCount { 
            get {
                return toStringCount == 0 ? 0 : (double)totalAppendCount / toStringCount;
            }
        }
 
        public static int AvgLength {
            get {
                return toStringCount == 0 ? 0 : totalLength / toStringCount;
            }
        }
 
        public static int MaxLength {
            get {
                return maxLength;
            }
        }
 
        public static int MinLength {
            get {
                return minLength;
            }
        }
#endif
    }
}