16f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 26f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org******************************************************************************* 36f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Copyright (C) 2010-2012, International Business Machines 46f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Corporation and others. All Rights Reserved. 56f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org******************************************************************************* 66f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* file name: stringtriebuilder.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: 2010dec24 126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* created by: Markus W. Scherer 136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org*/ 146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "utypeinfo.h" // for 'typeid' to work 166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/utypes.h" 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/stringtriebuilder.h" 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uassert.h" 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uhash.h" 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CDECL_BEGIN 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic int32_t U_CALLCONV 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orghashStringTrieNode(const UHashTok key) { 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return icu::StringTrieBuilder::hashNode(key.pointer); 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic UBool U_CALLCONV 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgequalStringTrieNodes(const UHashTok key1, const UHashTok key2) { 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return icu::StringTrieBuilder::equalNodes(key1.pointer, key2.pointer); 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CDECL_END 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_NAMESPACE_BEGIN 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::StringTrieBuilder() : nodes(NULL) {} 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::~StringTrieBuilder() { 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org deleteCompactBuilder(); 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode) { 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org nodes=uhash_openSize(hashStringTrieNode, equalStringTrieNodes, NULL, 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org sizeGuess, &errorCode); 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_SUCCESS(errorCode)) { 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(nodes==NULL) { 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org errorCode=U_MEMORY_ALLOCATION_ERROR; 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uhash_setKeyDeleter(nodes, uprv_deleteUObject); 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::deleteCompactBuilder() { 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uhash_close(nodes); 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org nodes=NULL; 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::build(UStringTrieBuildOption buildOption, int32_t elementsLength, 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UErrorCode &errorCode) { 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(buildOption==USTRINGTRIE_BUILD_FAST) { 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeNode(0, elementsLength, 0); 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else /* USTRINGTRIE_BUILD_SMALL */ { 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org createCompactBuilder(2*elementsLength, errorCode); 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *root=makeNode(0, elementsLength, 0, errorCode); 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_SUCCESS(errorCode)) { 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org root->markRightEdgesFirst(-1); 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org root->write(*this); 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org deleteCompactBuilder(); 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// Requires start<limit, 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// and all strings of the [start..limit[ elements must be sorted and 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// have a common prefix of length unitIndex. 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::writeNode(int32_t start, int32_t limit, int32_t unitIndex) { 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool hasValue=FALSE; 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value=0; 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t type; 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(unitIndex==getElementStringLength(start)) { 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // An intermediate or final value. 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=getElementValue(start++); 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(start==limit) { 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return writeValueAndFinal(value, TRUE); // final-value node 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hasValue=TRUE; 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Now all [start..limit[ strings are longer than unitIndex. 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t minUnit=getElementUnit(start, unitIndex); 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t maxUnit=getElementUnit(limit-1, unitIndex); 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(minUnit==maxUnit) { 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Linear-match node: All strings have the same character at unitIndex. 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex); 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeNode(start, limit, lastUnitIndex); 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength. 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=lastUnitIndex-unitIndex; 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t maxLinearMatchLength=getMaxLinearMatchLength(); 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>maxLinearMatchLength) { 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org lastUnitIndex-=maxLinearMatchLength; 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length-=maxLinearMatchLength; 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeElementUnits(start, lastUnitIndex, maxLinearMatchLength); 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org write(getMinLinearMatch()+maxLinearMatchLength-1); 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeElementUnits(start, unitIndex, length); 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org type=getMinLinearMatch()+length-1; 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Branch node. 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=countElementUnits(start, limit, unitIndex); 1186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // length>=2 because minUnit!=maxUnit. 1196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeBranchSubNode(start, limit, unitIndex, length); 1206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(--length<getMinLinearMatch()) { 1216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org type=length; 1226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org write(length); 1246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org type=0; 1256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return writeValueAndType(hasValue, value, type); 1286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// start<limit && all strings longer than unitIndex && 1316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// length different units at unitIndex 1326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 1336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length) { 1346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UChar middleUnits[kMaxSplitBranchLevels]; 1356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t lessThan[kMaxSplitBranchLevels]; 1366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t ltLength=0; 1376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>getMaxBranchLinearSubNodeLength()) { 1386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Branch on the middle unit. 1396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // First, find the middle unit. 1406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2); 1416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Encode the less-than branch first. 1426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org middleUnits[ltLength]=getElementUnit(i, unitIndex); // middle unit 1436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org lessThan[ltLength]=writeBranchSubNode(start, i, unitIndex, length/2); 1446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++ltLength; 1456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Continue for the greater-or-equal branch. 1466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=i; 1476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-length/2; 1486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // For each unit, find its elements array start and whether it has a final value. 1506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t starts[kMaxBranchLinearSubNodeLength]; 1516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool isFinal[kMaxBranchLinearSubNodeLength-1]; 1526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t unitNumber=0; 1536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 1546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i=starts[unitNumber]=start; 1556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UChar unit=getElementUnit(i++, unitIndex); 1566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org i=indexOfElementWithNextUnit(i, unitIndex, unit); 1576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org isFinal[unitNumber]= start==i-1 && unitIndex+1==getElementStringLength(start); 1586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=i; 1596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(++unitNumber<length-1); 1606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // unitNumber==length-1, and the maxUnit elements range is [start..limit[ 1616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org starts[unitNumber]=start; 1626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the sub-nodes in reverse order: The jump lengths are deltas from 1646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // after their own positions, so if we wrote the minUnit sub-node first, 1656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // then its jump delta would be larger. 1666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Instead we write the minUnit sub-node last, for a shorter delta. 1676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t jumpTargets[kMaxBranchLinearSubNodeLength-1]; 1686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 1696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --unitNumber; 1706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!isFinal[unitNumber]) { 1716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org jumpTargets[unitNumber]=writeNode(starts[unitNumber], starts[unitNumber+1], unitIndex+1); 1726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(unitNumber>0); 1746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The maxUnit sub-node is written as the very last one because we do 1756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // not jump for it at all. 1766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unitNumber=length-1; 1776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeNode(start, limit, unitIndex+1); 1786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t offset=write(getElementUnit(start, unitIndex)); 1796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the rest of this node's unit-value pairs. 1806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(--unitNumber>=0) { 1816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=starts[unitNumber]; 1826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value; 1836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(isFinal[unitNumber]) { 1846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the final value for the one string ending with this unit. 1856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=getElementValue(start); 1866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the delta to the start position of the sub-node. 1886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=offset-jumpTargets[unitNumber]; 1896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeValueAndFinal(value, isFinal[unitNumber]); 1916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=write(getElementUnit(start, unitIndex)); 1926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the split-branch nodes. 1946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(ltLength>0) { 1956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --ltLength; 1966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org writeDeltaTo(lessThan[ltLength]); 1976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=write(middleUnits[ltLength]); 1986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return offset; 2006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// Requires start<limit, 2036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// and all strings of the [start..limit[ elements must be sorted and 2046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// have a common prefix of length unitIndex. 2056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::Node * 2066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode) { 2076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 2086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool hasValue=FALSE; 2116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value=0; 2126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(unitIndex==getElementStringLength(start)) { 2136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // An intermediate or final value. 2146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=getElementValue(start++); 2156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(start==limit) { 2166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return registerFinalValue(value, errorCode); 2176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org hasValue=TRUE; 2196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *node; 2216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Now all [start..limit[ strings are longer than unitIndex. 2226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t minUnit=getElementUnit(start, unitIndex); 2236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t maxUnit=getElementUnit(limit-1, unitIndex); 2246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(minUnit==maxUnit) { 2256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Linear-match node: All strings have the same character at unitIndex. 2266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex); 2276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *nextNode=makeNode(start, limit, lastUnitIndex, errorCode); 2286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength. 2296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=lastUnitIndex-unitIndex; 2306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t maxLinearMatchLength=getMaxLinearMatchLength(); 2316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>maxLinearMatchLength) { 2326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org lastUnitIndex-=maxLinearMatchLength; 2336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length-=maxLinearMatchLength; 2346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=createLinearMatchNode(start, lastUnitIndex, maxLinearMatchLength, nextNode); 2356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org nextNode=registerNode(node, errorCode); 2366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=createLinearMatchNode(start, unitIndex, length, nextNode); 2386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Branch node. 2406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length=countElementUnits(start, limit, unitIndex); 2416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // length>=2 because minUnit!=maxUnit. 2426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *subNode=makeBranchSubNode(start, limit, unitIndex, length, errorCode); 2436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=new BranchHeadNode(length, subNode); 2446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(hasValue && node!=NULL) { 2466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(matchNodesCanHaveValues()) { 2476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ((ValueNode *)node)->setValue(value); 2486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=new IntermediateValueNode(value, registerNode(node, errorCode)); 2506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return registerNode(node, errorCode); 2536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// start<limit && all strings longer than unitIndex && 2566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// length different units at unitIndex 2576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::Node * 2586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, 2596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t length, UErrorCode &errorCode) { 2606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 2616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UChar middleUnits[kMaxSplitBranchLevels]; 2646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *lessThan[kMaxSplitBranchLevels]; 2656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t ltLength=0; 2666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(length>getMaxBranchLinearSubNodeLength()) { 2676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Branch on the middle unit. 2686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // First, find the middle unit. 2696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2); 2706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Create the less-than branch. 2716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org middleUnits[ltLength]=getElementUnit(i, unitIndex); // middle unit 2726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org lessThan[ltLength]=makeBranchSubNode(start, i, unitIndex, length/2, errorCode); 2736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++ltLength; 2746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Continue for the greater-or-equal branch. 2756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=i; 2766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org length=length-length/2; 2776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 2796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ListBranchNode *listNode=new ListBranchNode(); 2826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(listNode==NULL) { 2836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org errorCode=U_MEMORY_ALLOCATION_ERROR; 2846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 2856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // For each unit, find its elements array start and whether it has a final value. 2876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t unitNumber=0; 2886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 2896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i=start; 2906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UChar unit=getElementUnit(i++, unitIndex); 2916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org i=indexOfElementWithNextUnit(i, unitIndex, unit); 2926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(start==i-1 && unitIndex+1==getElementStringLength(start)) { 2936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org listNode->add(unit, getElementValue(start)); 2946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org listNode->add(unit, makeNode(start, i, unitIndex+1, errorCode)); 2966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=i; 2986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(++unitNumber<length-1); 2996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // unitNumber==length-1, and the maxUnit elements range is [start..limit[ 3006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UChar unit=getElementUnit(start, unitIndex); 3016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(start==limit-1 && unitIndex+1==getElementStringLength(start)) { 3026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org listNode->add(unit, getElementValue(start)); 3036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 3046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org listNode->add(unit, makeNode(start, limit, unitIndex+1, errorCode)); 3056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *node=registerNode(listNode, errorCode); 3076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Create the split-branch nodes. 3086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(ltLength>0) { 3096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --ltLength; 3106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org node=registerNode( 3116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org new SplitBranchNode(middleUnits[ltLength], lessThan[ltLength], node), errorCode); 3126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return node; 3146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::Node * 3176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::registerNode(Node *newNode, UErrorCode &errorCode) { 3186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 3196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delete newNode; 3206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(newNode==NULL) { 3236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org errorCode=U_MEMORY_ALLOCATION_ERROR; 3246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashElement *old=uhash_find(nodes, newNode); 3276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(old!=NULL) { 3286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delete newNode; 3296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (Node *)old->key.pointer; 3306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // If uhash_puti() returns a non-zero value from an equivalent, previously 3326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // registered node, then uhash_find() failed to find that and we will leak newNode. 3336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#if U_DEBUG 3346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t oldValue= // Only in debug mode to avoid a compiler warning about unused oldValue. 3356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#endif 3366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uhash_puti(nodes, newNode, 1, &errorCode); 3376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(oldValue==0); 3386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 3396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delete newNode; 3406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return newNode; 3436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::Node * 3466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::registerFinalValue(int32_t value, UErrorCode &errorCode) { 3476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 3486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org FinalValueNode key(value); 3516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const UHashElement *old=uhash_find(nodes, &key); 3526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(old!=NULL) { 3536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (Node *)old->key.pointer; 3546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *newNode=new FinalValueNode(value); 3566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(newNode==NULL) { 3576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org errorCode=U_MEMORY_ALLOCATION_ERROR; 3586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // If uhash_puti() returns a non-zero value from an equivalent, previously 3616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // registered node, then uhash_find() failed to find that and we will leak newNode. 3626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#if U_DEBUG 3636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t oldValue= // Only in debug mode to avoid a compiler warning about unused oldValue. 3646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#endif 3656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uhash_puti(nodes, newNode, 1, &errorCode); 3666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(oldValue==0); 3676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(U_FAILURE(errorCode)) { 3686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org delete newNode; 3696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return NULL; 3706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return newNode; 3726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 3756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::hashNode(const void *node) { 3766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return ((const Node *)node)->hashCode(); 3776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 3806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::equalNodes(const void *left, const void *right) { 3816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return *(const Node *)left==*(const Node *)right; 3826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 3856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::Node::operator==(const Node &other) const { 3866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return this==&other || (typeid(*this)==typeid(other) && hash==other.hash); 3876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 3906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::Node::markRightEdgesFirst(int32_t edgeNumber) { 3916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(offset==0) { 3926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=edgeNumber; 3936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 3946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return edgeNumber; 3956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 3966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 3976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 3986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::FinalValueNode::operator==(const Node &other) const { 3996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 4006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 4016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!Node::operator==(other)) { 4036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 4046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const FinalValueNode &o=(const FinalValueNode &)other; 4066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return value==o.value; 4076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 4106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::FinalValueNode::write(StringTrieBuilder &builder) { 4116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.writeValueAndFinal(value, TRUE); 4126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 4156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::ValueNode::operator==(const Node &other) const { 4166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 4176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 4186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!Node::operator==(other)) { 4206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 4216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const ValueNode &o=(const ValueNode &)other; 4236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return hasValue==o.hasValue && (!hasValue || value==o.value); 4246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 4276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::IntermediateValueNode::operator==(const Node &other) const { 4286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 4296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 4306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!ValueNode::operator==(other)) { 4326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 4336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const IntermediateValueNode &o=(const IntermediateValueNode &)other; 4356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return next==o.next; 4366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 4396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::IntermediateValueNode::markRightEdgesFirst(int32_t edgeNumber) { 4406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(offset==0) { 4416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); 4426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return edgeNumber; 4446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 4476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::IntermediateValueNode::write(StringTrieBuilder &builder) { 4486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org next->write(builder); 4496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.writeValueAndFinal(value, FALSE); 4506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 4536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::LinearMatchNode::operator==(const Node &other) const { 4546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 4556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 4566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!ValueNode::operator==(other)) { 4586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 4596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const LinearMatchNode &o=(const LinearMatchNode &)other; 4616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return length==o.length && next==o.next; 4626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 4656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::LinearMatchNode::markRightEdgesFirst(int32_t edgeNumber) { 4666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(offset==0) { 4676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); 4686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return edgeNumber; 4706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 4736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::ListBranchNode::operator==(const Node &other) const { 4746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 4756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 4766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!Node::operator==(other)) { 4786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 4796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const ListBranchNode &o=(const ListBranchNode &)other; 4816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(int32_t i=0; i<length; ++i) { 4826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(units[i]!=o.units[i] || values[i]!=o.values[i] || equal[i]!=o.equal[i]) { 4836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 4846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 4866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 4876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 4886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 4896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 4906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::ListBranchNode::markRightEdgesFirst(int32_t edgeNumber) { 4916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(offset==0) { 4926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org firstEdgeNumber=edgeNumber; 4936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t step=0; 4946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i=length; 4956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 4966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *edge=equal[--i]; 4976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(edge!=NULL) { 4986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org edgeNumber=edge->markRightEdgesFirst(edgeNumber-step); 4996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // For all but the rightmost edge, decrement the edge number. 5016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org step=1; 5026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(i>0); 5036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=edgeNumber; 5046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return edgeNumber; 5066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 5096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::ListBranchNode::write(StringTrieBuilder &builder) { 5106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the sub-nodes in reverse order: The jump lengths are deltas from 5116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // after their own positions, so if we wrote the minUnit sub-node first, 5126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // then its jump delta would be larger. 5136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Instead we write the minUnit sub-node last, for a shorter delta. 5146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t unitNumber=length-1; 5156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Node *rightEdge=equal[unitNumber]; 5166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t rightEdgeNumber= rightEdge==NULL ? firstEdgeNumber : rightEdge->getOffset(); 5176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 5186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --unitNumber; 5196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(equal[unitNumber]!=NULL) { 5206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org equal[unitNumber]->writeUnlessInsideRightEdge(firstEdgeNumber, rightEdgeNumber, builder); 5216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(unitNumber>0); 5236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The maxUnit sub-node is written as the very last one because we do 5246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // not jump for it at all. 5256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unitNumber=length-1; 5266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(rightEdge==NULL) { 5276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org builder.writeValueAndFinal(values[unitNumber], TRUE); 5286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 5296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org rightEdge->write(builder); 5306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.write(units[unitNumber]); 5326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the rest of this node's unit-value pairs. 5336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(--unitNumber>=0) { 5346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t value; 5356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool isFinal; 5366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(equal[unitNumber]==NULL) { 5376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the final value for the one string ending with this unit. 5386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=values[unitNumber]; 5396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org isFinal=TRUE; 5406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 5416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write the delta to the start position of the sub-node. 5426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(equal[unitNumber]->getOffset()>0); 5436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org value=offset-equal[unitNumber]->getOffset(); 5446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org isFinal=FALSE; 5456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org builder.writeValueAndFinal(value, isFinal); 5476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.write(units[unitNumber]); 5486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 5526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::SplitBranchNode::operator==(const Node &other) const { 5536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 5546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 5556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!Node::operator==(other)) { 5576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 5586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const SplitBranchNode &o=(const SplitBranchNode &)other; 5606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return unit==o.unit && lessThan==o.lessThan && greaterOrEqual==o.greaterOrEqual; 5616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 5646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::SplitBranchNode::markRightEdgesFirst(int32_t edgeNumber) { 5656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(offset==0) { 5666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org firstEdgeNumber=edgeNumber; 5676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org edgeNumber=greaterOrEqual->markRightEdgesFirst(edgeNumber); 5686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=edgeNumber=lessThan->markRightEdgesFirst(edgeNumber-1); 5696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return edgeNumber; 5716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 5746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::SplitBranchNode::write(StringTrieBuilder &builder) { 5756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Encode the less-than branch first. 5766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org lessThan->writeUnlessInsideRightEdge(firstEdgeNumber, greaterOrEqual->getOffset(), builder); 5776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Encode the greater-or-equal branch last because we do not jump for it at all. 5786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org greaterOrEqual->write(builder); 5796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Write this node. 5806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org U_ASSERT(lessThan->getOffset()>0); 5816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org builder.writeDeltaTo(lessThan->getOffset()); // less-than 5826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.write(unit); 5836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgUBool 5866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::BranchHeadNode::operator==(const Node &other) const { 5876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(this==&other) { 5886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TRUE; 5896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(!ValueNode::operator==(other)) { 5916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return FALSE; 5926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 5936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const BranchHeadNode &o=(const BranchHeadNode &)other; 5946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return length==o.length && next==o.next; 5956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 5966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 5976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint32_t 5986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::BranchHeadNode::markRightEdgesFirst(int32_t edgeNumber) { 5996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(offset==0) { 6006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); 6016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 6026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return edgeNumber; 6036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid 6066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgStringTrieBuilder::BranchHeadNode::write(StringTrieBuilder &builder) { 6076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org next->write(builder); 6086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length<=builder.getMinLinearMatch()) { 6096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.writeValueAndType(hasValue, value, length-1); 6106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 6116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org builder.write(length-1); 6126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org offset=builder.writeValueAndType(hasValue, value, 0); 6136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 6146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 6156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 6166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_NAMESPACE_END 617