| // © 2016 and later: Unicode, Inc. and others. |
| // License & terms of use: http://www.unicode.org/copyright.html |
| /* |
| ******************************************************************************* |
| * Copyright (C) 2010-2012, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ******************************************************************************* |
| * file name: bytestrieiterator.cpp |
| * encoding: UTF-8 |
| * tab size: 8 (not used) |
| * indentation:4 |
| * |
| * created on: 2010nov03 |
| * created by: Markus W. Scherer |
| */ |
| |
| #if defined(STARBOARD) |
| #include "starboard/client_porting/poem/assert_poem.h" |
| #endif // defined(STARBOARD) |
| #include "unicode/utypes.h" |
| #include "unicode/bytestrie.h" |
| #include "unicode/stringpiece.h" |
| #include "charstr.h" |
| #include "uvectr32.h" |
| |
| U_NAMESPACE_BEGIN |
| |
| BytesTrie::Iterator::Iterator(const void *trieBytes, int32_t maxStringLength, |
| UErrorCode &errorCode) |
| : bytes_(static_cast<const uint8_t *>(trieBytes)), |
| pos_(bytes_), initialPos_(bytes_), |
| remainingMatchLength_(-1), initialRemainingMatchLength_(-1), |
| str_(NULL), maxLength_(maxStringLength), value_(0), stack_(NULL) { |
| if(U_FAILURE(errorCode)) { |
| return; |
| } |
| // str_ and stack_ are pointers so that it's easy to turn bytestrie.h into |
| // a public API header for which we would want it to depend only on |
| // other public headers. |
| // Unlike BytesTrie itself, its Iterator performs memory allocations anyway |
| // via the CharString and UVector32 implementations, so this additional |
| // cost is minimal. |
| str_=new CharString(); |
| stack_=new UVector32(errorCode); |
| if(U_SUCCESS(errorCode) && (str_==NULL || stack_==NULL)) { |
| errorCode=U_MEMORY_ALLOCATION_ERROR; |
| } |
| } |
| |
| BytesTrie::Iterator::Iterator(const BytesTrie &trie, int32_t maxStringLength, |
| UErrorCode &errorCode) |
| : bytes_(trie.bytes_), pos_(trie.pos_), initialPos_(trie.pos_), |
| remainingMatchLength_(trie.remainingMatchLength_), |
| initialRemainingMatchLength_(trie.remainingMatchLength_), |
| str_(NULL), maxLength_(maxStringLength), value_(0), stack_(NULL) { |
| if(U_FAILURE(errorCode)) { |
| return; |
| } |
| str_=new CharString(); |
| stack_=new UVector32(errorCode); |
| if(U_FAILURE(errorCode)) { |
| return; |
| } |
| if(str_==NULL || 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 bytes to str_. |
| ++length; |
| if(maxLength_>0 && length>maxLength_) { |
| length=maxLength_; // This will leave remainingMatchLength>=0 as a signal. |
| } |
| str_->append(reinterpret_cast<const char *>(pos_), length, errorCode); |
| pos_+=length; |
| remainingMatchLength_-=length; |
| } |
| } |
| |
| BytesTrie::Iterator::~Iterator() { |
| delete str_; |
| delete stack_; |
| } |
| |
| BytesTrie::Iterator & |
| BytesTrie::Iterator::reset() { |
| pos_=initialPos_; |
| remainingMatchLength_=initialRemainingMatchLength_; |
| 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 |
| BytesTrie::Iterator::hasNext() const { return pos_!=NULL || !stack_->isEmpty(); } |
| |
| UBool |
| BytesTrie::Iterator::next(UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { |
| return FALSE; |
| } |
| const uint8_t *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=bytes_+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((char)*pos++, errorCode); |
| } |
| } |
| if(remainingMatchLength_>=0) { |
| // We only get here if we started in a pending linear-match node |
| // with more than maxLength remaining bytes. |
| return truncateAndStop(); |
| } |
| for(;;) { |
| int32_t node=*pos++; |
| if(node>=kMinValueLead) { |
| // Deliver value for the byte sequence so far. |
| UBool isFinal=(UBool)(node&kValueIsFinal); |
| value_=readValue(pos, node>>1); |
| if(isFinal || (maxLength_>0 && str_->length()==maxLength_)) { |
| pos_=NULL; |
| } else { |
| pos_=skipValue(pos, node); |
| } |
| 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 bytes to str_. |
| int32_t length=node-kMinLinearMatch+1; |
| if(maxLength_>0 && str_->length()+length>maxLength_) { |
| str_->append(reinterpret_cast<const char *>(pos), |
| maxLength_-str_->length(), errorCode); |
| return truncateAndStop(); |
| } |
| str_->append(reinterpret_cast<const char *>(pos), length, errorCode); |
| pos+=length; |
| } |
| } |
| } |
| |
| StringPiece |
| BytesTrie::Iterator::getString() const { |
| return str_ == NULL ? StringPiece() : str_->toStringPiece(); |
| } |
| |
| UBool |
| BytesTrie::Iterator::truncateAndStop() { |
| pos_=NULL; |
| value_=-1; // no real value for str |
| return TRUE; |
| } |
| |
| // Branch node, needs to take the first outbound edge and push state for the rest. |
| const uint8_t * |
| BytesTrie::Iterator::branchNext(const uint8_t *pos, int32_t length, UErrorCode &errorCode) { |
| while(length>kMaxBranchLinearSubNodeLength) { |
| ++pos; // ignore the comparison byte |
| // Push state for the greater-or-equal edge. |
| stack_->addElement((int32_t)(skipDelta(pos)-bytes_), 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. |
| uint8_t trieByte=*pos++; |
| int32_t node=*pos++; |
| UBool isFinal=(UBool)(node&kValueIsFinal); |
| int32_t value=readValue(pos, node>>1); |
| pos=skipValue(pos, node); |
| stack_->addElement((int32_t)(pos-bytes_), errorCode); |
| stack_->addElement(((length-1)<<16)|str_->length(), errorCode); |
| str_->append((char)trieByte, errorCode); |
| if(isFinal) { |
| pos_=NULL; |
| value_=value; |
| return NULL; |
| } else { |
| return pos+value; |
| } |
| } |
| |
| U_NAMESPACE_END |
