12fc2651226baac27029e38c9d6ef883fa32084dbSteve Block/* 22fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 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#include "config.h" 322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "DocumentOrderedMap.h" 332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "Element.h" 352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "HTMLMapElement.h" 362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "HTMLNames.h" 372daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch#include "TreeScope.h" 382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 392fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace WebCore { 402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 412fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing namespace HTMLNames; 422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 432fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline bool keyMatchesId(AtomicStringImpl* key, Element* element) 442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return element->hasID() && element->getIdAttribute().impl() == key; 462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 482fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline bool keyMatchesMapName(AtomicStringImpl* key, Element* element) 492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().impl() == key; 512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 532fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline bool keyMatchesLowercasedMapName(AtomicStringImpl* key, Element* element) 542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key; 562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 582fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid DocumentOrderedMap::clear() 592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.clear(); 612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_duplicateCounts.clear(); 622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 642fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid DocumentOrderedMap::add(AtomicStringImpl* key, Element* element) 652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(key); 672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(element); 682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!m_duplicateCounts.contains(key)) { 702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Fast path. The key is not already in m_duplicateCounts, so we assume that it's 712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // also not already in m_map and try to add it. If that add succeeds, we're done. 722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block pair<Map::iterator, bool> addResult = m_map.add(key, element); 732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (addResult.second) 742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return; 752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The add failed, so this key was already cached in m_map. 772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // There are multiple elements with this key. Remove the m_map 782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // cache for this key so get searches for it next time it is called. 792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.remove(addResult.first); 802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_duplicateCounts.add(key); 812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else { 822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // There are multiple elements with this key. Remove the m_map 832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // cache for this key so get will search for it next time it is called. 842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Map::iterator cachedItem = m_map.find(key); 852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (cachedItem != m_map.end()) { 862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.remove(cachedItem); 872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_duplicateCounts.add(key); 882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_duplicateCounts.add(key); 922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 942fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element) 952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(key); 972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(element); 982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.checkConsistency(); 1002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Map::iterator cachedItem = m_map.find(key); 1012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (cachedItem != m_map.end() && cachedItem->second == element) 1022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.remove(cachedItem); 1032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block else 1042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_duplicateCounts.remove(key); 1052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 1062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1072fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktemplate<bool keyMatches(AtomicStringImpl*, Element*)> 1082daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdochinline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope* scope) const 1092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 1102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(key); 1112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.checkConsistency(); 1132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Element* element = m_map.get(key); 1152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (element) 1162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return element; 1172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_duplicateCounts.contains(key)) { 1192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // We know there's at least one node that matches; iterate to find the first one. 1202daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch for (Node* node = scope->firstChild(); node; node = node->traverseNextNode()) { 1212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!node->isElementNode()) 1222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block continue; 1232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block element = static_cast<Element*>(node); 1242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!keyMatches(key, element)) 1252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block continue; 1262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_duplicateCounts.remove(key); 1272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_map.set(key, element); 1282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return element; 1292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT_NOT_REACHED(); 1312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return 0; 1342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 1352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1362daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben MurdochElement* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const 1372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 1382daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch return get<keyMatchesId>(key, scope); 1392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 1402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1412daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben MurdochElement* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const 1422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 1432daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch return get<keyMatchesMapName>(key, scope); 1442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 1452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1462daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben MurdochElement* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const 1472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 1482daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch return get<keyMatchesLowercasedMapName>(key, scope); 1492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 1502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // namespace WebCore 1522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 153