Line data Source code
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-2011, International Business Machines
6 : * Corporation and others. All Rights Reserved.
7 : *******************************************************************************
8 : * file name: bytestrie.cpp
9 : * encoding: UTF-8
10 : * tab size: 8 (not used)
11 : * indentation:4
12 : *
13 : * created on: 2010sep25
14 : * created by: Markus W. Scherer
15 : */
16 :
17 : #include "unicode/utypes.h"
18 : #include "unicode/bytestream.h"
19 : #include "unicode/bytestrie.h"
20 : #include "unicode/uobject.h"
21 : #include "cmemory.h"
22 : #include "uassert.h"
23 :
24 : U_NAMESPACE_BEGIN
25 :
26 0 : BytesTrie::~BytesTrie() {
27 0 : uprv_free(ownedArray_);
28 0 : }
29 :
30 : // lead byte already shifted right by 1.
31 : int32_t
32 0 : BytesTrie::readValue(const uint8_t *pos, int32_t leadByte) {
33 : int32_t value;
34 0 : if(leadByte<kMinTwoByteValueLead) {
35 0 : value=leadByte-kMinOneByteValueLead;
36 0 : } else if(leadByte<kMinThreeByteValueLead) {
37 0 : value=((leadByte-kMinTwoByteValueLead)<<8)|*pos;
38 0 : } else if(leadByte<kFourByteValueLead) {
39 0 : value=((leadByte-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1];
40 0 : } else if(leadByte==kFourByteValueLead) {
41 0 : value=(pos[0]<<16)|(pos[1]<<8)|pos[2];
42 : } else {
43 0 : value=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3];
44 : }
45 0 : return value;
46 : }
47 :
48 : const uint8_t *
49 0 : BytesTrie::jumpByDelta(const uint8_t *pos) {
50 0 : int32_t delta=*pos++;
51 0 : if(delta<kMinTwoByteDeltaLead) {
52 : // nothing to do
53 0 : } else if(delta<kMinThreeByteDeltaLead) {
54 0 : delta=((delta-kMinTwoByteDeltaLead)<<8)|*pos++;
55 0 : } else if(delta<kFourByteDeltaLead) {
56 0 : delta=((delta-kMinThreeByteDeltaLead)<<16)|(pos[0]<<8)|pos[1];
57 0 : pos+=2;
58 0 : } else if(delta==kFourByteDeltaLead) {
59 0 : delta=(pos[0]<<16)|(pos[1]<<8)|pos[2];
60 0 : pos+=3;
61 : } else {
62 0 : delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3];
63 0 : pos+=4;
64 : }
65 0 : return pos+delta;
66 : }
67 :
68 : UStringTrieResult
69 0 : BytesTrie::current() const {
70 0 : const uint8_t *pos=pos_;
71 0 : if(pos==NULL) {
72 0 : return USTRINGTRIE_NO_MATCH;
73 : } else {
74 : int32_t node;
75 0 : return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ?
76 0 : valueResult(node) : USTRINGTRIE_NO_VALUE;
77 : }
78 : }
79 :
80 : UStringTrieResult
81 0 : BytesTrie::branchNext(const uint8_t *pos, int32_t length, int32_t inByte) {
82 : // Branch according to the current byte.
83 0 : if(length==0) {
84 0 : length=*pos++;
85 : }
86 0 : ++length;
87 : // The length of the branch is the number of bytes to select from.
88 : // The data structure encodes a binary search.
89 0 : while(length>kMaxBranchLinearSubNodeLength) {
90 0 : if(inByte<*pos++) {
91 0 : length>>=1;
92 0 : pos=jumpByDelta(pos);
93 : } else {
94 0 : length=length-(length>>1);
95 0 : pos=skipDelta(pos);
96 : }
97 : }
98 : // Drop down to linear search for the last few bytes.
99 : // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3
100 : // and divides length by 2.
101 0 : do {
102 0 : if(inByte==*pos++) {
103 : UStringTrieResult result;
104 0 : int32_t node=*pos;
105 0 : U_ASSERT(node>=kMinValueLead);
106 0 : if(node&kValueIsFinal) {
107 : // Leave the final value for getValue() to read.
108 0 : result=USTRINGTRIE_FINAL_VALUE;
109 : } else {
110 : // Use the non-final value as the jump delta.
111 0 : ++pos;
112 : // int32_t delta=readValue(pos, node>>1);
113 0 : node>>=1;
114 : int32_t delta;
115 0 : if(node<kMinTwoByteValueLead) {
116 0 : delta=node-kMinOneByteValueLead;
117 0 : } else if(node<kMinThreeByteValueLead) {
118 0 : delta=((node-kMinTwoByteValueLead)<<8)|*pos++;
119 0 : } else if(node<kFourByteValueLead) {
120 0 : delta=((node-kMinThreeByteValueLead)<<16)|(pos[0]<<8)|pos[1];
121 0 : pos+=2;
122 0 : } else if(node==kFourByteValueLead) {
123 0 : delta=(pos[0]<<16)|(pos[1]<<8)|pos[2];
124 0 : pos+=3;
125 : } else {
126 0 : delta=(pos[0]<<24)|(pos[1]<<16)|(pos[2]<<8)|pos[3];
127 0 : pos+=4;
128 : }
129 : // end readValue()
130 0 : pos+=delta;
131 0 : node=*pos;
132 0 : result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE;
133 : }
134 0 : pos_=pos;
135 0 : return result;
136 : }
137 0 : --length;
138 0 : pos=skipValue(pos);
139 0 : } while(length>1);
140 0 : if(inByte==*pos++) {
141 0 : pos_=pos;
142 0 : int32_t node=*pos;
143 0 : return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE;
144 : } else {
145 0 : stop();
146 0 : return USTRINGTRIE_NO_MATCH;
147 : }
148 : }
149 :
150 : UStringTrieResult
151 0 : BytesTrie::nextImpl(const uint8_t *pos, int32_t inByte) {
152 : for(;;) {
153 0 : int32_t node=*pos++;
154 0 : if(node<kMinLinearMatch) {
155 0 : return branchNext(pos, node, inByte);
156 0 : } else if(node<kMinValueLead) {
157 : // Match the first of length+1 bytes.
158 0 : int32_t length=node-kMinLinearMatch; // Actual match length minus 1.
159 0 : if(inByte==*pos++) {
160 0 : remainingMatchLength_=--length;
161 0 : pos_=pos;
162 0 : return (length<0 && (node=*pos)>=kMinValueLead) ?
163 0 : valueResult(node) : USTRINGTRIE_NO_VALUE;
164 : } else {
165 : // No match.
166 0 : break;
167 : }
168 0 : } else if(node&kValueIsFinal) {
169 : // No further matching bytes.
170 0 : break;
171 : } else {
172 : // Skip intermediate value.
173 0 : pos=skipValue(pos, node);
174 : // The next node must not also be a value node.
175 0 : U_ASSERT(*pos<kMinValueLead);
176 : }
177 0 : }
178 0 : stop();
179 0 : return USTRINGTRIE_NO_MATCH;
180 : }
181 :
182 : UStringTrieResult
183 0 : BytesTrie::next(int32_t inByte) {
184 0 : const uint8_t *pos=pos_;
185 0 : if(pos==NULL) {
186 0 : return USTRINGTRIE_NO_MATCH;
187 : }
188 0 : if(inByte<0) {
189 0 : inByte+=0x100;
190 : }
191 0 : int32_t length=remainingMatchLength_; // Actual remaining match length minus 1.
192 0 : if(length>=0) {
193 : // Remaining part of a linear-match node.
194 0 : if(inByte==*pos++) {
195 0 : remainingMatchLength_=--length;
196 0 : pos_=pos;
197 : int32_t node;
198 0 : return (length<0 && (node=*pos)>=kMinValueLead) ?
199 0 : valueResult(node) : USTRINGTRIE_NO_VALUE;
200 : } else {
201 0 : stop();
202 0 : return USTRINGTRIE_NO_MATCH;
203 : }
204 : }
205 0 : return nextImpl(pos, inByte);
206 : }
207 :
208 : UStringTrieResult
209 0 : BytesTrie::next(const char *s, int32_t sLength) {
210 0 : if(sLength<0 ? *s==0 : sLength==0) {
211 : // Empty input.
212 0 : return current();
213 : }
214 0 : const uint8_t *pos=pos_;
215 0 : if(pos==NULL) {
216 0 : return USTRINGTRIE_NO_MATCH;
217 : }
218 0 : int32_t length=remainingMatchLength_; // Actual remaining match length minus 1.
219 : for(;;) {
220 : // Fetch the next input byte, if there is one.
221 : // Continue a linear-match node without rechecking sLength<0.
222 : int32_t inByte;
223 0 : if(sLength<0) {
224 : for(;;) {
225 0 : if((inByte=*s++)==0) {
226 0 : remainingMatchLength_=length;
227 0 : pos_=pos;
228 : int32_t node;
229 0 : return (length<0 && (node=*pos)>=kMinValueLead) ?
230 0 : valueResult(node) : USTRINGTRIE_NO_VALUE;
231 : }
232 0 : if(length<0) {
233 0 : remainingMatchLength_=length;
234 0 : break;
235 : }
236 0 : if(inByte!=*pos) {
237 0 : stop();
238 0 : return USTRINGTRIE_NO_MATCH;
239 : }
240 0 : ++pos;
241 0 : --length;
242 0 : }
243 : } else {
244 : for(;;) {
245 0 : if(sLength==0) {
246 0 : remainingMatchLength_=length;
247 0 : pos_=pos;
248 : int32_t node;
249 0 : return (length<0 && (node=*pos)>=kMinValueLead) ?
250 0 : valueResult(node) : USTRINGTRIE_NO_VALUE;
251 : }
252 0 : inByte=*s++;
253 0 : --sLength;
254 0 : if(length<0) {
255 0 : remainingMatchLength_=length;
256 0 : break;
257 : }
258 0 : if(inByte!=*pos) {
259 0 : stop();
260 0 : return USTRINGTRIE_NO_MATCH;
261 : }
262 0 : ++pos;
263 0 : --length;
264 0 : }
265 : }
266 : for(;;) {
267 0 : int32_t node=*pos++;
268 0 : if(node<kMinLinearMatch) {
269 0 : UStringTrieResult result=branchNext(pos, node, inByte);
270 0 : if(result==USTRINGTRIE_NO_MATCH) {
271 0 : return USTRINGTRIE_NO_MATCH;
272 : }
273 : // Fetch the next input byte, if there is one.
274 0 : if(sLength<0) {
275 0 : if((inByte=*s++)==0) {
276 0 : return result;
277 : }
278 : } else {
279 0 : if(sLength==0) {
280 0 : return result;
281 : }
282 0 : inByte=*s++;
283 0 : --sLength;
284 : }
285 0 : if(result==USTRINGTRIE_FINAL_VALUE) {
286 : // No further matching bytes.
287 0 : stop();
288 0 : return USTRINGTRIE_NO_MATCH;
289 : }
290 0 : pos=pos_; // branchNext() advanced pos and wrote it to pos_ .
291 0 : } else if(node<kMinValueLead) {
292 : // Match length+1 bytes.
293 0 : length=node-kMinLinearMatch; // Actual match length minus 1.
294 0 : if(inByte!=*pos) {
295 0 : stop();
296 0 : return USTRINGTRIE_NO_MATCH;
297 : }
298 0 : ++pos;
299 0 : --length;
300 0 : break;
301 0 : } else if(node&kValueIsFinal) {
302 : // No further matching bytes.
303 0 : stop();
304 0 : return USTRINGTRIE_NO_MATCH;
305 : } else {
306 : // Skip intermediate value.
307 0 : pos=skipValue(pos, node);
308 : // The next node must not also be a value node.
309 0 : U_ASSERT(*pos<kMinValueLead);
310 : }
311 0 : }
312 0 : }
313 : }
314 :
315 : const uint8_t *
316 0 : BytesTrie::findUniqueValueFromBranch(const uint8_t *pos, int32_t length,
317 : UBool haveUniqueValue, int32_t &uniqueValue) {
318 0 : while(length>kMaxBranchLinearSubNodeLength) {
319 0 : ++pos; // ignore the comparison byte
320 0 : if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) {
321 0 : return NULL;
322 : }
323 0 : length=length-(length>>1);
324 0 : pos=skipDelta(pos);
325 : }
326 0 : do {
327 0 : ++pos; // ignore a comparison byte
328 : // handle its value
329 0 : int32_t node=*pos++;
330 0 : UBool isFinal=(UBool)(node&kValueIsFinal);
331 0 : int32_t value=readValue(pos, node>>1);
332 0 : pos=skipValue(pos, node);
333 0 : if(isFinal) {
334 0 : if(haveUniqueValue) {
335 0 : if(value!=uniqueValue) {
336 0 : return NULL;
337 : }
338 : } else {
339 0 : uniqueValue=value;
340 0 : haveUniqueValue=TRUE;
341 : }
342 : } else {
343 0 : if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) {
344 0 : return NULL;
345 : }
346 0 : haveUniqueValue=TRUE;
347 : }
348 : } while(--length>1);
349 0 : return pos+1; // ignore the last comparison byte
350 : }
351 :
352 : UBool
353 0 : BytesTrie::findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue) {
354 : for(;;) {
355 0 : int32_t node=*pos++;
356 0 : if(node<kMinLinearMatch) {
357 0 : if(node==0) {
358 0 : node=*pos++;
359 : }
360 0 : pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue);
361 0 : if(pos==NULL) {
362 0 : return FALSE;
363 : }
364 0 : haveUniqueValue=TRUE;
365 0 : } else if(node<kMinValueLead) {
366 : // linear-match node
367 0 : pos+=node-kMinLinearMatch+1; // Ignore the match bytes.
368 : } else {
369 0 : UBool isFinal=(UBool)(node&kValueIsFinal);
370 0 : int32_t value=readValue(pos, node>>1);
371 0 : if(haveUniqueValue) {
372 0 : if(value!=uniqueValue) {
373 0 : return FALSE;
374 : }
375 : } else {
376 0 : uniqueValue=value;
377 0 : haveUniqueValue=TRUE;
378 : }
379 0 : if(isFinal) {
380 0 : return TRUE;
381 : }
382 0 : pos=skipValue(pos, node);
383 : }
384 0 : }
385 : }
386 :
387 : int32_t
388 0 : BytesTrie::getNextBytes(ByteSink &out) const {
389 0 : const uint8_t *pos=pos_;
390 0 : if(pos==NULL) {
391 0 : return 0;
392 : }
393 0 : if(remainingMatchLength_>=0) {
394 0 : append(out, *pos); // Next byte of a pending linear-match node.
395 0 : return 1;
396 : }
397 0 : int32_t node=*pos++;
398 0 : if(node>=kMinValueLead) {
399 0 : if(node&kValueIsFinal) {
400 0 : return 0;
401 : } else {
402 0 : pos=skipValue(pos, node);
403 0 : node=*pos++;
404 0 : U_ASSERT(node<kMinValueLead);
405 : }
406 : }
407 0 : if(node<kMinLinearMatch) {
408 0 : if(node==0) {
409 0 : node=*pos++;
410 : }
411 0 : getNextBranchBytes(pos, ++node, out);
412 0 : return node;
413 : } else {
414 : // First byte of the linear-match node.
415 0 : append(out, *pos);
416 0 : return 1;
417 : }
418 : }
419 :
420 : void
421 0 : BytesTrie::getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out) {
422 0 : while(length>kMaxBranchLinearSubNodeLength) {
423 0 : ++pos; // ignore the comparison byte
424 0 : getNextBranchBytes(jumpByDelta(pos), length>>1, out);
425 0 : length=length-(length>>1);
426 0 : pos=skipDelta(pos);
427 : }
428 0 : do {
429 0 : append(out, *pos++);
430 0 : pos=skipValue(pos);
431 : } while(--length>1);
432 0 : append(out, *pos);
433 0 : }
434 :
435 : void
436 0 : BytesTrie::append(ByteSink &out, int c) {
437 0 : char ch=(char)c;
438 0 : out.Append(&ch, 1);
439 0 : }
440 :
441 : U_NAMESPACE_END
|
