wtf/text/StringBuilder.cpp

   1 /*
   2  * Copyright (C) 2010 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "StringBuilder.h"
  28
  29 #include "WTFString.h"
  30
  31 namespace WTF {
  32
  33 void StringBuilder::reifyString()
  34 {
  35     // Check if the string already exists.
  36     if (!m_string.isNull()) {
  37         ASSERT(m_string.length() == m_length);
  38         return;
  39     }
  40
  41     // Check for empty.
  42     if (!m_length) {
  43         m_string = StringImpl::empty();
  44         return;
  45     }
  46
  47     // Must be valid in the buffer, take a substring (unless string fills the buffer).
  48     ASSERT(m_buffer && m_length <= m_buffer->length());
  49     m_string = (m_length == m_buffer->length())
  50         ? m_buffer.get()
  51         : StringImpl::create(m_buffer, 0, m_length);
  52 }
  53
  54 void StringBuilder::resize(unsigned newSize)
  55 {
  56     // Check newSize < m_length, hence m_length > 0.
  57     ASSERT(newSize <= m_length);
  58     if (newSize == m_length)
  59         return;
  60     ASSERT(m_length);
  61
  62     // If there is a buffer, we only need to duplicate it if it has more than one ref.
  63     if (m_buffer) {
  64         if (!m_buffer->hasOneRef())
  65             allocateBuffer(m_buffer->characters(), m_buffer->length());
  66         m_length = newSize;
  67         m_string = String();
  68         return;
  69     }
  70
  71     // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
  72     ASSERT(!m_string.isEmpty());
  73     ASSERT(m_length == m_string.length());
  74     ASSERT(newSize < m_string.length());
  75     m_length = newSize;
  76     m_string = StringImpl::create(m_string.impl(), 0, newSize);
  77 }
  78
  79 void StringBuilder::reserveCapacity(unsigned newCapacity)
  80 {
  81     if (m_buffer) {
  82         // If there is already a buffer, then grow if necessary.
  83         if (newCapacity > m_buffer->length())
  84             allocateBuffer(m_buffer->characters(), newCapacity);
  85     } else {
  86         // Grow the string, if necessary.
  87         if (newCapacity > m_length)
  88             allocateBuffer(m_string.characters(), newCapacity);
  89     }
  90 }
  91
  92 // Allocate a new buffer, copying in currentCharacters (these may come from either m_string
  93 // or m_buffer,  neither will be reassigned until the copy has completed).
  94 void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
  95 {
  96     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
  97     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters);
  98     memcpy(m_bufferCharacters, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // This can't overflow.
  99
 100     // Update the builder state.
 101     m_buffer = buffer.release();
 102     m_string = String();
 103 }
 104
 105 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
 106 // return a pointer to the newly allocated storage.
 107 UChar* StringBuilder::appendUninitialized(unsigned length)
 108 {
 109     ASSERT(length);
 110
 111     // Calcuate the new size of the builder after appending.
 112     unsigned requiredLength = length + m_length;
 113     if (requiredLength < length)
 114         CRASH();
 115
 116     if (m_buffer) {
 117         // If the buffer is valid it must be at least as long as the current builder contents!
 118         ASSERT(m_buffer->length() >= m_length);
 119
 120         // Check if the buffer already has sufficient capacity.
 121         if (requiredLength <= m_buffer->length()) {
 122             unsigned currentLength = m_length;
 123             m_string = String();
 124             m_length = requiredLength;
 125             return m_bufferCharacters + currentLength;
 126         }
 127
 128         // We need to realloc the buffer.
 129         allocateBuffer(m_buffer->characters(), std::max(requiredLength, m_buffer->length() * 2));
 130     } else {
 131         ASSERT(m_string.length() == m_length);
 132         allocateBuffer(m_string.characters(), std::max(requiredLength, requiredLength * 2));
 133     }
 134
 135     UChar* result = m_bufferCharacters + m_length;
 136     m_length = requiredLength;
 137     return result;
 138 }
 139
 140 void StringBuilder::append(const UChar* characters, unsigned length)
 141 {
 142     if (!length)
 143         return;
 144     ASSERT(characters);
 145
 146     memcpy(appendUninitialized(length), characters, static_cast<size_t>(length) * 2);
 147 }
 148
 149 void StringBuilder::append(const char* characters, unsigned length)
 150 {
 151     if (!length)
 152         return;
 153     ASSERT(characters);
 154
 155     UChar* dest = appendUninitialized(length);
 156     const char* end = characters + length;
 157     while (characters < end)
 158         *(dest++) = *(const unsigned char*)(characters++);
 159 }
 160
 161 void StringBuilder::shrinkToFit()
 162 {
 163     // If the buffer is at least 80% full, don't bother copying. Need to tune this heuristic!
 164     if (m_buffer && m_buffer->length() > (m_length + (m_length >> 2))) {
 165         UChar* result;
 166         m_string = StringImpl::createUninitialized(m_length, result);
 167         memcpy(result, m_buffer->characters(), static_cast<size_t>(m_length) * 2); // This can't overflow.
 168         m_buffer = 0;
 169     }
 170 }
 171
 172 } // namespace WTF