summaryrefslogtreecommitdiff
path: root/deps/node/deps/icu-small/source/common/bytestrie.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'deps/node/deps/icu-small/source/common/bytestrie.cpp')
-rw-r--r--deps/node/deps/icu-small/source/common/bytestrie.cpp441
1 files changed, 0 insertions, 441 deletions
diff --git a/deps/node/deps/icu-small/source/common/bytestrie.cpp b/deps/node/deps/icu-small/source/common/bytestrie.cpp
deleted file mode 100644
index c4d498c4..00000000
--- a/deps/node/deps/icu-small/source/common/bytestrie.cpp
+++ /dev/null
@@ -1,441 +0,0 @@
-// © 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: UTF-8
-* 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-08 12:02:34 +0000