← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/WTF/wtf/text/StringBuilder.cpp

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
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