/*
*******************************************************************************
* 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 "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