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: bytestrie.cpp 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: 2010sep25 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/bytestream.h" 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/bytestrie.h" 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/uobject.h" 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "cmemory.h" 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uassert.h" 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_NAMESPACE_BEGIN 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::~BytesTrie() { 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(ownedArray_); 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// lead byte already shifted right by 1. 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::readValue(const uint8_t *pos, int32_t leadByte) { 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value; 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(leadByte<kMinTwoByteValueLead) { 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=leadByte-kMinOneByteValueLead; 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(leadByte<kMinThreeByteValueLead) { 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=((leadByte-kMinTwoByteValueLead)<<8)|*pos; 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(leadByte<kFourByteValueLead) { 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=((leadByte-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(leadByte==kFourByteValueLead) { 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=(pos[0]<<16)|(pos[1]<<8)|pos[2]; 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return value; 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgconst uint8_t * 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::jumpByDelta(const uint8_t *pos) { 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t delta=*pos++; 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(delta<kMinTwoByteDeltaLead) { 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // nothing to do 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(delta<kMinThreeByteDeltaLead) { 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=((delta-kMinTwoByteDeltaLead)<<8)|*pos++; 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(delta<kFourByteDeltaLead) { 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=((delta-kMinThreeByteDeltaLead)<<16)|(pos[0]<<8)|pos[1]; 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=2; 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(delta==kFourByteDeltaLead) { 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=3; 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=4; 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return pos+delta; 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::current() const { 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const uint8_t *pos=pos_; 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ? 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::branchNext(const uint8_t *pos, int32_t length, int32_t inByte) { 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Branch according to the current byte. 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length==0) { 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=*pos++; 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++length; 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The length of the branch is the number of bytes to select from. 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The data structure encodes a binary search. 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>kMaxBranchLinearSubNodeLength) { 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte<*pos++) { 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length>>=1; 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=jumpByDelta(pos); 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-(length>>1); 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipDelta(pos); 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Drop down to linear search for the last few bytes. 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // and divides length by 2. 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte==*pos++) { 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UStringTrieResult result; 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos; 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(node>=kMinValueLead); 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node&kValueIsFinal) { 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Leave the final value for getValue() to read. 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result=USTRINGTRIE_FINAL_VALUE; 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Use the non-final value as the jump delta. 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // int32_t delta=readValue(pos, node>>1); 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node>>=1; 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t delta; 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinTwoByteValueLead) { 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=node-kMinOneByteValueLead; 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinThreeByteValueLead) { 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=((node-kMinTwoByteValueLead)<<8)|*pos++; 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kFourByteValueLead) { 1186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=((node-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; 1196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=2; 1206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node==kFourByteValueLead) { 1216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; 1226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=3; 1236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; 1256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=4; 1266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // end readValue() 1286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=delta; 1296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos; 1306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; 1316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 1346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 1366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos); 1376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(length>1); 1386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte==*pos++) { 1396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos; 1416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; 1426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 1446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 1496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::nextImpl(const uint8_t *pos, int32_t inByte) { 1506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 1516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 1526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 1536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return branchNext(pos, node, inByte); 1546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinValueLead) { 1556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Match the first of length+1 bytes. 1566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=node-kMinLinearMatch; // Actual match length minus 1. 1576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte==*pos++) { 1586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=--length; 1596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 1606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 1616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 1626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No match. 1646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 1656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node&kValueIsFinal) { 1676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No further matching bytes. 1686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 1696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Skip intermediate value. 1716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos, node); 1726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The next node must not also be a value node. 1736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(*pos<kMinValueLead); 1746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 1776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 1816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::next(int32_t inByte) { 1826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const uint8_t *pos=pos_; 1836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 1846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 1856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte<0) { 1876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org inByte+=0x100; 1886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. 1906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length>=0) { 1916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Remaining part of a linear-match node. 1926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte==*pos++) { 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 } else { 1996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return nextImpl(pos, inByte); 2046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUStringTrieResult 2076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::next(const char *s, int32_t sLength) { 2086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength<0 ? *s==0 : sLength==0) { 2096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Empty input. 2106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return current(); 2116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const uint8_t *pos=pos_; 2136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 2146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. 2176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 2186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Fetch the next input byte, if there is one. 2196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Continue a linear-match node without rechecking sLength<0. 2206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t inByte; 2216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength<0) { 2226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 2236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((inByte=*s++)==0) { 2246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 2266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 2276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 2286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 2296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length<0) { 2316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 2336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte!=*pos) { 2356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 2396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 2406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 2436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength==0) { 2446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos_=pos; 2466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node; 2476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (length<0 && (node=*pos)>=kMinValueLead) ? 2486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org valueResult(node) : USTRINGTRIE_NO_VALUE; 2496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org inByte=*s++; 2516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --sLength; 2526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length<0) { 2536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org remainingMatchLength_=length; 2546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 2556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte!=*pos) { 2576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 2616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 2626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 2656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 2666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 2676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UStringTrieResult result=branchNext(pos, node, inByte); 2686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(result==USTRINGTRIE_NO_MATCH) { 2696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Fetch the next input byte, if there is one. 2726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength<0) { 2736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((inByte=*s++)==0) { 2746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 2756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(sLength==0) { 2786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return result; 2796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org inByte=*s++; 2816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --sLength; 2826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(result==USTRINGTRIE_FINAL_VALUE) { 2846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No further matching bytes. 2856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=pos_; // branchNext() advanced pos and wrote it to pos_ . 2896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinValueLead) { 2906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Match length+1 bytes. 2916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=node-kMinLinearMatch; // Actual match length minus 1. 2926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(inByte!=*pos) { 2936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 2946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 2956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; 2976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --length; 2986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 2996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node&kValueIsFinal) { 3006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // No further matching bytes. 3016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org stop(); 3026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return USTRINGTRIE_NO_MATCH; 3036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Skip intermediate value. 3056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos, node); 3066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The next node must not also be a value node. 3076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(*pos<kMinValueLead); 3086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgconst uint8_t * 3146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::findUniqueValueFromBranch(const uint8_t *pos, int32_t length, 3156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool haveUniqueValue, int32_t &uniqueValue) { 3166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>kMaxBranchLinearSubNodeLength) { 3176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; // ignore the comparison byte 3186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) { 3196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-(length>>1); 3226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipDelta(pos); 3236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 3256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; // ignore a comparison byte 3266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // handle its value 3276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 3286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool isFinal=(UBool)(node&kValueIsFinal); 3296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value=readValue(pos, node>>1); 3306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos, node); 3316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(isFinal) { 3326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(haveUniqueValue) { 3336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(value!=uniqueValue) { 3346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uniqueValue=value; 3386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) { 3426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(--length>1); 3476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return pos+1; // ignore the last comparison byte 3486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 3516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue) { 3526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(;;) { 3536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 3546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 3556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node==0) { 3566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 3576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue); 3596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 3606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 3616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(node<kMinValueLead) { 3646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // linear-match node 3656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos+=node-kMinLinearMatch+1; // Ignore the match bytes. 3666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool isFinal=(UBool)(node&kValueIsFinal); 3686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value=readValue(pos, node>>1); 3696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(haveUniqueValue) { 3706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(value!=uniqueValue) { 3716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 3726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uniqueValue=value; 3756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org haveUniqueValue=TRUE; 3766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(isFinal) { 3786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 3796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos, node); 3816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 3866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::getNextBytes(ByteSink &out) const { 3876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const uint8_t *pos=pos_; 3886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pos==NULL) { 3896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 0; 3906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(remainingMatchLength_>=0) { 3926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org append(out, *pos); // Next byte of a pending linear-match node. 3936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 1; 3946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t node=*pos++; 3966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node>=kMinValueLead) { 3976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node&kValueIsFinal) { 3986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 0; 3996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 4006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos, node); 4016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 4026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(node<kMinValueLead); 4036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node<kMinLinearMatch) { 4066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(node==0) { 4076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=*pos++; 4086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org getNextBranchBytes(pos, ++node, out); 4106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return node; 4116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 4126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // First byte of the linear-match node. 4136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org append(out, *pos); 4146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 1; 4156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 4196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out) { 4206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>kMaxBranchLinearSubNodeLength) { 4216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++pos; // ignore the comparison byte 4226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org getNextBranchBytes(jumpByDelta(pos), length>>1, out); 4236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-(length>>1); 4246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipDelta(pos); 4256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 4276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org append(out, *pos++); 4286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pos=skipValue(pos); 4296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(--length>1); 4306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org append(out, *pos); 4316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 4346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgBytesTrie::append(ByteSink &out, int c) { 4356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org char ch=(char)c; 4366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org out.Append(&ch, 1); 4376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_NAMESPACE_END 440