a143d0a10c1ef68ba08f55ca8d4ec6a52cc15c10
[WebKit-https.git] / Source / WTF / wtf / text / StringBuilder.cpp
1 /*
2  * Copyright (C) 2010 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 const unsigned minimumCapacity = 16;
36
37 void StringBuilder::reifyString() const
38 {
39     // Check if the string already exists.
40     if (!m_string.isNull()) {
41         ASSERT(m_string.length() == m_length);
42         return;
43     }
44
45     // Check for empty.
46     if (!m_length) {
47         m_string = StringImpl::empty();
48         return;
49     }
50
51     // Must be valid in the buffer, take a substring (unless string fills the buffer).
52     ASSERT(m_buffer && m_length <= m_buffer->length());
53     m_string = (m_length == m_buffer->length())
54         ? m_buffer.get()
55         : StringImpl::create(m_buffer, 0, m_length);
56
57     if (m_buffer->has16BitShadow() && m_valid16BitShadowLength < m_length)
58         m_buffer->upconvertCharacters(m_valid16BitShadowLength, m_length);
59
60     m_valid16BitShadowLength = m_length;
61 }
62
63 void StringBuilder::resize(unsigned newSize)
64 {
65     // Check newSize < m_length, hence m_length > 0.
66     ASSERT(newSize <= m_length);
67     if (newSize == m_length)
68         return;
69     ASSERT(m_length);
70
71     // If there is a buffer, we only need to duplicate it if it has more than one ref.
72     if (m_buffer) {
73         m_string = String(); // Clear the string to remove the reference to m_buffer if any before checking the reference count of m_buffer.
74         if (!m_buffer->hasOneRef()) {
75             if (m_buffer->is8Bit())
76                 allocateBuffer(m_buffer->characters8(), m_buffer->length());
77             else
78                 allocateBuffer(m_buffer->characters16(), m_buffer->length());
79         }
80         m_length = newSize;
81         return;
82     }
83
84     // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
85     ASSERT(!m_string.isEmpty());
86     ASSERT(m_length == m_string.length());
87     ASSERT(newSize < m_string.length());
88     m_length = newSize;
89     m_string = StringImpl::create(m_string.impl(), 0, newSize);
90 }
91
92 // Allocate a new 8 bit 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 LChar* currentCharacters, unsigned requiredLength)
95 {
96     ASSERT(m_is8Bit);
97     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
98     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters8);
99     memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length) * sizeof(LChar)); // This can't overflow.
100     
101     // Update the builder state.
102     m_buffer = buffer.release();
103     m_string = String();
104 }
105
106 // Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
107 // or m_buffer,  neither will be reassigned until the copy has completed).
108 void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
109 {
110     ASSERT(!m_is8Bit);
111     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
112     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
113     memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // This can't overflow.
114     
115     // Update the builder state.
116     m_buffer = buffer.release();
117     m_string = String();
118 }
119
120 // Allocate a new 16 bit buffer, copying in currentCharacters (which is 8 bit and may come
121 // from either m_string or m_buffer, neither will be reassigned until the copy has completed).
122 void StringBuilder::allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength)
123 {
124     ASSERT(m_is8Bit);
125     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
126     RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
127     for (unsigned i = 0; i < m_length; ++i)
128         m_bufferCharacters16[i] = currentCharacters[i];
129     
130     m_is8Bit = false;
131     
132     // Update the builder state.
133     m_buffer = buffer.release();
134     m_string = String();
135 }
136
137 template <>
138 void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
139 {
140     // If the buffer has only one ref (by this StringBuilder), reallocate it,
141     // otherwise fall back to "allocate and copy" method.
142     m_string = String();
143     
144     ASSERT(m_is8Bit);
145     ASSERT(m_buffer->is8Bit());
146     
147     if (m_buffer->hasOneRef())
148         m_buffer = StringImpl::reallocate(m_buffer.release(), requiredLength, m_bufferCharacters8);
149     else
150         allocateBuffer(m_buffer->characters8(), requiredLength);
151 }
152
153 template <>
154 void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
155 {
156     // If the buffer has only one ref (by this StringBuilder), reallocate it,
157     // otherwise fall back to "allocate and copy" method.
158     m_string = String();
159     
160     if (m_buffer->is8Bit())
161         allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
162     else if (m_buffer->hasOneRef())
163         m_buffer = StringImpl::reallocate(m_buffer.release(), requiredLength, m_bufferCharacters16);
164     else
165         allocateBuffer(m_buffer->characters16(), requiredLength);
166 }
167
168 void StringBuilder::reserveCapacity(unsigned newCapacity)
169 {
170     if (m_buffer) {
171         // If there is already a buffer, then grow if necessary.
172         if (newCapacity > m_buffer->length()) {
173             if (m_buffer->is8Bit())
174                 reallocateBuffer<LChar>(newCapacity);
175             else
176                 reallocateBuffer<UChar>(newCapacity);
177         }
178     } else {
179         // Grow the string, if necessary.
180         if (newCapacity > m_length) {
181             if (!m_length) {
182                 LChar* nullPlaceholder = 0;
183                 allocateBuffer(nullPlaceholder, newCapacity);
184             } else if (m_string.is8Bit())
185                 allocateBuffer(m_string.characters8(), newCapacity);
186             else
187                 allocateBuffer(m_string.characters16(), newCapacity);
188         }
189     }
190 }
191
192 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
193 // return a pointer to the newly allocated storage.
194 template <typename CharType>
195 ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
196 {
197     ASSERT(length);
198
199     // Calculate the new size of the builder after appending.
200     unsigned requiredLength = length + m_length;
201     if (requiredLength < length)
202         CRASH();
203
204     if ((m_buffer) && (requiredLength <= m_buffer->length())) {
205         // If the buffer is valid it must be at least as long as the current builder contents!
206         ASSERT(m_buffer->length() >= m_length);
207         unsigned currentLength = m_length;
208         m_string = String();
209         m_length = requiredLength;
210         return getBufferCharacters<CharType>() + currentLength;
211     }
212     
213     return appendUninitializedSlow<CharType>(requiredLength);
214 }
215
216 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
217 // return a pointer to the newly allocated storage.
218 template <typename CharType>
219 CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
220 {
221     ASSERT(requiredLength);
222
223     if (m_buffer) {
224         // If the buffer is valid it must be at least as long as the current builder contents!
225         ASSERT(m_buffer->length() >= m_length);
226         
227         reallocateBuffer<CharType>(std::max(requiredLength, std::max(minimumCapacity, m_buffer->length() * 2)));
228     } else {
229         ASSERT(m_string.length() == m_length);
230         allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
231     }
232     
233     CharType* result = getBufferCharacters<CharType>() + m_length;
234     m_length = requiredLength;
235     return result;
236 }
237
238 void StringBuilder::append(const UChar* characters, unsigned length)
239 {
240     if (!length)
241         return;
242
243     ASSERT(characters);
244
245     if (m_is8Bit) {
246         if (length == 1 && !(*characters & ~0xff)) {
247             // Append as 8 bit character
248             LChar lChar = static_cast<LChar>(*characters);
249             append(&lChar, 1);
250             return;
251         }
252
253         // Calculate the new size of the builder after appending.
254         unsigned requiredLength = length + m_length;
255         if (requiredLength < length)
256             CRASH();
257         
258         if (m_buffer) {
259             // If the buffer is valid it must be at least as long as the current builder contents!
260             ASSERT(m_buffer->length() >= m_length);
261             
262             allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
263         } else {
264             ASSERT(m_string.length() == m_length);
265             allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
266         }
267
268         memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));        
269         m_length = requiredLength;
270     } else
271         memcpy(appendUninitialized<UChar>(length), characters, static_cast<size_t>(length) * sizeof(UChar));
272 }
273
274 void StringBuilder::append(const LChar* characters, unsigned length)
275 {
276     if (!length)
277         return;
278     ASSERT(characters);
279
280     if (m_is8Bit) {
281         LChar* dest = appendUninitialized<LChar>(length);
282         if (length > 8)
283             memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
284         else {
285             const LChar* end = characters + length;
286             while (characters < end)
287                 *(dest++) = *(characters++);
288         }
289     } else {
290         UChar* dest = appendUninitialized<UChar>(length);
291         const LChar* end = characters + length;
292         while (characters < end)
293             *(dest++) = *(characters++);
294     }
295 }
296
297 void StringBuilder::appendNumber(int number)
298 {
299     numberToStringSigned<StringBuilder>(number, this);
300 }
301
302 void StringBuilder::appendNumber(unsigned int number)
303 {
304     numberToStringUnsigned<StringBuilder>(number, this);
305 }
306
307 void StringBuilder::appendNumber(long number)
308 {
309     numberToStringSigned<StringBuilder>(number, this);
310 }
311
312 void StringBuilder::appendNumber(unsigned long number)
313 {
314     numberToStringUnsigned<StringBuilder>(number, this);
315 }
316
317 void StringBuilder::appendNumber(long long number)
318 {
319     numberToStringSigned<StringBuilder>(number, this);
320 }
321
322 void StringBuilder::appendNumber(unsigned long long number)
323 {
324     numberToStringUnsigned<StringBuilder>(number, this);
325 }
326
327 bool StringBuilder::canShrink() const
328 {
329     // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
330     return m_buffer && m_buffer->length() > (m_length + (m_length >> 2));
331 }
332
333 void StringBuilder::shrinkToFit()
334 {
335     if (canShrink()) {
336         if (m_is8Bit)
337             reallocateBuffer<LChar>(m_length);
338         else
339             reallocateBuffer<UChar>(m_length);
340         m_string = m_buffer;
341         m_buffer = 0;
342     }
343 }
344
345 } // namespace WTF