ICU 49.1.1  49.1.1
ucharstrie.h
Go to the documentation of this file.
00001 /*
00002 *******************************************************************************
00003 *   Copyright (C) 2010-2012, International Business Machines
00004 *   Corporation and others.  All Rights Reserved.
00005 *******************************************************************************
00006 *   file name:  ucharstrie.h
00007 *   encoding:   US-ASCII
00008 *   tab size:   8 (not used)
00009 *   indentation:4
00010 *
00011 *   created on: 2010nov14
00012 *   created by: Markus W. Scherer
00013 */
00014 
00015 #ifndef __UCHARSTRIE_H__
00016 #define __UCHARSTRIE_H__
00017 
00024 #include "unicode/utypes.h"
00025 #include "unicode/unistr.h"
00026 #include "unicode/uobject.h"
00027 #include "unicode/ustringtrie.h"
00028 
00029 U_NAMESPACE_BEGIN
00030 
00031 class Appendable;
00032 class UCharsTrieBuilder;
00033 class UVector32;
00034 
00048 class U_COMMON_API UCharsTrie : public UMemory {
00049 public:
00064     UCharsTrie(const UChar *trieUChars)
00065             : ownedArray_(NULL), uchars_(trieUChars),
00066               pos_(uchars_), remainingMatchLength_(-1) {}
00067 
00072     ~UCharsTrie();
00073 
00080     UCharsTrie(const UCharsTrie &other)
00081             : ownedArray_(NULL), uchars_(other.uchars_),
00082               pos_(other.pos_), remainingMatchLength_(other.remainingMatchLength_) {}
00083 
00089     UCharsTrie &reset() {
00090         pos_=uchars_;
00091         remainingMatchLength_=-1;
00092         return *this;
00093     }
00094 
00100     class State : public UMemory {
00101     public:
00106         State() { uchars=NULL; }
00107     private:
00108         friend class UCharsTrie;
00109 
00110         const UChar *uchars;
00111         const UChar *pos;
00112         int32_t remainingMatchLength;
00113     };
00114 
00122     const UCharsTrie &saveState(State &state) const {
00123         state.uchars=uchars_;
00124         state.pos=pos_;
00125         state.remainingMatchLength=remainingMatchLength_;
00126         return *this;
00127     }
00128 
00139     UCharsTrie &resetToState(const State &state) {
00140         if(uchars_==state.uchars && uchars_!=NULL) {
00141             pos_=state.pos;
00142             remainingMatchLength_=state.remainingMatchLength;
00143         }
00144         return *this;
00145     }
00146 
00153     UStringTrieResult current() const;
00154 
00162     inline UStringTrieResult first(int32_t uchar) {
00163         remainingMatchLength_=-1;
00164         return nextImpl(uchars_, uchar);
00165     }
00166 
00175     UStringTrieResult firstForCodePoint(UChar32 cp);
00176 
00183     UStringTrieResult next(int32_t uchar);
00184 
00192     UStringTrieResult nextForCodePoint(UChar32 cp);
00193 
00209     UStringTrieResult next(const UChar *s, int32_t length);
00210 
00220     inline int32_t getValue() const {
00221         const UChar *pos=pos_;
00222         int32_t leadUnit=*pos++;
00223         // U_ASSERT(leadUnit>=kMinValueLead);
00224         return leadUnit&kValueIsFinal ?
00225             readValue(pos, leadUnit&0x7fff) : readNodeValue(pos, leadUnit);
00226     }
00227 
00237     inline UBool hasUniqueValue(int32_t &uniqueValue) const {
00238         const UChar *pos=pos_;
00239         // Skip the rest of a pending linear-match node.
00240         return pos!=NULL && findUniqueValue(pos+remainingMatchLength_+1, FALSE, uniqueValue);
00241     }
00242 
00250     int32_t getNextUChars(Appendable &out) const;
00251 
00256     class U_COMMON_API Iterator : public UMemory {
00257     public:
00269         Iterator(const UChar *trieUChars, int32_t maxStringLength, UErrorCode &errorCode);
00270 
00282         Iterator(const UCharsTrie &trie, int32_t maxStringLength, UErrorCode &errorCode);
00283 
00288         ~Iterator();
00289 
00295         Iterator &reset();
00296 
00301         UBool hasNext() const;
00302 
00317         UBool next(UErrorCode &errorCode);
00318 
00323         const UnicodeString &getString() const { return str_; }
00328         int32_t getValue() const { return value_; }
00329 
00330     private:
00331         UBool truncateAndStop() {
00332             pos_=NULL;
00333             value_=-1;  // no real value for str
00334             return TRUE;
00335         }
00336 
00337         const UChar *branchNext(const UChar *pos, int32_t length, UErrorCode &errorCode);
00338 
00339         const UChar *uchars_;
00340         const UChar *pos_;
00341         const UChar *initialPos_;
00342         int32_t remainingMatchLength_;
00343         int32_t initialRemainingMatchLength_;
00344         UBool skipValue_;  // Skip intermediate value which was already delivered.
00345 
00346         UnicodeString str_;
00347         int32_t maxLength_;
00348         int32_t value_;
00349 
00350         // The stack stores pairs of integers for backtracking to another
00351         // outbound edge of a branch node.
00352         // The first integer is an offset from uchars_.
00353         // The second integer has the str_.length() from before the node in bits 15..0,
00354         // and the remaining branch length in bits 31..16.
00355         // (We could store the remaining branch length minus 1 in bits 30..16 and not use the sign bit,
00356         // but the code looks more confusing that way.)
00357         UVector32 *stack_;
00358     };
00359 
00360 private:
00361     friend class UCharsTrieBuilder;
00362 
00369     UCharsTrie(UChar *adoptUChars, const UChar *trieUChars)
00370             : ownedArray_(adoptUChars), uchars_(trieUChars),
00371               pos_(uchars_), remainingMatchLength_(-1) {}
00372 
00373     // No assignment operator.
00374     UCharsTrie &operator=(const UCharsTrie &other);
00375 
00376     inline void stop() {
00377         pos_=NULL;
00378     }
00379 
00380     // Reads a compact 32-bit integer.
00381     // pos is already after the leadUnit, and the lead unit has bit 15 reset.
00382     static inline int32_t readValue(const UChar *pos, int32_t leadUnit) {
00383         int32_t value;
00384         if(leadUnit<kMinTwoUnitValueLead) {
00385             value=leadUnit;
00386         } else if(leadUnit<kThreeUnitValueLead) {
00387             value=((leadUnit-kMinTwoUnitValueLead)<<16)|*pos;
00388         } else {
00389             value=(pos[0]<<16)|pos[1];
00390         }
00391         return value;
00392     }
00393     static inline const UChar *skipValue(const UChar *pos, int32_t leadUnit) {
00394         if(leadUnit>=kMinTwoUnitValueLead) {
00395             if(leadUnit<kThreeUnitValueLead) {
00396                 ++pos;
00397             } else {
00398                 pos+=2;
00399             }
00400         }
00401         return pos;
00402     }
00403     static inline const UChar *skipValue(const UChar *pos) {
00404         int32_t leadUnit=*pos++;
00405         return skipValue(pos, leadUnit&0x7fff);
00406     }
00407 
00408     static inline int32_t readNodeValue(const UChar *pos, int32_t leadUnit) {
00409         // U_ASSERT(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
00410         int32_t value;
00411         if(leadUnit<kMinTwoUnitNodeValueLead) {
00412             value=(leadUnit>>6)-1;
00413         } else if(leadUnit<kThreeUnitNodeValueLead) {
00414             value=(((leadUnit&0x7fc0)-kMinTwoUnitNodeValueLead)<<10)|*pos;
00415         } else {
00416             value=(pos[0]<<16)|pos[1];
00417         }
00418         return value;
00419     }
00420     static inline const UChar *skipNodeValue(const UChar *pos, int32_t leadUnit) {
00421         // U_ASSERT(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
00422         if(leadUnit>=kMinTwoUnitNodeValueLead) {
00423             if(leadUnit<kThreeUnitNodeValueLead) {
00424                 ++pos;
00425             } else {
00426                 pos+=2;
00427             }
00428         }
00429         return pos;
00430     }
00431 
00432     static inline const UChar *jumpByDelta(const UChar *pos) {
00433         int32_t delta=*pos++;
00434         if(delta>=kMinTwoUnitDeltaLead) {
00435             if(delta==kThreeUnitDeltaLead) {
00436                 delta=(pos[0]<<16)|pos[1];
00437                 pos+=2;
00438             } else {
00439                 delta=((delta-kMinTwoUnitDeltaLead)<<16)|*pos++;
00440             }
00441         }
00442         return pos+delta;
00443     }
00444 
00445     static const UChar *skipDelta(const UChar *pos) {
00446         int32_t delta=*pos++;
00447         if(delta>=kMinTwoUnitDeltaLead) {
00448             if(delta==kThreeUnitDeltaLead) {
00449                 pos+=2;
00450             } else {
00451                 ++pos;
00452             }
00453         }
00454         return pos;
00455     }
00456 
00457     static inline UStringTrieResult valueResult(int32_t node) {
00458         return (UStringTrieResult)(USTRINGTRIE_INTERMEDIATE_VALUE-(node>>15));
00459     }
00460 
00461     // Handles a branch node for both next(uchar) and next(string).
00462     UStringTrieResult branchNext(const UChar *pos, int32_t length, int32_t uchar);
00463 
00464     // Requires remainingLength_<0.
00465     UStringTrieResult nextImpl(const UChar *pos, int32_t uchar);
00466 
00467     // Helper functions for hasUniqueValue().
00468     // Recursively finds a unique value (or whether there is not a unique one)
00469     // from a branch.
00470     static const UChar *findUniqueValueFromBranch(const UChar *pos, int32_t length,
00471                                                   UBool haveUniqueValue, int32_t &uniqueValue);
00472     // Recursively finds a unique value (or whether there is not a unique one)
00473     // starting from a position on a node lead unit.
00474     static UBool findUniqueValue(const UChar *pos, UBool haveUniqueValue, int32_t &uniqueValue);
00475 
00476     // Helper functions for getNextUChars().
00477     // getNextUChars() when pos is on a branch node.
00478     static void getNextBranchUChars(const UChar *pos, int32_t length, Appendable &out);
00479 
00480     // UCharsTrie data structure
00481     //
00482     // The trie consists of a series of UChar-serialized nodes for incremental
00483     // Unicode string/UChar sequence matching. (UChar=16-bit unsigned integer)
00484     // The root node is at the beginning of the trie data.
00485     //
00486     // Types of nodes are distinguished by their node lead unit ranges.
00487     // After each node, except a final-value node, another node follows to
00488     // encode match values or continue matching further units.
00489     //
00490     // Node types:
00491     //  - Final-value node: Stores a 32-bit integer in a compact, variable-length format.
00492     //    The value is for the string/UChar sequence so far.
00493     //  - Match node, optionally with an intermediate value in a different compact format.
00494     //    The value, if present, is for the string/UChar sequence so far.
00495     //
00496     //  Aside from the value, which uses the node lead unit's high bits:
00497     //
00498     //  - Linear-match node: Matches a number of units.
00499     //  - Branch node: Branches to other nodes according to the current input unit.
00500     //    The node unit is the length of the branch (number of units to select from)
00501     //    minus 1. It is followed by a sub-node:
00502     //    - If the length is at most kMaxBranchLinearSubNodeLength, then
00503     //      there are length-1 (key, value) pairs and then one more comparison unit.
00504     //      If one of the key units matches, then the value is either a final value for
00505     //      the string so far, or a "jump" delta to the next node.
00506     //      If the last unit matches, then matching continues with the next node.
00507     //      (Values have the same encoding as final-value nodes.)
00508     //    - If the length is greater than kMaxBranchLinearSubNodeLength, then
00509     //      there is one unit and one "jump" delta.
00510     //      If the input unit is less than the sub-node unit, then "jump" by delta to
00511     //      the next sub-node which will have a length of length/2.
00512     //      (The delta has its own compact encoding.)
00513     //      Otherwise, skip the "jump" delta to the next sub-node
00514     //      which will have a length of length-length/2.
00515 
00516     // Match-node lead unit values, after masking off intermediate-value bits:
00517 
00518     // 0000..002f: Branch node. If node!=0 then the length is node+1, otherwise
00519     // the length is one more than the next unit.
00520 
00521     // For a branch sub-node with at most this many entries, we drop down
00522     // to a linear search.
00523     static const int32_t kMaxBranchLinearSubNodeLength=5;
00524 
00525     // 0030..003f: Linear-match node, match 1..16 units and continue reading the next node.
00526     static const int32_t kMinLinearMatch=0x30;
00527     static const int32_t kMaxLinearMatchLength=0x10;
00528 
00529     // Match-node lead unit bits 14..6 for the optional intermediate value.
00530     // If these bits are 0, then there is no intermediate value.
00531     // Otherwise, see the *NodeValue* constants below.
00532     static const int32_t kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength;  // 0x0040
00533     static const int32_t kNodeTypeMask=kMinValueLead-1;  // 0x003f
00534 
00535     // A final-value node has bit 15 set.
00536     static const int32_t kValueIsFinal=0x8000;
00537 
00538     // Compact value: After testing and masking off bit 15, use the following thresholds.
00539     static const int32_t kMaxOneUnitValue=0x3fff;
00540 
00541     static const int32_t kMinTwoUnitValueLead=kMaxOneUnitValue+1;  // 0x4000
00542     static const int32_t kThreeUnitValueLead=0x7fff;
00543 
00544     static const int32_t kMaxTwoUnitValue=((kThreeUnitValueLead-kMinTwoUnitValueLead)<<16)-1;  // 0x3ffeffff
00545 
00546     // Compact intermediate-value integer, lead unit shared with a branch or linear-match node.
00547     static const int32_t kMaxOneUnitNodeValue=0xff;
00548     static const int32_t kMinTwoUnitNodeValueLead=kMinValueLead+((kMaxOneUnitNodeValue+1)<<6);  // 0x4040
00549     static const int32_t kThreeUnitNodeValueLead=0x7fc0;
00550 
00551     static const int32_t kMaxTwoUnitNodeValue=
00552         ((kThreeUnitNodeValueLead-kMinTwoUnitNodeValueLead)<<10)-1;  // 0xfdffff
00553 
00554     // Compact delta integers.
00555     static const int32_t kMaxOneUnitDelta=0xfbff;
00556     static const int32_t kMinTwoUnitDeltaLead=kMaxOneUnitDelta+1;  // 0xfc00
00557     static const int32_t kThreeUnitDeltaLead=0xffff;
00558 
00559     static const int32_t kMaxTwoUnitDelta=((kThreeUnitDeltaLead-kMinTwoUnitDeltaLead)<<16)-1;  // 0x03feffff
00560 
00561     UChar *ownedArray_;
00562 
00563     // Fixed value referencing the UCharsTrie words.
00564     const UChar *uchars_;
00565 
00566     // Iterator variables.
00567 
00568     // Pointer to next trie unit to read. NULL if no more matches.
00569     const UChar *pos_;
00570     // Remaining length of a linear-match node, minus 1. Negative if not in such a node.
00571     int32_t remainingMatchLength_;
00572 };
00573 
00574 U_NAMESPACE_END
00575 
00576 #endif  // __UCHARSTRIE_H__