4 ms·

Interesting, from libHTML: class Node { Vector<Node*> m_children; Node* m_next_sibling { nullptr }; Node* m_previous_sibling { nullptr };

• ameixaseca 4y ago
  Unless sibling is sideways (same level of the tree) and children is downward (one level closer to the leaves). I haven't looked at the code but that's my first impression given the nomenclature.
  • c-smile 4y ago
    No, you didn't get it. You may have children accounted as DL list and so each Node should have m_next / m_previous node references. + Parent node to have m_first_child reference (if list is circular). + m_parent (Node) reference. So you need 4 pointers per each non-terminal node. Or 3 pointers for terminals. Otherwise (vector of children): You need only m_parent (Node) reference in terminals. And in container nodes additional vector<NodePtr> m_children; to store child references.
    • eb2 4y ago
      You don’t need parent because you can use a breadcrumb stack to track parents. You want sibling nodes otherwise you will have to traverse back to the root node sometimes to find a sibling.
      • c-smile 4y ago
        > You don’t need parent You do need parent, check this: https://developer.mozilla.org/en-US/docs/Web/API/Node/parentNode https://developer.mozilla.org/en-US/docs/Web/API/Node/parent... > You want sibling nodes otherwise you will have to traverse back to the root node sometimes to find a sibling. The only need for this is in Node.nextSibling implementation: https://developer.mozilla.org/en-US/docs/Web/API/Node/nextSibling https://developer.mozilla.org/en-US/docs/Web/API/Node/nextSi... Where vector<>::find is pretty sufficient. But in reality (at least in my Sciter) node stores its index in parent's m_children so it is O(1) operation.
        • lenkite 4y ago
          Is there source code available online illustrating your more-efficient DOM data-structure ?
        • xigoi 4y ago
          How about the + operator in CSS?
          • c-smile 4y ago
            And what is wrong with it? and ~ combinator and :nth-child(n) selector for that matter too.
            • xigoi 4y ago
              I'm responding to the claim that you only need the ability to find a sibling for the nextSibling method.
• Ygg2 4y ago
  You usually keep next/previous sibling to speed up iteration See: http://aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html#data-structures-for-the-document-object-model http://aosabook.org/en/posa/parsing-xml-at-the-speed-of-ligh...
  • c-smile 4y ago
    You can store index of the node in parent m_children collection. Iteration on array is faster (cache locality) than DL list traversal. And there are issues when you traverse tree while changing it. In any case I've found that storing child nodes as m_children collection is more convenient in many cases. At least in Sciter (https://sciter.com https://sciter.com). struct node { weak_ref<element> m_parent; uint m_node_index; } struct element : node { vector<ref<node>> m_children; // strict ownership, sic! }