m_matchedRuleCount = 0;
    firstRuleIndex = lastRuleIndex = -1;
    if (!rules || !element) return;

    // We need to collect the rules for id, class, tag, and everything else into a buffer and
    // then sort the buffer.
    if (element->hasID())
        matchRulesForList(rules->getIDRules(element->getIDAttribute().implementation()),
                          firstRuleIndex, lastRuleIndex);
    if (element->hasClass()) {
        for (const AtomicStringList* singleClass = element->getClassList();
             singleClass; singleClass = singleClass->next())
            matchRulesForList(rules->getClassRules(singleClass->string().implementation()),
                                                   firstRuleIndex, lastRuleIndex);
    }
    matchRulesForList(rules->getTagRules((void*)(int)localNamePart(element->id())),
                      firstRuleIndex, lastRuleIndex);
    matchRulesForList(rules->getUniversalRules(), firstRuleIndex, lastRuleIndex);

    // If we didn't match any rules, we're done.
    if (m_matchedRuleCount == 0) return;

    // Sort the set of matched rules.
    sortMatchedRules(0, m_matchedRuleCount);

    // Now transfer the set of matched rules over to our list of decls.
    for (unsigned i = 0; i < m_matchedRuleCount; i++)
        addMatchedDeclaration(m_matchedRules[i]->rule()->declaration());
}

void CSSStyleSelector::matchRulesForList(CSSRuleDataList* rules,
                                         int& firstRuleIndex, int& lastRuleIndex)
{
    if (!rules) return;
    for (CSSRuleData* d = rules->first(); d; d = d->next()) {
        CSSStyleRuleImpl* rule = d->rule();
        Q_UINT16 cssTagId = localNamePart(element->id());
        Q_UINT16 tag = localNamePart(d->selector()->tag);
        if ((cssTagId == tag || tag == anyLocalName) && checkSelector(d->selector(), element)) {
            // If the rule has no properties to apply, then ignore it.
            CSSMutableStyleDeclarationImpl* decl = rule->declaration();
            if (!decl || !decl->length()) continue;

            // If we're matching normal rules, set a pseudo bit if
            // we really just matched a pseudo-element.
            if (dynamicPseudo != RenderStyle::NOPSEUDO && pseudoStyle == RenderStyle::NOPSEUDO)
                style->setHasPseudoStyle(dynamicPseudo);
            else {
                // Update our first/last rule indices in the matched rules array.
                lastRuleIndex = m_matchedDeclCount + m_matchedRuleCount;
                if (firstRuleIndex == -1) firstRuleIndex = m_matchedDeclCount + m_matchedRuleCount;

                // Add this rule to our list of matched rules.
                addMatchedRule(d);
            }
        }
    }
}

bool operator >(CSSRuleData& r1, CSSRuleData& r2)
{
    int spec1 = r1.selector()->specificity();
    int spec2 = r2.selector()->specificity();
    return (spec1 == spec2) ? r1.position() > r2.position() : spec1 > spec2;
}
bool operator <=(CSSRuleData& r1, CSSRuleData& r2)
{
    return !(r1 > r2);
}

void CSSStyleSelector::sortMatchedRules(uint start, uint end)
{
    if (start >= end || (end-start == 1))
        return; // Sanity check.

    if (end - start <= 6) {
        // Apply a bubble sort for smaller lists.
        for (uint i = end-1; i > start; i--) {
            bool sorted = true;
            for (uint j = start; j < i; j++) {
                CSSRuleData* elt = m_matchedRules[j];
                CSSRuleData* elt2 = m_matchedRules[j+1];
                if (*elt > *elt2) {
                    sorted = false;
                    m_matchedRules[j] = elt2;
                    m_matchedRules[j+1] = elt;
                }
            }
            if (sorted)
                return;
        }
    }
    else {
        // Peform a merge sort for larger lists.
        uint mid = (start+end)/2;
        sortMatchedRules(start, mid);
        sortMatchedRules(mid, end);

        CSSRuleData* elt = m_matchedRules[mid-1];
        CSSRuleData* elt2 = m_matchedRules[mid];

        // Handle the fast common case (of equal specificity).  The list may already
        // be completely sorted.
        if (*elt <= *elt2)
            return;

        // We have to merge sort.  Ensure our merge buffer is big enough to hold
        // all the items.
        m_tmpRules.resize(end - start);
        uint i1 = start;
        uint i2 = mid;

        elt = m_matchedRules[i1];
        elt2 = m_matchedRules[i2];

        while (i1 < mid || i2 < end) {
            if (i1 < mid && (i2 == end || *elt <= *elt2)) {
                m_tmpRules[m_tmpRuleCount++] = elt;
                i1++;
                if (i1 < mid)
                    elt = m_matchedRules[i1];
            }
            else {
                m_tmpRules[m_tmpRuleCount++] = elt2;
                i2++;
                if (i2 < end)
                    elt2 = m_matchedRules[i2];
            }
        }

        for (uint i = start; i < end; i++)
            m_matchedRules[i] = m_tmpRules[i-start];

        m_tmpRuleCount = 0;
    }
}

void CSSStyleSelector::initElementAndPseudoState(ElementImpl* e)
{
    element = e;
    if (element && element->isHTMLElement())
        htmlElement = static_cast<HTMLElementImpl*>(element);
    else
        htmlElement = 0;
    ::encodedurl = &encodedurl;
    pseudoState = PseudoUnknown;
}

void CSSStyleSelector::initForStyleResolve(ElementImpl* e, RenderStyle* defaultParent)
{
    // set some variables we will need
    pseudoStyle = RenderStyle::NOPSEUDO;

    parentNode = e->parentNode();
    if (defaultParent)
        parentStyle = defaultParent;
    else
        parentStyle = (parentNode && parentNode->renderer()) ? parentNode->renderer()->style() : 0;
    view = element->getDocument()->view();
    isXMLDoc = !element->getDocument()->isHTMLDocument();
    part = element->getDocument()->part();
    settings = part ? part->settings() : 0;
    paintDeviceMetrics = element->getDocument()->paintDeviceMetrics();

    style = 0;

    m_matchedRuleCount = 0;
    m_matchedDeclCount = 0;
    m_tmpRuleCount = 0;

    fontDirty = false;
}

// modified version of the one in kurl.cpp
static void cleanpath(QString &path)
{
    int pos;
    while ( (pos = path.find( "/../" )) != -1 ) {
        int prev = 0;
        if ( pos > 0 )
            prev = path.findRev( "/", pos -1 );
        // don't remove the host, i.e. http://foo.org/../foo.html
        if (prev < 0 || (prev > 3 && path.findRev("://", prev-1) == prev-2))
            path.remove( pos, 3);
        else
            // matching directory found ?
            path.remove( prev, pos- prev + 3 );
    }
    pos = 0;

    // Don't remove "//" from an anchor identifier. -rjw
    // Set refPos to -2 to mean "I haven't looked for the anchor yet".
    // We don't want to waste a function call on the search for the the anchor
    // in the vast majority of cases where there is no "//" in the path.
    int refPos = -2;
    while ( (pos = path.find( "//", pos )) != -1) {
        if (refPos == -2)
            refPos = path.find("#", 0);
        if (refPos > 0 && pos >= refPos)
            break;

        if ( pos == 0 || path[pos-1] != ':' )
            path.remove( pos, 1 );
        else
            pos += 2;
    }
    while ( (pos = path.find( "/./" )) != -1)
        path.remove( pos, 2 );
    //kdDebug() << "checkPseudoState " << path << endl;
}

static void checkPseudoState( DOM::ElementImpl *e, bool checkVisited = true )
{
    if (!e->hasAnchor()) {
        pseudoState = PseudoNone;
        return;
    }

    const AtomicString& attr = e->getAttribute(ATTR_HREF);
    if (attr.isNull()) {
        pseudoState = PseudoNone;
        return;
    }

    if (!checkVisited) {
        pseudoState = PseudoAnyLink;
        return;
    }

    QConstString cu(attr.unicode(), attr.length());
    QString u = cu.string();
    if ( !u.contains("://") ) {
        if ( u[0] == '/' )
            u.prepend(encodedurl->host);
        else if ( u[0] == '#' )
            u.prepend(encodedurl->file);
        else
            u.prepend(encodedurl->path);
        cleanpath( u );
    }
    //completeURL( attr.string() );
    pseudoState = KHTMLFactory::vLinks()->contains( u ) ? PseudoVisited : PseudoLink;
}

#ifdef STYLE_SHARING_STATS
static int fraction = 0;
static int total = 0;
#endif

const int siblingThreshold = 10;

NodeImpl* CSSStyleSelector::locateCousinList(ElementImpl* parent)
{
    if (parent && parent->isHTMLElement()) {
        HTMLElementImpl* p = static_cast<HTMLElementImpl*>(parent);
        if (p->renderer() && !p->inlineStyleDecl() && !p->hasID()) {
            DOM::NodeImpl* r = p->previousSibling();
            int subcount = 0;
            RenderStyle* st = p->renderer()->style();
            while (r) {
                if (r->renderer() && r->renderer()->style() == st)
                    return r->lastChild();
                if (subcount++ == siblingThreshold)
                    return 0;
                r = r->previousSibling();
            }
            if (!r)
                r = locateCousinList(static_cast<ElementImpl*>(parent->parentNode()));
            while (r) {
                if (r->renderer() && r->renderer()->style() == st)
                    return r->lastChild();
                if (subcount++ == siblingThreshold)
                    return 0;
                r = r->previousSibling();
            }
        }
    }
    return 0;
}

bool CSSStyleSelector::canShareStyleWithElement(NodeImpl* n)
{
    if (n->isHTMLElement()) {
        bool mouseInside = element->renderer() ? element->renderer()->mouseInside() : false;
        HTMLElementImpl* s = static_cast<HTMLElementImpl*>(n);
        if (s->renderer() && (s->id() == element->id()) && !s->hasID() &&
            (s->hasClass() == element->hasClass()) && !s->inlineStyleDecl() &&
            (s->hasMappedAttributes() == htmlElement->hasMappedAttributes()) &&
            (s->hasAnchor() == element->hasAnchor()) &&
            !s->renderer()->style()->affectedByAttributeSelectors() &&
            (s->renderer()->mouseInside() == mouseInside) &&
            (s->active() == element->active()) &&
            (s->focused() == element->focused())) {
            bool classesMatch = true;
            if (s->hasClass()) {
                const AtomicString& class1 = element->getAttribute(ATTR_CLASS);
                const AtomicString& class2 = s->getAttribute(ATTR_CLASS);
                classesMatch = (class1 == class2);
            }

            if (classesMatch) {
                bool mappedAttrsMatch = true;
                if (s->hasMappedAttributes())
                    mappedAttrsMatch = s->htmlAttributes()->mapsEquivalent(htmlElement->htmlAttributes());
                if (mappedAttrsMatch) {
                    bool anchorsMatch = true;
                    if (s->hasAnchor()) {
                        // We need to check to see if the visited state matches.
                        QColor linkColor = element->getDocument()->linkColor();
                        QColor visitedColor = element->getDocument()->visitedLinkColor();
                        if (pseudoState == PseudoUnknown)
                            checkPseudoState(element, s->renderer()->style()->pseudoState() != PseudoAnyLink ||
                                             linkColor != visitedColor);
                        anchorsMatch = (pseudoState == s->renderer()->style()->pseudoState());
                    }

                    if (anchorsMatch)
                        return true;
                }
            }
        }
    }
    return false;
}

RenderStyle* CSSStyleSelector::locateSharedStyle()
{
    if (htmlElement && !htmlElement->inlineStyleDecl() && !htmlElement->hasID() &&
        !htmlElement->getDocument()->usesSiblingRules()) {
        // Check previous siblings.
        int count = 0;
        DOM::NodeImpl* n;
        for (n = element->previousSibling(); n && !n->isElementNode(); n = n->previousSibling());
        while (n) {
            if (canShareStyleWithElement(n))
                return n->renderer()->style();
            if (count++ == siblingThreshold)
                return 0;
            for (n = n->previousSibling(); n && !n->isElementNode(); n = n->previousSibling());
        }
        if (!n)
            n = locateCousinList(static_cast<ElementImpl*>(element->parentNode()));