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
31 namespace WebCore {
32
33 namespace {
34
halfway(const HTMLEntityTableEntry * left,const HTMLEntityTableEntry * right)35 const HTMLEntityTableEntry* halfway(const HTMLEntityTableEntry* left, const HTMLEntityTableEntry* right)
36 {
37 return &left[(right - left) / 2];
38 }
39
40 }
41
HTMLEntitySearch()42 HTMLEntitySearch::HTMLEntitySearch()
43 : m_currentLength(0)
44 , m_currentValue(0)
45 , m_mostRecentMatch(0)
46 , m_first(HTMLEntityTable::firstEntry())
47 , m_last(HTMLEntityTable::lastEntry())
48 {
49 }
50
compare(const HTMLEntityTableEntry * entry,UChar nextCharacter) const51 HTMLEntitySearch::CompareResult HTMLEntitySearch::compare(const HTMLEntityTableEntry* entry, UChar nextCharacter) const
52 {
53 if (entry->length < m_currentLength + 1)
54 return Before;
55 UChar entryNextCharacter = entry->entity[m_currentLength];
56 if (entryNextCharacter == nextCharacter)
57 return Prefix;
58 return entryNextCharacter < nextCharacter ? Before : After;
59 }
60
findFirst(UChar nextCharacter) const61 const HTMLEntityTableEntry* HTMLEntitySearch::findFirst(UChar nextCharacter) const
62 {
63 const HTMLEntityTableEntry* left = m_first;
64 const HTMLEntityTableEntry* right = m_last;
65 if (left == right)
66 return left;
67 CompareResult result = compare(left, nextCharacter);
68 if (result == Prefix)
69 return left;
70 if (result == After)
71 return right;
72 while (left + 1 < right) {
73 const HTMLEntityTableEntry* probe = halfway(left, right);
74 result = compare(probe, nextCharacter);
75 if (result == Before)
76 left = probe;
77 else {
78 ASSERT(result == After || result == Prefix);
79 right = probe;
80 }
81 }
82 ASSERT(left + 1 == right);
83 return right;
84 }
85
findLast(UChar nextCharacter) const86 const HTMLEntityTableEntry* HTMLEntitySearch::findLast(UChar nextCharacter) const
87 {
88 const HTMLEntityTableEntry* left = m_first;
89 const HTMLEntityTableEntry* right = m_last;
90 if (left == right)
91 return right;
92 CompareResult result = compare(right, nextCharacter);
93 if (result == Prefix)
94 return right;
95 if (result == Before)
96 return left;
97 while (left + 1 < right) {
98 const HTMLEntityTableEntry* probe = halfway(left, right);
99 result = compare(probe, nextCharacter);
100 if (result == After)
101 right = probe;
102 else {
103 ASSERT(result == Before || result == Prefix);
104 left = probe;
105 }
106 }
107 ASSERT(left + 1 == right);
108 return left;
109 }
110
advance(UChar nextCharacter)111 void HTMLEntitySearch::advance(UChar nextCharacter)
112 {
113 ASSERT(isEntityPrefix());
114 if (!m_currentLength) {
115 m_first = HTMLEntityTable::firstEntryStartingWith(nextCharacter);
116 m_last = HTMLEntityTable::lastEntryStartingWith(nextCharacter);
117 if (!m_first || !m_last)
118 return fail();
119 } else {
120 m_first = findFirst(nextCharacter);
121 m_last = findLast(nextCharacter);
122 if (m_first == m_last && compare(m_first, nextCharacter) != Prefix)
123 return fail();
124 }
125 ++m_currentLength;
126 if (m_first->length != m_currentLength) {
127 m_currentValue = 0;
128 return;
129 }
130 m_mostRecentMatch = m_first;
131 m_currentValue = m_mostRecentMatch->value;
132 }
133
134 }
135