blob: b3132241fe2b7ab33961807c5e4f142a6dd60f74 [file] [log] [blame]
// © 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: ucharstrieiterator.h
* encoding: UTF-8
* tab size: 8 (not used)
* indentation:4
*
* created on: 2010nov15
* created by: Markus W. Scherer
*/
#include "unicode/utypes.h"
#include "unicode/ucharstrie.h"
#include "unicode/unistr.h"
#include "uvectr32.h"
U_NAMESPACE_BEGIN
UCharsTrie::Iterator::Iterator(ConstChar16Ptr trieUChars, int32_t maxStringLength,
UErrorCode &errorCode)
: uchars_(trieUChars),
pos_(uchars_), initialPos_(uchars_),
remainingMatchLength_(-1), initialRemainingMatchLength_(-1),
skipValue_(FALSE),
maxLength_(maxStringLength), value_(0), stack_(NULL) {
if(U_FAILURE(errorCode)) {
return;
}
// stack_ is a pointer so that it's easy to turn ucharstrie.h into
// a public API header for which we would want it to depend only on
// other public headers.
// Unlike UCharsTrie itself, its Iterator performs memory allocations anyway
// via the UnicodeString and UVector32 implementations, so this additional
// cost is minimal.
stack_=new UVector32(errorCode);
if(stack_==NULL) {
errorCode=U_MEMORY_ALLOCATION_ERROR;
}
}
UCharsTrie::Iterator::Iterator(const UCharsTrie &trie, int32_t maxStringLength,
UErrorCode &errorCode)
: uchars_(trie.uchars_), pos_(trie.pos_), initialPos_(trie.pos_),
remainingMatchLength_(trie.remainingMatchLength_),
initialRemainingMatchLength_(trie.remainingMatchLength_),
skipValue_(FALSE),
maxLength_(maxStringLength), value_(0), stack_(NULL) {
if(U_FAILURE(errorCode)) {
return;
}
stack_=new UVector32(errorCode);
if(U_FAILURE(errorCode)) {
return;
}
if(stack_==NULL) {
errorCode=U_MEMORY_ALLOCATION_ERROR;
return;
}
int32_t length=remainingMatchLength_; // Actual remaining match length minus 1.
if(length>=0) {
// Pending linear-match node, append remaining UChars to str_.
++length;
if(maxLength_>0 && length>maxLength_) {
length=maxLength_; // This will leave remainingMatchLength>=0 as a signal.
}
str_.append(pos_, length);
pos_+=length;
remainingMatchLength_-=length;
}
}
UCharsTrie::Iterator::~Iterator() {
delete stack_;
}
UCharsTrie::Iterator &
UCharsTrie::Iterator::reset() {
pos_=initialPos_;
remainingMatchLength_=initialRemainingMatchLength_;
skipValue_=FALSE;
int32_t length=remainingMatchLength_+1; // Remaining match length.
if(maxLength_>0 && length>maxLength_) {
length=maxLength_;
}
str_.truncate(length);
pos_+=length;
remainingMatchLength_-=length;
stack_->setSize(0);
return *this;
}
UBool
UCharsTrie::Iterator::hasNext() const { return pos_!=NULL || !stack_->isEmpty(); }
UBool
UCharsTrie::Iterator::next(UErrorCode &errorCode) {
if(U_FAILURE(errorCode)) {
return FALSE;
}
const UChar *pos=pos_;
if(pos==NULL) {
if(stack_->isEmpty()) {
return FALSE;
}
// Pop the state off the stack and continue with the next outbound edge of
// the branch node.
int32_t stackSize=stack_->size();
int32_t length=stack_->elementAti(stackSize-1);
pos=uchars_+stack_->elementAti(stackSize-2);
stack_->setSize(stackSize-2);
str_.truncate(length&0xffff);
length=(int32_t)((uint32_t)length>>16);
if(length>1) {
pos=branchNext(pos, length, errorCode);
if(pos==NULL) {
return TRUE; // Reached a final value.
}
} else {
str_.append(*pos++);
}
}
if(remainingMatchLength_>=0) {
// We only get here if we started in a pending linear-match node
// with more than maxLength remaining units.
return truncateAndStop();
}
for(;;) {
int32_t node=*pos++;
if(node>=kMinValueLead) {
if(skipValue_) {
pos=skipNodeValue(pos, node);
node&=kNodeTypeMask;
skipValue_=FALSE;
} else {
// Deliver value for the string so far.
UBool isFinal=(UBool)(node>>15);
if(isFinal) {
value_=readValue(pos, node&0x7fff);
} else {
value_=readNodeValue(pos, node);
}
if(isFinal || (maxLength_>0 && str_.length()==maxLength_)) {
pos_=NULL;
} else {
// We cannot skip the value right here because it shares its
// lead unit with a match node which we have to evaluate
// next time.
// Instead, keep pos_ on the node lead unit itself.
pos_=pos-1;
skipValue_=TRUE;
}
return TRUE;
}
}
if(maxLength_>0 && str_.length()==maxLength_) {
return truncateAndStop();
}
if(node<kMinLinearMatch) {
if(node==0) {
node=*pos++;
}
pos=branchNext(pos, node+1, errorCode);
if(pos==NULL) {
return TRUE; // Reached a final value.
}
} else {
// Linear-match node, append length units to str_.
int32_t length=node-kMinLinearMatch+1;
if(maxLength_>0 && str_.length()+length>maxLength_) {
str_.append(pos, maxLength_-str_.length());
return truncateAndStop();
}
str_.append(pos, length);
pos+=length;
}
}
}
// Branch node, needs to take the first outbound edge and push state for the rest.
const UChar *
UCharsTrie::Iterator::branchNext(const UChar *pos, int32_t length, UErrorCode &errorCode) {
while(length>kMaxBranchLinearSubNodeLength) {
++pos; // ignore the comparison unit
// Push state for the greater-or-equal edge.
stack_->addElement((int32_t)(skipDelta(pos)-uchars_), errorCode);
stack_->addElement(((length-(length>>1))<<16)|str_.length(), errorCode);
// Follow the less-than edge.
length>>=1;
pos=jumpByDelta(pos);
}
// List of key-value pairs where values are either final values or jump deltas.
// Read the first (key, value) pair.
UChar trieUnit=*pos++;
int32_t node=*pos++;
UBool isFinal=(UBool)(node>>15);
int32_t value=readValue(pos, node&=0x7fff);
pos=skipValue(pos, node);
stack_->addElement((int32_t)(pos-uchars_), errorCode);
stack_->addElement(((length-1)<<16)|str_.length(), errorCode);
str_.append(trieUnit);
if(isFinal) {
pos_=NULL;
value_=value;
return NULL;
} else {
return pos+value;
}
}
U_NAMESPACE_END