code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/html/parser/HTMLEntitySearch.cpp

   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
  35 const HTMLEntityTableEntry* halfway(const HTMLEntityTableEntry* left, const HTMLEntityTableEntry* right)
  36 {
  37     return &left[(right - left) / 2];
  38 }
  39
  40 }
  41
  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
  51 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
  61 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
  86 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
 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 }