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 173