16f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 26f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org******************************************************************************* 36f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Copyright (C) 2010-2011, International Business Machines 46f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Corporation and others. All Rights Reserved. 56f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org******************************************************************************* 66f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* file name: ucharstrie.h 76f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* encoding: US-ASCII 86f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* tab size: 8 (not used) 96f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* indentation:4 106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* created on: 2010nov14 126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* created by: Markus W. Scherer 136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org*/ 146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/utypes.h" 166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/appendable.h" 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/ucharstrie.h" 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/uobject.h" 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/utf16.h" 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "cmemory.h" 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uassert.h" 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_NAMESPACE_BEGIN 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::~UCharsTrie() { 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(ownedArray_); 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::current() const { 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *pos=pos_; 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ? 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::firstForCodePoint(UChar32 cp) { 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return cp<=0xffff ? 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org first(cp) : 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org (USTRINGTRIE_HAS_NEXT(first(U16_LEAD(cp))) ? 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org next(U16_TRAIL(cp)) : 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org USTRINGTRIE_NO_MATCH); 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::nextForCodePoint(UChar32 cp) { 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return cp<=0xffff ? 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org next(cp) : 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org (USTRINGTRIE_HAS_NEXT(next(U16_LEAD(cp))) ? 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org next(U16_TRAIL(cp)) : 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org USTRINGTRIE_NO_MATCH); 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::branchNext(const UChar *pos, int32_t length, int32_t uchar) { 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Branch according to the current unit. 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length==0) { 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=*pos++; 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++length; 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The length of the branch is the number of units to select from. 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The data structure encodes a binary search. 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>kMaxBranchLinearSubNodeLength) { 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar<*pos++) { 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length>>=1; 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=jumpByDelta(pos); 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-(length>>1); 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipDelta(pos); 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Drop down to linear search for the last few units. 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // and divides length by 2. 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar==*pos++) { 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UStringTrieResult result; 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos; 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node&kValueIsFinal) { 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Leave the final value for getValue() to read. 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result=USTRINGTRIE_FINAL_VALUE; 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Use the non-final value as the jump delta. 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // int32_t delta=readValue(pos, node); 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t delta; 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinTwoUnitValueLead) { 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=node; 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kThreeUnitValueLead) { 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=((node-kMinTwoUnitValueLead)<<16)|*pos++; 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=(pos[0]<<16)|pos[1]; 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=2; 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // end readValue() 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=delta; 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos; 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos); 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(length>1); 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar==*pos++) { 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos; 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 1226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::nextImpl(const UChar *pos, int32_t uchar) { 1236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 1246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 1256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 1266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return branchNext(pos, node, uchar); 1276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinValueLead) { 1286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Match the first of length+1 units. 1296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=node-kMinLinearMatch; // Actual match length minus 1. 1306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar==*pos++) { 1316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=--length; 1326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 1346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 1356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No match. 1376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 1386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node&kValueIsFinal) { 1406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No further matching units. 1416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 1426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Skip intermediate value. 1446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipNodeValue(pos, node); 1456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node&=kNodeTypeMask; 1466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 1496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 1536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::next(int32_t uchar) { 1546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *pos=pos_; 1556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 1566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. 1596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length>=0) { 1606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Remaining part of a linear-match node. 1616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar==*pos++) { 1626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=--length; 1636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 1656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 1666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 1676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 1696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return nextImpl(pos, uchar); 1736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 1766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::next(const UChar *s, int32_t sLength) { 1776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength<0 ? *s==0 : sLength==0) { 1786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Empty input. 1796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return current(); 1806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *pos=pos_; 1826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 1836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. 1866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 1876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Fetch the next input unit, if there is one. 1886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Continue a linear-match node without rechecking sLength<0. 1896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t uchar; 1906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength<0) { 1916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 1926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((uchar=*s++)==0) { 1936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 1946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 1966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 1976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 1986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length<0) { 2006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 2026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar!=*pos) { 2046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 2086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 2096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 2126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength==0) { 2136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 2156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 2166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 2176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 2186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uchar=*s++; 2206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --sLength; 2216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length<0) { 2226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 2246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar!=*pos) { 2266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 2306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 2316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 2346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 2356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 2366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UStringTrieResult result=branchNext(pos, node, uchar); 2376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(result==USTRINGTRIE_NO_MATCH) { 2386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Fetch the next input unit, if there is one. 2416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength<0) { 2426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((uchar=*s++)==0) { 2436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 2446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength==0) { 2476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 2486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uchar=*s++; 2506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --sLength; 2516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(result==USTRINGTRIE_FINAL_VALUE) { 2536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No further matching units. 2546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=pos_; // branchNext() advanced pos and wrote it to pos_ . 2586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 2596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinValueLead) { 2606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Match length+1 units. 2616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=node-kMinLinearMatch; // Actual match length minus 1. 2626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(uchar!=*pos) { 2636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 2676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 2686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 2696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node&kValueIsFinal) { 2706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No further matching units. 2716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Skip intermediate value. 2756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipNodeValue(pos, node); 2766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node&=kNodeTypeMask; 2776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgconst UChar * 2836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::findUniqueValueFromBranch(const UChar *pos, int32_t length, 2846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool haveUniqueValue, int32_t &uniqueValue) { 2856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>kMaxBranchLinearSubNodeLength) { 2866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; // ignore the comparison unit 2876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) { 2886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-(length>>1); 2916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipDelta(pos); 2926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 2946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; // ignore a comparison unit 2956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // handle its value 2966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 2976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool isFinal=(UBool)(node>>15); 2986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node&=0x7fff; 2996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value=readValue(pos, node); 3006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos, node); 3016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(isFinal) { 3026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(haveUniqueValue) { 3036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(value!=uniqueValue) { 3046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uniqueValue=value; 3086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) { 3126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(--length>1); 3176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return pos+1; // ignore the last comparison unit 3186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 3216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::findUniqueValue(const UChar *pos, UBool haveUniqueValue, int32_t &uniqueValue) { 3226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 3236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 3246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 3256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node==0) { 3266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 3276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue); 3296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 3306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 3316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 3346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinValueLead) { 3356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // linear-match node 3366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=node-kMinLinearMatch+1; // Ignore the match units. 3376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 3386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool isFinal=(UBool)(node>>15); 3406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value; 3416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(isFinal) { 3426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=readValue(pos, node&0x7fff); 3436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=readNodeValue(pos, node); 3456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(haveUniqueValue) { 3476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(value!=uniqueValue) { 3486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 3496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uniqueValue=value; 3526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(isFinal) { 3556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 3566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipNodeValue(pos, node); 3586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node&=kNodeTypeMask; 3596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 3646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::getNextUChars(Appendable &out) const { 3656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UChar *pos=pos_; 3666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 3676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 0; 3686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(remainingMatchLength_>=0) { 3706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org out.appendCodeUnit(*pos); // Next unit of a pending linear-match node. 3716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 1; 3726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 3746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node>=kMinValueLead) { 3756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node&kValueIsFinal) { 3766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 0; 3776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipNodeValue(pos, node); 3796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node&=kNodeTypeMask; 3806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 3836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node==0) { 3846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 3856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org out.reserveAppendCapacity(++node); 3876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org getNextBranchUChars(pos, node, out); 3886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return node; 3896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // First unit of the linear-match node. 3916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org out.appendCodeUnit(*pos); 3926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 1; 3936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 3976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUCharsTrie::getNextBranchUChars(const UChar *pos, int32_t length, Appendable &out) { 3986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>kMaxBranchLinearSubNodeLength) { 3996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; // ignore the comparison unit 4006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org getNextBranchUChars(jumpByDelta(pos), length>>1, out); 4016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-(length>>1); 4026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipDelta(pos); 4036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 4056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org out.appendCodeUnit(*pos++); 4066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos); 4076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(--length>1); 4086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org out.appendCodeUnit(*pos); 4096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_NAMESPACE_END 412