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