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
31namespace WTF {
32
33void 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
54void 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
79void 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).
94void 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.
107UChar* 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
140void 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
149void 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
161void 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