ICU 4.8.1.1
4.8.1.1
|
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__