icuSources/common/unicode/bytestrie.h

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