Home | History | Annotate | Download | only in dom
      1 /*
      2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 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 #include "config.h"
     32 #include "DocumentOrderedMap.h"
     33 
     34 #include "Element.h"
     35 #include "HTMLMapElement.h"
     36 #include "HTMLNames.h"
     37 #include "TreeScope.h"
     38 
     39 namespace WebCore {
     40 
     41 using namespace HTMLNames;
     42 
     43 inline bool keyMatchesId(AtomicStringImpl* key, Element* element)
     44 {
     45     return element->hasID() && element->getIdAttribute().impl() == key;
     46 }
     47 
     48 inline bool keyMatchesMapName(AtomicStringImpl* key, Element* element)
     49 {
     50     return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().impl() == key;
     51 }
     52 
     53 inline bool keyMatchesLowercasedMapName(AtomicStringImpl* key, Element* element)
     54 {
     55     return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key;
     56 }
     57 
     58 void DocumentOrderedMap::clear()
     59 {
     60     m_map.clear();
     61     m_duplicateCounts.clear();
     62 }
     63 
     64 void DocumentOrderedMap::add(AtomicStringImpl* key, Element* element)
     65 {
     66     ASSERT(key);
     67     ASSERT(element);
     68 
     69     if (!m_duplicateCounts.contains(key)) {
     70         // Fast path. The key is not already in m_duplicateCounts, so we assume that it's
     71         // also not already in m_map and try to add it. If that add succeeds, we're done.
     72         pair<Map::iterator, bool> addResult = m_map.add(key, element);
     73         if (addResult.second)
     74             return;
     75 
     76         // The add failed, so this key was already cached in m_map.
     77         // There are multiple elements with this key. Remove the m_map
     78         // cache for this key so get searches for it next time it is called.
     79         m_map.remove(addResult.first);
     80         m_duplicateCounts.add(key);
     81     } else {
     82         // There are multiple elements with this key. Remove the m_map
     83         // cache for this key so get will search for it next time it is called.
     84         Map::iterator cachedItem = m_map.find(key);
     85         if (cachedItem != m_map.end()) {
     86             m_map.remove(cachedItem);
     87             m_duplicateCounts.add(key);
     88         }
     89     }
     90 
     91     m_duplicateCounts.add(key);
     92 }
     93 
     94 void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element)
     95 {
     96     ASSERT(key);
     97     ASSERT(element);
     98 
     99     m_map.checkConsistency();
    100     Map::iterator cachedItem = m_map.find(key);
    101     if (cachedItem != m_map.end() && cachedItem->second == element)
    102         m_map.remove(cachedItem);
    103     else
    104         m_duplicateCounts.remove(key);
    105 }
    106 
    107 template<bool keyMatches(AtomicStringImpl*, Element*)>
    108 inline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope* scope) const
    109 {
    110     ASSERT(key);
    111 
    112     m_map.checkConsistency();
    113 
    114     Element* element = m_map.get(key);
    115     if (element)
    116         return element;
    117 
    118     if (m_duplicateCounts.contains(key)) {
    119         // We know there's at least one node that matches; iterate to find the first one.
    120         for (Node* node = scope->firstChild(); node; node = node->traverseNextNode()) {
    121             if (!node->isElementNode())
    122                 continue;
    123             element = static_cast<Element*>(node);
    124             if (!keyMatches(key, element))
    125                 continue;
    126             m_duplicateCounts.remove(key);
    127             m_map.set(key, element);
    128             return element;
    129         }
    130         ASSERT_NOT_REACHED();
    131     }
    132 
    133     return 0;
    134 }
    135 
    136 Element* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const
    137 {
    138     return get<keyMatchesId>(key, scope);
    139 }
    140 
    141 Element* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const
    142 {
    143     return get<keyMatchesMapName>(key, scope);
    144 }
    145 
    146 Element* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const
    147 {
    148     return get<keyMatchesLowercasedMapName>(key, scope);
    149 }
    150 
    151 } // namespace WebCore
    152 
    153