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