+ ASSERT(isRope());
+
+ // Allocate the buffer to hold the final string, position initially points to the end.
+ UChar* buffer;
+ if (PassRefPtr<UStringImpl> newImpl = UStringImpl::tryCreateUninitialized(m_length, buffer))
+ m_value = newImpl;
+ else {
+ for (unsigned i = 0; i < m_fiberCount; ++i) {
+ RopeImpl::deref(m_other.m_fibers[i]);
+ m_other.m_fibers[i] = 0;
+ }
+ m_fiberCount = 0;
+ ASSERT(!isRope());
+ ASSERT(m_value == UString());
+ if (exec)
+ throwOutOfMemoryError(exec);
+ return;
+ }
+ UChar* position = buffer + m_length;
+
+ // Start with the current RopeImpl.
+ Vector<RopeImpl::Fiber, 32> workQueue;
+ RopeImpl::Fiber currentFiber;
+ for (unsigned i = 0; i < (m_fiberCount - 1); ++i)
+ workQueue.append(m_other.m_fibers[i]);
+ currentFiber = m_other.m_fibers[m_fiberCount - 1];
+ while (true) {
+ if (RopeImpl::isRope(currentFiber)) {
+ RopeImpl* rope = static_cast<RopeImpl*>(currentFiber);
+ // Copy the contents of the current rope into the workQueue, with the last item in 'currentFiber'
+ // (we will be working backwards over the rope).
+ unsigned fiberCountMinusOne = rope->fiberCount() - 1;
+ for (unsigned i = 0; i < fiberCountMinusOne; ++i)
+ workQueue.append(rope->fibers()[i]);
+ currentFiber = rope->fibers()[fiberCountMinusOne];
+ } else {
+ UStringImpl* string = static_cast<UStringImpl*>(currentFiber);
+ unsigned length = string->length();
+ position -= length;
+ UStringImpl::copyChars(position, string->characters(), length);
+
+ // Was this the last item in the work queue?
+ if (workQueue.isEmpty()) {
+ // Create a string from the UChar buffer, clear the rope RefPtr.
+ ASSERT(buffer == position);
+ for (unsigned i = 0; i < m_fiberCount; ++i) {
+ RopeImpl::deref(m_other.m_fibers[i]);
+ m_other.m_fibers[i] = 0;
+ }
+ m_fiberCount = 0;
+
+ ASSERT(!isRope());
+ return;
+ }
+
+ // No! - set the next item up to process.
+ currentFiber = workQueue.last();
+ workQueue.removeLast();
+ }
+ }
+}
+
+// This function construsts a substring out of a rope without flattening by reusing the existing fibers.
+// This can reduce memory usage substantially. Since traversing ropes is slow the function will revert
+// back to flattening if the rope turns out to be long.
+JSString* JSString::substringFromRope(ExecState* exec, unsigned substringStart, unsigned substringLength)
+{
+ ASSERT(isRope());
+
+ JSGlobalData* globalData = &exec->globalData();
+
+ UString substringFibers[3];
+
+ unsigned fiberCount = 0;
+ unsigned substringFiberCount = 0;
+ unsigned substringEnd = substringStart + substringLength;
+ unsigned fiberEnd = 0;
+
+ RopeIterator end;
+ for (RopeIterator it(m_other.m_fibers, m_fiberCount); it != end; ++it) {
+ ++fiberCount;
+ UStringImpl* fiberString = *it;
+ unsigned fiberStart = fiberEnd;
+ fiberEnd = fiberStart + fiberString->length();
+ if (fiberEnd <= substringStart)
+ continue;
+ unsigned copyStart = std::max(substringStart, fiberStart);
+ unsigned copyEnd = std::min(substringEnd, fiberEnd);
+ if (copyStart == fiberStart && copyEnd == fiberEnd)
+ substringFibers[substringFiberCount++] = UString(fiberString);
+ else
+ substringFibers[substringFiberCount++] = UString(UStringImpl::create(fiberString, copyStart - fiberStart, copyEnd - copyStart));
+ if (fiberEnd >= substringEnd)
+ break;
+ if (fiberCount > resolveRopeForSubstringCutoff || substringFiberCount >= 3) {
+ // This turned out to be a really inefficient rope. Just flatten it.
+ resolveRope(exec);
+ return jsSubstring(&exec->globalData(), m_value, substringStart, substringLength);
+ }
+ }
+ ASSERT(substringFiberCount && substringFiberCount <= 3);
+
+ if (substringLength == 1) {
+ ASSERT(substringFiberCount == 1);
+ UChar c = substringFibers[0].data()[0];
+ if (c <= 0xFF)
+ return globalData->smallStrings.singleCharacterString(globalData, c);
+ }
+ if (substringFiberCount == 1)
+ return new (globalData) JSString(globalData, substringFibers[0]);
+ if (substringFiberCount == 2)
+ return new (globalData) JSString(globalData, substringFibers[0], substringFibers[1]);
+ return new (globalData) JSString(globalData, substringFibers[0], substringFibers[1], substringFibers[2]);
projects / apple / javascriptcore.git / blobdiff