ICU 4.8.1.1  4.8.1.1
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ucharstrie.h
Go to the documentation of this file.
1 /*
2 *******************************************************************************
3 * Copyright (C) 2010-2011, International Business Machines
4 * Corporation and others. All Rights Reserved.
5 *******************************************************************************
6 * file name: ucharstrie.h
7 * encoding: US-ASCII
8 * tab size: 8 (not used)
9 * indentation:4
10 *
11 * created on: 2010nov14
12 * created by: Markus W. Scherer
13 */
14 
15 #ifndef __UCHARSTRIE_H__
16 #define __UCHARSTRIE_H__
17 
24 #include "unicode/utypes.h"
25 #include "unicode/unistr.h"
26 #include "unicode/uobject.h"
27 #include "unicode/ustringtrie.h"
28 
30 
31 class Appendable;
32 class UCharsTrieBuilder;
33 class UVector32;
34 
49 public:
64  UCharsTrie(const UChar *trieUChars)
65  : ownedArray_(NULL), uchars_(trieUChars),
66  pos_(uchars_), remainingMatchLength_(-1) {}
67 
72  ~UCharsTrie();
73 
80  UCharsTrie(const UCharsTrie &other)
81  : ownedArray_(NULL), uchars_(other.uchars_),
82  pos_(other.pos_), remainingMatchLength_(other.remainingMatchLength_) {}
83 
90  pos_=uchars_;
91  remainingMatchLength_=-1;
92  return *this;
93  }
94 
100  class State : public UMemory {
101  public:
106  State() { uchars=NULL; }
107  private:
108  friend class UCharsTrie;
109 
110  const UChar *uchars;
111  const UChar *pos;
112  int32_t remainingMatchLength;
113  };
114 
122  const UCharsTrie &saveState(State &state) const {
123  state.uchars=uchars_;
124  state.pos=pos_;
125  state.remainingMatchLength=remainingMatchLength_;
126  return *this;
127  }
128 
139  UCharsTrie &resetToState(const State &state) {
140  if(uchars_==state.uchars && uchars_!=NULL) {
141  pos_=state.pos;
142  remainingMatchLength_=state.remainingMatchLength;
143  }
144  return *this;
145  }
146 
153  UStringTrieResult current() const;
154 
162  inline UStringTrieResult first(int32_t uchar) {
163  remainingMatchLength_=-1;
164  return nextImpl(uchars_, uchar);
165  }
166 
176  return cp<=0xffff ?
177  first(cp) :
179  next(U16_TRAIL(cp)) :
181  }
182 
189  UStringTrieResult next(int32_t uchar);
190 
199  return cp<=0xffff ?
200  next(cp) :
202  next(U16_TRAIL(cp)) :
204  }
205 
221  UStringTrieResult next(const UChar *s, int32_t length);
222 
232  inline int32_t getValue() const {
233  const UChar *pos=pos_;
234  int32_t leadUnit=*pos++;
235  // U_ASSERT(leadUnit>=kMinValueLead);
236  return leadUnit&kValueIsFinal ?
237  readValue(pos, leadUnit&0x7fff) : readNodeValue(pos, leadUnit);
238  }
239 
249  inline UBool hasUniqueValue(int32_t &uniqueValue) const {
250  const UChar *pos=pos_;
251  // Skip the rest of a pending linear-match node.
252  return pos!=NULL && findUniqueValue(pos+remainingMatchLength_+1, FALSE, uniqueValue);
253  }
254 
262  int32_t getNextUChars(Appendable &out) const;
263 
268  class U_COMMON_API Iterator : public UMemory {
269  public:
281  Iterator(const UChar *trieUChars, int32_t maxStringLength, UErrorCode &errorCode);
282 
294  Iterator(const UCharsTrie &trie, int32_t maxStringLength, UErrorCode &errorCode);
295 
300  ~Iterator();
301 
307  Iterator &reset();
308 
313  UBool hasNext() const;
314 
329  UBool next(UErrorCode &errorCode);
330 
335  const UnicodeString &getString() const { return str_; }
340  int32_t getValue() const { return value_; }
341 
342  private:
343  UBool truncateAndStop() {
344  pos_=NULL;
345  value_=-1; // no real value for str
346  return TRUE;
347  }
348 
349  const UChar *branchNext(const UChar *pos, int32_t length, UErrorCode &errorCode);
350 
351  const UChar *uchars_;
352  const UChar *pos_;
353  const UChar *initialPos_;
354  int32_t remainingMatchLength_;
355  int32_t initialRemainingMatchLength_;
356  UBool skipValue_; // Skip intermediate value which was already delivered.
357 
358  UnicodeString str_;
359  int32_t maxLength_;
360  int32_t value_;
361 
362  // The stack stores pairs of integers for backtracking to another
363  // outbound edge of a branch node.
364  // The first integer is an offset from uchars_.
365  // The second integer has the str_.length() from before the node in bits 15..0,
366  // and the remaining branch length in bits 31..16.
367  // (We could store the remaining branch length minus 1 in bits 30..16 and not use the sign bit,
368  // but the code looks more confusing that way.)
369  UVector32 *stack_;
370  };
371 
372 private:
373  friend class UCharsTrieBuilder;
374 
381  UCharsTrie(UChar *adoptUChars, const UChar *trieUChars)
382  : ownedArray_(adoptUChars), uchars_(trieUChars),
383  pos_(uchars_), remainingMatchLength_(-1) {}
384 
385  // No assignment operator.
386  UCharsTrie &operator=(const UCharsTrie &other);
387 
388  inline void stop() {
389  pos_=NULL;
390  }
391 
392  // Reads a compact 32-bit integer.
393  // pos is already after the leadUnit, and the lead unit has bit 15 reset.
394  static inline int32_t readValue(const UChar *pos, int32_t leadUnit) {
395  int32_t value;
396  if(leadUnit<kMinTwoUnitValueLead) {
397  value=leadUnit;
398  } else if(leadUnit<kThreeUnitValueLead) {
399  value=((leadUnit-kMinTwoUnitValueLead)<<16)|*pos;
400  } else {
401  value=(pos[0]<<16)|pos[1];
402  }
403  return value;
404  }
405  static inline const UChar *skipValue(const UChar *pos, int32_t leadUnit) {
406  if(leadUnit>=kMinTwoUnitValueLead) {
407  if(leadUnit<kThreeUnitValueLead) {
408  ++pos;
409  } else {
410  pos+=2;
411  }
412  }
413  return pos;
414  }
415  static inline const UChar *skipValue(const UChar *pos) {
416  int32_t leadUnit=*pos++;
417  return skipValue(pos, leadUnit&0x7fff);
418  }
419 
420  static inline int32_t readNodeValue(const UChar *pos, int32_t leadUnit) {
421  // U_ASSERT(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
422  int32_t value;
423  if(leadUnit<kMinTwoUnitNodeValueLead) {
424  value=(leadUnit>>6)-1;
425  } else if(leadUnit<kThreeUnitNodeValueLead) {
426  value=(((leadUnit&0x7fc0)-kMinTwoUnitNodeValueLead)<<10)|*pos;
427  } else {
428  value=(pos[0]<<16)|pos[1];
429  }
430  return value;
431  }
432  static inline const UChar *skipNodeValue(const UChar *pos, int32_t leadUnit) {
433  // U_ASSERT(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
434  if(leadUnit>=kMinTwoUnitNodeValueLead) {
435  if(leadUnit<kThreeUnitNodeValueLead) {
436  ++pos;
437  } else {
438  pos+=2;
439  }
440  }
441  return pos;
442  }
443 
444  static inline const UChar *jumpByDelta(const UChar *pos) {
445  int32_t delta=*pos++;
446  if(delta>=kMinTwoUnitDeltaLead) {
447  if(delta==kThreeUnitDeltaLead) {
448  delta=(pos[0]<<16)|pos[1];
449  pos+=2;
450  } else {
451  delta=((delta-kMinTwoUnitDeltaLead)<<16)|*pos++;
452  }
453  }
454  return pos+delta;
455  }
456 
457  static const UChar *skipDelta(const UChar *pos) {
458  int32_t delta=*pos++;
459  if(delta>=kMinTwoUnitDeltaLead) {
460  if(delta==kThreeUnitDeltaLead) {
461  pos+=2;
462  } else {
463  ++pos;
464  }
465  }
466  return pos;
467  }
468 
469  static inline UStringTrieResult valueResult(int32_t node) {
471  }
472 
473  // Handles a branch node for both next(uchar) and next(string).
474  UStringTrieResult branchNext(const UChar *pos, int32_t length, int32_t uchar);
475 
476  // Requires remainingLength_<0.
477  UStringTrieResult nextImpl(const UChar *pos, int32_t uchar);
478 
479  // Helper functions for hasUniqueValue().
480  // Recursively finds a unique value (or whether there is not a unique one)
481  // from a branch.
482  static const UChar *findUniqueValueFromBranch(const UChar *pos, int32_t length,
483  UBool haveUniqueValue, int32_t &uniqueValue);
484  // Recursively finds a unique value (or whether there is not a unique one)
485  // starting from a position on a node lead unit.
486  static UBool findUniqueValue(const UChar *pos, UBool haveUniqueValue, int32_t &uniqueValue);
487 
488  // Helper functions for getNextUChars().
489  // getNextUChars() when pos is on a branch node.
490  static void getNextBranchUChars(const UChar *pos, int32_t length, Appendable &out);
491 
492  // UCharsTrie data structure
493  //
494  // The trie consists of a series of UChar-serialized nodes for incremental
495  // Unicode string/UChar sequence matching. (UChar=16-bit unsigned integer)
496  // The root node is at the beginning of the trie data.
497  //
498  // Types of nodes are distinguished by their node lead unit ranges.
499  // After each node, except a final-value node, another node follows to
500  // encode match values or continue matching further units.
501  //
502  // Node types:
503  // - Final-value node: Stores a 32-bit integer in a compact, variable-length format.
504  // The value is for the string/UChar sequence so far.
505  // - Match node, optionally with an intermediate value in a different compact format.
506  // The value, if present, is for the string/UChar sequence so far.
507  //
508  // Aside from the value, which uses the node lead unit's high bits:
509  //
510  // - Linear-match node: Matches a number of units.
511  // - Branch node: Branches to other nodes according to the current input unit.
512  // The node unit is the length of the branch (number of units to select from)
513  // minus 1. It is followed by a sub-node:
514  // - If the length is at most kMaxBranchLinearSubNodeLength, then
515  // there are length-1 (key, value) pairs and then one more comparison unit.
516  // If one of the key units matches, then the value is either a final value for
517  // the string so far, or a "jump" delta to the next node.
518  // If the last unit matches, then matching continues with the next node.
519  // (Values have the same encoding as final-value nodes.)
520  // - If the length is greater than kMaxBranchLinearSubNodeLength, then
521  // there is one unit and one "jump" delta.
522  // If the input unit is less than the sub-node unit, then "jump" by delta to
523  // the next sub-node which will have a length of length/2.
524  // (The delta has its own compact encoding.)
525  // Otherwise, skip the "jump" delta to the next sub-node
526  // which will have a length of length-length/2.
527 
528  // Match-node lead unit values, after masking off intermediate-value bits:
529 
530  // 0000..002f: Branch node. If node!=0 then the length is node+1, otherwise
531  // the length is one more than the next unit.
532 
533  // For a branch sub-node with at most this many entries, we drop down
534  // to a linear search.
535  static const int32_t kMaxBranchLinearSubNodeLength=5;
536 
537  // 0030..003f: Linear-match node, match 1..16 units and continue reading the next node.
538  static const int32_t kMinLinearMatch=0x30;
539  static const int32_t kMaxLinearMatchLength=0x10;
540 
541  // Match-node lead unit bits 14..6 for the optional intermediate value.
542  // If these bits are 0, then there is no intermediate value.
543  // Otherwise, see the *NodeValue* constants below.
544  static const int32_t kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength; // 0x0040
545  static const int32_t kNodeTypeMask=kMinValueLead-1; // 0x003f
546 
547  // A final-value node has bit 15 set.
548  static const int32_t kValueIsFinal=0x8000;
549 
550  // Compact value: After testing and masking off bit 15, use the following thresholds.
551  static const int32_t kMaxOneUnitValue=0x3fff;
552 
553  static const int32_t kMinTwoUnitValueLead=kMaxOneUnitValue+1; // 0x4000
554  static const int32_t kThreeUnitValueLead=0x7fff;
555 
556  static const int32_t kMaxTwoUnitValue=((kThreeUnitValueLead-kMinTwoUnitValueLead)<<16)-1; // 0x3ffeffff
557 
558  // Compact intermediate-value integer, lead unit shared with a branch or linear-match node.
559  static const int32_t kMaxOneUnitNodeValue=0xff;
560  static const int32_t kMinTwoUnitNodeValueLead=kMinValueLead+((kMaxOneUnitNodeValue+1)<<6); // 0x4040
561  static const int32_t kThreeUnitNodeValueLead=0x7fc0;
562 
563  static const int32_t kMaxTwoUnitNodeValue=
564  ((kThreeUnitNodeValueLead-kMinTwoUnitNodeValueLead)<<10)-1; // 0xfdffff
565 
566  // Compact delta integers.
567  static const int32_t kMaxOneUnitDelta=0xfbff;
568  static const int32_t kMinTwoUnitDeltaLead=kMaxOneUnitDelta+1; // 0xfc00
569  static const int32_t kThreeUnitDeltaLead=0xffff;
570 
571  static const int32_t kMaxTwoUnitDelta=((kThreeUnitDeltaLead-kMinTwoUnitDeltaLead)<<16)-1; // 0x03feffff
572 
573  UChar *ownedArray_;
574 
575  // Fixed value referencing the UCharsTrie words.
576  const UChar *uchars_;
577 
578  // Iterator variables.
579 
580  // Pointer to next trie unit to read. NULL if no more matches.
581  const UChar *pos_;
582  // Remaining length of a linear-match node, minus 1. Negative if not in such a node.
583  int32_t remainingMatchLength_;
584 };
585 
587 
588 #endif // __UCHARSTRIE_H__
#define U16_TRAIL(supplementary)
Get the trail surrogate (0xdc00..0xdfff) for a supplementary code point (0x10000..0x10ffff).
Definition: utf16.h:131
Base class for objects to which Unicode characters and strings can be appended.
Definition: appendable.h:49
int32_t getValue() const
Returns a matching string&#39;s value if called immediately after current()/first()/next() returned USTRI...
Definition: ucharstrie.h:232
int32_t getNextUChars(Appendable &out) const
Finds each UChar which continues the string from the current state.
UStringTrieResult next(int32_t uchar)
Traverses the trie from the current state for this input UChar.
Light-weight, non-const reader class for a UCharsTrie.
Definition: ucharstrie.h:48
UCharsTrie & resetToState(const State &state)
Resets this trie to the saved state.
Definition: ucharstrie.h:139
UBool hasUniqueValue(int32_t &uniqueValue) const
Determines whether all strings reachable from the current state map to the same value.
Definition: ucharstrie.h:249
UStringTrieResult first(int32_t uchar)
Traverses the trie from the initial state for this input UChar.
Definition: ucharstrie.h:162
static const int32_t kMaxBranchLinearSubNodeLength
C++ API: Unicode String.
const UnicodeString & getString() const
Definition: ucharstrie.h:335
UStringTrieResult
Return values for BytesTrie::next(), UCharsTrie::next() and similar methods.
Definition: ustringtrie.h:32
State()
Constructs an empty State.
Definition: ucharstrie.h:106
The input unit(s) did not continue a matching string.
Definition: ustringtrie.h:40
#define U_NAMESPACE_BEGIN
This is used to begin a declaration of a public ICU C++ API.
Definition: uversion.h:131
UCharsTrie(const UChar *trieUChars)
Constructs a UCharsTrie reader instance.
Definition: ucharstrie.h:64
UCharsTrie state object, for saving a trie&#39;s current state and resetting the trie back to this state ...
Definition: ucharstrie.h:100
UStringTrieResult current() const
Determines whether the string so far matches, whether it has a value, and whether another input UChar...
#define USTRINGTRIE_HAS_NEXT(result)
Equivalent to (result==USTRINGTRIE_NO_VALUE || result==USTRINGTRIE_INTERMEDIATE_VALUE) but this macro...
Definition: ustringtrie.h:92
int32_t UChar32
Define UChar32 as a type for single Unicode code points.
Definition: umachine.h:345
#define NULL
Define NULL if necessary, to 0 for C++ and to ((void *)0) for C.
Definition: utypes.h:299
int32_t getValue() const
Definition: ucharstrie.h:340
#define TRUE
The TRUE value of a UBool.
Definition: umachine.h:232
UMemory is the common ICU base class.
Definition: uobject.h:101
UnicodeString is a string class that stores Unicode characters directly and provides similar function...
Definition: unistr.h:188
#define U16_LEAD(supplementary)
Get the lead surrogate (0xd800..0xdbff) for a supplementary code point (0x10000..0x10ffff).
Definition: utf16.h:122
C++ API: Common ICU base class UObject.
UStringTrieResult nextForCodePoint(UChar32 cp)
Traverses the trie from the current state for the one or two UTF-16 code units for this input code po...
Definition: ucharstrie.h:198
uint16_t UChar
Define UChar to be wchar_t if that is 16 bits wide; always assumed to be unsigned.
Definition: umachine.h:325
#define U_NAMESPACE_END
This is used to end a declaration of a public ICU C++ API.
Definition: uversion.h:132
const UCharsTrie & saveState(State &state) const
Saves the state of this trie.
Definition: ucharstrie.h:122
Builder class for UCharsTrie.
Iterator for all of the (string, value) pairs in a UCharsTrie.
Definition: ucharstrie.h:268
UErrorCode
Error code to replace exception handling, so that the code is compatible with all C++ compilers...
Definition: utypes.h:639
C API: Helper definitions for dictionary trie APIs.
Basic definitions for ICU, for both C and C++ APIs.
UCharsTrie & reset()
Resets this trie to its initial state.
Definition: ucharstrie.h:89
#define FALSE
The FALSE value of a UBool.
Definition: umachine.h:236
#define U_COMMON_API
Set to export library symbols from inside the common library, and to import them from outside...
Definition: utypes.h:520
UStringTrieResult firstForCodePoint(UChar32 cp)
Traverses the trie from the initial state for the one or two UTF-16 code units for this input code po...
Definition: ucharstrie.h:175
The input unit(s) continued a matching string and there is a value for the string so far...
Definition: ustringtrie.h:63
int8_t UBool
The ICU boolean type.
Definition: umachine.h:228
UCharsTrie(const UCharsTrie &other)
Copy constructor, copies the other trie reader object and its state, but not the UChar array which wi...
Definition: ucharstrie.h:80