1/* 2 * Copyright (C) 2010 Google, 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 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#include "config.h" 27#include "core/html/parser/HTMLEntitySearch.h" 28 29#include "core/html/parser/HTMLEntityTable.h" 30 31namespace blink { 32 33static const HTMLEntityTableEntry* halfway(const HTMLEntityTableEntry* left, const HTMLEntityTableEntry* right) 34{ 35 return &left[(right - left) / 2]; 36} 37 38HTMLEntitySearch::HTMLEntitySearch() 39 : m_currentLength(0) 40 , m_mostRecentMatch(0) 41 , m_first(HTMLEntityTable::firstEntry()) 42 , m_last(HTMLEntityTable::lastEntry()) 43{ 44} 45 46HTMLEntitySearch::CompareResult HTMLEntitySearch::compare(const HTMLEntityTableEntry* entry, UChar nextCharacter) const 47{ 48 if (entry->length < m_currentLength + 1) 49 return Before; 50 const LChar* entityString = HTMLEntityTable::entityString(*entry); 51 UChar entryNextCharacter = entityString[m_currentLength]; 52 if (entryNextCharacter == nextCharacter) 53 return Prefix; 54 return entryNextCharacter < nextCharacter ? Before : After; 55} 56 57const HTMLEntityTableEntry* HTMLEntitySearch::findFirst(UChar nextCharacter) const 58{ 59 const HTMLEntityTableEntry* left = m_first; 60 const HTMLEntityTableEntry* right = m_last; 61 if (left == right) 62 return left; 63 CompareResult result = compare(left, nextCharacter); 64 if (result == Prefix) 65 return left; 66 if (result == After) 67 return right; 68 while (left + 1 < right) { 69 const HTMLEntityTableEntry* probe = halfway(left, right); 70 result = compare(probe, nextCharacter); 71 if (result == Before) 72 left = probe; 73 else { 74 ASSERT(result == After || result == Prefix); 75 right = probe; 76 } 77 } 78 ASSERT(left + 1 == right); 79 return right; 80} 81 82const HTMLEntityTableEntry* HTMLEntitySearch::findLast(UChar nextCharacter) const 83{ 84 const HTMLEntityTableEntry* left = m_first; 85 const HTMLEntityTableEntry* right = m_last; 86 if (left == right) 87 return right; 88 CompareResult result = compare(right, nextCharacter); 89 if (result == Prefix) 90 return right; 91 if (result == Before) 92 return left; 93 while (left + 1 < right) { 94 const HTMLEntityTableEntry* probe = halfway(left, right); 95 result = compare(probe, nextCharacter); 96 if (result == After) 97 right = probe; 98 else { 99 ASSERT(result == Before || result == Prefix); 100 left = probe; 101 } 102 } 103 ASSERT(left + 1 == right); 104 return left; 105} 106 107void HTMLEntitySearch::advance(UChar nextCharacter) 108{ 109 ASSERT(isEntityPrefix()); 110 if (!m_currentLength) { 111 m_first = HTMLEntityTable::firstEntryStartingWith(nextCharacter); 112 m_last = HTMLEntityTable::lastEntryStartingWith(nextCharacter); 113 if (!m_first || !m_last) 114 return fail(); 115 } else { 116 m_first = findFirst(nextCharacter); 117 m_last = findLast(nextCharacter); 118 if (m_first == m_last && compare(m_first, nextCharacter) != Prefix) 119 return fail(); 120 } 121 ++m_currentLength; 122 if (m_first->length != m_currentLength) { 123 return; 124 } 125 m_mostRecentMatch = m_first; 126} 127 128} 129