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 "HTMLEntitySearch.h" 28 29#include "HTMLEntityTable.h" 30 31namespace WebCore { 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 UChar entryNextCharacter = entry->entity[m_currentLength]; 51 if (entryNextCharacter == nextCharacter) 52 return Prefix; 53 return entryNextCharacter < nextCharacter ? Before : After; 54} 55 56const HTMLEntityTableEntry* HTMLEntitySearch::findFirst(UChar nextCharacter) const 57{ 58 const HTMLEntityTableEntry* left = m_first; 59 const HTMLEntityTableEntry* right = m_last; 60 if (left == right) 61 return left; 62 CompareResult result = compare(left, nextCharacter); 63 if (result == Prefix) 64 return left; 65 if (result == After) 66 return right; 67 while (left + 1 < right) { 68 const HTMLEntityTableEntry* probe = halfway(left, right); 69 result = compare(probe, nextCharacter); 70 if (result == Before) 71 left = probe; 72 else { 73 ASSERT(result == After || result == Prefix); 74 right = probe; 75 } 76 } 77 ASSERT(left + 1 == right); 78 return right; 79} 80 81const HTMLEntityTableEntry* HTMLEntitySearch::findLast(UChar nextCharacter) const 82{ 83 const HTMLEntityTableEntry* left = m_first; 84 const HTMLEntityTableEntry* right = m_last; 85 if (left == right) 86 return right; 87 CompareResult result = compare(right, nextCharacter); 88 if (result == Prefix) 89 return right; 90 if (result == Before) 91 return left; 92 while (left + 1 < right) { 93 const HTMLEntityTableEntry* probe = halfway(left, right); 94 result = compare(probe, nextCharacter); 95 if (result == After) 96 right = probe; 97 else { 98 ASSERT(result == Before || result == Prefix); 99 left = probe; 100 } 101 } 102 ASSERT(left + 1 == right); 103 return left; 104} 105 106void HTMLEntitySearch::advance(UChar nextCharacter) 107{ 108 ASSERT(isEntityPrefix()); 109 if (!m_currentLength) { 110 m_first = HTMLEntityTable::firstEntryStartingWith(nextCharacter); 111 m_last = HTMLEntityTable::lastEntryStartingWith(nextCharacter); 112 if (!m_first || !m_last) 113 return fail(); 114 } else { 115 m_first = findFirst(nextCharacter); 116 m_last = findLast(nextCharacter); 117 if (m_first == m_last && compare(m_first, nextCharacter) != Prefix) 118 return fail(); 119 } 120 ++m_currentLength; 121 if (m_first->length != m_currentLength) { 122 return; 123 } 124 m_mostRecentMatch = m_first; 125} 126 127} 128