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