src/third_party/icu/source/common/bytestrieiterator.cpp

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 2010-2012, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   file name:  bytestrieiterator.cpp
   7 *   encoding:   US-ASCII
   8 *   tab size:   8 (not used)
   9 *   indentation:4
  10 *
  11 *   created on: 2010nov03
  12 *   created by: Markus W. Scherer
  13 */
  14
  15 #include "unicode/utypes.h"
  16 #include "unicode/bytestrie.h"
  17 #include "unicode/stringpiece.h"
  18 #include "charstr.h"
  19 #include "uvectr32.h"
  20
  21 U_NAMESPACE_BEGIN
  22
  23 BytesTrie::Iterator::Iterator(const void *trieBytes, int32_t maxStringLength,
  24                               UErrorCode &errorCode)
  25         : bytes_(static_cast<const uint8_t *>(trieBytes)),
  26           pos_(bytes_), initialPos_(bytes_),
  27           remainingMatchLength_(-1), initialRemainingMatchLength_(-1),
  28           str_(NULL), maxLength_(maxStringLength), value_(0), stack_(NULL) {
  29     if(U_FAILURE(errorCode)) {
  30         return;
  31     }
  32     // str_ and stack_ are pointers so that it's easy to turn bytestrie.h into
  33     // a public API header for which we would want it to depend only on
  34     // other public headers.
  35     // Unlike BytesTrie itself, its Iterator performs memory allocations anyway
  36     // via the CharString and UVector32 implementations, so this additional
  37     // cost is minimal.
  38     str_=new CharString();
  39     stack_=new UVector32(errorCode);
  40     if(U_SUCCESS(errorCode) && (str_==NULL || stack_==NULL)) {
  41         errorCode=U_MEMORY_ALLOCATION_ERROR;
  42     }
  43 }
  44
  45 BytesTrie::Iterator::Iterator(const BytesTrie &trie, int32_t maxStringLength,
  46                               UErrorCode &errorCode)
  47         : bytes_(trie.bytes_), pos_(trie.pos_), initialPos_(trie.pos_),
  48           remainingMatchLength_(trie.remainingMatchLength_),
  49           initialRemainingMatchLength_(trie.remainingMatchLength_),
  50           str_(NULL), maxLength_(maxStringLength), value_(0), stack_(NULL) {
  51     if(U_FAILURE(errorCode)) {
  52         return;
  53     }
  54     str_=new CharString();
  55     stack_=new UVector32(errorCode);
  56     if(U_FAILURE(errorCode)) {
  57         return;
  58     }
  59     if(str_==NULL || stack_==NULL) {
  60         errorCode=U_MEMORY_ALLOCATION_ERROR;
  61         return;
  62     }
  63     int32_t length=remainingMatchLength_;  // Actual remaining match length minus 1.
  64     if(length>=0) {
  65         // Pending linear-match node, append remaining bytes to str_.
  66         ++length;
  67         if(maxLength_>0 && length>maxLength_) {
  68             length=maxLength_;  // This will leave remainingMatchLength>=0 as a signal.
  69         }
  70         str_->append(reinterpret_cast<const char *>(pos_), length, errorCode);
  71         pos_+=length;
  72         remainingMatchLength_-=length;
  73     }
  74 }
  75
  76 BytesTrie::Iterator::~Iterator() {
  77     delete str_;
  78     delete stack_;
  79 }
  80
  81 BytesTrie::Iterator &
  82 BytesTrie::Iterator::reset() {
  83     pos_=initialPos_;
  84     remainingMatchLength_=initialRemainingMatchLength_;
  85     int32_t length=remainingMatchLength_+1;  // Remaining match length.
  86     if(maxLength_>0 && length>maxLength_) {
  87         length=maxLength_;
  88     }
  89     str_->truncate(length);
  90     pos_+=length;
  91     remainingMatchLength_-=length;
  92     stack_->setSize(0);
  93     return *this;
  94 }
  95
  96 UBool
  97 BytesTrie::Iterator::hasNext() const { return pos_!=NULL || !stack_->isEmpty(); }
  98
  99 UBool
 100 BytesTrie::Iterator::next(UErrorCode &errorCode) {
 101     if(U_FAILURE(errorCode)) {
 102         return FALSE;
 103     }
 104     const uint8_t *pos=pos_;
 105     if(pos==NULL) {
 106         if(stack_->isEmpty()) {
 107             return FALSE;
 108         }
 109         // Pop the state off the stack and continue with the next outbound edge of
 110         // the branch node.
 111         int32_t stackSize=stack_->size();
 112         int32_t length=stack_->elementAti(stackSize-1);
 113         pos=bytes_+stack_->elementAti(stackSize-2);
 114         stack_->setSize(stackSize-2);
 115         str_->truncate(length&0xffff);
 116         length=(int32_t)((uint32_t)length>>16);
 117         if(length>1) {
 118             pos=branchNext(pos, length, errorCode);
 119             if(pos==NULL) {
 120                 return TRUE;  // Reached a final value.
 121             }
 122         } else {
 123             str_->append((char)*pos++, errorCode);
 124         }
 125     }
 126     if(remainingMatchLength_>=0) {
 127         // We only get here if we started in a pending linear-match node
 128         // with more than maxLength remaining bytes.
 129         return truncateAndStop();
 130     }
 131     for(;;) {
 132         int32_t node=*pos++;
 133         if(node>=kMinValueLead) {
 134             // Deliver value for the byte sequence so far.
 135             UBool isFinal=(UBool)(node&kValueIsFinal);
 136             value_=readValue(pos, node>>1);
 137             if(isFinal || (maxLength_>0 && str_->length()==maxLength_)) {
 138                 pos_=NULL;
 139             } else {
 140                 pos_=skipValue(pos, node);
 141             }
 142             sp_.set(str_->data(), str_->length());
 143             return TRUE;
 144         }
 145         if(maxLength_>0 && str_->length()==maxLength_) {
 146             return truncateAndStop();
 147         }
 148         if(node<kMinLinearMatch) {
 149             if(node==0) {
 150                 node=*pos++;
 151             }
 152             pos=branchNext(pos, node+1, errorCode);
 153             if(pos==NULL) {
 154                 return TRUE;  // Reached a final value.
 155             }
 156         } else {
 157             // Linear-match node, append length bytes to str_.
 158             int32_t length=node-kMinLinearMatch+1;
 159             if(maxLength_>0 && str_->length()+length>maxLength_) {
 160                 str_->append(reinterpret_cast<const char *>(pos),
 161                             maxLength_-str_->length(), errorCode);
 162                 return truncateAndStop();
 163             }
 164             str_->append(reinterpret_cast<const char *>(pos), length, errorCode);
 165             pos+=length;
 166         }
 167     }
 168 }
 169
 170 UBool
 171 BytesTrie::Iterator::truncateAndStop() {
 172     pos_=NULL;
 173     sp_.set(str_->data(), str_->length());
 174     value_=-1;  // no real value for str
 175     return TRUE;
 176 }
 177
 178 // Branch node, needs to take the first outbound edge and push state for the rest.
 179 const uint8_t *
 180 BytesTrie::Iterator::branchNext(const uint8_t *pos, int32_t length, UErrorCode &errorCode) {
 181     while(length>kMaxBranchLinearSubNodeLength) {
 182         ++pos;  // ignore the comparison byte
 183         // Push state for the greater-or-equal edge.
 184         stack_->addElement((int32_t)(skipDelta(pos)-bytes_), errorCode);
 185         stack_->addElement(((length-(length>>1))<<16)|str_->length(), errorCode);
 186         // Follow the less-than edge.
 187         length>>=1;
 188         pos=jumpByDelta(pos);
 189     }
 190     // List of key-value pairs where values are either final values or jump deltas.
 191     // Read the first (key, value) pair.
 192     uint8_t trieByte=*pos++;
 193     int32_t node=*pos++;
 194     UBool isFinal=(UBool)(node&kValueIsFinal);
 195     int32_t value=readValue(pos, node>>1);
 196     pos=skipValue(pos, node);
 197     stack_->addElement((int32_t)(pos-bytes_), errorCode);
 198     stack_->addElement(((length-1)<<16)|str_->length(), errorCode);
 199     str_->append((char)trieByte, errorCode);
 200     if(isFinal) {
 201         pos_=NULL;
 202         sp_.set(str_->data(), str_->length());
 203         value_=value;
 204         return NULL;
 205     } else {
 206         return pos+value;
 207     }
 208 }
 209
 210 U_NAMESPACE_END