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 WebCore { 37 38 class CSSSelector; 39 40 class SelectorFilter { 41 public: 42 void pushParentStackFrame(Element* parent); 43 void popParentStackFrame(); 44 45 void setupParentStack(Element* parent); 46 void pushParent(Element* parent); 47 void popParent() { popParentStackFrame(); } 48 bool parentStackIsEmpty() const { return m_parentStack.isEmpty(); } 49 bool parentStackIsConsistent(const ContainerNode* parentNode) const { return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode; } 50 51 template <unsigned maximumIdentifierCount> 52 inline bool fastRejectSelector(const unsigned* identifierHashes) const; 53 static void collectIdentifierHashes(const CSSSelector*, unsigned* identifierHashes, unsigned maximumIdentifierCount); 54 55 private: 56 struct ParentStackFrame { 57 ParentStackFrame() : element(0) { } 58 ParentStackFrame(Element* element) : element(element) { } 59 Element* element; 60 Vector<unsigned, 4> identifierHashes; 61 }; 62 Vector<ParentStackFrame> m_parentStack; 63 64 // With 100 unique strings in the filter, 2^12 slot table has false positive rate of ~0.2%. 65 static const unsigned bloomFilterKeyBits = 12; 66 OwnPtr<BloomFilter<bloomFilterKeyBits> > m_ancestorIdentifierFilter; 67 }; 68 69 template <unsigned maximumIdentifierCount> 70 inline bool SelectorFilter::fastRejectSelector(const unsigned* identifierHashes) const 71 { 72 ASSERT(m_ancestorIdentifierFilter); 73 for (unsigned n = 0; n < maximumIdentifierCount && identifierHashes[n]; ++n) { 74 if (!m_ancestorIdentifierFilter->mayContain(identifierHashes[n])) 75 return true; 76 } 77 return false; 78 } 79 80 } 81 82 #endif 83
