Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/unicode/bytestrie.h @ 69:33d812a61356

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