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__