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: bytestrie.h |
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 | #ifndef __BYTESTRIE_H__ |
18 | #define __BYTESTRIE_H__ |
19 | |
20 | /** |
21 | * \file |
22 | * \brief C++ API: Trie for mapping byte sequences to integer values. |
23 | */ |
24 | |
25 | #include "unicode/utypes.h" |
26 | |
27 | #if U_SHOW_CPLUSPLUS_API |
28 | |
29 | #include "unicode/stringpiece.h" |
30 | #include "unicode/uobject.h" |
31 | #include "unicode/ustringtrie.h" |
32 | |
33 | class BytesTrieTest; |
34 | |
35 | U_NAMESPACE_BEGIN |
36 | |
37 | class ByteSink; |
38 | class BytesTrieBuilder; |
39 | class CharString; |
40 | class UVector32; |
41 | |
42 | /** |
43 | * Light-weight, non-const reader class for a BytesTrie. |
44 | * Traverses a byte-serialized data structure with minimal state, |
45 | * for mapping byte sequences to non-negative integer values. |
46 | * |
47 | * This class owns the serialized trie data only if it was constructed by |
48 | * the builder's build() method. |
49 | * The public constructor and the copy constructor only alias the data (only copy the pointer). |
50 | * There is no assignment operator. |
51 | * |
52 | * This class is not intended for public subclassing. |
53 | * @stable ICU 4.8 |
54 | */ |
55 | class U_COMMON_API BytesTrie : public UMemory { |
56 | public: |
57 | /** |
58 | * Constructs a BytesTrie reader instance. |
59 | * |
60 | * The trieBytes must contain a copy of a byte sequence from the BytesTrieBuilder, |
61 | * starting with the first byte of that sequence. |
62 | * The BytesTrie object will not read more bytes than |
63 | * the BytesTrieBuilder generated in the corresponding build() call. |
64 | * |
65 | * The array is not copied/cloned and must not be modified while |
66 | * the BytesTrie object is in use. |
67 | * |
68 | * @param trieBytes The byte array that contains the serialized trie. |
69 | * @stable ICU 4.8 |
70 | */ |
71 | BytesTrie(const void *trieBytes) |
72 | : ownedArray_(nullptr), bytes_(static_cast<const uint8_t *>(trieBytes)), |
73 | pos_(bytes_), remainingMatchLength_(-1) {} |
74 | |
75 | /** |
76 | * Destructor. |
77 | * @stable ICU 4.8 |
78 | */ |
79 | ~BytesTrie(); |
80 | |
81 | /** |
82 | * Copy constructor, copies the other trie reader object and its state, |
83 | * but not the byte array which will be shared. (Shallow copy.) |
84 | * @param other Another BytesTrie object. |
85 | * @stable ICU 4.8 |
86 | */ |
87 | BytesTrie(const BytesTrie &other) |
88 | : ownedArray_(nullptr), bytes_(other.bytes_), |
89 | pos_(other.pos_), remainingMatchLength_(other.remainingMatchLength_) {} |
90 | |
91 | /** |
92 | * Resets this trie to its initial state. |
93 | * @return *this |
94 | * @stable ICU 4.8 |
95 | */ |
96 | BytesTrie &reset() { |
97 | pos_=bytes_; |
98 | remainingMatchLength_=-1; |
99 | return *this; |
100 | } |
101 | |
102 | /** |
103 | * Returns the state of this trie as a 64-bit integer. |
104 | * The state value is never 0. |
105 | * |
106 | * @return opaque state value |
107 | * @see resetToState64 |
108 | * @stable ICU 65 |
109 | */ |
110 | uint64_t getState64() const { |
111 | return (static_cast<uint64_t>(remainingMatchLength_ + 2) << kState64RemainingShift) | |
112 | (uint64_t)(pos_ - bytes_); |
113 | } |
114 | |
115 | /** |
116 | * Resets this trie to the saved state. |
117 | * Unlike resetToState(State), the 64-bit state value |
118 | * must be from getState64() from the same trie object or |
119 | * from one initialized the exact same way. |
120 | * Because of no validation, this method is faster. |
121 | * |
122 | * @param state The opaque trie state value from getState64(). |
123 | * @return *this |
124 | * @see getState64 |
125 | * @see resetToState |
126 | * @see reset |
127 | * @stable ICU 65 |
128 | */ |
129 | BytesTrie &resetToState64(uint64_t state) { |
130 | remainingMatchLength_ = static_cast<int32_t>(state >> kState64RemainingShift) - 2; |
131 | pos_ = bytes_ + (state & kState64PosMask); |
132 | return *this; |
133 | } |
134 | |
135 | /** |
136 | * BytesTrie state object, for saving a trie's current state |
137 | * and resetting the trie back to this state later. |
138 | * @stable ICU 4.8 |
139 | */ |
140 | class State : public UMemory { |
141 | public: |
142 | /** |
143 | * Constructs an empty State. |
144 | * @stable ICU 4.8 |
145 | */ |
146 | State() { bytes=nullptr; } |
147 | private: |
148 | friend class BytesTrie; |
149 | |
150 | const uint8_t *bytes; |
151 | const uint8_t *pos; |
152 | int32_t remainingMatchLength; |
153 | }; |
154 | |
155 | /** |
156 | * Saves the state of this trie. |
157 | * @param state The State object to hold the trie's state. |
158 | * @return *this |
159 | * @see resetToState |
160 | * @stable ICU 4.8 |
161 | */ |
162 | const BytesTrie &saveState(State &state) const { |
163 | state.bytes=bytes_; |
164 | state.pos=pos_; |
165 | state.remainingMatchLength=remainingMatchLength_; |
166 | return *this; |
167 | } |
168 | |
169 | /** |
170 | * Resets this trie to the saved state. |
171 | * If the state object contains no state, or the state of a different trie, |
172 | * then this trie remains unchanged. |
173 | * @param state The State object which holds a saved trie state. |
174 | * @return *this |
175 | * @see saveState |
176 | * @see reset |
177 | * @stable ICU 4.8 |
178 | */ |
179 | BytesTrie &resetToState(const State &state) { |
180 | if(bytes_==state.bytes && bytes_!=nullptr) { |
181 | pos_=state.pos; |
182 | remainingMatchLength_=state.remainingMatchLength; |
183 | } |
184 | return *this; |
185 | } |
186 | |
187 | /** |
188 | * Determines whether the byte sequence so far matches, whether it has a value, |
189 | * and whether another input byte can continue a matching byte sequence. |
190 | * @return The match/value Result. |
191 | * @stable ICU 4.8 |
192 | */ |
193 | UStringTrieResult current() const; |
194 | |
195 | /** |
196 | * Traverses the trie from the initial state for this input byte. |
197 | * Equivalent to reset().next(inByte). |
198 | * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff. |
199 | * Values below -0x100 and above 0xff will never match. |
200 | * @return The match/value Result. |
201 | * @stable ICU 4.8 |
202 | */ |
203 | inline UStringTrieResult first(int32_t inByte) { |
204 | remainingMatchLength_=-1; |
205 | if(inByte<0) { |
206 | inByte+=0x100; |
207 | } |
208 | return nextImpl(bytes_, inByte); |
209 | } |
210 | |
211 | /** |
212 | * Traverses the trie from the current state for this input byte. |
213 | * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff. |
214 | * Values below -0x100 and above 0xff will never match. |
215 | * @return The match/value Result. |
216 | * @stable ICU 4.8 |
217 | */ |
218 | UStringTrieResult next(int32_t inByte); |
219 | |
220 | /** |
221 | * Traverses the trie from the current state for this byte sequence. |
222 | * Equivalent to |
223 | * \code |
224 | * Result result=current(); |
225 | * for(each c in s) |
226 | * if(!USTRINGTRIE_HAS_NEXT(result)) return USTRINGTRIE_NO_MATCH; |
227 | * result=next(c); |
228 | * return result; |
229 | * \endcode |
230 | * @param s A string or byte sequence. Can be nullptr if length is 0. |
231 | * @param length The length of the byte sequence. Can be -1 if NUL-terminated. |
232 | * @return The match/value Result. |
233 | * @stable ICU 4.8 |
234 | */ |
235 | UStringTrieResult next(const char *s, int32_t length); |
236 | |
237 | /** |
238 | * Returns a matching byte sequence's value if called immediately after |
239 | * current()/first()/next() returned USTRINGTRIE_INTERMEDIATE_VALUE or USTRINGTRIE_FINAL_VALUE. |
240 | * getValue() can be called multiple times. |
241 | * |
242 | * Do not call getValue() after USTRINGTRIE_NO_MATCH or USTRINGTRIE_NO_VALUE! |
243 | * @return The value for the byte sequence so far. |
244 | * @stable ICU 4.8 |
245 | */ |
246 | inline int32_t getValue() const { |
247 | const uint8_t *pos=pos_; |
248 | int32_t leadByte=*pos++; |
249 | // U_ASSERT(leadByte>=kMinValueLead); |
250 | return readValue(pos, leadByte>>1); |
251 | } |
252 | |
253 | /** |
254 | * Determines whether all byte sequences reachable from the current state |
255 | * map to the same value. |
256 | * @param uniqueValue Receives the unique value, if this function returns true. |
257 | * (output-only) |
258 | * @return true if all byte sequences reachable from the current state |
259 | * map to the same value. |
260 | * @stable ICU 4.8 |
261 | */ |
262 | inline UBool hasUniqueValue(int32_t &uniqueValue) const { |
263 | const uint8_t *pos=pos_; |
264 | // Skip the rest of a pending linear-match node. |
265 | return pos!=nullptr && findUniqueValue(pos+remainingMatchLength_+1, false, uniqueValue); |
266 | } |
267 | |
268 | /** |
269 | * Finds each byte which continues the byte sequence from the current state. |
270 | * That is, each byte b for which it would be next(b)!=USTRINGTRIE_NO_MATCH now. |
271 | * @param out Each next byte is appended to this object. |
272 | * (Only uses the out.Append(s, length) method.) |
273 | * @return the number of bytes which continue the byte sequence from here |
274 | * @stable ICU 4.8 |
275 | */ |
276 | int32_t getNextBytes(ByteSink &out) const; |
277 | |
278 | /** |
279 | * Iterator for all of the (byte sequence, value) pairs in a BytesTrie. |
280 | * @stable ICU 4.8 |
281 | */ |
282 | class U_COMMON_API Iterator : public UMemory { |
283 | public: |
284 | /** |
285 | * Iterates from the root of a byte-serialized BytesTrie. |
286 | * @param trieBytes The trie bytes. |
287 | * @param maxStringLength If 0, the iterator returns full strings/byte sequences. |
288 | * Otherwise, the iterator returns strings with this maximum length. |
289 | * @param errorCode Standard ICU error code. Its input value must |
290 | * pass the U_SUCCESS() test, or else the function returns |
291 | * immediately. Check for U_FAILURE() on output or use with |
292 | * function chaining. (See User Guide for details.) |
293 | * @stable ICU 4.8 |
294 | */ |
295 | Iterator(const void *trieBytes, int32_t maxStringLength, UErrorCode &errorCode); |
296 | |
297 | /** |
298 | * Iterates from the current state of the specified BytesTrie. |
299 | * @param trie The trie whose state will be copied for iteration. |
300 | * @param maxStringLength If 0, the iterator returns full strings/byte sequences. |
301 | * Otherwise, the iterator returns strings with this maximum length. |
302 | * @param errorCode Standard ICU error code. Its input value must |
303 | * pass the U_SUCCESS() test, or else the function returns |
304 | * immediately. Check for U_FAILURE() on output or use with |
305 | * function chaining. (See User Guide for details.) |
306 | * @stable ICU 4.8 |
307 | */ |
308 | Iterator(const BytesTrie &trie, int32_t maxStringLength, UErrorCode &errorCode); |
309 | |
310 | /** |
311 | * Destructor. |
312 | * @stable ICU 4.8 |
313 | */ |
314 | ~Iterator(); |
315 | |
316 | /** |
317 | * Resets this iterator to its initial state. |
318 | * @return *this |
319 | * @stable ICU 4.8 |
320 | */ |
321 | Iterator &reset(); |
322 | |
323 | /** |
324 | * @return true if there are more elements. |
325 | * @stable ICU 4.8 |
326 | */ |
327 | UBool hasNext() const; |
328 | |
329 | /** |
330 | * Finds the next (byte sequence, value) pair if there is one. |
331 | * |
332 | * If the byte sequence is truncated to the maximum length and does not |
333 | * have a real value, then the value is set to -1. |
334 | * In this case, this "not a real value" is indistinguishable from |
335 | * a real value of -1. |
336 | * @param errorCode Standard ICU error code. Its input value must |
337 | * pass the U_SUCCESS() test, or else the function returns |
338 | * immediately. Check for U_FAILURE() on output or use with |
339 | * function chaining. (See User Guide for details.) |
340 | * @return true if there is another element. |
341 | * @stable ICU 4.8 |
342 | */ |
343 | UBool next(UErrorCode &errorCode); |
344 | |
345 | /** |
346 | * @return The NUL-terminated byte sequence for the last successful next(). |
347 | * @stable ICU 4.8 |
348 | */ |
349 | StringPiece getString() const; |
350 | /** |
351 | * @return The value for the last successful next(). |
352 | * @stable ICU 4.8 |
353 | */ |
354 | int32_t getValue() const { return value_; } |
355 | |
356 | private: |
357 | UBool truncateAndStop(); |
358 | |
359 | const uint8_t *branchNext(const uint8_t *pos, int32_t length, UErrorCode &errorCode); |
360 | |
361 | const uint8_t *bytes_; |
362 | const uint8_t *pos_; |
363 | const uint8_t *initialPos_; |
364 | int32_t remainingMatchLength_; |
365 | int32_t initialRemainingMatchLength_; |
366 | |
367 | CharString *str_; |
368 | int32_t maxLength_; |
369 | int32_t value_; |
370 | |
371 | // The stack stores pairs of integers for backtracking to another |
372 | // outbound edge of a branch node. |
373 | // The first integer is an offset from bytes_. |
374 | // The second integer has the str_->length() from before the node in bits 15..0, |
375 | // and the remaining branch length in bits 24..16. (Bits 31..25 are unused.) |
376 | // (We could store the remaining branch length minus 1 in bits 23..16 and not use bits 31..24, |
377 | // but the code looks more confusing that way.) |
378 | UVector32 *stack_; |
379 | }; |
380 | |
381 | private: |
382 | friend class BytesTrieBuilder; |
383 | friend class ::BytesTrieTest; |
384 | |
385 | /** |
386 | * Constructs a BytesTrie reader instance. |
387 | * Unlike the public constructor which just aliases an array, |
388 | * this constructor adopts the builder's array. |
389 | * This constructor is only called by the builder. |
390 | */ |
391 | BytesTrie(void *adoptBytes, const void *trieBytes) |
392 | : ownedArray_(static_cast<uint8_t *>(adoptBytes)), |
393 | bytes_(static_cast<const uint8_t *>(trieBytes)), |
394 | pos_(bytes_), remainingMatchLength_(-1) {} |
395 | |
396 | // No assignment operator. |
397 | BytesTrie &operator=(const BytesTrie &other) = delete; |
398 | |
399 | inline void stop() { |
400 | pos_=nullptr; |
401 | } |
402 | |
403 | // Reads a compact 32-bit integer. |
404 | // pos is already after the leadByte, and the lead byte is already shifted right by 1. |
405 | static int32_t readValue(const uint8_t *pos, int32_t leadByte); |
406 | static inline const uint8_t *skipValue(const uint8_t *pos, int32_t leadByte) { |
407 | // U_ASSERT(leadByte>=kMinValueLead); |
408 | if(leadByte>=(kMinTwoByteValueLead<<1)) { |
409 | if(leadByte<(kMinThreeByteValueLead<<1)) { |
410 | ++pos; |
411 | } else if(leadByte<(kFourByteValueLead<<1)) { |
412 | pos+=2; |
413 | } else { |
414 | pos+=3+((leadByte>>1)&1); |
415 | } |
416 | } |
417 | return pos; |
418 | } |
419 | static inline const uint8_t *skipValue(const uint8_t *pos) { |
420 | int32_t leadByte=*pos++; |
421 | return skipValue(pos, leadByte); |
422 | } |
423 | |
424 | // Reads a jump delta and jumps. |
425 | static const uint8_t *jumpByDelta(const uint8_t *pos); |
426 | |
427 | static inline const uint8_t *skipDelta(const uint8_t *pos) { |
428 | int32_t delta=*pos++; |
429 | if(delta>=kMinTwoByteDeltaLead) { |
430 | if(delta<kMinThreeByteDeltaLead) { |
431 | ++pos; |
432 | } else if(delta<kFourByteDeltaLead) { |
433 | pos+=2; |
434 | } else { |
435 | pos+=3+(delta&1); |
436 | } |
437 | } |
438 | return pos; |
439 | } |
440 | |
441 | static inline UStringTrieResult valueResult(int32_t node) { |
442 | return (UStringTrieResult)(USTRINGTRIE_INTERMEDIATE_VALUE-(node&kValueIsFinal)); |
443 | } |
444 | |
445 | // Handles a branch node for both next(byte) and next(string). |
446 | UStringTrieResult branchNext(const uint8_t *pos, int32_t length, int32_t inByte); |
447 | |
448 | // Requires remainingLength_<0. |
449 | UStringTrieResult nextImpl(const uint8_t *pos, int32_t inByte); |
450 | |
451 | // Helper functions for hasUniqueValue(). |
452 | // Recursively finds a unique value (or whether there is not a unique one) |
453 | // from a branch. |
454 | static const uint8_t *findUniqueValueFromBranch(const uint8_t *pos, int32_t length, |
455 | UBool haveUniqueValue, int32_t &uniqueValue); |
456 | // Recursively finds a unique value (or whether there is not a unique one) |
457 | // starting from a position on a node lead byte. |
458 | static UBool findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue); |
459 | |
460 | // Helper functions for getNextBytes(). |
461 | // getNextBytes() when pos is on a branch node. |
462 | static void getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out); |
463 | static void append(ByteSink &out, int c); |
464 | |
465 | // BytesTrie data structure |
466 | // |
467 | // The trie consists of a series of byte-serialized nodes for incremental |
468 | // string/byte sequence matching. The root node is at the beginning of the trie data. |
469 | // |
470 | // Types of nodes are distinguished by their node lead byte ranges. |
471 | // After each node, except a final-value node, another node follows to |
472 | // encode match values or continue matching further bytes. |
473 | // |
474 | // Node types: |
475 | // - Value node: Stores a 32-bit integer in a compact, variable-length format. |
476 | // The value is for the string/byte sequence so far. |
477 | // One node bit indicates whether the value is final or whether |
478 | // matching continues with the next node. |
479 | // - Linear-match node: Matches a number of bytes. |
480 | // - Branch node: Branches to other nodes according to the current input byte. |
481 | // The node byte is the length of the branch (number of bytes to select from) |
482 | // minus 1. It is followed by a sub-node: |
483 | // - If the length is at most kMaxBranchLinearSubNodeLength, then |
484 | // there are length-1 (key, value) pairs and then one more comparison byte. |
485 | // If one of the key bytes matches, then the value is either a final value for |
486 | // the string/byte sequence so far, or a "jump" delta to the next node. |
487 | // If the last byte matches, then matching continues with the next node. |
488 | // (Values have the same encoding as value nodes.) |
489 | // - If the length is greater than kMaxBranchLinearSubNodeLength, then |
490 | // there is one byte and one "jump" delta. |
491 | // If the input byte is less than the sub-node byte, then "jump" by delta to |
492 | // the next sub-node which will have a length of length/2. |
493 | // (The delta has its own compact encoding.) |
494 | // Otherwise, skip the "jump" delta to the next sub-node |
495 | // which will have a length of length-length/2. |
496 | |
497 | // Node lead byte values. |
498 | |
499 | // 00..0f: Branch node. If node!=0 then the length is node+1, otherwise |
500 | // the length is one more than the next byte. |
501 | |
502 | // For a branch sub-node with at most this many entries, we drop down |
503 | // to a linear search. |
504 | static const int32_t kMaxBranchLinearSubNodeLength=5; |
505 | |
506 | // 10..1f: Linear-match node, match 1..16 bytes and continue reading the next node. |
507 | static const int32_t kMinLinearMatch=0x10; |
508 | static const int32_t kMaxLinearMatchLength=0x10; |
509 | |
510 | // 20..ff: Variable-length value node. |
511 | // If odd, the value is final. (Otherwise, intermediate value or jump delta.) |
512 | // Then shift-right by 1 bit. |
513 | // The remaining lead byte value indicates the number of following bytes (0..4) |
514 | // and contains the value's top bits. |
515 | static const int32_t kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength; // 0x20 |
516 | // It is a final value if bit 0 is set. |
517 | static const int32_t kValueIsFinal=1; |
518 | |
519 | // Compact value: After testing bit 0, shift right by 1 and then use the following thresholds. |
520 | static const int32_t kMinOneByteValueLead=kMinValueLead/2; // 0x10 |
521 | static const int32_t kMaxOneByteValue=0x40; // At least 6 bits in the first byte. |
522 | |
523 | static const int32_t kMinTwoByteValueLead=kMinOneByteValueLead+kMaxOneByteValue+1; // 0x51 |
524 | static const int32_t kMaxTwoByteValue=0x1aff; |
525 | |
526 | static const int32_t kMinThreeByteValueLead=kMinTwoByteValueLead+(kMaxTwoByteValue>>8)+1; // 0x6c |
527 | static const int32_t kFourByteValueLead=0x7e; |
528 | |
529 | // A little more than Unicode code points. (0x11ffff) |
530 | static const int32_t kMaxThreeByteValue=((kFourByteValueLead-kMinThreeByteValueLead)<<16)-1; |
531 | |
532 | static const int32_t kFiveByteValueLead=0x7f; |
533 | |
534 | // Compact delta integers. |
535 | static const int32_t kMaxOneByteDelta=0xbf; |
536 | static const int32_t kMinTwoByteDeltaLead=kMaxOneByteDelta+1; // 0xc0 |
537 | static const int32_t kMinThreeByteDeltaLead=0xf0; |
538 | static const int32_t kFourByteDeltaLead=0xfe; |
539 | static const int32_t kFiveByteDeltaLead=0xff; |
540 | |
541 | static const int32_t kMaxTwoByteDelta=((kMinThreeByteDeltaLead-kMinTwoByteDeltaLead)<<8)-1; // 0x2fff |
542 | static const int32_t kMaxThreeByteDelta=((kFourByteDeltaLead-kMinThreeByteDeltaLead)<<16)-1; // 0xdffff |
543 | |
544 | // For getState64(): |
545 | // The remainingMatchLength_ is -1..14=(kMaxLinearMatchLength=0x10)-2 |
546 | // so we need at least 5 bits for that. |
547 | // We add 2 to store it as a positive value 1..16=kMaxLinearMatchLength. |
548 | static constexpr int32_t kState64RemainingShift = 59; |
549 | static constexpr uint64_t kState64PosMask = (UINT64_C(1) << kState64RemainingShift) - 1; |
550 | |
551 | uint8_t *ownedArray_; |
552 | |
553 | // Fixed value referencing the BytesTrie bytes. |
554 | const uint8_t *bytes_; |
555 | |
556 | // Iterator variables. |
557 | |
558 | // Pointer to next trie byte to read. nullptr if no more matches. |
559 | const uint8_t *pos_; |
560 | // Remaining length of a linear-match node, minus 1. Negative if not in such a node. |
561 | int32_t remainingMatchLength_; |
562 | }; |
563 | |
564 | U_NAMESPACE_END |
565 | |
566 | #endif /* U_SHOW_CPLUSPLUS_API */ |
567 | |
568 | #endif // __BYTESTRIE_H__ |
569 | |