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