1 /* 2 * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org) 3 * (C) 2004-2005 Allan Sandfeld Jensen (kde (at) carewolf.com) 4 * Copyright (C) 2006, 2007 Nicholas Shanks (webkit (at) nickshanks.com) 5 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved. 6 * Copyright (C) 2007 Alexey Proskuryakov <ap (at) webkit.org> 7 * Copyright (C) 2007, 2008 Eric Seidel <eric (at) webkit.org> 8 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/) 9 * Copyright (c) 2011, Code Aurora Forum. All rights reserved. 10 * Copyright (C) Research In Motion Limited 2011. All rights reserved. 11 * Copyright (C) 2012 Google Inc. All rights reserved. 12 * 13 * This library is free software; you can redistribute it and/or 14 * modify it under the terms of the GNU Library General Public 15 * License as published by the Free Software Foundation; either 16 * version 2 of the License, or (at your option) any later version. 17 * 18 * This library is distributed in the hope that it will be useful, 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 21 * Library General Public License for more details. 22 * 23 * You should have received a copy of the GNU Library General Public License 24 * along with this library; see the file COPYING.LIB. If not, write to 25 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 26 * Boston, MA 02110-1301, USA. 27 */ 28 29 #ifndef SelectorFilter_h 30 #define SelectorFilter_h 31 32 #include "core/dom/Element.h" 33 #include "wtf/BloomFilter.h" 34 #include "wtf/Vector.h" 35 36 namespace blink { 37 38 class CSSSelector; 39 40 class SelectorFilter { 41 DISALLOW_ALLOCATION(); 42 public: 43 class ParentStackFrame { 44 ALLOW_ONLY_INLINE_ALLOCATION(); 45 public: 46 ParentStackFrame() : element(nullptr) { } 47 explicit ParentStackFrame(Element& element) : element(&element) { } 48 49 void trace(Visitor*); 50 51 RawPtrWillBeMember<Element> element; 52 Vector<unsigned, 4> identifierHashes; 53 }; 54 55 void pushParentStackFrame(Element& parent); 56 void popParentStackFrame(); 57 58 void setupParentStack(Element& parent); 59 void pushParent(Element& parent); 60 void popParent() { popParentStackFrame(); } 61 bool parentStackIsEmpty() const { return m_parentStack.isEmpty(); } 62 bool parentStackIsConsistent(const ContainerNode* parentNode) const { return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode; } 63 64 template <unsigned maximumIdentifierCount> 65 inline bool fastRejectSelector(const unsigned* identifierHashes) const; 66 static void collectIdentifierHashes(const CSSSelector&, unsigned* identifierHashes, unsigned maximumIdentifierCount); 67 68 void trace(Visitor*); 69 70 private: 71 WillBeHeapVector<ParentStackFrame> m_parentStack; 72 73 // With 100 unique strings in the filter, 2^12 slot table has false positive rate of ~0.2%. 74 static const unsigned bloomFilterKeyBits = 12; 75 OwnPtr<BloomFilter<bloomFilterKeyBits> > m_ancestorIdentifierFilter; 76 }; 77 78 template <unsigned maximumIdentifierCount> 79 inline bool SelectorFilter::fastRejectSelector(const unsigned* identifierHashes) const 80 { 81 ASSERT(m_ancestorIdentifierFilter); 82 for (unsigned n = 0; n < maximumIdentifierCount && identifierHashes[n]; ++n) { 83 if (!m_ancestorIdentifierFilter->mayContain(identifierHashes[n])) 84 return true; 85 } 86 return false; 87 } 88 89 } 90 91 WTF_ALLOW_INIT_WITH_MEM_FUNCTIONS(blink::SelectorFilter::ParentStackFrame); 92 93 #endif 94
