1dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block/* 2dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * Copyright (C) 2009, 2010 Apple Inc. All rights reserved. 3dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * 4dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * Redistribution and use in source and binary forms, with or without 5dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * modification, are permitted provided that the following conditions 6dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * are met: 7dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * 1. Redistributions of source code must retain the above copyright 8dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * notice, this list of conditions and the following disclaimer. 9dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * 2. Redistributions in binary form must reproduce the above copyright 10dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * notice, this list of conditions and the following disclaimer in the 11dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * documentation and/or other materials provided with the distribution. 12dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * 13dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block */ 25dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 26dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block#ifndef RopeImpl_h 27dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block#define RopeImpl_h 28dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 29f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick#include <wtf/text/StringImpl.h> 30dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 31dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Blocknamespace JSC { 32dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 33dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Blockclass RopeImpl : public StringImplBase { 34dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Blockpublic: 35dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block // A RopeImpl is composed from a set of smaller strings called Fibers. 36f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick // Each Fiber in a rope is either StringImpl or another RopeImpl. 37dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block typedef StringImplBase* Fiber; 38dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 39dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block // Creates a RopeImpl comprising of 'fiberCount' Fibers. 40dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block // The RopeImpl is constructed in an uninitialized state - initialize must be called for each Fiber in the RopeImpl. 41dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block static PassRefPtr<RopeImpl> tryCreateUninitialized(unsigned fiberCount) 42dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block { 43dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block void* allocation; 44dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block if (tryFastMalloc(sizeof(RopeImpl) + (fiberCount - 1) * sizeof(Fiber)).getValue(allocation)) 45dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block return adoptRef(new (allocation) RopeImpl(fiberCount)); 46dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block return 0; 47dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block } 48dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 49dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block static bool isRope(Fiber fiber) 50dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block { 51dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block return !fiber->isStringImpl(); 52dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block } 53dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 54dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block static void deref(Fiber fiber) 55dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block { 56dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block if (isRope(fiber)) 57dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block static_cast<RopeImpl*>(fiber)->deref(); 58dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block else 59f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick static_cast<StringImpl*>(fiber)->deref(); 60dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block } 61dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 626c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen void initializeFiber(unsigned &index, Fiber fiber) 636c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen { 646c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen m_fibers[index++] = fiber; 656c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen fiber->ref(); 666c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen m_length += fiber->length(); 676c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen } 686c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen 696c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen unsigned fiberCount() { return m_size; } 706c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen Fiber* fibers() { return m_fibers; } 716c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen 726c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen ALWAYS_INLINE void deref() 736c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen { 746c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen m_refCountAndFlags -= s_refCountIncrement; 756c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen if (!(m_refCountAndFlags & s_refCountMask)) 766c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen destructNonRecursive(); 776c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen } 786c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen 79dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Blockprivate: 806c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen RopeImpl(unsigned fiberCount) 816c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen : StringImplBase(ConstructNonStringImpl) 826c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen , m_size(fiberCount) 836c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen { 846c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen } 85dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 86dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block void destructNonRecursive(); 87dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block void derefFibersNonRecursive(Vector<RopeImpl*, 32>& workQueue); 88dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 89dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block bool hasOneRef() { return (m_refCountAndFlags & s_refCountMask) == s_refCountIncrement; } 90dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 916c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen unsigned m_size; 92dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block Fiber m_fibers[1]; 93dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block}; 94dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 95dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block} 96dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block 97dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block#endif 98