Cache element indices for :nth-child and :nth-last-child selectors.
In order to avoid n^2 for :nth-selectors, we introduce a cache where we
store the index of every kth child of a parent node P the first time the
nth-count is queried for one of its children. The number k is given by
the "spread" constant.
After the cache has been populated for the children of P, the nth-index
for an element will be found by walking the siblings from the element
queried for and leftwards until a cached element/index pair is found.
So populating the cache for P is O(n). Subsequent lookups are best case
O(1), worst case O(k).
The cache is created on the stack when we do operations where we know we
can benefit from having it. Currently, those are querySelector,
querySelectorAll, and updateStyle. We are throwing away the cache after
each operation to avoid holding on to potentially large caches in memory.
R=esprehn@chromium.org
BUG=461878
Review URL: https://codereview.chromium.org/1023393002
git-svn-id: svn://svn.chromium.org/blink/trunk@193268 bbb929c8-8fbe-4397-9dbb-9b2b20218538
12 files changed
