1b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/* 2b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho******************************************************************************* 3b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Copyright (C) 2010-2011, International Business Machines 4b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Corporation and others. All Rights Reserved. 5b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho******************************************************************************* 6b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* file name: stringtriebuilder.cpp 7b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* encoding: US-ASCII 8b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* tab size: 8 (not used) 9b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* indentation:4 10b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* 11b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* created on: 2010dec24 12b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* created by: Markus W. Scherer 13b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*/ 14b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 15b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include <typeinfo> // for 'typeid' to work 16b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/utypes.h" 17b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/stringtriebuilder.h" 18b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "uassert.h" 19b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "uhash.h" 20b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 21b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_CDECL_BEGIN 22b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 23b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehostatic int32_t U_CALLCONV 24b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehohashStringTrieNode(const UHashTok key) { 25b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return U_NAMESPACE_QUALIFIER StringTrieBuilder::hashNode(key.pointer); 26b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 27b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 28b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehostatic UBool U_CALLCONV 29b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoequalStringTrieNodes(const UHashTok key1, const UHashTok key2) { 30b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return U_NAMESPACE_QUALIFIER StringTrieBuilder::equalNodes(key1.pointer, key2.pointer); 31b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 32b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 33b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_CDECL_END 34b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 35b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_NAMESPACE_BEGIN 36b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 37b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::StringTrieBuilder() : nodes(NULL) {} 38b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 39b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::~StringTrieBuilder() { 40b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho deleteCompactBuilder(); 41b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 42b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 43b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 44b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode) { 45b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 46b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return; 47b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 48b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho nodes=uhash_openSize(hashStringTrieNode, equalStringTrieNodes, NULL, 49b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho sizeGuess, &errorCode); 50b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_SUCCESS(errorCode) && nodes==NULL) { 51b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho errorCode=U_MEMORY_ALLOCATION_ERROR; 52b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 53b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_SUCCESS(errorCode)) { 54b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uhash_setKeyDeleter(nodes, uhash_deleteUObject); 55b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 56b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 57b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 58b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 59b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::deleteCompactBuilder() { 60b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uhash_close(nodes); 61b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho nodes=NULL; 62b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 63b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 64b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 65b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::build(UStringTrieBuildOption buildOption, int32_t elementsLength, 66b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UErrorCode &errorCode) { 67b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(buildOption==USTRINGTRIE_BUILD_FAST) { 68b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeNode(0, elementsLength, 0); 69b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else /* USTRINGTRIE_BUILD_SMALL */ { 70b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho createCompactBuilder(2*elementsLength, errorCode); 71b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *root=makeNode(0, elementsLength, 0, errorCode); 72b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_SUCCESS(errorCode)) { 73b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho root->markRightEdgesFirst(-1); 74b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho root->write(*this); 75b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 76b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho deleteCompactBuilder(); 77b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 78b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 79b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 80b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// Requires start<limit, 81b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// and all strings of the [start..limit[ elements must be sorted and 82b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// have a common prefix of length unitIndex. 83b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 84b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::writeNode(int32_t start, int32_t limit, int32_t unitIndex) { 85b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool hasValue=FALSE; 86b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value=0; 87b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t type; 88b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(unitIndex==getElementStringLength(start)) { 89b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // An intermediate or final value. 90b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=getElementValue(start++); 91b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(start==limit) { 92b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return writeValueAndFinal(value, TRUE); // final-value node 93b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 94b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho hasValue=TRUE; 95b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 96b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Now all [start..limit[ strings are longer than unitIndex. 97b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t minUnit=getElementUnit(start, unitIndex); 98b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t maxUnit=getElementUnit(limit-1, unitIndex); 99b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(minUnit==maxUnit) { 100b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Linear-match node: All strings have the same character at unitIndex. 101b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex); 102b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeNode(start, limit, lastUnitIndex); 103b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength. 104b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=lastUnitIndex-unitIndex; 105b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t maxLinearMatchLength=getMaxLinearMatchLength(); 106b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>maxLinearMatchLength) { 107b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho lastUnitIndex-=maxLinearMatchLength; 108b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length-=maxLinearMatchLength; 109b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeElementUnits(start, lastUnitIndex, maxLinearMatchLength); 110b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho write(getMinLinearMatch()+maxLinearMatchLength-1); 111b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 112b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeElementUnits(start, unitIndex, length); 113b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho type=getMinLinearMatch()+length-1; 114b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 115b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Branch node. 116b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=countElementUnits(start, limit, unitIndex); 117b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // length>=2 because minUnit!=maxUnit. 118b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeBranchSubNode(start, limit, unitIndex, length); 119b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(--length<getMinLinearMatch()) { 120b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho type=length; 121b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 122b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho write(length); 123b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho type=0; 124b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 125b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 126b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return writeValueAndType(hasValue, value, type); 127b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 128b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 129b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// start<limit && all strings longer than unitIndex && 130b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// length different units at unitIndex 131b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 132b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length) { 133b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UChar middleUnits[kMaxSplitBranchLevels]; 134b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t lessThan[kMaxSplitBranchLevels]; 135b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t ltLength=0; 136b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>getMaxBranchLinearSubNodeLength()) { 137b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Branch on the middle unit. 138b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // First, find the middle unit. 139b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2); 140b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Encode the less-than branch first. 141b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho middleUnits[ltLength]=getElementUnit(i, unitIndex); // middle unit 142b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho lessThan[ltLength]=writeBranchSubNode(start, i, unitIndex, length/2); 143b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++ltLength; 144b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Continue for the greater-or-equal branch. 145b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho start=i; 146b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=length-length/2; 147b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 148b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // For each unit, find its elements array start and whether it has a final value. 149b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t starts[kMaxBranchLinearSubNodeLength]; 150b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool isFinal[kMaxBranchLinearSubNodeLength-1]; 151b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t unitNumber=0; 152b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 153b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t i=starts[unitNumber]=start; 154b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UChar unit=getElementUnit(i++, unitIndex); 155b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho i=indexOfElementWithNextUnit(i, unitIndex, unit); 156b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho isFinal[unitNumber]= start==i-1 && unitIndex+1==getElementStringLength(start); 157b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho start=i; 158b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(++unitNumber<length-1); 159b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // unitNumber==length-1, and the maxUnit elements range is [start..limit[ 160b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho starts[unitNumber]=start; 161b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 162b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the sub-nodes in reverse order: The jump lengths are deltas from 163b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // after their own positions, so if we wrote the minUnit sub-node first, 164b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // then its jump delta would be larger. 165b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Instead we write the minUnit sub-node last, for a shorter delta. 166b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t jumpTargets[kMaxBranchLinearSubNodeLength-1]; 167b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 168b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --unitNumber; 169b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!isFinal[unitNumber]) { 170b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho jumpTargets[unitNumber]=writeNode(starts[unitNumber], starts[unitNumber+1], unitIndex+1); 171b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 172b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(unitNumber>0); 173b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // The maxUnit sub-node is written as the very last one because we do 174b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // not jump for it at all. 175b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho unitNumber=length-1; 176b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeNode(start, limit, unitIndex+1); 177b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t offset=write(getElementUnit(start, unitIndex)); 178b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the rest of this node's unit-value pairs. 179b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(--unitNumber>=0) { 180b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho start=starts[unitNumber]; 181b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value; 182b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(isFinal[unitNumber]) { 183b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the final value for the one string ending with this unit. 184b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=getElementValue(start); 185b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 186b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the delta to the start position of the sub-node. 187b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=offset-jumpTargets[unitNumber]; 188b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 189b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeValueAndFinal(value, isFinal[unitNumber]); 190b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=write(getElementUnit(start, unitIndex)); 191b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 192b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the split-branch nodes. 193b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(ltLength>0) { 194b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --ltLength; 195b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho writeDeltaTo(lessThan[ltLength]); 196b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=write(middleUnits[ltLength]); 197b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 198b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return offset; 199b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 200b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 201b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// Requires start<limit, 202b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// and all strings of the [start..limit[ elements must be sorted and 203b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// have a common prefix of length unitIndex. 204b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node * 205b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode) { 206b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 207b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 208b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 209b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool hasValue=FALSE; 210b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value=0; 211b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(unitIndex==getElementStringLength(start)) { 212b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // An intermediate or final value. 213b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=getElementValue(start++); 214b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(start==limit) { 215b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return registerFinalValue(value, errorCode); 216b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 217b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho hasValue=TRUE; 218b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 219b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *node; 220b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Now all [start..limit[ strings are longer than unitIndex. 221b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t minUnit=getElementUnit(start, unitIndex); 222b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t maxUnit=getElementUnit(limit-1, unitIndex); 223b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(minUnit==maxUnit) { 224b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Linear-match node: All strings have the same character at unitIndex. 225b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex); 226b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *nextNode=makeNode(start, limit, lastUnitIndex, errorCode); 227b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength. 228b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=lastUnitIndex-unitIndex; 229b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t maxLinearMatchLength=getMaxLinearMatchLength(); 230b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>maxLinearMatchLength) { 231b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho lastUnitIndex-=maxLinearMatchLength; 232b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length-=maxLinearMatchLength; 233b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=createLinearMatchNode(start, lastUnitIndex, maxLinearMatchLength, nextNode); 234b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho nextNode=registerNode(node, errorCode); 235b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 236b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=createLinearMatchNode(start, unitIndex, length, nextNode); 237b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 238b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Branch node. 239b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=countElementUnits(start, limit, unitIndex); 240b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // length>=2 because minUnit!=maxUnit. 241b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *subNode=makeBranchSubNode(start, limit, unitIndex, length, errorCode); 242b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=new BranchHeadNode(length, subNode); 243b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 244b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(hasValue && node!=NULL) { 245b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(matchNodesCanHaveValues()) { 246b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ((ValueNode *)node)->setValue(value); 247b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 248b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=new IntermediateValueNode(value, registerNode(node, errorCode)); 249b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 250b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 251b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return registerNode(node, errorCode); 252b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 253b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 254b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// start<limit && all strings longer than unitIndex && 255b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// length different units at unitIndex 256b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node * 257b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, 258b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length, UErrorCode &errorCode) { 259b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 260b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 261b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 262b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UChar middleUnits[kMaxSplitBranchLevels]; 263b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *lessThan[kMaxSplitBranchLevels]; 264b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t ltLength=0; 265b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>getMaxBranchLinearSubNodeLength()) { 266b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Branch on the middle unit. 267b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // First, find the middle unit. 268b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2); 269b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Create the less-than branch. 270b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho middleUnits[ltLength]=getElementUnit(i, unitIndex); // middle unit 271b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho lessThan[ltLength]=makeBranchSubNode(start, i, unitIndex, length/2, errorCode); 272b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++ltLength; 273b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Continue for the greater-or-equal branch. 274b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho start=i; 275b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=length-length/2; 276b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 277b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 278b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 279b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 280b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ListBranchNode *listNode=new ListBranchNode(); 281b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(listNode==NULL) { 282b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho errorCode=U_MEMORY_ALLOCATION_ERROR; 283b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 284b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 285b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // For each unit, find its elements array start and whether it has a final value. 286b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t unitNumber=0; 287b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 288b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t i=start; 289b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UChar unit=getElementUnit(i++, unitIndex); 290b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho i=indexOfElementWithNextUnit(i, unitIndex, unit); 291b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(start==i-1 && unitIndex+1==getElementStringLength(start)) { 292b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho listNode->add(unit, getElementValue(start)); 293b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 294b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho listNode->add(unit, makeNode(start, i, unitIndex+1, errorCode)); 295b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 296b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho start=i; 297b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(++unitNumber<length-1); 298b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // unitNumber==length-1, and the maxUnit elements range is [start..limit[ 299b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UChar unit=getElementUnit(start, unitIndex); 300b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(start==limit-1 && unitIndex+1==getElementStringLength(start)) { 301b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho listNode->add(unit, getElementValue(start)); 302b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 303b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho listNode->add(unit, makeNode(start, limit, unitIndex+1, errorCode)); 304b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 305b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *node=registerNode(listNode, errorCode); 306b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Create the split-branch nodes. 307b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(ltLength>0) { 308b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --ltLength; 309b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=registerNode( 310b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho new SplitBranchNode(middleUnits[ltLength], lessThan[ltLength], node), errorCode); 311b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 312b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return node; 313b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 314b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 315b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node * 316b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::registerNode(Node *newNode, UErrorCode &errorCode) { 317b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 318b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delete newNode; 319b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 320b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 321b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(newNode==NULL) { 322b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho errorCode=U_MEMORY_ALLOCATION_ERROR; 323b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 324b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 325b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const UHashElement *old=uhash_find(nodes, newNode); 326b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(old!=NULL) { 327b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delete newNode; 328b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (Node *)old->key.pointer; 329b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 330b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // If uhash_puti() returns a non-zero value from an equivalent, previously 331b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // registered node, then uhash_find() failed to find that and we will leak newNode. 332b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#if !U_RELEASE 333b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t oldValue= // Only in debug mode to avoid a compiler warning about unused oldValue. 334b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#endif 335b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uhash_puti(nodes, newNode, 1, &errorCode); 336b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(oldValue==0); 337b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 338b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delete newNode; 339b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 340b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 341b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return newNode; 342b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 343b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 344b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node * 345b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::registerFinalValue(int32_t value, UErrorCode &errorCode) { 346b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 347b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 348b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 349b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho FinalValueNode key(value); 350b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const UHashElement *old=uhash_find(nodes, &key); 351b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(old!=NULL) { 352b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (Node *)old->key.pointer; 353b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 354b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *newNode=new FinalValueNode(value); 355b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(newNode==NULL) { 356b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho errorCode=U_MEMORY_ALLOCATION_ERROR; 357b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 358b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 359b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // If uhash_puti() returns a non-zero value from an equivalent, previously 360b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // registered node, then uhash_find() failed to find that and we will leak newNode. 361b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#if !U_RELEASE 362b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t oldValue= // Only in debug mode to avoid a compiler warning about unused oldValue. 363b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#endif 364b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uhash_puti(nodes, newNode, 1, &errorCode); 365b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(oldValue==0); 366b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(U_FAILURE(errorCode)) { 367b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delete newNode; 368b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 369b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 370b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return newNode; 371b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 372b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 373b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 374b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::hashNode(const void *node) { 375b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return ((const Node *)node)->hashCode(); 376b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 377b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 378b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 379b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::equalNodes(const void *left, const void *right) { 380b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return *(const Node *)left==*(const Node *)right; 381b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 382b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 383b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUOBJECT_DEFINE_NO_RTTI_IMPLEMENTATION(StringTrieBuilder) 384b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 385b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 386b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node::operator==(const Node &other) const { 387b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return this==&other || (typeid(*this)==typeid(other) && hash==other.hash); 388b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 389b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 390b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 391b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node::markRightEdgesFirst(int32_t edgeNumber) { 392b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(offset==0) { 393b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=edgeNumber; 394b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 395b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return edgeNumber; 396b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 397b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 398b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUOBJECT_DEFINE_NO_RTTI_IMPLEMENTATION(StringTrieBuilder::Node) 399b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 400b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 401b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::FinalValueNode::operator==(const Node &other) const { 402b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 403b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 404b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 405b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!Node::operator==(other)) { 406b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 407b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 408b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const FinalValueNode &o=(const FinalValueNode &)other; 409b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return value==o.value; 410b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 411b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 412b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 413b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::FinalValueNode::write(StringTrieBuilder &builder) { 414b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.writeValueAndFinal(value, TRUE); 415b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 416b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 417b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 418b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::ValueNode::operator==(const Node &other) const { 419b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 420b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 421b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 422b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!Node::operator==(other)) { 423b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 424b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 425b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const ValueNode &o=(const ValueNode &)other; 426b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return hasValue==o.hasValue && (!hasValue || value==o.value); 427b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 428b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 429b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 430b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::IntermediateValueNode::operator==(const Node &other) const { 431b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 432b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 433b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 434b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!ValueNode::operator==(other)) { 435b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 436b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 437b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const IntermediateValueNode &o=(const IntermediateValueNode &)other; 438b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return next==o.next; 439b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 440b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 441b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 442b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::IntermediateValueNode::markRightEdgesFirst(int32_t edgeNumber) { 443b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(offset==0) { 444b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); 445b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 446b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return edgeNumber; 447b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 448b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 449b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 450b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::IntermediateValueNode::write(StringTrieBuilder &builder) { 451b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho next->write(builder); 452b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.writeValueAndFinal(value, FALSE); 453b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 454b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 455b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 456b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::LinearMatchNode::operator==(const Node &other) const { 457b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 458b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 459b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 460b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!ValueNode::operator==(other)) { 461b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 462b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 463b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const LinearMatchNode &o=(const LinearMatchNode &)other; 464b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return length==o.length && next==o.next; 465b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 466b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 467b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 468b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::LinearMatchNode::markRightEdgesFirst(int32_t edgeNumber) { 469b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(offset==0) { 470b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); 471b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 472b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return edgeNumber; 473b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 474b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 475b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 476b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::ListBranchNode::operator==(const Node &other) const { 477b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 478b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 479b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 480b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!Node::operator==(other)) { 481b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 482b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 483b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const ListBranchNode &o=(const ListBranchNode &)other; 484b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(int32_t i=0; i<length; ++i) { 485b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(units[i]!=o.units[i] || values[i]!=o.values[i] || equal[i]!=o.equal[i]) { 486b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 487b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 488b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 489b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 490b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 491b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 492b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 493b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::ListBranchNode::markRightEdgesFirst(int32_t edgeNumber) { 494b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(offset==0) { 495b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho firstEdgeNumber=edgeNumber; 496b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t step=0; 497b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t i=length; 498b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 499b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *edge=equal[--i]; 500b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(edge!=NULL) { 501b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho edgeNumber=edge->markRightEdgesFirst(edgeNumber-step); 502b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 503b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // For all but the rightmost edge, decrement the edge number. 504b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho step=1; 505b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(i>0); 506b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=edgeNumber; 507b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 508b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return edgeNumber; 509b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 510b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 511b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 512b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::ListBranchNode::write(StringTrieBuilder &builder) { 513b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the sub-nodes in reverse order: The jump lengths are deltas from 514b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // after their own positions, so if we wrote the minUnit sub-node first, 515b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // then its jump delta would be larger. 516b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Instead we write the minUnit sub-node last, for a shorter delta. 517b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t unitNumber=length-1; 518b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho Node *rightEdge=equal[unitNumber]; 519b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t rightEdgeNumber= rightEdge==NULL ? firstEdgeNumber : rightEdge->getOffset(); 520b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 521b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --unitNumber; 522b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(equal[unitNumber]!=NULL) { 523b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho equal[unitNumber]->writeUnlessInsideRightEdge(firstEdgeNumber, rightEdgeNumber, builder); 524b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 525b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(unitNumber>0); 526b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // The maxUnit sub-node is written as the very last one because we do 527b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // not jump for it at all. 528b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho unitNumber=length-1; 529b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(rightEdge==NULL) { 530b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho builder.writeValueAndFinal(values[unitNumber], TRUE); 531b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 532b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho rightEdge->write(builder); 533b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 534b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.write(units[unitNumber]); 535b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the rest of this node's unit-value pairs. 536b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(--unitNumber>=0) { 537b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value; 538b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool isFinal; 539b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(equal[unitNumber]==NULL) { 540b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the final value for the one string ending with this unit. 541b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=values[unitNumber]; 542b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho isFinal=TRUE; 543b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 544b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write the delta to the start position of the sub-node. 545b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(equal[unitNumber]->getOffset()>0); 546b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=offset-equal[unitNumber]->getOffset(); 547b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho isFinal=FALSE; 548b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 549b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho builder.writeValueAndFinal(value, isFinal); 550b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.write(units[unitNumber]); 551b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 552b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 553b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 554b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 555b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::SplitBranchNode::operator==(const Node &other) const { 556b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 557b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 558b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 559b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!Node::operator==(other)) { 560b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 561b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 562b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const SplitBranchNode &o=(const SplitBranchNode &)other; 563b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return unit==o.unit && lessThan==o.lessThan && greaterOrEqual==o.greaterOrEqual; 564b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 565b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 566b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 567b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::SplitBranchNode::markRightEdgesFirst(int32_t edgeNumber) { 568b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(offset==0) { 569b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho firstEdgeNumber=edgeNumber; 570b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho edgeNumber=greaterOrEqual->markRightEdgesFirst(edgeNumber); 571b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=edgeNumber=lessThan->markRightEdgesFirst(edgeNumber-1); 572b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 573b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return edgeNumber; 574b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 575b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 576b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 577b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::SplitBranchNode::write(StringTrieBuilder &builder) { 578b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Encode the less-than branch first. 579b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho lessThan->writeUnlessInsideRightEdge(firstEdgeNumber, greaterOrEqual->getOffset(), builder); 580b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Encode the greater-or-equal branch last because we do not jump for it at all. 581b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho greaterOrEqual->write(builder); 582b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Write this node. 583b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(lessThan->getOffset()>0); 584b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho builder.writeDeltaTo(lessThan->getOffset()); // less-than 585b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.write(unit); 586b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 587b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 588b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 589b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::BranchHeadNode::operator==(const Node &other) const { 590b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(this==&other) { 591b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 592b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 593b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!ValueNode::operator==(other)) { 594b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 595b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 596b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const BranchHeadNode &o=(const BranchHeadNode &)other; 597b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return length==o.length && next==o.next; 598b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 599b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 600b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 601b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::BranchHeadNode::markRightEdgesFirst(int32_t edgeNumber) { 602b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(offset==0) { 603b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); 604b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 605b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return edgeNumber; 606b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 607b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 608b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 609b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::BranchHeadNode::write(StringTrieBuilder &builder) { 610b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho next->write(builder); 611b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(length<=builder.getMinLinearMatch()) { 612b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.writeValueAndType(hasValue, value, length-1); 613b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 614b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho builder.write(length-1); 615b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho offset=builder.writeValueAndType(hasValue, value, 0); 616b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 617b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 618b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 619b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_NAMESPACE_END 620