merge

5 files changed, 125 insertions, 32 deletions

diff --git a/src/css.cc b/src/css.cc
index 2b069f18..50b73674 100644
--- a/src/css.cc
+++ b/src/css.cc
@@ -51,6 +51,7 @@ CssSelector::CssSelector (int element, const char *klass,
    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 @@ CssSelector::~CssSelector () {
 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 @@ bool CssSelector::match (Doctree *docTree) {
    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,18 @@ bool CssSelector::match (Doctree *docTree) {
                return false;
             break;
          case DESCENDENT:
-            while (!sel->match (node)) {
-               node = docTree->parent (node);
-               if (node == NULL)
+            n = node;
+
+            while (true) {
+               if (node == NULL || node->num < *notMatchingBefore) {
+                  *notMatchingBefore = n->num;
                   return false;
+               }
+
+               if (sel->match (node))
+                  break;
+
+               node = docTree->parent (node);
             }
             break;
          default:
@@ -107,6 +118,7 @@ void CssSelector::addSimpleSelector (Combinator c, int element,
    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;
@@ -157,7 +169,6 @@ void CssSimpleSelector::print () {
 }
 
 CssRule::CssRule (CssSelector *selector, CssPropertyList *props) {
-   refCount = 0;
    this->selector = selector;
    this->selector->ref ();
    this->props = props;
@@ -181,31 +192,53 @@ void CssRule::print () {
 
 CssStyleSheet::CssStyleSheet () {
    for (int i = 0; i < ntags; i++)
-      ruleTable[i] = new lout::misc::SimpleVector <CssRule*> (1);
+      elementTable[i] = new RuleList ();
+
+   idTable = new RuleMap ();
+   classTable = new RuleMap ();
+   anyTable = new RuleList ();
 }
 
 CssStyleSheet::~CssStyleSheet () {
-   for (int i = 0; i < ntags; i++) {
-      for (int j = 0; j < ruleTable[i]->size (); j++)
-         ruleTable[i]->get (j)->unref ();
-         
-      delete ruleTable[i];
-   }
+   for (int i = 0; i < ntags; i++)
+      delete elementTable[i];
+   delete idTable;
+   delete classTable;
+   delete anyTable;
 }
 
 void CssStyleSheet::addRule (CssRule *rule) {
-   int topElement = rule->selector->top ()->element;
-
-   if (topElement == CssSimpleSelector::ELEMENT_ANY) {
-      for (int i = 0; i < ntags; i++) {
-         ruleTable[i]->increase ();
-         *ruleTable[i]->getRef (ruleTable[i]->size () - 1) = rule;
-         rule->ref ();
+   CssSimpleSelector *top = rule->selector->top ();
+   RuleList *ruleList = NULL;
+   lout::object::ConstString *string;
+   
+   if (top->id) {
+      string = new lout::object::ConstString (top->id);
+      ruleList = idTable->get (string);
+      if (ruleList == NULL) {
+         ruleList = new RuleList ();
+         idTable->put (string, ruleList);
+      } else {
+         delete string;
       }
-   } else if (topElement >= 0 && topElement < ntags) {
-      ruleTable[topElement]->increase ();
-      *ruleTable[topElement]->getRef (ruleTable[topElement]->size()-1) = rule;
-      rule->ref ();
+   } else if (top->klass) {
+      string = new lout::object::ConstString (top->klass);
+      ruleList = classTable->get (string);
+      if (ruleList == NULL) {
+         ruleList = new RuleList;
+         classTable->put (string, ruleList);
+      } else {
+         delete string;
+      }
+   } else if (top->element >= 0 && top->element < ntags) {
+      ruleList = elementTable[top->element];
+   } else if (top->element == CssSimpleSelector::ELEMENT_ANY) {
+      ruleList = anyTable;
+   }
+
+   if (ruleList) {
+      ruleList->increase ();
+      *ruleList->getRef (ruleList->size() - 1) = rule;
    }
 }
 
@@ -215,11 +248,44 @@ void CssStyleSheet::addRule (CssSelector *selector, CssPropertyList *props) {
 }
 
 void CssStyleSheet::apply (CssPropertyList *props, Doctree *docTree) {
-   lout::misc::SimpleVector <CssRule*> *ruleList;
+   RuleList *ruleList[4] = {NULL, NULL, NULL, NULL};
+   const DoctreeNode *top = docTree->top ();
+   
+   if (top->id) {
+      lout::object::String idString (top->id);
+
+      ruleList[3] = idTable->get (&idString);
+   }
+
+   if (top->klass) {
+      lout::object::String classString (top->klass);
+
+      ruleList[2] = classTable->get (&classString);
+   }
+
+   ruleList[1] = elementTable[docTree->top ()->element];
+   ruleList[0] = anyTable;
 
-   ruleList = ruleTable[docTree->top ()->element];
-   for (int i = 0; i < ruleList->size (); i++)
-      ruleList->get (i)->apply (props, docTree);
+#if 0
+   fprintf(stderr, "==> ");
+   for (int j = 0; j < 4; j++)
+      fprintf(stderr, "%d ", ruleList[j]?ruleList[j]->size():0);
+   fprintf(stderr, "\n");
+#endif
+
+   for (int i = 0;; i++) {
+      int n = 0;
+
+      for (int j = 0; j < 4; j++) {
+         if (ruleList[j] && ruleList[j]->size () > i) {
+            ruleList[j]->get (i)->apply (props, docTree);
+            n++;
+         }
+      }
+
+      if (n == 0)
+         break;
+   } 
 }
 
 CssStyleSheet *CssContext::userAgentStyle;
diff --git a/src/css.hh b/src/css.hh
index 515831e9..d3472740 100644
--- a/src/css.hh
+++ b/src/css.hh
@@ -223,6 +223,7 @@ class CssSelector {
 
    private:
       struct CombinatorAndSelector {
+         int notMatchingBefore; // used for optimizing CSS selector matching
          Combinator combinator;
          CssSimpleSelector selector;
       };
@@ -255,7 +256,6 @@ class CssSelector {
  */
 class CssRule {
    private:
-      int refCount;
       CssPropertyList *props;
 
    public:
@@ -265,8 +265,6 @@ class CssRule {
       ~CssRule ();
 
       void apply (CssPropertyList *props, Doctree *docTree);
-      inline void ref () { refCount++; }
-      inline void unref () { if(--refCount == 0) delete this; }
       void print ();
 };
 
@@ -276,8 +274,32 @@ class CssRule {
  */
 class CssStyleSheet {
    private:
+      class RuleList : public lout::misc::SimpleVector <CssRule*>,
+                       public lout::object::Object {
+         public:
+            RuleList () : lout::misc::SimpleVector <CssRule*> (1) {};
+            ~RuleList () {
+               for (int i = 0; i < size (); i++)
+                  delete get (i);
+            };
+
+            bool equals (lout::object::Object *other) { return this == other; };
+            int hashValue () { return (intptr_t) this; };
+      };
+
+      class RuleMap : public lout::container::typed::HashTable
+                             <lout::object::ConstString, RuleList > {
+         public:
+            RuleMap () : lout::container::typed::HashTable
+                    <lout::object::ConstString, RuleList > (true, true, 256) {};
+      };
+
       static const int ntags = 90; // \todo replace 90
-      lout::misc::SimpleVector <CssRule*> *ruleTable[ntags];
+      RuleList *elementTable[ntags];
+
+      RuleMap *idTable;
+      RuleMap *classTable;
+      RuleList *anyTable;
 
    public:
       CssStyleSheet();
diff --git a/src/doctree.hh b/src/doctree.hh
index 97686e40..f74350b0 100644
--- a/src/doctree.hh
+++ b/src/doctree.hh
@@ -3,6 +3,7 @@
 
 class DoctreeNode {
    public:
+      int num; // unique ascending id
       int depth;
       int element;
       const char *klass;
diff --git a/src/styleengine.cc b/src/styleengine.cc
index accfbd7d..b5e2a3a4 100644
--- a/src/styleengine.cc
+++ b/src/styleengine.cc
@@ -23,6 +23,7 @@ StyleEngine::StyleEngine (dw::core::Layout *layout) {
    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 @@ StyleEngine::StyleEngine (dw::core::Layout *layout) {
    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 @@ void StyleEngine::startElement (int element) {
 
    stack->increase ();
    Node *n =  stack->getRef (stack->size () - 1);
+   n->num = num++;
    n->style = NULL;
    n->wordStyle = NULL;
    n->depth = stack->size () - 1;
diff --git a/src/styleengine.hh b/src/styleengine.hh
index d063fb27..9669ccf0 100644
--- a/src/styleengine.hh
+++ b/src/styleengine.hh
@@ -19,6 +19,7 @@ class StyleEngine : public Doctree {
       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);