Systems and methods for parallel traversal of document object model tree

Patent metadata

Field	Value
Publication number	US-2015135061-A1
Application number	US-201314075920-A
Country	US
Kind code	A1
Filing date	Nov 8, 2013
Priority date	Nov 8, 2013
Publication date	May 14, 2015
Grant date	—

Abstract

Systems and methods are disclosed for traversing a DOM tree in parallel by utilizing a multi-core processor to expedite webpage layout process. The contents of an HTML webpage may be parsed into a Document Object Model (DOM) tree including nodes representing the contents of the HTML webpage. A Cascade Style Sheet (CSS) selector is used to select one or more HTML elements for styling. The DOM tree may be divided into a plurality of sub-trees. The plurality of sub-trees are traversed simultaneously to search for element nodes representing HTML elements that match the CSS selector.

First claim

What is claimed is:

1 . A method for displaying data on a display device, comprising:
receiving a Hyper Text Markup Language (HTML) webpage; parsing contents of the HTML webpage into a Document Object Model (DOM) tree including nodes representing the contents of the HTML webpage; receiving a Cascade Style Sheet (CSS) selector selecting one or more HTML elements of the HTML webpage for styling; dividing the DOM tree into a plurality of sub-trees; and traversing, by a multi-core processor, the plurality of sub-trees simultaneously to search for element nodes representing HTML elements that match the CSS selector.

2 . The method of claim 1 , wherein the DOM tree is divided based on a number of processing cores of the multi-core processor used for traversing the DOM tree.

3 . The method of claim 1 , wherein the nodes of the DOM tree are distributed evenly among the plurality of sub-trees.

4 . The method of claim 1 , wherein traversals of the plurality of sub-trees are started at the same time, such that the traversals of the plurality of sub-tress are executed by different cores of the multi-core processor respectively.

5 . The method of claim 1 further comprising:
storing pointers of the element nodes of the DOM tree in a cache; and
traversing the sub-trees without traversing non-element nodes by referencing the cache.

6 . The method of claim 5 further comprising: distributing the element nodes of the DOM tree evenly among the sub-trees by referencing the cache.

7 . The method of claim 5 further comprising:
determining whether the DOM tree has been modified; and
updating the cache when the DOM tree has been modified to reflect modifications to the DOM tree.

8 . The method of claim 6 , wherein the DOM tree is modified when one of a number and an order of the nodes in the DOM tree is changed.

9 . An apparatus, comprising:
a non-transitory memory configured to store a plurality of machine-readable instructions; and one or more processors coupled to the memory and operable to read the instructions from the memory and to:
receive a Hyper Text Markup Language (HTML) webpage;
parse contents of the HTML webpage into a Document Object Model (DOM) tree including nodes representing the contents of the HTML webpage;
receive a Cascade Style Sheet (CSS) selector selecting one or more HTML elements of the HTML webpage for styling;
divide the DOM tree into a plurality of sub-trees; and
traverse the plurality of sub-trees simultaneously to search for element nodes representing HTML elements that match the CSS selector.

10 . The apparatus of claim 9 ,
wherein the one or more processors comprise a multi-core processor, and wherein the DOM tree is divided based on a number of cores of the multi-core processor used for traversing the DOM tree.

11 . The apparatus of claim 9 , wherein the nodes of the DOM tree are distributed evenly among the plurality of sub-trees.

12 . The apparatus of claim 9 ,
wherein the one or more processors comprises a multi-core processor; and wherein the traversals of the plurality of sub-trees are started at the same time, such that the traversals of the plurality of sub-tress are executed by different cores of the multi-core processor respectively.

13 . The apparatus of claim 9 , wherein the one or more processors are further operable to:
store pointers of the element nodes of the DOM tree in a cache; and traverse the sub-trees without traversing non-element nodes by referencing the cache.

14 . The apparatus of claim 13 , wherein the one or more processors are further operable to perform the step of distributing the element nodes of the DOM tree evenly among the sub-trees by referencing the cache.

15 . The apparatus of claim 13 , wherein the one or more processors are further operable to:
determine whether the DOM tree has been modified; and update the cache when the DOM tree has been modified to reflect modifications to the DOM tree.

16 . The apparatus of claim 14 , wherein the DOM tree is modified when one of a number and an order of the nodes in the DOM tree is changed.

17 . A non-transitory computer-readable medium comprising a plurality of machine-readable instructions which, when executed by one or more processors, are adapted to cause the one or more processors to perform a method for displaying data on a display device, comprising:
receiving a Hyper Text Markup Language (HTML) webpage; parsing contents of the HTML webpage into a Document Object Model (DOM) tree including nodes representing the contents of the HTML webpage; receiving a Cascade Style Sheet (CSS) selector selecting one or more HTML elements of the HTML webpage for styling; dividing the DOM tree into a plurality of sub-trees; and traversing the plurality of sub-trees simultaneously to search for element nodes representing HTML elements that match the CSS selector.

18 . The non-transitory computer-readable medium of claim 17 , the method further comprising:
storing pointers of the element nodes of the DOM tree in a cache; and traversing the sub-trees without traversing non-element nodes by referencing the cache.

19 . The none-transitory computer readable medium of claim 18 , the method further comprising: distributing the element nodes of the DOM tree evenly among the sub-trees by referencing the cache.

20 . The none-transitory computer readable medium of claim 18 , the method further comprising:
determining whether the DOM tree has been modified; and updating the cache when the DOM tree has been modified to reflect modifications to the DOM tree.

21 . A system for displaying data on a display device, comprising:
means for receiving a Hyper Text Markup Language (HTML) webpage; means for parsing contents of the HTML webpage into a Document Object Model (DOM) tree including nodes representing the contents of the HTML webpage; means for receiving a Cascade Style Sheet (CSS) selector selecting one or more HTML elements of the HTML webpage for styling; means for dividing the DOM tree into a plurality of sub-trees; and means for traversing the plurality of sub-trees simultaneously to search for element nodes representing HTML elements that match the CSS selector.

22 . The system of claim 21 further comprising:
means for storing pointers of the element nodes of the DOM tree in a cache; and
means for traversing the sub-trees without traversing non-element nodes by referencing the cache.

23 . The system of claim 22 further comprising means for distributing the element nodes of the DOM tree evenly among the sub-trees by referencing the cache.

24 . The system of claim 22 further comprising:
means for determining whether the DOM tree has been modified; and
means for updating the cache when the DOM tree has been modified to reflect modifications to the DOM tree.

Assignees

• Qualcomm Inc

Inventors

• Palanichamy Kulanthaivel
• Hart Kevin A
• Mondal Shyama Prasad
• Namasivayam Balachandar

Classifications

• G06F40/221

  Parsing markup language streams (streaming G06F40/149) · CPC title

• G06F40/154 Primary

  Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets · CPC title

• G06F17/2247 Primary

  Physics · mapped topic

• G06F40/143

  Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD] · CPC title