12fc2651226baac27029e38c9d6ef883fa32084dbSteve Block/* 22fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. 32fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 42fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * Redistribution and use in source and binary forms, with or without 52fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * modification, are permitted provided that the following conditions are 62fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * met: 72fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 82fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * * Redistributions of source code must retain the above copyright 92fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * notice, this list of conditions and the following disclaimer. 102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * * Redistributions in binary form must reproduce the above 112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * copyright notice, this list of conditions and the following disclaimer 122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * in the documentation and/or other materials provided with the 132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * distribution. 142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * * Neither the name of Google Inc. nor the names of its 152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * contributors may be used to endorse or promote products derived from 162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * this software without specific prior written permission. 172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block */ 302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef DocumentOrderedMap_h 322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#define DocumentOrderedMap_h 332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/HashCountedSet.h> 352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/HashMap.h> 362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/text/AtomicStringImpl.h> 372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 382fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace WebCore { 392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 402fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockclass Element; 412daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdochclass TreeScope; 422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 432fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockclass DocumentOrderedMap { 442fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockpublic: 452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void add(AtomicStringImpl*, Element*); 462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void remove(AtomicStringImpl*, Element*); 472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void clear(); 482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool contains(AtomicStringImpl*) const; 502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool containsMultiple(AtomicStringImpl*) const; 512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // concrete instantiations of the get<>() method template 522daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch Element* getElementById(AtomicStringImpl*, const TreeScope*) const; 532daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch Element* getElementByMapName(AtomicStringImpl*, const TreeScope*) const; 542daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch Element* getElementByLowercasedMapName(AtomicStringImpl*, const TreeScope*) const; 552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void checkConsistency() const; 572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 582fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockprivate: 592daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch template<bool keyMatches(AtomicStringImpl*, Element*)> Element* get(AtomicStringImpl*, const TreeScope*) const; 602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block typedef HashMap<AtomicStringImpl*, Element*> Map; 622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // We maintain the invariant that m_duplicateCounts is the count of all elements with a given key 642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // excluding the one referenced in m_map, if any. This means it one less than the total count 652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // when the first node with a given key is cached, otherwise the same as the total count. 662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block mutable Map m_map; 672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block mutable HashCountedSet<AtomicStringImpl*> m_duplicateCounts; 682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 702fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline bool DocumentOrderedMap::contains(AtomicStringImpl* id) const 712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_map.contains(id) || m_duplicateCounts.contains(id); 732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 752fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline bool DocumentOrderedMap::containsMultiple(AtomicStringImpl* id) const 762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_duplicateCounts.contains(id); 782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // namespace WebCore 812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif // DocumentOrderedMap_h 832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 84