The Tor Browser / file revision

 /*

 *******************************************************************************

 *   Copyright (C) 2010-2012, International Business Machines

 *   Corporation and others.  All Rights Reserved.

 *******************************************************************************

 *   file name:  bytestrieiterator.cpp

 *   encoding:   US-ASCII

 *   tab size:   8 (not used)

 *   indentation:4

 *

 *   created on: 2010nov03

 *   created by: Markus W. Scherer

 */

 #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);

             }

             sp_.set(str_->data(), str_->length());

             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;

         }

     }

 }

 UBool

 BytesTrie::Iterator::truncateAndStop() {

     pos_=NULL;

     sp_.set(str_->data(), str_->length());

     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;

         sp_.set(str_->data(), str_->length());

         value_=value;

         return NULL;

     } else {

         return pos+value;

     }

 }

 U_NAMESPACE_END