Source/WTF/wtf/text/StringBuilder.cpp

   1 /*
   2  * Copyright (C) 2010, 2013 Apple Inc. All rights reserved.
   3  * Copyright (C) 2012 Google Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "config.h"
  28 #include "StringBuilder.h"
  29
  30 #include "IntegerToStringConversion.h"
  31 #include "WTFString.h"
  32
  33 namespace WTF {
  34
  35 static size_t expandedCapacity(size_t capacity, size_t newLength)
  36 {
  37     static const size_t minimumCapacity = 16;
  38     return std::max(capacity, std::max(minimumCapacity, newLength * 2));
  39 }
  40
  41 void StringBuilder::reifyString() const
  42 {
  43     // Check if the string already exists.
  44     if (!m_string.isNull()) {
  45         ASSERT(m_string.length() == m_length);
  46         return;
  47     }
  48
  49     // Check for empty.
  50     if (!m_length) {
  51         m_string = StringImpl::empty();
  52         return;
  53     }
  54
  55     // Must be valid in the buffer, take a substring (unless string fills the buffer).
  56     ASSERT(m_buffer && m_length <= m_buffer->length());
  57     m_string = (m_length == m_buffer->length())
  58         ? m_buffer.get()
  59         : StringImpl::create(m_buffer, 0, m_length);
  60
  61     if (m_buffer->has16BitShadow() && m_valid16BitShadowLength < m_length)
  62         m_buffer->upconvertCharacters(m_valid16BitShadowLength, m_length);
  63
  64     m_valid16BitShadowLength = m_length;
  65 }
  66
  67 void StringBuilder::resize(unsigned newSize)
  68 {
  69     // Check newSize < m_length, hence m_length > 0.
  70     ASSERT(newSize <= m_length);
  71     if (newSize == m_length)
  72         return;
  73     ASSERT(m_length);
  74
  75     // If there is a buffer, we only need to duplicate it if it has more than one ref.
  76     if (m_buffer) {
  77         m_string = String(); // Clear the string to remove the reference to m_buffer if any before checking the reference count of m_buffer.
  78         if (!m_buffer->hasOneRef()) {
  79             if (m_buffer->is8Bit())
  80                 allocateBuffer(m_buffer->characters8(), m_buffer->length());
  81             else
  82                 allocateBuffer(m_buffer->characters16(), m_buffer->length());
  83         }
  84         m_length = newSize;
  85         return;
  86     }
  87
  88     // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
  89     ASSERT(!m_string.isEmpty());
  90     ASSERT(m_length == m_string.length());
  91     ASSERT(newSize < m_string.length());
  92     m_length = newSize;
  93     m_string = StringImpl::create(m_string.impl(), 0, newSize);
  94 }
  95
  96 // Allocate a new 8 bit buffer, copying in currentCharacters (these may come from either m_string
  97 // or m_buffer, neither will be reassigned until the copy has completed).
  98 void StringBuilder::allocateBuffer(const LChar* currentCharacters, unsigned requiredLength)
  99 {
 100     ASSERT(m_is8Bit);
 101     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
 102     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters8);
 103     memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length) * sizeof(LChar)); // This can't overflow.
 104
 105     // Update the builder state.
 106     m_buffer = buffer.release();
 107     m_string = String();
 108 }
 109
 110 // Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
 111 // or m_buffer,  neither will be reassigned until the copy has completed).
 112 void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
 113 {
 114     ASSERT(!m_is8Bit);
 115     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
 116     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
 117     memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // This can't overflow.
 118
 119     // Update the builder state.
 120     m_buffer = buffer.release();
 121     m_string = String();
 122 }
 123
 124 // Allocate a new 16 bit buffer, copying in currentCharacters (which is 8 bit and may come
 125 // from either m_string or m_buffer, neither will be reassigned until the copy has completed).
 126 void StringBuilder::allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength)
 127 {
 128     ASSERT(m_is8Bit);
 129     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
 130     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
 131     for (unsigned i = 0; i < m_length; ++i)
 132         m_bufferCharacters16[i] = currentCharacters[i];
 133
 134     m_is8Bit = false;
 135
 136     // Update the builder state.
 137     m_buffer = buffer.release();
 138     m_string = String();
 139 }
 140
 141 template <>
 142 void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
 143 {
 144     // If the buffer has only one ref (by this StringBuilder), reallocate it,
 145     // otherwise fall back to "allocate and copy" method.
 146     m_string = String();
 147
 148     ASSERT(m_is8Bit);
 149     ASSERT(m_buffer->is8Bit());
 150
 151     if (m_buffer->hasOneRef())
 152         m_buffer = StringImpl::reallocate(m_buffer.release(), requiredLength, m_bufferCharacters8);
 153     else
 154         allocateBuffer(m_buffer->characters8(), requiredLength);
 155 }
 156
 157 template <>
 158 void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
 159 {
 160     // If the buffer has only one ref (by this StringBuilder), reallocate it,
 161     // otherwise fall back to "allocate and copy" method.
 162     m_string = String();
 163
 164     if (m_buffer->is8Bit())
 165         allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
 166     else if (m_buffer->hasOneRef())
 167         m_buffer = StringImpl::reallocate(m_buffer.release(), requiredLength, m_bufferCharacters16);
 168     else
 169         allocateBuffer(m_buffer->characters16(), requiredLength);
 170 }
 171
 172 void StringBuilder::reserveCapacity(unsigned newCapacity)
 173 {
 174     if (m_buffer) {
 175         // If there is already a buffer, then grow if necessary.
 176         if (newCapacity > m_buffer->length()) {
 177             if (m_buffer->is8Bit())
 178                 reallocateBuffer<LChar>(newCapacity);
 179             else
 180                 reallocateBuffer<UChar>(newCapacity);
 181         }
 182     } else {
 183         // Grow the string, if necessary.
 184         if (newCapacity > m_length) {
 185             if (!m_length) {
 186                 LChar* nullPlaceholder = 0;
 187                 allocateBuffer(nullPlaceholder, newCapacity);
 188             } else if (m_string.is8Bit())
 189                 allocateBuffer(m_string.characters8(), newCapacity);
 190             else
 191                 allocateBuffer(m_string.characters16(), newCapacity);
 192         }
 193     }
 194 }
 195
 196 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
 197 // return a pointer to the newly allocated storage.
 198 template <typename CharType>
 199 ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
 200 {
 201     ASSERT(length);
 202
 203     // Calculate the new size of the builder after appending.
 204     unsigned requiredLength = length + m_length;
 205     if (requiredLength < length)
 206         CRASH();
 207
 208     if ((m_buffer) && (requiredLength <= m_buffer->length())) {
 209         // If the buffer is valid it must be at least as long as the current builder contents!
 210         ASSERT(m_buffer->length() >= m_length);
 211         unsigned currentLength = m_length;
 212         m_string = String();
 213         m_length = requiredLength;
 214         return getBufferCharacters<CharType>() + currentLength;
 215     }
 216
 217     return appendUninitializedSlow<CharType>(requiredLength);
 218 }
 219
 220 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
 221 // return a pointer to the newly allocated storage.
 222 template <typename CharType>
 223 CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
 224 {
 225     ASSERT(requiredLength);
 226
 227     if (m_buffer) {
 228         // If the buffer is valid it must be at least as long as the current builder contents!
 229         ASSERT(m_buffer->length() >= m_length);
 230
 231         reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
 232     } else {
 233         ASSERT(m_string.length() == m_length);
 234         allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
 235     }
 236
 237     CharType* result = getBufferCharacters<CharType>() + m_length;
 238     m_length = requiredLength;
 239     return result;
 240 }
 241
 242 void StringBuilder::append(const UChar* characters, unsigned length)
 243 {
 244     if (!length)
 245         return;
 246
 247     ASSERT(characters);
 248
 249     if (m_is8Bit) {
 250         if (length == 1 && !(*characters & ~0xff)) {
 251             // Append as 8 bit character
 252             LChar lChar = static_cast<LChar>(*characters);
 253             append(&lChar, 1);
 254             return;
 255         }
 256
 257         // Calculate the new size of the builder after appending.
 258         unsigned requiredLength = length + m_length;
 259         if (requiredLength < length)
 260             CRASH();
 261
 262         if (m_buffer) {
 263             // If the buffer is valid it must be at least as long as the current builder contents!
 264             ASSERT(m_buffer->length() >= m_length);
 265
 266             allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
 267         } else {
 268             ASSERT(m_string.length() == m_length);
 269             allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
 270         }
 271
 272         memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));
 273         m_length = requiredLength;
 274     } else
 275         memcpy(appendUninitialized<UChar>(length), characters, static_cast<size_t>(length) * sizeof(UChar));
 276 }
 277
 278 void StringBuilder::append(const LChar* characters, unsigned length)
 279 {
 280     if (!length)
 281         return;
 282     ASSERT(characters);
 283
 284     if (m_is8Bit) {
 285         LChar* dest = appendUninitialized<LChar>(length);
 286         if (length > 8)
 287             memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
 288         else {
 289             const LChar* end = characters + length;
 290             while (characters < end)
 291                 *(dest++) = *(characters++);
 292         }
 293     } else {
 294         UChar* dest = appendUninitialized<UChar>(length);
 295         const LChar* end = characters + length;
 296         while (characters < end)
 297             *(dest++) = *(characters++);
 298     }
 299 }
 300
 301 void StringBuilder::appendNumber(int number)
 302 {
 303     numberToStringSigned<StringBuilder>(number, this);
 304 }
 305
 306 void StringBuilder::appendNumber(unsigned int number)
 307 {
 308     numberToStringUnsigned<StringBuilder>(number, this);
 309 }
 310
 311 void StringBuilder::appendNumber(long number)
 312 {
 313     numberToStringSigned<StringBuilder>(number, this);
 314 }
 315
 316 void StringBuilder::appendNumber(unsigned long number)
 317 {
 318     numberToStringUnsigned<StringBuilder>(number, this);
 319 }
 320
 321 void StringBuilder::appendNumber(long long number)
 322 {
 323     numberToStringSigned<StringBuilder>(number, this);
 324 }
 325
 326 void StringBuilder::appendNumber(unsigned long long number)
 327 {
 328     numberToStringUnsigned<StringBuilder>(number, this);
 329 }
 330
 331 bool StringBuilder::canShrink() const
 332 {
 333     // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
 334     return m_buffer && m_buffer->length() > (m_length + (m_length >> 2));
 335 }
 336
 337 void StringBuilder::shrinkToFit()
 338 {
 339     if (canShrink()) {
 340         if (m_is8Bit)
 341             reallocateBuffer<LChar>(m_length);
 342         else
 343             reallocateBuffer<UChar>(m_length);
 344         m_string = m_buffer;
 345         m_buffer = 0;
 346     }
 347 }
 348
 349 } // namespace WTF