1 /* 2 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #ifndef DocumentOrderedMap_h 32 #define DocumentOrderedMap_h 33 34 #include <wtf/HashCountedSet.h> 35 #include <wtf/HashMap.h> 36 #include <wtf/text/AtomicStringImpl.h> 37 38 namespace WebCore { 39 40 class Element; 41 class TreeScope; 42 43 class DocumentOrderedMap { 44 public: 45 void add(AtomicStringImpl*, Element*); 46 void remove(AtomicStringImpl*, Element*); 47 void clear(); 48 49 bool contains(AtomicStringImpl*) const; 50 bool containsMultiple(AtomicStringImpl*) const; 51 // concrete instantiations of the get<>() method template 52 Element* getElementById(AtomicStringImpl*, const TreeScope*) const; 53 Element* getElementByMapName(AtomicStringImpl*, const TreeScope*) const; 54 Element* getElementByLowercasedMapName(AtomicStringImpl*, const TreeScope*) const; 55 56 void checkConsistency() const; 57 58 private: 59 template<bool keyMatches(AtomicStringImpl*, Element*)> Element* get(AtomicStringImpl*, const TreeScope*) const; 60 61 typedef HashMap<AtomicStringImpl*, Element*> Map; 62 63 // We maintain the invariant that m_duplicateCounts is the count of all elements with a given key 64 // excluding the one referenced in m_map, if any. This means it one less than the total count 65 // when the first node with a given key is cached, otherwise the same as the total count. 66 mutable Map m_map; 67 mutable HashCountedSet<AtomicStringImpl*> m_duplicateCounts; 68 }; 69 70 inline bool DocumentOrderedMap::contains(AtomicStringImpl* id) const 71 { 72 return m_map.contains(id) || m_duplicateCounts.contains(id); 73 } 74 75 inline bool DocumentOrderedMap::containsMultiple(AtomicStringImpl* id) const 76 { 77 return m_duplicateCounts.contains(id); 78 } 79 80 } // namespace WebCore 81 82 #endif // DocumentOrderedMap_h 83 84
