1b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/* 2b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho******************************************************************************* 3b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Copyright (C) 2010-2011, International Business Machines 4b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Corporation and others. All Rights Reserved. 5b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho******************************************************************************* 6b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* file name: bytestrie.cpp 7b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* encoding: US-ASCII 8b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* tab size: 8 (not used) 9b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* indentation:4 10b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* 11b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* created on: 2010sep25 12b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* created by: Markus W. Scherer 13b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*/ 14b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 15b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/utypes.h" 16b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/bytestream.h" 17b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/bytestrie.h" 18b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/uobject.h" 19b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "cmemory.h" 20b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "uassert.h" 21b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 22b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_NAMESPACE_BEGIN 23b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 24b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::~BytesTrie() { 25b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uprv_free(ownedArray_); 26b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 27b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 28b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho// lead byte already shifted right by 1. 29b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 30b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::readValue(const uint8_t *pos, int32_t leadByte) { 31b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value; 32b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(leadByte<kMinTwoByteValueLead) { 33b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=leadByte-kMinOneByteValueLead; 34b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(leadByte<kMinThreeByteValueLead) { 35b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=((leadByte-kMinTwoByteValueLead)<<8)|*pos; 36b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(leadByte<kFourByteValueLead) { 37b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=((leadByte-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; 38b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(leadByte==kFourByteValueLead) { 39b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=(pos[0]<<16)|(pos[1]<<8)|pos[2]; 40b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 41b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho value=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; 42b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 43b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return value; 44b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 45b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 46b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoconst uint8_t * 47b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::jumpByDelta(const uint8_t *pos) { 48b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t delta=*pos++; 49b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(delta<kMinTwoByteDeltaLead) { 50b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // nothing to do 51b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(delta<kMinThreeByteDeltaLead) { 52b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=((delta-kMinTwoByteDeltaLead)<<8)|*pos++; 53b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(delta<kFourByteDeltaLead) { 54b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=((delta-kMinThreeByteDeltaLead)<<16)|(pos[0]<<8)|pos[1]; 55b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=2; 56b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(delta==kFourByteDeltaLead) { 57b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; 58b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=3; 59b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 60b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; 61b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=4; 62b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 63b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return pos+delta; 64b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 65b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 66b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUStringTrieResult 67b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::current() const { 68b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const uint8_t *pos=pos_; 69b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(pos==NULL) { 70b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 71b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 72b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node; 73b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ? 74b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho valueResult(node) : USTRINGTRIE_NO_VALUE; 75b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 76b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 77b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 78b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUStringTrieResult 79b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::branchNext(const uint8_t *pos, int32_t length, int32_t inByte) { 80b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Branch according to the current byte. 81b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(length==0) { 82b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=*pos++; 83b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 84b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++length; 85b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // The length of the branch is the number of bytes to select from. 86b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // The data structure encodes a binary search. 87b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>kMaxBranchLinearSubNodeLength) { 88b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte<*pos++) { 89b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length>>=1; 90b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=jumpByDelta(pos); 91b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 92b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=length-(length>>1); 93b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipDelta(pos); 94b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 95b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 96b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Drop down to linear search for the last few bytes. 97b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 98b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // and divides length by 2. 99b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 100b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte==*pos++) { 101b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UStringTrieResult result; 102b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos; 103b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(node>=kMinValueLead); 104b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node&kValueIsFinal) { 105b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Leave the final value for getValue() to read. 106b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho result=USTRINGTRIE_FINAL_VALUE; 107b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 108b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Use the non-final value as the jump delta. 109b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; 110b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // int32_t delta=readValue(pos, node>>1); 111b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node>>=1; 112b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t delta; 113b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node<kMinTwoByteValueLead) { 114b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=node-kMinOneByteValueLead; 115b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node<kMinThreeByteValueLead) { 116b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=((node-kMinTwoByteValueLead)<<8)|*pos++; 117b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node<kFourByteValueLead) { 118b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=((node-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; 119b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=2; 120b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node==kFourByteValueLead) { 121b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; 122b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=3; 123b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 124b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; 125b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=4; 126b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 127b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // end readValue() 128b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=delta; 129b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=*pos; 130b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; 131b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 132b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos_=pos; 133b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return result; 134b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 135b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --length; 136b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos); 137b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(length>1); 138b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte==*pos++) { 139b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos_=pos; 140b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos; 141b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; 142b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 143b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 144b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 145b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 146b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 147b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 148b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUStringTrieResult 149b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::nextImpl(const uint8_t *pos, int32_t inByte) { 150b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(;;) { 151b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos++; 152b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node<kMinLinearMatch) { 153b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return branchNext(pos, node, inByte); 154b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node<kMinValueLead) { 155b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Match the first of length+1 bytes. 156b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=node-kMinLinearMatch; // Actual match length minus 1. 157b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte==*pos++) { 158b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho remainingMatchLength_=--length; 159b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos_=pos; 160b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (length<0 && (node=*pos)>=kMinValueLead) ? 161b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho valueResult(node) : USTRINGTRIE_NO_VALUE; 162b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 163b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // No match. 164b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho break; 165b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 166b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node&kValueIsFinal) { 167b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // No further matching bytes. 168b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho break; 169b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 170b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Skip intermediate value. 171b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos, node); 172b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // The next node must not also be a value node. 173b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(*pos<kMinValueLead); 174b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 175b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 176b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 177b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 178b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 179b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 180b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUStringTrieResult 181b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::next(int32_t inByte) { 182b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const uint8_t *pos=pos_; 183b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(pos==NULL) { 184b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 185b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 186b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte<0) { 187b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho inByte+=0x100; 188b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 189b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. 190b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(length>=0) { 191b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Remaining part of a linear-match node. 192b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte==*pos++) { 193b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho remainingMatchLength_=--length; 194b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos_=pos; 195b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node; 196b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (length<0 && (node=*pos)>=kMinValueLead) ? 197b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho valueResult(node) : USTRINGTRIE_NO_VALUE; 198b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 199b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 200b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 201b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 202b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 203b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return nextImpl(pos, inByte); 204b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 205b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 206b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUStringTrieResult 207b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::next(const char *s, int32_t sLength) { 208b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(sLength<0 ? *s==0 : sLength==0) { 209b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Empty input. 210b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return current(); 211b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 212b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const uint8_t *pos=pos_; 213b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(pos==NULL) { 214b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 215b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 216b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. 217b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(;;) { 218b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Fetch the next input byte, if there is one. 219b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Continue a linear-match node without rechecking sLength<0. 220b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t inByte; 221b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(sLength<0) { 222b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(;;) { 223b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if((inByte=*s++)==0) { 224b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho remainingMatchLength_=length; 225b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos_=pos; 226b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node; 227b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (length<0 && (node=*pos)>=kMinValueLead) ? 228b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho valueResult(node) : USTRINGTRIE_NO_VALUE; 229b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 230b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(length<0) { 231b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho remainingMatchLength_=length; 232b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho break; 233b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 234b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte!=*pos) { 235b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 236b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 237b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 238b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; 239b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --length; 240b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 241b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 242b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(;;) { 243b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(sLength==0) { 244b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho remainingMatchLength_=length; 245b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos_=pos; 246b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node; 247b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return (length<0 && (node=*pos)>=kMinValueLead) ? 248b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho valueResult(node) : USTRINGTRIE_NO_VALUE; 249b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 250b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho inByte=*s++; 251b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --sLength; 252b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(length<0) { 253b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho remainingMatchLength_=length; 254b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho break; 255b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 256b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte!=*pos) { 257b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 258b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 259b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 260b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; 261b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --length; 262b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 263b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 264b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(;;) { 265b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos++; 266b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node<kMinLinearMatch) { 267b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UStringTrieResult result=branchNext(pos, node, inByte); 268b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(result==USTRINGTRIE_NO_MATCH) { 269b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 270b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 271b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Fetch the next input byte, if there is one. 272b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(sLength<0) { 273b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if((inByte=*s++)==0) { 274b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return result; 275b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 276b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 277b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(sLength==0) { 278b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return result; 279b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 280b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho inByte=*s++; 281b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --sLength; 282b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 283b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(result==USTRINGTRIE_FINAL_VALUE) { 284b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // No further matching bytes. 285b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 286b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 287b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 288b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=pos_; // branchNext() advanced pos and wrote it to pos_ . 289b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node<kMinValueLead) { 290b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Match length+1 bytes. 291b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=node-kMinLinearMatch; // Actual match length minus 1. 292b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(inByte!=*pos) { 293b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 294b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 295b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 296b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; 297b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho --length; 298b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho break; 299b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node&kValueIsFinal) { 300b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // No further matching bytes. 301b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho stop(); 302b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return USTRINGTRIE_NO_MATCH; 303b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 304b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Skip intermediate value. 305b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos, node); 306b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // The next node must not also be a value node. 307b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(*pos<kMinValueLead); 308b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 309b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 310b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 311b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 312b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 313b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoconst uint8_t * 314b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::findUniqueValueFromBranch(const uint8_t *pos, int32_t length, 315b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool haveUniqueValue, int32_t &uniqueValue) { 316b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>kMaxBranchLinearSubNodeLength) { 317b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; // ignore the comparison byte 318b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) { 319b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 320b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 321b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=length-(length>>1); 322b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipDelta(pos); 323b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 324b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 325b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; // ignore a comparison byte 326b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // handle its value 327b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos++; 328b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool isFinal=(UBool)(node&kValueIsFinal); 329b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value=readValue(pos, node>>1); 330b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos, node); 331b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(isFinal) { 332b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(haveUniqueValue) { 333b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(value!=uniqueValue) { 334b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 335b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 336b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 337b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uniqueValue=value; 338b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho haveUniqueValue=TRUE; 339b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 340b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 341b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) { 342b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return NULL; 343b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 344b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho haveUniqueValue=TRUE; 345b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 346b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(--length>1); 347b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return pos+1; // ignore the last comparison byte 348b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 349b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 350b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool 351b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue) { 352b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for(;;) { 353b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos++; 354b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node<kMinLinearMatch) { 355b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node==0) { 356b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=*pos++; 357b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 358b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue); 359b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(pos==NULL) { 360b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 361b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 362b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho haveUniqueValue=TRUE; 363b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else if(node<kMinValueLead) { 364b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // linear-match node 365b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos+=node-kMinLinearMatch+1; // Ignore the match bytes. 366b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 367b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho UBool isFinal=(UBool)(node&kValueIsFinal); 368b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t value=readValue(pos, node>>1); 369b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(haveUniqueValue) { 370b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(value!=uniqueValue) { 371b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return FALSE; 372b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 373b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 374b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uniqueValue=value; 375b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho haveUniqueValue=TRUE; 376b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 377b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(isFinal) { 378b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return TRUE; 379b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 380b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos, node); 381b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 382b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 383b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 384b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 385b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t 386b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::getNextBytes(ByteSink &out) const { 387b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho const uint8_t *pos=pos_; 388b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(pos==NULL) { 389b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return 0; 390b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 391b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(remainingMatchLength_>=0) { 392b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho append(out, *pos); // Next byte of a pending linear-match node. 393b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return 1; 394b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 395b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho int32_t node=*pos++; 396b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node>=kMinValueLead) { 397b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node&kValueIsFinal) { 398b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return 0; 399b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 400b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos, node); 401b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=*pos++; 402b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho U_ASSERT(node<kMinValueLead); 403b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 404b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 405b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node<kMinLinearMatch) { 406b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(node==0) { 407b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho node=*pos++; 408b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 409b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho getNextBranchBytes(pos, ++node, out); 410b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return node; 411b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 412b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // First byte of the linear-match node. 413b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho append(out, *pos); 414b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho return 1; 415b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 416b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 417b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 418b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 419b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out) { 420b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho while(length>kMaxBranchLinearSubNodeLength) { 421b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho ++pos; // ignore the comparison byte 422b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho getNextBranchBytes(jumpByDelta(pos), length>>1, out); 423b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho length=length-(length>>1); 424b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipDelta(pos); 425b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 426b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho do { 427b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho append(out, *pos++); 428b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho pos=skipValue(pos); 429b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } while(--length>1); 430b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho append(out, *pos); 431b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 432b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 433b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid 434b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoBytesTrie::append(ByteSink &out, int c) { 435b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho char ch=(char)c; 436b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho out.Append(&ch, 1); 437b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 438b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 439b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_NAMESPACE_END 440