| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 31 namespace blink { | |
| 32 | |
| 33 static const HTMLEntityTableEntry* halfway(const HTMLEntityTableEntry* left, con
st HTMLEntityTableEntry* right) | |
| 34 { | |
| 35 return &left[(right - left) / 2]; | |
| 36 } | |
| 37 | |
| 38 HTMLEntitySearch::HTMLEntitySearch() | |
| 39 : m_currentLength(0) | |
| 40 , m_mostRecentMatch(0) | |
| 41 , m_first(HTMLEntityTable::firstEntry()) | |
| 42 , m_last(HTMLEntityTable::lastEntry()) | |
| 43 { | |
| 44 } | |
| 45 | |
| 46 HTMLEntitySearch::CompareResult HTMLEntitySearch::compare(const HTMLEntityTableE
ntry* 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 | |
| 57 const HTMLEntityTableEntry* HTMLEntitySearch::findFirst(UChar nextCharacter) con
st | |
| 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 | |
| 82 const HTMLEntityTableEntry* HTMLEntitySearch::findLast(UChar nextCharacter) cons
t | |
| 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 | |
| 107 void 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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
