Mercurial > dillo_port1.3
changeset 763:df8153796f48
initial implementation of a CSS selector matching optimization
The idea is to avoid repeated checks of CssSimpleSelector against the
same part of the doctree.
E.g
.navigation * { background-color:green }
Would result in checking for class="navigation" all the way down to the
document root for all elements.
The optimization shortcuts this, for parts of the doctree that have been
checked before.
| author | Johannes Hofmann <Johannes.Hofmann@gmx.de> |
|---|---|
| date | Tue, 13 Jan 2009 09:02:41 +0100 |
| parents | 336ae7ab06a8 |
| children | 570b3440dc19 |
| files | src/css.cc src/css.hh src/doctree.hh src/styleengine.cc src/styleengine.hh |
| diffstat | 5 files changed, 22 insertions(+), 3 deletions(-) [+] |
line wrap: on
line diff
--- a/src/css.cc Mon Jan 12 18:12:33 2009 +0100 +++ b/src/css.cc Tue Jan 13 09:02:41 2009 +0100 @@ -51,6 +51,7 @@ selectorList = new lout::misc::SimpleVector <struct CombinatorAndSelector> (1); selectorList->increase (); + selectorList->getRef (0)->notMatchingBefore = -1; top ()->element = element; top ()->klass = klass; top ()->pseudo = pseudo; @@ -64,7 +65,8 @@ bool CssSelector::match (Doctree *docTree) { CssSimpleSelector *sel; Combinator comb; - const DoctreeNode *node = docTree->top (); + int *notMatchingBefore; + const DoctreeNode *n, *node = docTree->top (); assert (selectorList->size () > 0); @@ -76,6 +78,7 @@ for (int i = selectorList->size () - 2; i >= 0; i--) { sel = &selectorList->getRef (i)->selector; comb = selectorList->getRef (i + 1)->combinator; + notMatchingBefore = &selectorList->getRef (i + 1)->notMatchingBefore; node = docTree->parent (node); if (node == NULL) @@ -87,10 +90,19 @@ return false; break; case DESCENDENT: + n = node; while (!sel->match (node)) { + if (node == NULL || *notMatchingBefore >= node->num) { + *notMatchingBefore = n->num; + return false; + } + node = docTree->parent (node); - if (node == NULL) + + if (node == NULL || *notMatchingBefore >= node->num) { + *notMatchingBefore = n->num; return false; + } } break; default: @@ -107,6 +119,7 @@ selectorList->increase (); selectorList->getRef (selectorList->size () - 1)->combinator = c; + selectorList->getRef (selectorList->size () - 1)->notMatchingBefore = -1; top ()->element = element; top ()->klass = klass; top ()->pseudo = pseudo;
--- a/src/css.hh Mon Jan 12 18:12:33 2009 +0100 +++ b/src/css.hh Tue Jan 13 09:02:41 2009 +0100 @@ -223,6 +223,7 @@ private: struct CombinatorAndSelector { + int notMatchingBefore; // used for optimizing CSS selector matching Combinator combinator; CssSimpleSelector selector; };
--- a/src/doctree.hh Mon Jan 12 18:12:33 2009 +0100 +++ b/src/doctree.hh Tue Jan 13 09:02:41 2009 +0100 @@ -3,6 +3,7 @@ class DoctreeNode { public: + int num; // unique ascending id int depth; int element; const char *klass;
--- a/src/styleengine.cc Mon Jan 12 18:12:33 2009 +0100 +++ b/src/styleengine.cc Tue Jan 13 09:02:41 2009 +0100 @@ -23,6 +23,7 @@ stack = new lout::misc::SimpleVector <Node> (1); cssContext = new CssContext (); this->layout = layout; + num = 0; stack->increase (); Node *n = stack->getRef (stack->size () - 1); @@ -37,7 +38,8 @@ style_attrs.font = Font::create (layout, &font_attrs); style_attrs.color = Color::create (layout, 0); style_attrs.backgroundColor = Color::create (layout, 0xffffff); - + + n->num = num++; n->style = Style::create (layout, &style_attrs); n->wordStyle = NULL; n->pseudo = NULL; @@ -62,6 +64,7 @@ stack->increase (); Node *n = stack->getRef (stack->size () - 1); + n->num = num++; n->style = NULL; n->wordStyle = NULL; n->depth = stack->size () - 1;
--- a/src/styleengine.hh Mon Jan 12 18:12:33 2009 +0100 +++ b/src/styleengine.hh Tue Jan 13 09:02:41 2009 +0100 @@ -19,6 +19,7 @@ dw::core::Layout *layout; lout::misc::SimpleVector <Node> *stack; CssContext *cssContext; + int num; dw::core::style::Style *style0 (CssPropertyList *nonCssHints = NULL); dw::core::style::Style *wordStyle0 (CssPropertyList *nonCssHints = NULL);