ICU 4.8.1.1  4.8.1.1
ucharstrie.h
Go to the documentation of this file.
00001 /*
00002 *******************************************************************************
00003 *   Copyright (C) 2010-2011, 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     inline UStringTrieResult firstForCodePoint(UChar32 cp) {
00176         return cp<=0xffff ?
00177             first(cp) :
00178             (USTRINGTRIE_HAS_NEXT(first(U16_LEAD(cp))) ?
00179                 next(U16_TRAIL(cp)) :
00180                 USTRINGTRIE_NO_MATCH);
00181     }
00182 
00189     UStringTrieResult next(int32_t uchar);
00190 
00198     inline UStringTrieResult nextForCodePoint(UChar32 cp) {
00199         return cp<=0xffff ?
00200             next(cp) :
00201             (USTRINGTRIE_HAS_NEXT(next(U16_LEAD(cp))) ?
00202                 next(U16_TRAIL(cp)) :
00203                 USTRINGTRIE_NO_MATCH);
00204     }
00205 
00221     UStringTrieResult next(const UChar *s, int32_t length);
00222 
00232     inline int32_t getValue() const {
00233         const UChar *pos=pos_;
00234         int32_t leadUnit=*pos++;
00235         // U_ASSERT(leadUnit>=kMinValueLead);
00236         return leadUnit&kValueIsFinal ?
00237             readValue(pos, leadUnit&0x7fff) : readNodeValue(pos, leadUnit);
00238     }
00239 
00249     inline UBool hasUniqueValue(int32_t &uniqueValue) const {
00250         const UChar *pos=pos_;
00251         // Skip the rest of a pending linear-match node.
00252         return pos!=NULL && findUniqueValue(pos+remainingMatchLength_+1, FALSE, uniqueValue);
00253     }
00254 
00262     int32_t getNextUChars(Appendable &out) const;
00263 
00268     class U_COMMON_API Iterator : public UMemory {
00269     public:
00281         Iterator(const UChar *trieUChars, int32_t maxStringLength, UErrorCode &errorCode);
00282 
00294         Iterator(const UCharsTrie &trie, int32_t maxStringLength, UErrorCode &errorCode);
00295 
00300         ~Iterator();
00301 
00307         Iterator &reset();
00308 
00313         UBool hasNext() const;
00314 
00329         UBool next(UErrorCode &errorCode);
00330 
00335         const UnicodeString &getString() const { return str_; }
00340         int32_t getValue() const { return value_; }
00341 
00342     private:
00343         UBool truncateAndStop() {
00344             pos_=NULL;
00345             value_=-1;  // no real value for str
00346             return TRUE;
00347         }
00348 
00349         const UChar *branchNext(const UChar *pos, int32_t length, UErrorCode &errorCode);
00350 
00351         const UChar *uchars_;
00352         const UChar *pos_;
00353         const UChar *initialPos_;
00354         int32_t remainingMatchLength_;
00355         int32_t initialRemainingMatchLength_;
00356         UBool skipValue_;  // Skip intermediate value which was already delivered.
00357 
00358         UnicodeString str_;
00359         int32_t maxLength_;
00360         int32_t value_;
00361 
00362         // The stack stores pairs of integers for backtracking to another
00363         // outbound edge of a branch node.
00364         // The first integer is an offset from uchars_.
00365         // The second integer has the str_.length() from before the node in bits 15..0,
00366         // and the remaining branch length in bits 31..16.
00367         // (We could store the remaining branch length minus 1 in bits 30..16 and not use the sign bit,
00368         // but the code looks more confusing that way.)
00369         UVector32 *stack_;
00370     };
00371 
00372 private:
00373     friend class UCharsTrieBuilder;
00374 
00381     UCharsTrie(UChar *adoptUChars, const UChar *trieUChars)
00382             : ownedArray_(adoptUChars), uchars_(trieUChars),
00383               pos_(uchars_), remainingMatchLength_(-1) {}
00384 
00385     // No assignment operator.
00386     UCharsTrie &operator=(const UCharsTrie &other);
00387 
00388     inline void stop() {
00389         pos_=NULL;
00390     }
00391 
00392     // Reads a compact 32-bit integer.
00393     // pos is already after the leadUnit, and the lead unit has bit 15 reset.
00394     static inline int32_t readValue(const UChar *pos, int32_t leadUnit) {
00395         int32_t value;
00396         if(leadUnit<kMinTwoUnitValueLead) {
00397             value=leadUnit;
00398         } else if(leadUnit<kThreeUnitValueLead) {
00399             value=((leadUnit-kMinTwoUnitValueLead)<<16)|*pos;
00400         } else {
00401             value=(pos[0]<<16)|pos[1];
00402         }
00403         return value;
00404     }
00405     static inline const UChar *skipValue(const UChar *pos, int32_t leadUnit) {
00406         if(leadUnit>=kMinTwoUnitValueLead) {
00407             if(leadUnit<kThreeUnitValueLead) {
00408                 ++pos;
00409             } else {
00410                 pos+=2;
00411             }
00412         }
00413         return pos;
00414     }
00415     static inline const UChar *skipValue(const UChar *pos) {
00416         int32_t leadUnit=*pos++;
00417         return skipValue(pos, leadUnit&0x7fff);
00418     }
00419 
00420     static inline int32_t readNodeValue(const UChar *pos, int32_t leadUnit) {
00421         // U_ASSERT(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
00422         int32_t value;
00423         if(leadUnit<kMinTwoUnitNodeValueLead) {
00424             value=(leadUnit>>6)-1;
00425         } else if(leadUnit<kThreeUnitNodeValueLead) {
00426             value=(((leadUnit&0x7fc0)-kMinTwoUnitNodeValueLead)<<10)|*pos;
00427         } else {
00428             value=(pos[0]<<16)|pos[1];
00429         }
00430         return value;
00431     }
00432     static inline const UChar *skipNodeValue(const UChar *pos, int32_t leadUnit) {
00433         // U_ASSERT(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
00434         if(leadUnit>=kMinTwoUnitNodeValueLead) {
00435             if(leadUnit<kThreeUnitNodeValueLead) {
00436                 ++pos;
00437             } else {
00438                 pos+=2;
00439             }
00440         }
00441         return pos;
00442     }
00443 
00444     static inline const UChar *jumpByDelta(const UChar *pos) {
00445         int32_t delta=*pos++;
00446         if(delta>=kMinTwoUnitDeltaLead) {
00447             if(delta==kThreeUnitDeltaLead) {
00448                 delta=(pos[0]<<16)|pos[1];
00449                 pos+=2;
00450             } else {
00451                 delta=((delta-kMinTwoUnitDeltaLead)<<16)|*pos++;
00452             }
00453         }
00454         return pos+delta;
00455     }
00456 
00457     static const UChar *skipDelta(const UChar *pos) {
00458         int32_t delta=*pos++;
00459         if(delta>=kMinTwoUnitDeltaLead) {
00460             if(delta==kThreeUnitDeltaLead) {
00461                 pos+=2;
00462             } else {
00463                 ++pos;
00464             }
00465         }
00466         return pos;
00467     }
00468 
00469     static inline UStringTrieResult valueResult(int32_t node) {
00470         return (UStringTrieResult)(USTRINGTRIE_INTERMEDIATE_VALUE-(node>>15));
00471     }
00472 
00473     // Handles a branch node for both next(uchar) and next(string).
00474     UStringTrieResult branchNext(const UChar *pos, int32_t length, int32_t uchar);
00475 
00476     // Requires remainingLength_<0.
00477     UStringTrieResult nextImpl(const UChar *pos, int32_t uchar);
00478 
00479     // Helper functions for hasUniqueValue().
00480     // Recursively finds a unique value (or whether there is not a unique one)
00481     // from a branch.
00482     static const UChar *findUniqueValueFromBranch(const UChar *pos, int32_t length,
00483                                                   UBool haveUniqueValue, int32_t &uniqueValue);
00484     // Recursively finds a unique value (or whether there is not a unique one)
00485     // starting from a position on a node lead unit.
00486     static UBool findUniqueValue(const UChar *pos, UBool haveUniqueValue, int32_t &uniqueValue);
00487 
00488     // Helper functions for getNextUChars().
00489     // getNextUChars() when pos is on a branch node.
00490     static void getNextBranchUChars(const UChar *pos, int32_t length, Appendable &out);
00491 
00492     // UCharsTrie data structure
00493     //
00494     // The trie consists of a series of UChar-serialized nodes for incremental
00495     // Unicode string/UChar sequence matching. (UChar=16-bit unsigned integer)
00496     // The root node is at the beginning of the trie data.
00497     //
00498     // Types of nodes are distinguished by their node lead unit ranges.
00499     // After each node, except a final-value node, another node follows to
00500     // encode match values or continue matching further units.
00501     //
00502     // Node types:
00503     //  - Final-value node: Stores a 32-bit integer in a compact, variable-length format.
00504     //    The value is for the string/UChar sequence so far.
00505     //  - Match node, optionally with an intermediate value in a different compact format.
00506     //    The value, if present, is for the string/UChar sequence so far.
00507     //
00508     //  Aside from the value, which uses the node lead unit's high bits:
00509     //
00510     //  - Linear-match node: Matches a number of units.
00511     //  - Branch node: Branches to other nodes according to the current input unit.
00512     //    The node unit is the length of the branch (number of units to select from)
00513     //    minus 1. It is followed by a sub-node:
00514     //    - If the length is at most kMaxBranchLinearSubNodeLength, then
00515     //      there are length-1 (key, value) pairs and then one more comparison unit.
00516     //      If one of the key units matches, then the value is either a final value for
00517     //      the string so far, or a "jump" delta to the next node.
00518     //      If the last unit matches, then matching continues with the next node.
00519     //      (Values have the same encoding as final-value nodes.)
00520     //    - If the length is greater than kMaxBranchLinearSubNodeLength, then
00521     //      there is one unit and one "jump" delta.
00522     //      If the input unit is less than the sub-node unit, then "jump" by delta to
00523     //      the next sub-node which will have a length of length/2.
00524     //      (The delta has its own compact encoding.)
00525     //      Otherwise, skip the "jump" delta to the next sub-node
00526     //      which will have a length of length-length/2.
00527 
00528     // Match-node lead unit values, after masking off intermediate-value bits:
00529 
00530     // 0000..002f: Branch node. If node!=0 then the length is node+1, otherwise
00531     // the length is one more than the next unit.
00532 
00533     // For a branch sub-node with at most this many entries, we drop down
00534     // to a linear search.
00535     static const int32_t kMaxBranchLinearSubNodeLength=5;
00536 
00537     // 0030..003f: Linear-match node, match 1..16 units and continue reading the next node.
00538     static const int32_t kMinLinearMatch=0x30;
00539     static const int32_t kMaxLinearMatchLength=0x10;
00540 
00541     // Match-node lead unit bits 14..6 for the optional intermediate value.
00542     // If these bits are 0, then there is no intermediate value.
00543     // Otherwise, see the *NodeValue* constants below.
00544     static const int32_t kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength;  // 0x0040
00545     static const int32_t kNodeTypeMask=kMinValueLead-1;  // 0x003f
00546 
00547     // A final-value node has bit 15 set.
00548     static const int32_t kValueIsFinal=0x8000;
00549 
00550     // Compact value: After testing and masking off bit 15, use the following thresholds.
00551     static const int32_t kMaxOneUnitValue=0x3fff;
00552 
00553     static const int32_t kMinTwoUnitValueLead=kMaxOneUnitValue+1;  // 0x4000
00554     static const int32_t kThreeUnitValueLead=0x7fff;
00555 
00556     static const int32_t kMaxTwoUnitValue=((kThreeUnitValueLead-kMinTwoUnitValueLead)<<16)-1;  // 0x3ffeffff
00557 
00558     // Compact intermediate-value integer, lead unit shared with a branch or linear-match node.
00559     static const int32_t kMaxOneUnitNodeValue=0xff;
00560     static const int32_t kMinTwoUnitNodeValueLead=kMinValueLead+((kMaxOneUnitNodeValue+1)<<6);  // 0x4040
00561     static const int32_t kThreeUnitNodeValueLead=0x7fc0;
00562 
00563     static const int32_t kMaxTwoUnitNodeValue=
00564         ((kThreeUnitNodeValueLead-kMinTwoUnitNodeValueLead)<<10)-1;  // 0xfdffff
00565 
00566     // Compact delta integers.
00567     static const int32_t kMaxOneUnitDelta=0xfbff;
00568     static const int32_t kMinTwoUnitDeltaLead=kMaxOneUnitDelta+1;  // 0xfc00
00569     static const int32_t kThreeUnitDeltaLead=0xffff;
00570 
00571     static const int32_t kMaxTwoUnitDelta=((kThreeUnitDeltaLead-kMinTwoUnitDeltaLead)<<16)-1;  // 0x03feffff
00572 
00573     UChar *ownedArray_;
00574 
00575     // Fixed value referencing the UCharsTrie words.
00576     const UChar *uchars_;
00577 
00578     // Iterator variables.
00579 
00580     // Pointer to next trie unit to read. NULL if no more matches.
00581     const UChar *pos_;
00582     // Remaining length of a linear-match node, minus 1. Negative if not in such a node.
00583     int32_t remainingMatchLength_;
00584 };
00585 
00586 U_NAMESPACE_END
00587 
00588 #endif  // __UCHARSTRIE_H__
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines