Back to index

lightning-sunbird  0.9+nobinonly
Public Types | Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | Friends
txNodeSet Class Reference

Implementation of an XPath NodeSet. More...

#include <txNodeSet.h>

Inheritance diagram for txNodeSet:
Inheritance graph
[legend]
Collaboration diagram for txNodeSet:
Collaboration graph
[legend]

List of all members.

Public Types

enum  ResultType {
  NODESET, BOOLEAN, NUMBER, STRING,
  RESULT_TREE_FRAGMENT
}

Public Member Functions

 txNodeSet (txResultRecycler *aRecycler)
 Creates a new empty NodeSet.
 txNodeSet (const txXPathNode &aNode, txResultRecycler *aRecycler)
 Creates a new NodeSet with one node.
 txNodeSet (const txNodeSet &aSource, txResultRecycler *aRecycler)
 Creates a new txNodeSet, copying the node references from the source NodeSet.
virtual ~txNodeSet ()
 Destructor for txNodeSet, deletes the nodes.
nsresult add (const txXPathNode &aNode)
 Adds the specified txXPathNode to this NodeSet if it is not already in this NodeSet.
nsresult add (const txNodeSet &aNodes)
 Adds the nodes in specified NodeSet to this NodeSet.
nsresult addAndTransfer (txNodeSet *aNodes)
nsresult append (const txXPathNode &aNode)
 Append API These functions should be used with care.
nsresult append (const txNodeSet &aNodes)
 Appends the nodes in the specified NodeSet to the end of this NodeSet.
void setReverse ()
 API to implement reverse axes in LocationStep.
void unsetReverse ()
nsresult mark (PRInt32 aIndex)
 API to implement predicates in PredicateExpr.
nsresult sweep ()
void clear ()
 Removes all nodes from this nodeset.
PRInt32 indexOf (const txXPathNode &aNode) const
 Returns the index of the specified Node, or -1 if the Node is not contained in the NodeSet.
PRBool contains (const txXPathNode &aNode) const
 Returns true if the specified Node is contained in the set.
const txXPathNodeget (PRInt32 aIndex) const
 Returns the Node at the specified node in this NodeSet.
PRBool isEmpty () const
 Returns true if there are no Nodes in the NodeSet.
PRInt32 size () const
 Returns the number of elements in the NodeSet.
void AddRef ()
void Release ()
virtual short getResultType ()=0
 Returns the type of ExprResult represented.
virtual void stringValue (nsAString &str)=0
 Creates a String representation of this ExprResult.
virtual nsAString * stringValuePointer ()=0
 Returns a pointer to the stringvalue if possible.
virtual MBool booleanValue ()=0
 Converts this ExprResult to a Boolean (MBool) value.
virtual double numberValue ()=0
 Converts this ExprResult to a Number (double) value.

Private Types

typedef void(* transferOp )(txXPathNode *aDest, const txXPathNode *aStart, const txXPathNode *aEnd)

Private Member Functions

PRBool ensureGrowSize (PRInt32 aSize)
 Ensure that this nodeset can take another aSize nodes.
txXPathNodefindPosition (const txXPathNode &aNode, txXPathNode *aFirst, txXPathNode *aLast, PRBool &aDupe) const
 Finds position in the buffer where a node should be inserted to keep the nodeset in document order.
nsresult add (const txNodeSet &aNodes, transferOp aTransfer)
 add(aNodeSet, aTransferOp)

Static Private Member Functions

static void toString (const txNodeSet &aNodes, nsAString &aResult)
static void copyElements (txXPathNode *aDest, const txXPathNode *aStart, const txXPathNode *aEnd)
static void transferElements (txXPathNode *aDest, const txXPathNode *aStart, const txXPathNode *aEnd)

Private Attributes

txXPathNodemStart
txXPathNodemEnd
txXPathNodemStartBuffer
txXPathNodemEndBuffer
PRInt32 mDirection
PRPackedBoolmMarks

Friends

class txResultRecycler

Detailed Description

Implementation of an XPath NodeSet.

Definition at line 51 of file txNodeSet.h.


Member Typedef Documentation

Definition at line 231 of file txNodeSet.h.


Member Enumeration Documentation

enum txAExprResult::ResultType [inherited]
Enumerator:
NODESET 
BOOLEAN 
NUMBER 
STRING 
RESULT_TREE_FRAGMENT 

Definition at line 61 of file ExprResult.h.


Constructor & Destructor Documentation

Creates a new empty NodeSet.

Definition at line 53 of file txNodeSet.cpp.

txNodeSet::txNodeSet ( const txXPathNode aNode,
txResultRecycler aRecycler 
)

Creates a new NodeSet with one node.

Definition at line 64 of file txNodeSet.cpp.

Here is the call graph for this function:

txNodeSet::txNodeSet ( const txNodeSet aSource,
txResultRecycler aRecycler 
)

Creates a new txNodeSet, copying the node references from the source NodeSet.

Definition at line 81 of file txNodeSet.cpp.

Here is the call graph for this function:

txNodeSet::~txNodeSet ( ) [virtual]

Destructor for txNodeSet, deletes the nodes.

Definition at line 93 of file txNodeSet.cpp.

{
    delete [] mMarks;

    if (mStartBuffer) {
        while (mStart < mEnd) {
            mStart->~txXPathNode();
            ++mStart;
        }

        nsMemory::Free(mStartBuffer);
    }
}

Member Function Documentation

Adds the specified txXPathNode to this NodeSet if it is not already in this NodeSet.

The node is inserted according to document order.

Parameters:
aNodethe txXPathNode to add to the NodeSet
Returns:
errorcode.

Definition at line 107 of file txNodeSet.cpp.

{
    NS_ASSERTION(mDirection == kForward,
                 "only append(aNode) is supported on reversed nodesets");

    if (isEmpty()) {
        return append(aNode);
    }

    PRBool dupe;
    txXPathNode* pos = findPosition(aNode, mStart, mEnd, dupe);

    if (dupe) {
        return NS_OK;
    }

    // save pos, ensureGrowSize messes with the pointers
    PRInt32 moveSize = mEnd - pos;
    PRInt32 offset = pos - mStart;
    if (!ensureGrowSize(1)) {
        return NS_ERROR_OUT_OF_MEMORY;
    }
    // set pos to where it was
    pos = mStart + offset;

    if (moveSize > 0) {
        memmove(pos + 1, pos, moveSize * sizeof(txXPathNode));
    }

    new(pos) txXPathNode(aNode);
    ++mEnd;

    return NS_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Adds the nodes in specified NodeSet to this NodeSet.

The resulting NodeSet is sorted in document order and does not contain any duplicate nodes.

Parameters:
aNodesthe NodeSet to add, must be in document order.
Returns:
errorcode.

Definition at line 142 of file txNodeSet.cpp.

{
    return add(aNodes, copyElements);
}

Here is the call graph for this function:

nsresult txNodeSet::add ( const txNodeSet aNodes,
transferOp  aTransfer 
) [private]

add(aNodeSet, aTransferOp)

The code is optimized to make a minimum number of calls to Node::compareDocumentPosition. The idea is this: We have the two nodesets (number indicate "document position")

1 3 7 <- source 1 2 3 6 8 9 <- source 2 _ _ _ _ _ _ _ _ <- result

When merging these nodesets into the result, the nodes are transfered in chunks to the end of the buffer so that each chunk does not contain a node from the other nodeset, in document order.

We select the last non-transfered node in the first nodeset and find where in the other nodeset it would be inserted. In this case we would take the 7 from the first nodeset and find the position between the 6 and 8 in the second. We then take the nodes after the insert-position and transfer them to the end of the resulting nodeset. Which in this case means that we first transfered the 8 and 9 nodes, giving us the following:

1 3 7 <- source 1 2 3 6 <- source 2 _ _ _ _ _ _ 8 9 <- result

The corresponding procedure is done for the second nodeset, that is the insertion position of the 6 in the first nodeset is found, which is between the 3 and the 7. The 7 is memmoved (as it stays within the same nodeset) to the result buffer.

As the result buffer is filled from the end, it is safe to share the buffer between this nodeset and the result.

This is repeated until both of the nodesets are empty.

If we find a duplicate node when searching for where insertposition we check for sequences of duplicate nodes, which can be optimized.

Definition at line 205 of file txNodeSet.cpp.

{
    NS_ASSERTION(mDirection == kForward,
                 "only append(aNode) is supported on reversed nodesets");

    if (aNodes.isEmpty()) {
        return NS_OK;
    }

    if (!ensureGrowSize(aNodes.size())) {
        return NS_ERROR_OUT_OF_MEMORY;
    }

    // This is probably a rather common case, so lets try to shortcut.
    if (mStart == mEnd ||
        txXPathNodeUtils::comparePosition(mEnd[-1], *aNodes.mStart) < 0) {
        aTransfer(mEnd, aNodes.mStart, aNodes.mEnd);
        mEnd += aNodes.size();

        return NS_OK;
    }

    // Last element in this nodeset
    txXPathNode* thisPos = mEnd;

    // Last element of the other nodeset
    txXPathNode* otherPos = aNodes.mEnd;

    // Pointer to the insertion point in this nodeset
    txXPathNode* insertPos = mEndBuffer;

    PRBool dupe;
    txXPathNode* pos;
    PRInt32 count;
    while (thisPos > mStart || otherPos > aNodes.mStart) {
        // Find where the last remaining node of this nodeset would
        // be inserted in the other nodeset.
        if (thisPos > mStart) {
            pos = findPosition(thisPos[-1], aNodes.mStart, otherPos, dupe);

            if (dupe) {
                --thisPos; // this is already added
                // check dupe sequence
                while (thisPos > mStart && pos > aNodes.mStart &&
                       thisPos[-1] == pos[-1]) {
                    --thisPos;
                    --pos;
                }
            }
        }
        else {
            pos = aNodes.mStart;
        }

        // Transfer the otherNodes after the insertion point to the result
        count = otherPos - pos;
        if (count > 0) {
            insertPos -= count;
            aTransfer(insertPos, pos, otherPos);
            otherPos -= count;
        }

        // Find where the last remaining node of the otherNodeset would
        // be inserted in this nodeset.
        if (otherPos > aNodes.mStart) {
            pos = findPosition(otherPos[-1], mStart, thisPos, dupe);

            if (dupe) {
                --otherPos; // this is already added
                // check dupe sequence
                while (otherPos > aNodes.mStart && pos > mStart &&
                       otherPos[-1] == pos[-1]) {
                    --otherPos;
                    --pos;
                }
            }
        }
        else {
            pos = mStart;
        }

        // Move the nodes from this nodeset after the insertion point
        // to the result
        count = thisPos - pos;
        if (count > 0) {
            insertPos -= count;
            memmove(insertPos, pos, count * sizeof(txXPathNode));
            thisPos -= count;
        }
    }
    mStart = insertPos;
    mEnd = mEndBuffer;
    
    return NS_OK;
}

Here is the call graph for this function:

Definition at line 147 of file txNodeSet.cpp.

{
    // failure is out-of-memory, transfer didn't happen
    nsresult rv = add(*aNodes, transferElements);
    NS_ENSURE_SUCCESS(rv, rv);

#ifdef TX_DONT_RECYCLE_BUFFER
    if (aNodes->mStartBuffer) {
        nsMemory::Free(aNodes->mStartBuffer);
        aNodes->mStartBuffer = aNodes->mEndBuffer = nsnull;
    }
#endif
    aNodes->mStart = aNodes->mEnd = aNodes->mStartBuffer;

    return NS_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void txAExprResult::AddRef ( void  ) [inline, inherited]

Definition at line 72 of file ExprResult.h.

    {
        ++mRefCnt;
    }

Append API These functions should be used with care.

They are intended to be used when the caller assures that the resulting NodeSet remains in document order. Abuse will break document order, and cause errors in the result. These functions are significantly faster than the add API, as no order info operations will be performed. Appends the specified Node to the end of this NodeSet

Parameters:
aNodethe Node to append to the NodeSet
Returns:
errorcode.

They are intended to be used when the caller assures that the resulting nodeset remains in document order. Abuse will break document order, and cause errors in the result. These functions are significantly faster than the add API, as no order info operations will be performed.

Definition at line 312 of file txNodeSet.cpp.

{
    if (!ensureGrowSize(1)) {
        return NS_ERROR_OUT_OF_MEMORY;
    }

    if (mDirection == kForward) {
        new(mEnd) txXPathNode(aNode);
        ++mEnd;

        return NS_OK;
    }

    new(--mStart) txXPathNode(aNode);

    return NS_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Appends the nodes in the specified NodeSet to the end of this NodeSet.

Parameters:
aNodesthe NodeSet to append to the NodeSet
Returns:
errorcode.

Definition at line 331 of file txNodeSet.cpp.

{
    NS_ASSERTION(mDirection == kForward,
                 "only append(aNode) is supported on reversed nodesets");

    if (aNodes.isEmpty()) {
        return NS_OK;
    }

    PRInt32 appended = aNodes.size();
    if (!ensureGrowSize(appended)) {
        return NS_ERROR_OUT_OF_MEMORY;
    }

    copyElements(mEnd, aNodes.mStart, aNodes.mEnd);
    mEnd += appended;

    return NS_OK;
}

Here is the call graph for this function:

virtual MBool txAExprResult::booleanValue ( ) [pure virtual, inherited]

Converts this ExprResult to a Boolean (MBool) value.

Returns:
the Boolean value

Here is the caller graph for this function:

Removes all nodes from this nodeset.

Definition at line 412 of file txNodeSet.cpp.

{
    while (mStart < mEnd) {
        mStart->~txXPathNode();
        ++mStart;
    }
#ifdef TX_DONT_RECYCLE_BUFFER
    if (mStartBuffer) {
        nsMemory::Free(mStartBuffer);
        mStartBuffer = mEndBuffer = nsnull;
    }
#endif
    mStart = mEnd = mStartBuffer;
    delete [] mMarks;
    mMarks = nsnull;
    mDirection = kForward;
}

Here is the caller graph for this function:

PRBool txNodeSet::contains ( const txXPathNode aNode) const [inline]

Returns true if the specified Node is contained in the set.

Parameters:
aNodethe Node to search for
Returns:
true if specified Node is contained in the NodeSet

Definition at line 166 of file txNodeSet.h.

    {
        return indexOf(aNode) >= 0;
    }

Here is the call graph for this function:

void txNodeSet::copyElements ( txXPathNode aDest,
const txXPathNode aStart,
const txXPathNode aEnd 
) [static, private]

Definition at line 609 of file txNodeSet.cpp.

{
    const txXPathNode* pos = aStart;
    while (pos < aEnd) {
        new(aDest) txXPathNode(*pos);
        ++aDest;
        ++pos;
    }
}

Here is the caller graph for this function:

Ensure that this nodeset can take another aSize nodes.

Changes mStart and mEnd as well as mBufferStart and mBufferEnd.

Definition at line 498 of file txNodeSet.cpp.

{
    // check if there is enough place in the buffer as is
    if (mDirection == kForward && aSize <= mEndBuffer - mEnd) {
        return PR_TRUE;
    }

    if (mDirection == kReversed && aSize <= mStart - mStartBuffer) {
        return PR_TRUE;
    }

    // check if we just have to align mStart to have enough space
    PRInt32 oldSize = mEnd - mStart;
    PRInt32 oldLength = mEndBuffer - mStartBuffer;
    PRInt32 ensureSize = oldSize + aSize;
    if (ensureSize <= oldLength) {
        // just move the buffer
        txXPathNode* dest = mStartBuffer;
        if (mDirection == kReversed) {
            dest = mEndBuffer - oldSize;
        }
        memmove(dest, mStart, oldSize * sizeof(txXPathNode));
        mStart = dest;
        mEnd = dest + oldSize;
            
        return PR_TRUE;
    }

    // This isn't 100% safe. But until someone manages to make a 1gig nodeset
    // it should be ok.
    PRInt32 newLength = PR_MAX(oldLength, kTxNodeSetMinSize);

    while (newLength < ensureSize) {
        newLength *= kTxNodeSetGrowFactor;
    }

    txXPathNode* newArr = NS_STATIC_CAST(txXPathNode*,
                                         nsMemory::Alloc(newLength *
                                                         sizeof(txXPathNode)));
    if (!newArr) {
        return PR_FALSE;
    }

    txXPathNode* dest = newArr;
    if (mDirection == kReversed) {
        dest += newLength - oldSize;
    }

    if (oldSize > 0) {
        memcpy(dest, mStart, oldSize * sizeof(txXPathNode));
    }

    if (mStartBuffer) {
#ifdef DEBUG
        memset(mStartBuffer, 0,
               (mEndBuffer - mStartBuffer) * sizeof(txXPathNode));
#endif
        nsMemory::Free(mStartBuffer);
    }

    mStartBuffer = newArr;
    mEndBuffer = mStartBuffer + newLength;
    mStart = dest;
    mEnd = dest + oldSize;

    return PR_TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

txXPathNode * txNodeSet::findPosition ( const txXPathNode aNode,
txXPathNode aFirst,
txXPathNode aLast,
PRBool aDupe 
) const [private]

Finds position in the buffer where a node should be inserted to keep the nodeset in document order.

Searches the positions aFirst-aLast, including aFirst, but not aLast.

Parameters:
aNodeNode to find insert position for.
aFirstFirst item of the search range, included.
aLastLast item of the search range, excluded.
aDupeout-param. Will be set to true if the node already exists in the NodeSet, false if it should be inserted.
Returns:
pointer where to insert the node. The node should be inserted before the given node. This value is always set, even if aNode already exists in the NodeSet

Definition at line 567 of file txNodeSet.cpp.

{
    aDupe = PR_FALSE;
    if (aLast - aFirst <= 2) {
        // If we search 2 nodes or less there is no point in further divides
        txXPathNode* pos = aFirst;
        for (; pos < aLast; ++pos) {
            PRIntn cmp = txXPathNodeUtils::comparePosition(aNode, *pos);
            if (cmp < 0) {
                return pos;
            }

            if (cmp == 0) {
                aDupe = PR_TRUE;

                return pos;
            }
        }
        return pos;
    }

    // (cannot add two pointers)
    txXPathNode* midpos = aFirst + (aLast - aFirst) / 2;
    PRIntn cmp = txXPathNodeUtils::comparePosition(aNode, *midpos);
    if (cmp == 0) {
        aDupe = PR_TRUE;

        return midpos;
    }

    if (cmp > 0) {
        return findPosition(aNode, midpos + 1, aLast, aDupe);
    }

    // midpos excluded as end of range

    return findPosition(aNode, aFirst, midpos, aDupe);
}

Here is the call graph for this function:

Here is the caller graph for this function:

const txXPathNode & txNodeSet::get ( PRInt32  aIndex) const

Returns the Node at the specified node in this NodeSet.

Parameters:
aIndexthe node of the Node to return
Returns:
Node at specified node

Definition at line 452 of file txNodeSet.cpp.

{
    if (mDirection == kForward) {
        return mStart[aIndex];
    }

    return mEnd[-aIndex - 1];
}

Here is the caller graph for this function:

virtual short txAExprResult::getResultType ( ) [pure virtual, inherited]

Returns the type of ExprResult represented.

Returns:
the type of ExprResult represented

Here is the caller graph for this function:

Returns the index of the specified Node, or -1 if the Node is not contained in the NodeSet.

Parameters:
aNodethe Node to get the index for
Returns:
index of specified node or -1 if the node does not exist

Definition at line 431 of file txNodeSet.cpp.

{
    NS_ASSERTION(mDirection == kForward,
                 "only append(aNode) is supported on reversed nodesets");

    if (!mStart || mStart == mEnd) {
        return -1;
    }

    PRInt32 counter = 0;
    txXPathNode* pos = mStart;
    for (; pos < mEnd; ++counter, ++pos) {
        if (*pos == aNode) {
            return counter;
        }
    }

    return -1;
}

Here is the caller graph for this function:

PRBool txNodeSet::isEmpty ( ) const [inline]

Returns true if there are no Nodes in the NodeSet.

Returns:
true if there are no Nodes in the NodeSet.

Definition at line 182 of file txNodeSet.h.

    {
        return mStart ? mStart == mEnd : PR_TRUE;
    }

Here is the caller graph for this function:

API to implement predicates in PredicateExpr.

mark(aIndex) marks the specified member of the nodeset. sweep() clears all members of the nodeset that haven't been marked before and clear the mMarks array.

Definition at line 352 of file txNodeSet.cpp.

{
    NS_ASSERTION(aIndex >= 0 && mStart && mEnd - mStart > aIndex,
                 "index out of bounds");
    if (!mMarks) {
        PRInt32 length = size();
        mMarks = new PRPackedBool[length];
        NS_ENSURE_TRUE(mMarks, NS_ERROR_OUT_OF_MEMORY);
        memset(mMarks, 0, length * sizeof(PRPackedBool));
    }
    if (mDirection == kForward) {
        mMarks[aIndex] = PR_TRUE;
    }
    else {
        mMarks[size() - aIndex - 1] = PR_TRUE;
    }

    return NS_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

virtual double txAExprResult::numberValue ( ) [pure virtual, inherited]

Converts this ExprResult to a Number (double) value.

Returns:
the Number value

Here is the caller graph for this function:

void txAExprResult::Release ( void  ) [inherited]

Definition at line 291 of file txResultRecycler.cpp.

{
    if (--mRefCnt == 0) {
        if (mRecycler) {
            mRecycler->recycle(this);
        }
        else {
            delete this;
        }
    }
}

API to implement reverse axes in LocationStep.

Before adding nodes to the nodeset for a reversed axis, call setReverse(). This will make the append(aNode) and get() methods treat the nodeset as required. Do only call append(aNode), get(), mark() and sweep() while the nodeset is reversed. Afterwards, call unsetReverse(). The nodes are stored in document order internally.

Definition at line 129 of file txNodeSet.h.

    {
        mDirection = -1;
    }
PRInt32 txNodeSet::size ( ) const [inline]

Returns the number of elements in the NodeSet.

Returns:
the number of elements in the NodeSet

Definition at line 191 of file txNodeSet.h.

    {
        return mStart ? mEnd - mStart : 0;
    }

Here is the caller graph for this function:

virtual void txAExprResult::stringValue ( nsAString &  str) [pure virtual, inherited]

Creates a String representation of this ExprResult.

Parameters:
strthe destination string to append the String representation to.

Here is the caller graph for this function:

virtual nsAString* txAExprResult::stringValuePointer ( ) [pure virtual, inherited]

Returns a pointer to the stringvalue if possible.

Otherwise null is returned.

Here is the caller graph for this function:

Definition at line 373 of file txNodeSet.cpp.

{
    if (!mMarks) {
        // sweep everything
        clear();
    }

    PRInt32 chunk, pos = 0;
    PRInt32 length = size();
    txXPathNode* insertion = mStartBuffer;

    while (pos < length) {
        while (pos < length && !mMarks[pos]) {
            // delete unmarked
            mStart[pos].~txXPathNode();
            ++pos;
        }
        // find chunk to move
        chunk = 0;
        while (pos < length && mMarks[pos]) {
            ++pos;
            ++chunk;
        }
        // move chunk
        if (chunk > 0) {
            memmove(insertion, mStart + pos - chunk,
                    chunk * sizeof(txXPathNode));
            insertion += chunk;
        }
    }
    mStart = mStartBuffer;
    mEnd = insertion;
    delete [] mMarks;
    mMarks = nsnull;

    return NS_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void txNodeSet::toString ( const txNodeSet aNodes,
nsAString &  aResult 
) [static, private]
void txNodeSet::transferElements ( txXPathNode aDest,
const txXPathNode aStart,
const txXPathNode aEnd 
) [static, private]

Definition at line 622 of file txNodeSet.cpp.

{
    memcpy(aDest, aStart, (aEnd - aStart) * sizeof(txXPathNode));
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 133 of file txNodeSet.h.

    {
        mDirection = 1;
    }

Friends And Related Function Documentation

friend class txResultRecycler [friend, inherited]

Definition at line 60 of file ExprResult.h.


Member Data Documentation

Definition at line 236 of file txNodeSet.h.

Definition at line 235 of file txNodeSet.h.

Definition at line 235 of file txNodeSet.h.

Definition at line 238 of file txNodeSet.h.

Definition at line 235 of file txNodeSet.h.

Definition at line 235 of file txNodeSet.h.


The documentation for this class was generated from the following files: