| /* |
| ******************************************************************************* |
| * Copyright (C) 2010-2011, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ******************************************************************************* |
| * file name: ucharstrie.h |
| * encoding: US-ASCII |
| * tab size: 8 (not used) |
| * indentation:4 |
| * |
| * created on: 2010nov14 |
| * created by: Markus W. Scherer |
| */ |
| |
| #include "starboard/client_porting/poem/string_poem.h" |
| #include "unicode/utypes.h" |
| #include "unicode/appendable.h" |
| #include "unicode/ucharstrie.h" |
| #include "unicode/uobject.h" |
| #include "unicode/utf16.h" |
| #include "cmemory.h" |
| #include "uassert.h" |
| |
| U_NAMESPACE_BEGIN |
| |
| UCharsTrie::~UCharsTrie() { |
| uprv_free(ownedArray_); |
| } |
| |
| UStringTrieResult |
| UCharsTrie::current() const { |
| const UChar *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 |
| UCharsTrie::firstForCodePoint(UChar32 cp) { |
| return cp<=0xffff ? |
| first(cp) : |
| (USTRINGTRIE_HAS_NEXT(first(U16_LEAD(cp))) ? |
| next(U16_TRAIL(cp)) : |
| USTRINGTRIE_NO_MATCH); |
| } |
| |
| UStringTrieResult |
| UCharsTrie::nextForCodePoint(UChar32 cp) { |
| return cp<=0xffff ? |
| next(cp) : |
| (USTRINGTRIE_HAS_NEXT(next(U16_LEAD(cp))) ? |
| next(U16_TRAIL(cp)) : |
| USTRINGTRIE_NO_MATCH); |
| } |
| |
| UStringTrieResult |
| UCharsTrie::branchNext(const UChar *pos, int32_t length, int32_t uchar) { |
| // Branch according to the current unit. |
| if(length==0) { |
| length=*pos++; |
| } |
| ++length; |
| // The length of the branch is the number of units to select from. |
| // The data structure encodes a binary search. |
| while(length>kMaxBranchLinearSubNodeLength) { |
| if(uchar<*pos++) { |
| length>>=1; |
| pos=jumpByDelta(pos); |
| } else { |
| length=length-(length>>1); |
| pos=skipDelta(pos); |
| } |
| } |
| // Drop down to linear search for the last few units. |
| // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 |
| // and divides length by 2. |
| do { |
| if(uchar==*pos++) { |
| UStringTrieResult result; |
| int32_t node=*pos; |
| 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); |
| int32_t delta; |
| if(node<kMinTwoUnitValueLead) { |
| delta=node; |
| } else if(node<kThreeUnitValueLead) { |
| delta=((node-kMinTwoUnitValueLead)<<16)|*pos++; |
| } else { |
| delta=(pos[0]<<16)|pos[1]; |
| pos+=2; |
| } |
| // 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(uchar==*pos++) { |
| pos_=pos; |
| int32_t node=*pos; |
| return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE; |
| } else { |
| stop(); |
| return USTRINGTRIE_NO_MATCH; |
| } |
| } |
| |
| UStringTrieResult |
| UCharsTrie::nextImpl(const UChar *pos, int32_t uchar) { |
| int32_t node=*pos++; |
| for(;;) { |
| if(node<kMinLinearMatch) { |
| return branchNext(pos, node, uchar); |
| } else if(node<kMinValueLead) { |
| // Match the first of length+1 units. |
| int32_t length=node-kMinLinearMatch; // Actual match length minus 1. |
| if(uchar==*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 units. |
| break; |
| } else { |
| // Skip intermediate value. |
| pos=skipNodeValue(pos, node); |
| node&=kNodeTypeMask; |
| } |
| } |
| stop(); |
| return USTRINGTRIE_NO_MATCH; |
| } |
| |
| UStringTrieResult |
| UCharsTrie::next(int32_t uchar) { |
| const UChar *pos=pos_; |
| if(pos==NULL) { |
| return USTRINGTRIE_NO_MATCH; |
| } |
| int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. |
| if(length>=0) { |
| // Remaining part of a linear-match node. |
| if(uchar==*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, uchar); |
| } |
| |
| UStringTrieResult |
| UCharsTrie::next(const UChar *s, int32_t sLength) { |
| if(sLength<0 ? *s==0 : sLength==0) { |
| // Empty input. |
| return current(); |
| } |
| const UChar *pos=pos_; |
| if(pos==NULL) { |
| return USTRINGTRIE_NO_MATCH; |
| } |
| int32_t length=remainingMatchLength_; // Actual remaining match length minus 1. |
| for(;;) { |
| // Fetch the next input unit, if there is one. |
| // Continue a linear-match node without rechecking sLength<0. |
| int32_t uchar; |
| if(sLength<0) { |
| for(;;) { |
| if((uchar=*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(uchar!=*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; |
| } |
| uchar=*s++; |
| --sLength; |
| if(length<0) { |
| remainingMatchLength_=length; |
| break; |
| } |
| if(uchar!=*pos) { |
| stop(); |
| return USTRINGTRIE_NO_MATCH; |
| } |
| ++pos; |
| --length; |
| } |
| } |
| int32_t node=*pos++; |
| for(;;) { |
| if(node<kMinLinearMatch) { |
| UStringTrieResult result=branchNext(pos, node, uchar); |
| if(result==USTRINGTRIE_NO_MATCH) { |
| return USTRINGTRIE_NO_MATCH; |
| } |
| // Fetch the next input unit, if there is one. |
| if(sLength<0) { |
| if((uchar=*s++)==0) { |
| return result; |
| } |
| } else { |
| if(sLength==0) { |
| return result; |
| } |
| uchar=*s++; |
| --sLength; |
| } |
| if(result==USTRINGTRIE_FINAL_VALUE) { |
| // No further matching units. |
| stop(); |
| return USTRINGTRIE_NO_MATCH; |
| } |
| pos=pos_; // branchNext() advanced pos and wrote it to pos_ . |
| node=*pos++; |
| } else if(node<kMinValueLead) { |
| // Match length+1 units. |
| length=node-kMinLinearMatch; // Actual match length minus 1. |
| if(uchar!=*pos) { |
| stop(); |
| return USTRINGTRIE_NO_MATCH; |
| } |
| ++pos; |
| --length; |
| break; |
| } else if(node&kValueIsFinal) { |
| // No further matching units. |
| stop(); |
| return USTRINGTRIE_NO_MATCH; |
| } else { |
| // Skip intermediate value. |
| pos=skipNodeValue(pos, node); |
| node&=kNodeTypeMask; |
| } |
| } |
| } |
| } |
| |
| const UChar * |
| UCharsTrie::findUniqueValueFromBranch(const UChar *pos, int32_t length, |
| UBool haveUniqueValue, int32_t &uniqueValue) { |
| while(length>kMaxBranchLinearSubNodeLength) { |
| ++pos; // ignore the comparison unit |
| if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) { |
| return NULL; |
| } |
| length=length-(length>>1); |
| pos=skipDelta(pos); |
| } |
| do { |
| ++pos; // ignore a comparison unit |
| // handle its value |
| int32_t node=*pos++; |
| UBool isFinal=(UBool)(node>>15); |
| node&=0x7fff; |
| int32_t value=readValue(pos, node); |
| 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 unit |
| } |
| |
| UBool |
| UCharsTrie::findUniqueValue(const UChar *pos, UBool haveUniqueValue, int32_t &uniqueValue) { |
| int32_t node=*pos++; |
| for(;;) { |
| if(node<kMinLinearMatch) { |
| if(node==0) { |
| node=*pos++; |
| } |
| pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue); |
| if(pos==NULL) { |
| return FALSE; |
| } |
| haveUniqueValue=TRUE; |
| node=*pos++; |
| } else if(node<kMinValueLead) { |
| // linear-match node |
| pos+=node-kMinLinearMatch+1; // Ignore the match units. |
| node=*pos++; |
| } else { |
| UBool isFinal=(UBool)(node>>15); |
| int32_t value; |
| if(isFinal) { |
| value=readValue(pos, node&0x7fff); |
| } else { |
| value=readNodeValue(pos, node); |
| } |
| if(haveUniqueValue) { |
| if(value!=uniqueValue) { |
| return FALSE; |
| } |
| } else { |
| uniqueValue=value; |
| haveUniqueValue=TRUE; |
| } |
| if(isFinal) { |
| return TRUE; |
| } |
| pos=skipNodeValue(pos, node); |
| node&=kNodeTypeMask; |
| } |
| } |
| } |
| |
| int32_t |
| UCharsTrie::getNextUChars(Appendable &out) const { |
| const UChar *pos=pos_; |
| if(pos==NULL) { |
| return 0; |
| } |
| if(remainingMatchLength_>=0) { |
| out.appendCodeUnit(*pos); // Next unit of a pending linear-match node. |
| return 1; |
| } |
| int32_t node=*pos++; |
| if(node>=kMinValueLead) { |
| if(node&kValueIsFinal) { |
| return 0; |
| } else { |
| pos=skipNodeValue(pos, node); |
| node&=kNodeTypeMask; |
| } |
| } |
| if(node<kMinLinearMatch) { |
| if(node==0) { |
| node=*pos++; |
| } |
| out.reserveAppendCapacity(++node); |
| getNextBranchUChars(pos, node, out); |
| return node; |
| } else { |
| // First unit of the linear-match node. |
| out.appendCodeUnit(*pos); |
| return 1; |
| } |
| } |
| |
| void |
| UCharsTrie::getNextBranchUChars(const UChar *pos, int32_t length, Appendable &out) { |
| while(length>kMaxBranchLinearSubNodeLength) { |
| ++pos; // ignore the comparison unit |
| getNextBranchUChars(jumpByDelta(pos), length>>1, out); |
| length=length-(length>>1); |
| pos=skipDelta(pos); |
| } |
| do { |
| out.appendCodeUnit(*pos++); |
| pos=skipValue(pos); |
| } while(--length>1); |
| out.appendCodeUnit(*pos); |
| } |
| |
| U_NAMESPACE_END |
