icuSources/common/ucharstrieiterator.cpp

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