diff options
Diffstat (limited to 'intl/icu/source/common/bytestrie.cpp')
| -rw-r--r-- | intl/icu/source/common/bytestrie.cpp | 441 |
1 files changed, 441 insertions, 0 deletions
diff --git a/intl/icu/source/common/bytestrie.cpp b/intl/icu/source/common/bytestrie.cpp new file mode 100644 index 000000000..093cd8ddb --- /dev/null +++ b/intl/icu/source/common/bytestrie.cpp @@ -0,0 +1,441 @@ +// Copyright (C) 2016 and later: Unicode, Inc. and others. +// License & terms of use: http://www.unicode.org/copyright.html +/* +******************************************************************************* +* Copyright (C) 2010-2011, International Business Machines +* Corporation and others. All Rights Reserved. +******************************************************************************* +* file name: bytestrie.cpp +* encoding: US-ASCII +* tab size: 8 (not used) +* indentation:4 +* +* created on: 2010sep25 +* created by: Markus W. Scherer +*/ + +#include "unicode/utypes.h" +#include "unicode/bytestream.h" +#include "unicode/bytestrie.h" +#include "unicode/uobject.h" +#include "cmemory.h" +#include "uassert.h" + +U_NAMESPACE_BEGIN + +BytesTrie::~BytesTrie() { + uprv_free(ownedArray_); +} + +// lead byte already shifted right by 1. +int32_t +BytesTrie::readValue(const uint8_t *pos, int32_t leadByte) { + int32_t value; + if(leadByte<kMinTwoByteValueLead) { + value=leadByte-kMinOneByteValueLead; + } else if(leadByte<kMinThreeByteValueLead) { + value=((leadByte-kMinTwoByteValueLead)<<8)|*pos; + } else if(leadByte<kFourByteValueLead) { + value=((leadByte-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; + } else if(leadByte==kFourByteValueLead) { + value=(pos[0]<<16)|(pos[1]<<8)|pos[2]; + } else { + value=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; + } + return value; +} + +const uint8_t * +BytesTrie::jumpByDelta(const uint8_t *pos) { + int32_t delta=*pos++; + if(delta<kMinTwoByteDeltaLead) { + // nothing to do + } else if(delta<kMinThreeByteDeltaLead) { + delta=((delta-kMinTwoByteDeltaLead)<<8)|*pos++; + } else if(delta<kFourByteDeltaLead) { + delta=((delta-kMinThreeByteDeltaLead)<<16)|(pos[0]<<8)|pos[1]; + pos+=2; + } else if(delta==kFourByteDeltaLead) { + delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; + pos+=3; + } else { + delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; + pos+=4; + } + return pos+delta; +} + +UStringTrieResult +BytesTrie::current() const { + const uint8_t *pos=pos_; + if(pos==NULL) { + return USTRINGTRIE_NO_MATCH; + } else { + int32_t node; + return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ? + valueResult(node) : USTRINGTRIE_NO_VALUE; + } +} + +UStringTrieResult +BytesTrie::branchNext(const uint8_t *pos, int32_t length, int32_t inByte) { + // Branch according to the current byte. + if(length==0) { + length=*pos++; + } + ++length; + // The length of the branch is the number of bytes to select from. + // The data structure encodes a binary search. + while(length>kMaxBranchLinearSubNodeLength) { + if(inByte<*pos++) { + length>>=1; + pos=jumpByDelta(pos); + } else { + length=length-(length>>1); + pos=skipDelta(pos); + } + } + // Drop down to linear search for the last few bytes. + // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 + // and divides length by 2. + do { + if(inByte==*pos++) { + UStringTrieResult result; + int32_t node=*pos; + U_ASSERT(node>=kMinValueLead); + if(node&kValueIsFinal) { + // Leave the final value for getValue() to read. + result=USTRINGTRIE_FINAL_VALUE; + } else { + // Use the non-final value as the jump delta. + ++pos; + // int32_t delta=readValue(pos, node>>1); + node>>=1; + int32_t delta; + if(node<kMinTwoByteValueLead) { + delta=node-kMinOneByteValueLead; + } else if(node<kMinThreeByteValueLead) { + delta=((node-kMinTwoByteValueLead)<<8)|*pos++; + } else if(node<kFourByteValueLead) { + delta=((node-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1]; + pos+=2; + } else if(node==kFourByteValueLead) { + delta=(pos[0]<<16)|(pos[1]<<8)|pos[2]; + pos+=3; + } else { + delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3]; + pos+=4; + } + // end readValue() + pos+=delta; + node=*pos; + result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; + } + pos_=pos; + return result; + } + --length; + pos=skipValue(pos); + } while(length>1); + if(inByte==*pos++) { + pos_=pos; + int32_t node=*pos; + return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; + } else { + stop(); + return USTRINGTRIE_NO_MATCH; + } +} + +UStringTrieResult +BytesTrie::nextImpl(const uint8_t *pos, int32_t inByte) { + for(;;) { + int32_t node=*pos++; + if(node<kMinLinearMatch) { + return branchNext(pos, node, inByte); + } else if(node<kMinValueLead) { + // Match the first of length+1 bytes. + int32_t length=node-kMinLinearMatch; // Actual match length minus 1. + if(inByte==*pos++) { + remainingMatchLength_=--length; + pos_=pos; + return (length<0 && (node=*pos)>=kMinValueLead) ? + valueResult(node) : USTRINGTRIE_NO_VALUE; + } else { + // No match. + break; + } + } else if(node&kValueIsFinal) { + // No further matching bytes. + break; + } else { + // Skip intermediate value. + pos=skipValue(pos, node); + // The next node must not also be a value node. + U_ASSERT(*pos<kMinValueLead); + } + } + stop(); + return USTRINGTRIE_NO_MATCH; +} + +UStringTrieResult +BytesTrie::next(int32_t inByte) { + const uint8_t *pos=pos_; + if(pos==NULL) { + return USTRINGTRIE_NO_MATCH; + } + if(inByte<0) { + inByte+=0x100; + } + int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. + if(length>=0) { + // Remaining part of a linear-match node. + if(inByte==*pos++) { + remainingMatchLength_=--length; + pos_=pos; + int32_t node; + return (length<0 && (node=*pos)>=kMinValueLead) ? + valueResult(node) : USTRINGTRIE_NO_VALUE; + } else { + stop(); + return USTRINGTRIE_NO_MATCH; + } + } + return nextImpl(pos, inByte); +} + +UStringTrieResult +BytesTrie::next(const char *s, int32_t sLength) { + if(sLength<0 ? *s==0 : sLength==0) { + // Empty input. + return current(); + } + const uint8_t *pos=pos_; + if(pos==NULL) { + return USTRINGTRIE_NO_MATCH; + } + int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. + for(;;) { + // Fetch the next input byte, if there is one. + // Continue a linear-match node without rechecking sLength<0. + int32_t inByte; + if(sLength<0) { + for(;;) { + if((inByte=*s++)==0) { + remainingMatchLength_=length; + pos_=pos; + int32_t node; + return (length<0 && (node=*pos)>=kMinValueLead) ? + valueResult(node) : USTRINGTRIE_NO_VALUE; + } + if(length<0) { + remainingMatchLength_=length; + break; + } + if(inByte!=*pos) { + stop(); + return USTRINGTRIE_NO_MATCH; + } + ++pos; + --length; + } + } else { + for(;;) { + if(sLength==0) { + remainingMatchLength_=length; + pos_=pos; + int32_t node; + return (length<0 && (node=*pos)>=kMinValueLead) ? + valueResult(node) : USTRINGTRIE_NO_VALUE; + } + inByte=*s++; + --sLength; + if(length<0) { + remainingMatchLength_=length; + break; + } + if(inByte!=*pos) { + stop(); + return USTRINGTRIE_NO_MATCH; + } + ++pos; + --length; + } + } + for(;;) { + int32_t node=*pos++; + if(node<kMinLinearMatch) { + UStringTrieResult result=branchNext(pos, node, inByte); + if(result==USTRINGTRIE_NO_MATCH) { + return USTRINGTRIE_NO_MATCH; + } + // Fetch the next input byte, if there is one. + if(sLength<0) { + if((inByte=*s++)==0) { + return result; + } + } else { + if(sLength==0) { + return result; + } + inByte=*s++; + --sLength; + } + if(result==USTRINGTRIE_FINAL_VALUE) { + // No further matching bytes. + stop(); + return USTRINGTRIE_NO_MATCH; + } + pos=pos_; // branchNext() advanced pos and wrote it to pos_ . + } else if(node<kMinValueLead) { + // Match length+1 bytes. + length=node-kMinLinearMatch; // Actual match length minus 1. + if(inByte!=*pos) { + stop(); + return USTRINGTRIE_NO_MATCH; + } + ++pos; + --length; + break; + } else if(node&kValueIsFinal) { + // No further matching bytes. + stop(); + return USTRINGTRIE_NO_MATCH; + } else { + // Skip intermediate value. + pos=skipValue(pos, node); + // The next node must not also be a value node. + U_ASSERT(*pos<kMinValueLead); + } + } + } +} + +const uint8_t * +BytesTrie::findUniqueValueFromBranch(const uint8_t *pos, int32_t length, + UBool haveUniqueValue, int32_t &uniqueValue) { + while(length>kMaxBranchLinearSubNodeLength) { + ++pos; // ignore the comparison byte + if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) { + return NULL; + } + length=length-(length>>1); + pos=skipDelta(pos); + } + do { + ++pos; // ignore a comparison byte + // handle its value + int32_t node=*pos++; + UBool isFinal=(UBool)(node&kValueIsFinal); + int32_t value=readValue(pos, node>>1); + pos=skipValue(pos, node); + if(isFinal) { + if(haveUniqueValue) { + if(value!=uniqueValue) { + return NULL; + } + } else { + uniqueValue=value; + haveUniqueValue=TRUE; + } + } else { + if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) { + return NULL; + } + haveUniqueValue=TRUE; + } + } while(--length>1); + return pos+1; // ignore the last comparison byte +} + +UBool +BytesTrie::findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue) { + for(;;) { + int32_t node=*pos++; + if(node<kMinLinearMatch) { + if(node==0) { + node=*pos++; + } + pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue); + if(pos==NULL) { + return FALSE; + } + haveUniqueValue=TRUE; + } else if(node<kMinValueLead) { + // linear-match node + pos+=node-kMinLinearMatch+1; // Ignore the match bytes. + } else { + UBool isFinal=(UBool)(node&kValueIsFinal); + int32_t value=readValue(pos, node>>1); + if(haveUniqueValue) { + if(value!=uniqueValue) { + return FALSE; + } + } else { + uniqueValue=value; + haveUniqueValue=TRUE; + } + if(isFinal) { + return TRUE; + } + pos=skipValue(pos, node); + } + } +} + +int32_t +BytesTrie::getNextBytes(ByteSink &out) const { + const uint8_t *pos=pos_; + if(pos==NULL) { + return 0; + } + if(remainingMatchLength_>=0) { + append(out, *pos); // Next byte of a pending linear-match node. + return 1; + } + int32_t node=*pos++; + if(node>=kMinValueLead) { + if(node&kValueIsFinal) { + return 0; + } else { + pos=skipValue(pos, node); + node=*pos++; + U_ASSERT(node<kMinValueLead); + } + } + if(node<kMinLinearMatch) { + if(node==0) { + node=*pos++; + } + getNextBranchBytes(pos, ++node, out); + return node; + } else { + // First byte of the linear-match node. + append(out, *pos); + return 1; + } +} + +void +BytesTrie::getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out) { + while(length>kMaxBranchLinearSubNodeLength) { + ++pos; // ignore the comparison byte + getNextBranchBytes(jumpByDelta(pos), length>>1, out); + length=length-(length>>1); + pos=skipDelta(pos); + } + do { + append(out, *pos++); + pos=skipValue(pos); + } while(--length>1); + append(out, *pos); +} + +void +BytesTrie::append(ByteSink &out, int c) { + char ch=(char)c; + out.Append(&ch, 1); +} + +U_NAMESPACE_END |