The Labs \ Source Viewer \ SSCLI \ System.Xml \ Buffer

  1. //------------------------------------------------------------------------------
  2. // <copyright file="BufferBuilder.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. //#define BUFFER_BUILDER_TRACING
  16. using System.IO;
  17. using System.Text;
  18. using System.Diagnostics;
  19. namespace System.Xml
  20. {
  21.     //
  22.     // Buffer Builder
  23.     //
  24.     // BufferBuilder is a replacement for StringBuilder for cases when large strings can occur.
  25.     // StringBuilder stores the string that is being built in one large chunk of memory. If it needs more memory,
  26.     // it allocates a new chunk of double size and copies the data into it. This results in bad perf and
  27.     // memory constumption in case the string is very large (>85kB). Large objects are allocated on Large Object
  28.     // Heap and are not freed by GC as fast as smaller objects.
  29.     //
  30.     // BufferBuilder uses a StringBuilder as long as the stored string is smaller that 64kB. If the final string
  31.     // should be bigger that that, it stores the data in a list of char[] arrays. A StringBuilder object still needs to be
  32.     // used in order to create the final string in ToString methods, but this is ok since at that point
  33.     // we already know the resulting string length and we can initialize the StringBuilder with the correct
  34.     // capacity.
  35.     //
  36.     // The BufferBuilder is designed for reusing. The Clear method will clear the state of the builder.
  37.     // The next string built by BufferBuilder will reuse the string builder and the buffer chunks allocated
  38.     // in the previous uses. (The string builder it not reused when it was last used to create a string >64kB because
  39.     // setting Length=0 on the string builder makes it allocate the big string again.)
  40.     // When the buffer chunks are not in use, they are stored as WeakReferences so they can be freed by GC
  41.     // in case memory-pressure situation happens.
  42.    
  43.     #if BUFFER_BUILDER_TRACING
  44.     public class BufferBuilder
  45.     {
  46.         #else
  47.         internal class BufferBuilder
  48.         {
  49.             #endif
  50.             //
  51.             // Private types
  52.             //
  53.             private struct Buffer
  54.             {
  55.                 internal char[] buffer;
  56.                 internal WeakReference recycledBuffer;
  57.             }
  58.            
  59.             //
  60.             // Fields
  61.             //
  62.             StringBuilder stringBuilder;
  63.            
  64.             Buffer[] buffers;
  65.             int buffersCount;
  66.             char[] lastBuffer;
  67.             int lastBufferIndex;
  68.             int length;
  69.            
  70.             #if BUFFER_BUILDER_TRACING
  71.             //
  72.             // Tracing
  73.             //
  74.             public static TextWriter s_TraceOutput = null;
  75.             static int minLength = int.MaxValue;
  76.             static int maxLength;
  77.             static int totalLength;
  78.             static int toStringCount;
  79.             static int totalAppendCount;
  80.             #endif
  81.            
  82.             //
  83.             // Constants
  84.             //
  85.             #if DEBUG
  86.             // make it easier to catch buffer-related bugs on debug builds
  87.             const int BufferSize = 4 * 1024;
  88.             #else
  89.             const int BufferSize = 64 * 1024;
  90.             #endif
  91.             const int InitialBufferArrayLength = 4;
  92.             const int MaxStringBuilderLength = BufferSize;
  93.             const int DefaultSBCapacity = 16;
  94.            
  95.             //
  96.             // Constructor
  97.             //
  98.             public BufferBuilder()
  99.             {
  100.                 #if BUFFER_BUILDER_TRACING
  101.                 if (s_TraceOutput != null) {
  102.                     s_TraceOutput.WriteLine("----------------------------\r\nnew BufferBuilder()\r\n----------------------------");
  103.                 }
  104.                 #endif
  105.             }
  106.            
  107.             //
  108.             // Properties
  109.             //
  110.             public int Length {
  111.                 get { return length; }
  112.                 set {
  113.                     #if BUFFER_BUILDER_TRACING
  114.                     if (s_TraceOutput != null) {
  115.                         s_TraceOutput.WriteLine("BufferBuilder.Length = " + value);
  116.                     }
  117.                     #endif
  118.                    
  119.                     if (value < 0 || value > length) {
  120.                         throw new ArgumentOutOfRangeException("value");
  121.                     }
  122.                     if (value == 0) {
  123.                         Clear();
  124.                     }
  125.                     else {
  126.                         SetLength(value);
  127.                     }
  128.                 }
  129.             }
  130.            
  131.             //
  132.             // Public methods
  133.             //
  134.            
  135.             public void Append(char value)
  136.             {
  137.                 #if BUFFER_BUILDER_TRACING
  138.                 if (s_TraceOutput != null) {
  139.                     s_TraceOutput.WriteLine("BufferBuilder.Append\tLength = 1\tchar '" + value.ToString() + "'");
  140.                     totalAppendCount++;
  141.                 }
  142.                 #endif
  143.                 if (length + 1 <= MaxStringBuilderLength) {
  144.                     if (stringBuilder == null) {
  145.                         stringBuilder = new StringBuilder();
  146.                     }
  147.                     stringBuilder.Append(value);
  148.                 }
  149.                 else {
  150.                     if (lastBuffer == null) {
  151.                         CreateBuffers();
  152.                     }
  153.                     if (lastBufferIndex == lastBuffer.Length) {
  154.                         AddBuffer();
  155.                     }
  156.                     lastBuffer[lastBufferIndex++] = value;
  157.                 }
  158.                 length++;
  159.             }
  160.            
  161.             public void Append(char[] value)
  162.             {
  163.                 Append(value, 0, value.Length);
  164.             }
  165.            
  166.             public void Append(char[] value, int start, int count)
  167.             {
  168.                 #if BUFFER_BUILDER_TRACING
  169.                 if (s_TraceOutput != null) {
  170.                     s_TraceOutput.WriteLine("BufferBuilder.Append\tLength = " + count + "\t char array \"" + new string(value, start, count) + "\"");
  171.                     totalAppendCount++;
  172.                 }
  173.                 #endif
  174.                 if (value == null) {
  175.                     if (start == 0 && count == 0) {
  176.                         return;
  177.                     }
  178.                     throw new ArgumentNullException("value");
  179.                 }
  180.                 if (count == 0) {
  181.                     return;
  182.                 }
  183.                 if (start < 0) {
  184.                     throw new ArgumentOutOfRangeException("start");
  185.                 }
  186.                 if (count < 0 || start + count > value.Length) {
  187.                     throw new ArgumentOutOfRangeException("count");
  188.                 }
  189.                
  190.                 if (length + count <= MaxStringBuilderLength) {
  191.                     if (stringBuilder == null) {
  192.                         stringBuilder = new StringBuilder(count < DefaultSBCapacity ? DefaultSBCapacity : count);
  193.                     }
  194.                     stringBuilder.Append(value, start, count);
  195.                     length += count;
  196.                 }
  197.                 else {
  198.                     unsafe {
  199.                         fixed (char* source = &value[start]) {
  200.                             AppendHelper(source, count);
  201.                         }
  202.                     }
  203.                 }
  204.             }
  205.            
  206.             public void Append(string value)
  207.             {
  208.                 Append(value, 0, value.Length);
  209.             }
  210.            
  211.             public void Append(string value, int start, int count)
  212.             {
  213.                 #if BUFFER_BUILDER_TRACING
  214.                 if (s_TraceOutput != null) {
  215.                     s_TraceOutput.WriteLine("BufferBuilder.Append\tLength = " + count + "\t string fragment \"" + value.Substring(start, count) + "\"");
  216.                     totalAppendCount++;
  217.                 }
  218.                 #endif
  219.                 if (value == null) {
  220.                     if (start == 0 && count == 0) {
  221.                         return;
  222.                     }
  223.                     throw new ArgumentNullException("value");
  224.                 }
  225.                 if (count == 0) {
  226.                     return;
  227.                 }
  228.                 if (start < 0) {
  229.                     throw new ArgumentOutOfRangeException("start");
  230.                 }
  231.                 if (count < 0 || start + count > value.Length) {
  232.                     throw new ArgumentOutOfRangeException("count");
  233.                 }
  234.                 if (length + count <= MaxStringBuilderLength) {
  235.                     if (stringBuilder == null) {
  236.                         stringBuilder = new StringBuilder(value, start, count, 0);
  237.                     }
  238.                     else {
  239.                         stringBuilder.Append(value, start, count);
  240.                     }
  241.                     length += count;
  242.                 }
  243.                 else {
  244.                     unsafe {
  245.                         fixed (char* source = value) {
  246.                             AppendHelper(source + start, count);
  247.                         }
  248.                     }
  249.                 }
  250.             }
  251.            
  252.             public void Clear()
  253.             {
  254.                 if (length <= MaxStringBuilderLength) {
  255.                     if (stringBuilder != null) {
  256.                         stringBuilder.Length = 0;
  257.                     }
  258.                 }
  259.                 else {
  260.                     if (lastBuffer != null) {
  261.                         ClearBuffers();
  262.                     }
  263.                     // destroy the string builder because setting its Length or Capacity to 0 makes it allocate the last string again :-|
  264.                     stringBuilder = null;
  265.                 }
  266.                 length = 0;
  267.             }
  268.            
  269.             internal void ClearBuffers()
  270.             {
  271.                 if (buffers != null) {
  272.                     // recycle all but the first the buffer
  273.                     for (int i = 0; i < buffersCount; i++) {
  274.                         Recycle(buffers[i]);
  275.                     }
  276.                     lastBuffer = null;
  277.                 }
  278.                 else {
  279.                     // just one buffer allocated with no buffers array -> no recycling
  280.                 }
  281.                 lastBufferIndex = 0;
  282.                 buffersCount = 0;
  283.             }
  284.            
  285.             public override string ToString()
  286.             {
  287.                 string returnString;
  288.                 if ((length <= MaxStringBuilderLength) || (buffersCount == 1 && lastBufferIndex == 0)) {
  289.                     returnString = (stringBuilder != null) ? stringBuilder.ToString() : string.Empty;
  290.                 }
  291.                 else {
  292.                     if (stringBuilder == null) {
  293.                         stringBuilder = new StringBuilder(length);
  294.                     }
  295.                     else {
  296.                         stringBuilder.Capacity = length;
  297.                     }
  298.                     int charsLeft = length - stringBuilder.Length;
  299.                     for (int i = 0; i < buffersCount - 1; i++) {
  300.                         char[] buf = buffers[i].buffer;
  301.                         stringBuilder.Append(buf, 0, buf.Length);
  302.                         charsLeft -= buf.Length;
  303.                     }
  304.                     stringBuilder.Append(buffers[buffersCount - 1].buffer, 0, charsLeft);
  305.                     ClearBuffers();
  306.                     returnString = stringBuilder.ToString();
  307.                 }
  308.                 #if BUFFER_BUILDER_TRACING
  309.                 if (s_TraceOutput != null) {
  310.                     s_TraceOutput.WriteLine("BufferBuilder.ToString() Length == " + returnString.Length + "\t \"" + returnString + "\"");
  311.                     toStringCount++;
  312.                     totalLength += returnString.Length;
  313.                     if (minLength > returnString.Length) {
  314.                         minLength = returnString.Length;
  315.                     }
  316.                     if (maxLength < returnString.Length) {
  317.                         maxLength = returnString.Length;
  318.                     }
  319.                 }
  320.                 #endif
  321.                 return returnString;
  322.             }
  323.            
  324.             public string ToString(int startIndex, int len)
  325.             {
  326.                 #if BUFFER_BUILDER_TRACING
  327.                 if (s_TraceOutput != null) {
  328.                     s_TraceOutput.WriteLine("BufferBuilder.ToString( " + startIndex + ", " + len + " )");
  329.                 }
  330.                 #endif
  331.                 if (startIndex < 0 || startIndex >= length) {
  332.                     throw new ArgumentOutOfRangeException("startIndex");
  333.                 }
  334.                 if (len < 0 || startIndex + len > length) {
  335.                     throw new ArgumentOutOfRangeException("len");
  336.                 }
  337.                
  338.                 if ((length <= MaxStringBuilderLength) || (buffersCount == 1 && lastBufferIndex == 0)) {
  339.                     return (stringBuilder != null) ? stringBuilder.ToString(startIndex, len) : string.Empty;
  340.                 }
  341.                 else {
  342.                     StringBuilder sb = new StringBuilder(len);
  343.                     if (stringBuilder != null) {
  344.                         if (startIndex < stringBuilder.Length) {
  345.                             if (len < stringBuilder.Length) {
  346.                                 return stringBuilder.ToString(startIndex, len);
  347.                             }
  348.                             else {
  349.                                 sb.Append(stringBuilder.ToString(startIndex, stringBuilder.Length));
  350.                                 startIndex = 0;
  351.                             }
  352.                         }
  353.                         else {
  354.                             startIndex -= stringBuilder.Length;
  355.                         }
  356.                     }
  357.                    
  358.                     int i;
  359.                     for (i = 0; i < buffersCount; i++) {
  360.                         if (startIndex < buffers[i].buffer.Length) {
  361.                             break;
  362.                         }
  363.                         startIndex -= buffers[i].buffer.Length;
  364.                     }
  365.                     if (i < buffersCount) {
  366.                         int charsLeft = len;
  367.                         for (; i < buffersCount && charsLeft > 0; i++) {
  368.                             char[] buf = buffers[i].buffer;
  369.                             int copyCount = (buf.Length < charsLeft) ? buf.Length : charsLeft;
  370.                             sb.Append(buf, startIndex, copyCount);
  371.                             startIndex = 0;
  372.                             charsLeft -= copyCount;
  373.                         }
  374.                     }
  375.                     return sb.ToString();
  376.                 }
  377.             }
  378.            
  379.            
  380.             //
  381.             // Private implementation methods
  382.             //
  383.             private void CreateBuffers()
  384.             {
  385.                 Debug.Assert(lastBuffer == null);
  386.                 if (buffers == null) {
  387.                     lastBuffer = new char[BufferSize];
  388.                     buffers = new Buffer[InitialBufferArrayLength];
  389.                     buffers[0].buffer = lastBuffer;
  390.                     buffersCount = 1;
  391.                 }
  392.                 else {
  393.                     AddBuffer();
  394.                 }
  395.             }
  396.            
  397.             unsafe private void AppendHelper(char* pSource, int count)
  398.             {
  399.                 if (lastBuffer == null) {
  400.                     CreateBuffers();
  401.                 }
  402.                 int copyCount = 0;
  403.                 while (count > 0) {
  404.                     if (lastBufferIndex >= lastBuffer.Length) {
  405.                         AddBuffer();
  406.                     }
  407.                    
  408.                     copyCount = count;
  409.                     int free = lastBuffer.Length - lastBufferIndex;
  410.                     if (free < copyCount) {
  411.                         copyCount = free;
  412.                     }
  413.                    
  414.                     fixed (char* pLastBuffer = &lastBuffer[lastBufferIndex]) {
  415.                         wstrcpy(pLastBuffer, pSource, copyCount);
  416.                     }
  417.                     pSource += copyCount;
  418.                     length += copyCount;
  419.                     lastBufferIndex += copyCount;
  420.                     count -= copyCount;
  421.                 }
  422.             }
  423.            
  424.             private void AddBuffer()
  425.             {
  426.                 Debug.Assert(buffers != null);
  427.                
  428.                 // check the buffers array it its big enough
  429.                 if (buffersCount + 1 == buffers.Length) {
  430.                     Buffer[] newBuffers = new Buffer[buffers.Length * 2];
  431.                     Array.Copy(buffers, 0, newBuffers, 0, buffers.Length);
  432.                     buffers = newBuffers;
  433.                 }
  434.                
  435.                 // use the recycled buffer if we have one
  436.                 char[] newBuffer;
  437.                 if (buffers[buffersCount].recycledBuffer != null) {
  438.                     newBuffer = (char[])buffers[buffersCount].recycledBuffer.Target;
  439.                     if (newBuffer != null) {
  440.                         buffers[buffersCount].recycledBuffer.Target = null;
  441.                         goto End;
  442.                     }
  443.                 }
  444.                 newBuffer = new char[BufferSize];
  445.                 End:
  446.                
  447.                 // add the buffer to the list
  448.                 lastBuffer = newBuffer;
  449.                 buffers[buffersCount++].buffer = newBuffer;
  450.                 lastBufferIndex = 0;
  451.             }
  452.            
  453.             private void Recycle(Buffer buf)
  454.             {
  455.                 // recycled buffers are kept as WeakReferences
  456.                 if (buf.recycledBuffer == null) {
  457.                     buf.recycledBuffer = new WeakReference(buf.buffer);
  458.                 }
  459.                 else {
  460.                     buf.recycledBuffer.Target = buf.buffer;
  461.                 }
  462.                 #if DEBUG
  463.                 for (int i = 0; i < buf.buffer.Length; i++) {
  464.                     buf.buffer[i] = (char)204;
  465.                 }
  466.                 #endif
  467.                 buf.buffer = null;
  468.             }
  469.            
  470.             private void SetLength(int newLength)
  471.             {
  472.                 Debug.Assert(newLength <= length);
  473.                
  474.                 if (newLength == length) {
  475.                     return;
  476.                 }
  477.                
  478.                 if (length <= MaxStringBuilderLength) {
  479.                     stringBuilder.Length = newLength;
  480.                 }
  481.                 else {
  482.                     int newLastIndex = newLength;
  483.                     int i;
  484.                     for (i = 0; i < buffersCount; i++) {
  485.                         if (newLastIndex < buffers[i].buffer.Length) {
  486.                             break;
  487.                         }
  488.                         newLastIndex -= buffers[i].buffer.Length;
  489.                     }
  490.                     if (i < buffersCount) {
  491.                         lastBuffer = buffers[i].buffer;
  492.                         lastBufferIndex = newLastIndex;
  493.                         i++;
  494.                         int newBuffersCount = i;
  495.                         for (; i < buffersCount; i++) {
  496.                             Recycle(buffers[i]);
  497.                         }
  498.                         buffersCount = newBuffersCount;
  499.                     }
  500.                 }
  501.                 length = newLength;
  502.             }
  503.            
  504.             unsafe static internal void wstrcpy(char* dmem, char* smem, int charCount)
  505.             {
  506.                 if (charCount > 0) {
  507.                     if ((((int)dmem ^ (int)smem) & 3) == 0) {
  508.                         while (((int)dmem & 3) != 0 && charCount > 0) {
  509.                             dmem[0] = smem[0];
  510.                             dmem += 1;
  511.                             smem += 1;
  512.                             charCount -= 1;
  513.                         }
  514.                         if (charCount >= 8) {
  515.                             charCount -= 8;
  516.                             do {
  517.                                 ((uint*)dmem)[0] = ((uint*)smem)[0];
  518.                                 ((uint*)dmem)[1] = ((uint*)smem)[1];
  519.                                 ((uint*)dmem)[2] = ((uint*)smem)[2];
  520.                                 ((uint*)dmem)[3] = ((uint*)smem)[3];
  521.                                 dmem += 8;
  522.                                 smem += 8;
  523.                                 charCount -= 8;
  524.                             }
  525.                             while (charCount >= 0);
  526.                         }
  527.                         if ((charCount & 4) != 0) {
  528.                             ((uint*)dmem)[0] = ((uint*)smem)[0];
  529.                             ((uint*)dmem)[1] = ((uint*)smem)[1];
  530.                             dmem += 4;
  531.                             smem += 4;
  532.                         }
  533.                         if ((charCount & 2) != 0) {
  534.                             ((uint*)dmem)[0] = ((uint*)smem)[0];
  535.                             dmem += 2;
  536.                             smem += 2;
  537.                         }
  538.                     }
  539.                     else {
  540.                         if (charCount >= 8) {
  541.                             charCount -= 8;
  542.                             do {
  543.                                 dmem[0] = smem[0];
  544.                                 dmem[1] = smem[1];
  545.                                 dmem[2] = smem[2];
  546.                                 dmem[3] = smem[3];
  547.                                 dmem[4] = smem[4];
  548.                                 dmem[5] = smem[5];
  549.                                 dmem[6] = smem[6];
  550.                                 dmem[7] = smem[7];
  551.                                 dmem += 8;
  552.                                 smem += 8;
  553.                                 charCount -= 8;
  554.                             }
  555.                             while (charCount >= 0);
  556.                         }
  557.                         if ((charCount & 4) != 0) {
  558.                             dmem[0] = smem[0];
  559.                             dmem[1] = smem[1];
  560.                             dmem[2] = smem[2];
  561.                             dmem[3] = smem[3];
  562.                             dmem += 4;
  563.                             smem += 4;
  564.                         }
  565.                         if ((charCount & 2) != 0) {
  566.                             dmem[0] = smem[0];
  567.                             dmem[1] = smem[1];
  568.                             dmem += 2;
  569.                             smem += 2;
  570.                         }
  571.                     }
  572.                    
  573.                     if ((charCount & 1) != 0) {
  574.                         dmem[0] = smem[0];
  575.                     }
  576.                 }
  577.             }
  578.            
  579.             #if BUFFER_BUILDER_TRACING
  580.             public static int ToStringCount {
  581.                 get { return toStringCount; }
  582.             }
  583.            
  584.             public static double AvgAppendCount {
  585.                 get { return toStringCount == 0 ? 0 : (double)totalAppendCount / toStringCount; }
  586.             }
  587.            
  588.             public static int AvgLength {
  589.                 get { return toStringCount == 0 ? 0 : totalLength / toStringCount; }
  590.             }
  591.            
  592.             public static int MaxLength {
  593.                 get { return maxLength; }
  594.             }
  595.            
  596.             public static int MinLength {
  597.                 get { return minLength; }
  598.             }
  599.             #endif
  600.         }
  601.     }
  602. }

Developer Fusion