w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

collationiterator.cpp
Go to the documentation of this file.
1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 * Copyright (C) 2010-2014, International Business Machines
6 * Corporation and others. All Rights Reserved.
7 *******************************************************************************
8 * collationiterator.cpp
9 *
10 * created on: 2010oct27
11 * created by: Markus W. Scherer
12 */
13 
14 #include "utypeinfo.h" // for 'typeid' to work
15 
16 #include "unicode/utypes.h"
17 
18 #if !UCONFIG_NO_COLLATION
19 
20 #include "unicode/ucharstrie.h"
21 #include "unicode/ustringtrie.h"
22 #include "charstr.h"
23 #include "cmemory.h"
24 #include "collation.h"
25 #include "collationdata.h"
26 #include "collationfcd.h"
27 #include "collationiterator.h"
28 #include "normalizer2impl.h"
29 #include "uassert.h"
30 #include "uvectr32.h"
31 
33 
35 
36 UBool
38  int32_t capacity = buffer.getCapacity();
39  if((length + appCap) <= capacity) { return TRUE; }
40  if(U_FAILURE(errorCode)) { return FALSE; }
41  do {
42  if(capacity < 1000) {
43  capacity *= 4;
44  } else {
45  capacity *= 2;
46  }
47  } while(capacity < (length + appCap));
48  int64_t *p = buffer.resize(capacity, length);
49  if(p == NULL) {
51  return FALSE;
52  }
53  return TRUE;
54 }
55 
56 // State of combining marks skipped in discontiguous contraction.
57 // We create a state object on first use and keep it around deactivated between uses.
58 class SkippedState : public UMemory {
59 public:
60  // Born active but empty.
61  SkippedState() : pos(0), skipLengthAtMatch(0) {}
62  void clear() {
63  oldBuffer.remove();
64  pos = 0;
65  // The newBuffer is reset by setFirstSkipped().
66  }
67 
68  UBool isEmpty() const { return oldBuffer.isEmpty(); }
69 
70  UBool hasNext() const { return pos < oldBuffer.length(); }
71 
72  // Requires hasNext().
74  UChar32 c = oldBuffer.char32At(pos);
75  pos += U16_LENGTH(c);
76  return c;
77  }
78 
79  // Accounts for one more input code point read beyond the end of the marks buffer.
80  void incBeyond() {
81  U_ASSERT(!hasNext());
82  ++pos;
83  }
84 
85  // Goes backward through the skipped-marks buffer.
86  // Returns the number of code points read beyond the skipped marks
87  // that need to be backtracked through normal input.
89  int32_t length = oldBuffer.length();
90  int32_t beyond = pos - length;
91  if(beyond > 0) {
92  if(beyond >= n) {
93  // Not back far enough to re-enter the oldBuffer.
94  pos -= n;
95  return n;
96  } else {
97  // Back out all beyond-oldBuffer code points and re-enter the buffer.
98  pos = oldBuffer.moveIndex32(length, beyond - n);
99  return beyond;
100  }
101  } else {
102  // Go backwards from inside the oldBuffer.
103  pos = oldBuffer.moveIndex32(pos, -n);
104  return 0;
105  }
106  }
107 
109  skipLengthAtMatch = 0;
110  newBuffer.setTo(c);
111  }
112 
113  void skip(UChar32 c) {
114  newBuffer.append(c);
115  }
116 
117  void recordMatch() { skipLengthAtMatch = newBuffer.length(); }
118 
119  // Replaces the characters we consumed with the newly skipped ones.
120  void replaceMatch() {
121  // Note: UnicodeString.replace() pins pos to at most length().
122  oldBuffer.replace(0, pos, newBuffer, 0, skipLengthAtMatch);
123  pos = 0;
124  }
125 
126  void saveTrieState(const UCharsTrie &trie) { trie.saveState(state); }
127  void resetToTrieState(UCharsTrie &trie) const { trie.resetToState(state); }
128 
129 private:
130  // Combining marks skipped in previous discontiguous-contraction matching.
131  // After that discontiguous contraction was completed, we start reading them from here.
132  UnicodeString oldBuffer;
133  // Combining marks newly skipped in current discontiguous-contraction matching.
134  // These might have been read from the normal text or from the oldBuffer.
135  UnicodeString newBuffer;
136  // Reading index in oldBuffer,
137  // or counter for how many code points have been read beyond oldBuffer (pos-oldBuffer.length()).
139  // newBuffer.length() at the time of the last matching character.
140  // When a partial match fails, we back out skipped and partial-matching input characters.
142  // We save the trie state before we attempt to match a character,
143  // so that we can skip it and try the next one.
145 };
146 
148  : UObject(other),
149  trie(other.trie),
150  data(other.data),
152  skipped(NULL),
156  int32_t length = other.ceBuffer.length;
158  for(int32_t i = 0; i < length; ++i) {
159  ceBuffer.set(i, other.ceBuffer.get(i));
160  }
162  } else {
163  cesIndex = 0;
164  }
165 }
166 
168  delete skipped;
169 }
170 
171 UBool
173  // Subclasses: Call this method and then add more specific checks.
174  // Compare the iterator state but not the collation data (trie & data fields):
175  // Assume that the caller compares the data.
176  // Ignore skipped since that should be unused between calls to nextCE().
177  // (It only stays around to avoid another memory allocation.)
178  if(!(typeid(*this) == typeid(other) &&
179  ceBuffer.length == other.ceBuffer.length &&
180  cesIndex == other.cesIndex &&
181  numCpFwd == other.numCpFwd &&
182  isNumeric == other.isNumeric)) {
183  return FALSE;
184  }
185  for(int32_t i = 0; i < ceBuffer.length; ++i) {
186  if(ceBuffer.get(i) != other.ceBuffer.get(i)) { return FALSE; }
187  }
188  return TRUE;
189 }
190 
191 void
193  cesIndex = ceBuffer.length = 0;
194  if(skipped != NULL) { skipped->clear(); }
195 }
196 
197 int32_t
200  // No need to loop for each expansion CE.
202  }
203  return ceBuffer.length;
204 }
205 
206 uint32_t
209  return (c < 0) ? Collation::FALLBACK_CE32 : data->getCE32(c);
210 }
211 
212 UChar
214  return 0;
215 }
216 
217 UBool
219  return FALSE;
220 }
221 
222 UBool
224  return FALSE;
225 }
226 
227 uint32_t
229  return data->getCE32(c);
230 }
231 
232 uint32_t
235  return 0;
236 }
237 
238 int64_t
241  --ceBuffer.length; // Undo ceBuffer.incLength().
242  appendCEsFromCE32(d, c, ce32, TRUE, errorCode);
243  if(U_SUCCESS(errorCode)) {
244  return ceBuffer.get(cesIndex++);
245  } else {
247  }
248 }
249 
250 void
253  while(Collation::isSpecialCE32(ce32)) {
254  switch(Collation::tagFromCE32(ce32)) {
258  return;
261  return;
264  return;
269  ceBuffer.length += 2;
270  }
271  return;
273  const uint32_t *ce32s = d->ce32s + Collation::indexFromCE32(ce32);
276  do {
278  } while(--length > 0);
279  }
280  return;
281  }
283  const int64_t *ces = d->ces + Collation::indexFromCE32(ce32);
286  do {
287  ceBuffer.appendUnsafe(*ces++);
288  } while(--length > 0);
289  }
290  return;
291  }
293  ce32 = getCE32FromBuilderData(ce32, errorCode);
294  if(U_FAILURE(errorCode)) { return; }
295  if(ce32 == Collation::FALLBACK_CE32) {
296  d = data->base;
297  ce32 = d->getCE32(c);
298  }
299  break;
302  ce32 = getCE32FromPrefix(d, ce32, errorCode);
304  break;
306  const UChar *p = d->contexts + Collation::indexFromCE32(ce32);
307  uint32_t defaultCE32 = CollationData::readCE32(p); // Default if no suffix match.
308  if(!forward) {
309  // Backward contractions are handled by previousCEUnsafe().
310  // c has contractions but they were not found.
311  ce32 = defaultCE32;
312  break;
313  }
314  UChar32 nextCp;
315  if(skipped == NULL && numCpFwd < 0) {
316  // Some portion of nextCE32FromContraction() pulled out here as an ASCII fast path,
317  // avoiding the function call and the nextSkippedCodePoint() overhead.
318  nextCp = nextCodePoint(errorCode);
319  if(nextCp < 0) {
320  // No more text.
321  ce32 = defaultCE32;
322  break;
323  } else if((ce32 & Collation::CONTRACT_NEXT_CCC) != 0 &&
324  !CollationFCD::mayHaveLccc(nextCp)) {
325  // All contraction suffixes start with characters with lccc!=0
326  // but the next code point has lccc==0.
328  ce32 = defaultCE32;
329  break;
330  }
331  } else {
333  if(nextCp < 0) {
334  // No more text.
335  ce32 = defaultCE32;
336  break;
337  } else if((ce32 & Collation::CONTRACT_NEXT_CCC) != 0 &&
338  !CollationFCD::mayHaveLccc(nextCp)) {
339  // All contraction suffixes start with characters with lccc!=0
340  // but the next code point has lccc==0.
342  ce32 = defaultCE32;
343  break;
344  }
345  }
346  ce32 = nextCE32FromContraction(d, ce32, p + 2, defaultCE32, nextCp, errorCode);
347  if(ce32 == Collation::NO_CE32) {
348  // CEs from a discontiguous contraction plus the skipped combining marks
349  // have been appended already.
350  return;
351  }
352  break;
353  }
355  if(isNumeric) {
357  return;
358  } else {
359  // Fetch the non-numeric-collation CE32 and continue.
360  ce32 = d->ce32s[Collation::indexFromCE32(ce32)];
361  break;
362  }
364  U_ASSERT(c == 0);
365  if(forward && foundNULTerminator()) {
366  // Handle NUL-termination. (Not needed in Java.)
368  return;
369  } else {
370  // Fetch the normal ce32 for U+0000 and continue.
371  ce32 = d->ce32s[0];
372  break;
373  }
374  case Collation::HANGUL_TAG: {
375  const uint32_t *jamoCE32s = d->jamoCE32s;
381  if((ce32 & Collation::HANGUL_NO_SPECIAL_JAMO) != 0) {
382  // None of the Jamo CE32s are isSpecialCE32().
383  // Avoid recursive function calls and per-Jamo tests.
384  if(ceBuffer.ensureAppendCapacity(t == 0 ? 2 : 3, errorCode)) {
386  ceBuffer.set(ceBuffer.length + 1, Collation::ceFromCE32(jamoCE32s[19 + v]));
387  ceBuffer.length += 2;
388  if(t != 0) {
389  ceBuffer.appendUnsafe(Collation::ceFromCE32(jamoCE32s[39 + t]));
390  }
391  }
392  return;
393  } else {
394  // We should not need to compute each Jamo code point.
395  // In particular, there should be no offset or implicit ce32.
397  appendCEsFromCE32(d, U_SENTINEL, jamoCE32s[19 + v], forward, errorCode);
398  if(t == 0) { return; }
399  // offset 39 = 19 + 21 - 1:
400  // 19 = JAMO_L_COUNT
401  // 21 = JAMO_T_COUNT
402  // -1 = omit t==0
403  ce32 = jamoCE32s[39 + t];
404  c = U_SENTINEL;
405  break;
406  }
407  }
409  U_ASSERT(forward); // Backward iteration should never see lead surrogate code _unit_ data.
411  UChar trail;
412  if(U16_IS_TRAIL(trail = handleGetTrailSurrogate())) {
413  c = U16_GET_SUPPLEMENTARY(c, trail);
415  if(ce32 == Collation::LEAD_ALL_UNASSIGNED) {
416  ce32 = Collation::UNASSIGNED_CE32; // unassigned-implicit
417  } else if(ce32 == Collation::LEAD_ALL_FALLBACK ||
418  (ce32 = d->getCE32FromSupplementary(c)) == Collation::FALLBACK_CE32) {
419  // fall back to the base data
420  d = d->base;
421  ce32 = d->getCE32FromSupplementary(c);
422  }
423  } else {
424  // c is an unpaired surrogate.
426  }
427  break;
428  }
430  U_ASSERT(c >= 0);
431  ceBuffer.append(d->getCEFromOffsetCE32(c, ce32), errorCode);
432  return;
434  U_ASSERT(c >= 0);
436  ce32 = Collation::FFFD_CE32;
437  break;
438  } else {
440  return;
441  }
442  }
443  }
445 }
446 
447 uint32_t
450  const UChar *p = d->contexts + Collation::indexFromCE32(ce32);
451  ce32 = CollationData::readCE32(p); // Default if no prefix match.
452  p += 2;
453  // Number of code points read before the original code point.
454  int32_t lookBehind = 0;
455  UCharsTrie prefixes(p);
456  for(;;) {
458  if(c < 0) { break; }
459  ++lookBehind;
460  UStringTrieResult match = prefixes.nextForCodePoint(c);
462  ce32 = (uint32_t)prefixes.getValue();
463  }
464  if(!USTRINGTRIE_HAS_NEXT(match)) { break; }
465  }
466  forwardNumCodePoints(lookBehind, errorCode);
467  return ce32;
468 }
469 
470 UChar32
472  if(skipped != NULL && skipped->hasNext()) { return skipped->next(); }
473  if(numCpFwd == 0) { return U_SENTINEL; }
475  if(skipped != NULL && !skipped->isEmpty() && c >= 0) { skipped->incBeyond(); }
476  if(numCpFwd > 0 && c >= 0) { --numCpFwd; }
477  return c;
478 }
479 
480 void
482  if(skipped != NULL && !skipped->isEmpty()) {
484  }
486  if(numCpFwd >= 0) { numCpFwd += n; }
487 }
488 
489 uint32_t
491  const UChar *p, uint32_t ce32, UChar32 c,
493  // c: next code point after the original one
494 
495  // Number of code points read beyond the original code point.
496  // Needed for discontiguous contraction matching.
497  int32_t lookAhead = 1;
498  // Number of code points read since the last match (initially only c).
499  int32_t sinceMatch = 1;
500  // Normally we only need a contiguous match,
501  // and therefore need not remember the suffixes state from before a mismatch for retrying.
502  // If we are already processing skipped combining marks, then we do track the state.
503  UCharsTrie suffixes(p);
505  UStringTrieResult match = suffixes.firstForCodePoint(c);
506  for(;;) {
507  UChar32 nextCp;
509  ce32 = (uint32_t)suffixes.getValue();
511  return ce32;
512  }
514  sinceMatch = 1;
515  } else if(match == USTRINGTRIE_NO_MATCH || (nextCp = nextSkippedCodePoint(errorCode)) < 0) {
516  // No match for c, or partial match (USTRINGTRIE_NO_VALUE) and no further text.
517  // Back up if necessary, and try a discontiguous contraction.
518  if((contractionCE32 & Collation::CONTRACT_TRAILING_CCC) != 0 &&
519  // Discontiguous contraction matching extends an existing match.
520  // If there is no match yet, then there is nothing to do.
521  ((contractionCE32 & Collation::CONTRACT_SINGLE_CP_NO_MATCH) == 0 ||
522  sinceMatch < lookAhead)) {
523  // The last character of at least one suffix has lccc!=0,
524  // allowing for discontiguous contractions.
525  // UCA S2.1.1 only processes non-starters immediately following
526  // "a match in the table" (sinceMatch=1).
527  if(sinceMatch > 1) {
528  // Return to the state after the last match.
529  // (Return to sinceMatch=0 and re-fetch the first partially-matched character.)
530  backwardNumSkipped(sinceMatch, errorCode);
532  lookAhead -= sinceMatch - 1;
533  sinceMatch = 1;
534  }
535  if(d->getFCD16(c) > 0xff) {
537  d, suffixes, ce32, lookAhead, c, errorCode);
538  }
539  }
540  break;
541  } else {
542  // Continue after partial match (USTRINGTRIE_NO_VALUE) for c.
543  // It does not have a result value, therefore it is not itself "a match in the table".
544  // If a partially-matched c has ccc!=0 then
545  // it might be skipped in discontiguous contraction.
546  c = nextCp;
547  ++sinceMatch;
548  }
549  ++lookAhead;
550  match = suffixes.nextForCodePoint(c);
551  }
552  backwardNumSkipped(sinceMatch, errorCode);
553  return ce32;
554 }
555 
556 uint32_t
558  const CollationData *d, UCharsTrie &suffixes, uint32_t ce32,
559  int32_t lookAhead, UChar32 c,
561  if(U_FAILURE(errorCode)) { return 0; }
562 
563  // UCA section 3.3.2 Contractions:
564  // Contractions that end with non-starter characters
565  // are known as discontiguous contractions.
566  // ... discontiguous contractions must be detected in input text
567  // whenever the final sequence of non-starter characters could be rearranged
568  // so as to make a contiguous matching sequence that is canonically equivalent.
569 
570  // UCA: http://www.unicode.org/reports/tr10/#S2.1
571  // S2.1 Find the longest initial substring S at each point that has a match in the table.
572  // S2.1.1 If there are any non-starters following S, process each non-starter C.
573  // S2.1.2 If C is not blocked from S, find if S + C has a match in the table.
574  // Note: A non-starter in a string is called blocked
575  // if there is another non-starter of the same canonical combining class or zero
576  // between it and the last character of canonical combining class 0.
577  // S2.1.3 If there is a match, replace S by S + C, and remove C.
578 
579  // First: Is a discontiguous contraction even possible?
580  uint16_t fcd16 = d->getFCD16(c);
581  U_ASSERT(fcd16 > 0xff); // The caller checked this already, as a shortcut.
583  if(nextCp < 0) {
584  // No further text.
586  return ce32;
587  }
588  ++lookAhead;
589  uint8_t prevCC = (uint8_t)fcd16;
590  fcd16 = d->getFCD16(nextCp);
591  if(fcd16 <= 0xff) {
592  // The next code point after c is a starter (S2.1.1 "process each non-starter").
594  return ce32;
595  }
596 
597  // We have read and matched (lookAhead-2) code points,
598  // read non-matching c and peeked ahead at nextCp.
599  // Return to the state before the mismatch and continue matching with nextCp.
600  if(skipped == NULL || skipped->isEmpty()) {
601  if(skipped == NULL) {
602  skipped = new SkippedState();
603  if(skipped == NULL) {
605  return 0;
606  }
607  }
608  suffixes.reset();
609  if(lookAhead > 2) {
610  // Replay the partial match so far.
611  backwardNumCodePoints(lookAhead, errorCode);
612  suffixes.firstForCodePoint(nextCodePoint(errorCode));
613  for(int32_t i = 3; i < lookAhead; ++i) {
614  suffixes.nextForCodePoint(nextCodePoint(errorCode));
615  }
616  // Skip c (which did not match) and nextCp (which we will try now).
618  }
620  } else {
621  // Reset to the trie state before the failed match of c.
623  }
624 
626  // Number of code points read since the last match (at this point: c and nextCp).
627  int32_t sinceMatch = 2;
628  c = nextCp;
629  for(;;) {
631  // "If C is not blocked from S, find if S + C has a match in the table." (S2.1.2)
632  if(prevCC < (fcd16 >> 8) && USTRINGTRIE_HAS_VALUE(match = suffixes.nextForCodePoint(c))) {
633  // "If there is a match, replace S by S + C, and remove C." (S2.1.3)
634  // Keep prevCC unchanged.
635  ce32 = (uint32_t)suffixes.getValue();
636  sinceMatch = 0;
637  skipped->recordMatch();
638  if(!USTRINGTRIE_HAS_NEXT(match)) { break; }
640  } else {
641  // No match for "S + C", skip C.
642  skipped->skip(c);
644  prevCC = (uint8_t)fcd16;
645  }
646  if((c = nextSkippedCodePoint(errorCode)) < 0) { break; }
647  ++sinceMatch;
648  fcd16 = d->getFCD16(c);
649  if(fcd16 <= 0xff) {
650  // The next code point after c is a starter (S2.1.1 "process each non-starter").
651  break;
652  }
653  }
654  backwardNumSkipped(sinceMatch, errorCode);
655  UBool isTopDiscontiguous = skipped->isEmpty();
657  if(isTopDiscontiguous && !skipped->isEmpty()) {
658  // We did get a match after skipping one or more combining marks,
659  // and we are not in a recursive discontiguous contraction.
660  // Append CEs from the contraction ce32
661  // and then from the combining marks that we skipped before the match.
662  c = U_SENTINEL;
663  for(;;) {
664  appendCEsFromCE32(d, c, ce32, TRUE, errorCode);
665  // Fetch CE32s for skipped combining marks from the normal data, with fallback,
666  // rather than from the CollationData where we found the contraction.
667  if(!skipped->hasNext()) { break; }
668  c = skipped->next();
669  ce32 = getDataCE32(c);
670  if(ce32 == Collation::FALLBACK_CE32) {
671  d = data->base;
672  ce32 = d->getCE32(c);
673  } else {
674  d = data;
675  }
676  // Note: A nested discontiguous-contraction match
677  // replaces consumed combining marks with newly skipped ones
678  // and resets the reading position to the beginning.
679  }
680  skipped->clear();
681  ce32 = Collation::NO_CE32; // Signal to the caller that the result is in the ceBuffer.
682  }
683  return ce32;
684 }
685 
686 void
688  // Collect digits.
690  if(forward) {
691  for(;;) {
692  char digit = Collation::digitFromCE32(ce32);
693  digits.append(digit, errorCode);
694  if(numCpFwd == 0) { break; }
696  if(c < 0) { break; }
697  ce32 = data->getCE32(c);
698  if(ce32 == Collation::FALLBACK_CE32) {
699  ce32 = data->base->getCE32(c);
700  }
703  break;
704  }
705  if(numCpFwd > 0) { --numCpFwd; }
706  }
707  } else {
708  for(;;) {
709  char digit = Collation::digitFromCE32(ce32);
710  digits.append(digit, errorCode);
712  if(c < 0) { break; }
713  ce32 = data->getCE32(c);
714  if(ce32 == Collation::FALLBACK_CE32) {
715  ce32 = data->base->getCE32(c);
716  }
719  break;
720  }
721  }
722  // Reverse the digit string.
723  char *p = digits.data();
724  char *q = p + digits.length() - 1;
725  while(p < q) {
726  char digit = *p;
727  *p++ = *q;
728  *q-- = digit;
729  }
730  }
731  if(U_FAILURE(errorCode)) { return; }
732  int32_t pos = 0;
733  do {
734  // Skip leading zeros.
735  while(pos < (digits.length() - 1) && digits[pos] == 0) { ++pos; }
736  // Write a sequence of CEs for at most 254 digits at a time.
737  int32_t segmentLength = digits.length() - pos;
738  if(segmentLength > 254) { segmentLength = 254; }
739  appendNumericSegmentCEs(digits.data() + pos, segmentLength, errorCode);
740  pos += segmentLength;
741  } while(U_SUCCESS(errorCode) && pos < digits.length());
742 }
743 
744 void
746  U_ASSERT(1 <= length && length <= 254);
747  U_ASSERT(length == 1 || digits[0] != 0);
748  uint32_t numericPrimary = data->numericPrimary;
749  // Note: We use primary byte values 2..255: digits are not compressible.
750  if(length <= 7) {
751  // Very dense encoding for small numbers.
752  int32_t value = digits[0];
753  for(int32_t i = 1; i < length; ++i) {
754  value = value * 10 + digits[i];
755  }
756  // Primary weight second byte values:
757  // 74 byte values 2.. 75 for small numbers in two-byte primary weights.
758  // 40 byte values 76..115 for medium numbers in three-byte primary weights.
759  // 16 byte values 116..131 for large numbers in four-byte primary weights.
760  // 124 byte values 132..255 for very large numbers with 4..127 digit pairs.
761  int32_t firstByte = 2;
762  int32_t numBytes = 74;
763  if(value < numBytes) {
764  // Two-byte primary for 0..73, good for day & month numbers etc.
765  uint32_t primary = numericPrimary | ((firstByte + value) << 16);
767  return;
768  }
769  value -= numBytes;
770  firstByte += numBytes;
771  numBytes = 40;
772  if(value < numBytes * 254) {
773  // Three-byte primary for 74..10233=74+40*254-1, good for year numbers and more.
774  uint32_t primary = numericPrimary |
775  ((firstByte + value / 254) << 16) | ((2 + value % 254) << 8);
777  return;
778  }
779  value -= numBytes * 254;
780  firstByte += numBytes;
781  numBytes = 16;
782  if(value < numBytes * 254 * 254) {
783  // Four-byte primary for 10234..1042489=10234+16*254*254-1.
784  uint32_t primary = numericPrimary | (2 + value % 254);
785  value /= 254;
786  primary |= (2 + value % 254) << 8;
787  value /= 254;
788  primary |= (firstByte + value % 254) << 16;
790  return;
791  }
792  // original value > 1042489
793  }
794  U_ASSERT(length >= 7);
795 
796  // The second primary byte value 132..255 indicates the number of digit pairs (4..127),
797  // then we generate primary bytes with those pairs.
798  // Omit trailing 00 pairs.
799  // Decrement the value for the last pair.
800 
801  // Set the exponent. 4 pairs->132, 5 pairs->133, ..., 127 pairs->255.
802  int32_t numPairs = (length + 1) / 2;
803  uint32_t primary = numericPrimary | ((132 - 4 + numPairs) << 16);
804  // Find the length without trailing 00 pairs.
805  while(digits[length - 1] == 0 && digits[length - 2] == 0) {
806  length -= 2;
807  }
808  // Read the first pair.
809  uint32_t pair;
810  int32_t pos;
811  if(length & 1) {
812  // Only "half a pair" if we have an odd number of digits.
813  pair = digits[0];
814  pos = 1;
815  } else {
816  pair = digits[0] * 10 + digits[1];
817  pos = 2;
818  }
819  pair = 11 + 2 * pair;
820  // Add the pairs of digits between pos and length.
821  int32_t shift = 8;
822  while(pos < length) {
823  if(shift == 0) {
824  // Every three pairs/bytes we need to store a 4-byte-primary CE
825  // and start with a new CE with the '0' primary lead byte.
826  primary |= pair;
828  primary = numericPrimary;
829  shift = 16;
830  } else {
831  primary |= pair << shift;
832  shift -= 8;
833  }
834  pair = 11 + 2 * (digits[pos] * 10 + digits[pos + 1]);
835  pos += 2;
836  }
837  primary |= (pair - 1) << shift;
839 }
840 
841 int64_t
843  if(ceBuffer.length > 0) {
844  // Return the previous buffered CE.
845  return ceBuffer.get(--ceBuffer.length);
846  }
847  offsets.removeAllElements();
848  int32_t limitOffset = getOffset();
850  if(c < 0) { return Collation::NO_CE; }
852  return previousCEUnsafe(c, offsets, errorCode);
853  }
854  // Simple, safe-backwards iteration:
855  // Get a CE going backwards, handle prefixes but no contractions.
856  uint32_t ce32 = data->getCE32(c);
857  const CollationData *d;
858  if(ce32 == Collation::FALLBACK_CE32) {
859  d = data->base;
860  ce32 = d->getCE32(c);
861  } else {
862  d = data;
863  }
865  return Collation::ceFromCE32(ce32);
866  }
867  appendCEsFromCE32(d, c, ce32, FALSE, errorCode);
868  if(U_SUCCESS(errorCode)) {
869  if(ceBuffer.length > 1) {
870  offsets.addElement(getOffset(), errorCode);
871  // For an expansion, the offset of each non-initial CE is the limit offset,
872  // consistent with forward iteration.
873  while(offsets.size() <= ceBuffer.length) {
874  offsets.addElement(limitOffset, errorCode);
875  }
876  }
877  return ceBuffer.get(--ceBuffer.length);
878  } else {
880  }
881 }
882 
883 int64_t
885  // We just move through the input counting safe and unsafe code points
886  // without collecting the unsafe-backward substring into a buffer and
887  // switching to it.
888  // This is to keep the logic simple. Otherwise we would have to handle
889  // prefix matching going before the backward buffer, switching
890  // to iteration and back, etc.
891  // In the most important case of iterating over a normal string,
892  // reading from the string itself is already maximally fast.
893  // The only drawback there is that after getting the CEs we always
894  // skip backward to the safe character rather than switching out
895  // of a backwardBuffer.
896  // But this should not be the common case for previousCE(),
897  // and correctness and maintainability are more important than
898  // complex optimizations.
899  // Find the first safe character before c.
900  int32_t numBackward = 1;
901  while((c = previousCodePoint(errorCode)) >= 0) {
902  ++numBackward;
903  if(!data->isUnsafeBackward(c, isNumeric)) {
904  break;
905  }
906  }
907  // Set the forward iteration limit.
908  // Note: This counts code points.
909  // We cannot enforce a limit in the middle of a surrogate pair or similar.
910  numCpFwd = numBackward;
911  // Reset the forward iterator.
912  cesIndex = 0;
913  U_ASSERT(ceBuffer.length == 0);
914  // Go forward and collect the CEs.
916  while(numCpFwd > 0) {
917  // nextCE() normally reads one code point.
918  // Contraction matching and digit specials read more and check numCpFwd.
919  --numCpFwd;
920  // Append one or more CEs to the ceBuffer.
923  // No need to loop for getting each expansion CE from nextCE().
925  // However, we need to write an offset for each CE.
926  // This is for CollationElementIterator::getOffset() to return
927  // intermediate offsets from the unsafe-backwards segment.
928  U_ASSERT(offsets.size() < ceBuffer.length);
929  offsets.addElement(offset, errorCode);
930  // For an expansion, the offset of each non-initial CE is the limit offset,
931  // consistent with forward iteration.
932  offset = getOffset();
933  while(offsets.size() < ceBuffer.length) {
934  offsets.addElement(offset, errorCode);
935  }
936  }
937  U_ASSERT(offsets.size() == ceBuffer.length);
938  // End offset corresponding to just after the unsafe-backwards segment.
939  offsets.addElement(offset, errorCode);
940  // Reset the forward iteration limit
941  // and move backward to before the segment for which we fetched CEs.
942  numCpFwd = -1;
943  backwardNumCodePoints(numBackward, errorCode);
944  // Use the collected CEs and return the last one.
945  cesIndex = 0; // Avoid cesIndex > ceBuffer.length when that gets decremented.
946  if(U_SUCCESS(errorCode)) {
947  return ceBuffer.get(--ceBuffer.length);
948  } else {
950  }
951 }
952 
954 
955 #endif // !UCONFIG_NO_COLLATION
q
Definition: afm2pl.c:2287
#define match
Definition: aptex-macros.h:359
static UBool mayHaveLccc(UChar32 c)
Definition: collationfcd.h:83
void append(int64_t ce, UErrorCode &errorCode)
UBool ensureAppendCapacity(int32_t appCap, UErrorCode &errorCode)
int64_t set(int32_t i, int64_t ce)
int64_t get(int32_t i) const
int64_t previousCE(UVector32 &offsets, UErrorCode &errorCode)
const UTrie2 * trie
virtual UBool operator==(const CollationIterator &other) const
int64_t nextCEFromCE32(const CollationData *d, UChar32 c, uint32_t ce32, UErrorCode &errorCode)
virtual void forwardNumCodePoints(int32_t num, UErrorCode &errorCode)=0
int64_t nextCE(UErrorCode &errorCode)
virtual UBool foundNULTerminator()
uint32_t nextCE32FromContraction(const CollationData *d, uint32_t contractionCE32, const UChar *p, uint32_t ce32, UChar32 c, UErrorCode &errorCode)
virtual UChar32 previousCodePoint(UErrorCode &errorCode)=0
virtual uint32_t handleNextCE32(UChar32 &c, UErrorCode &errorCode)
CollationIterator(const CollationData *d, UBool numeric)
int64_t previousCEUnsafe(UChar32 c, UVector32 &offsets, UErrorCode &errorCode)
virtual void backwardNumCodePoints(int32_t num, UErrorCode &errorCode)=0
virtual UChar handleGetTrailSurrogate()
SkippedState * skipped
const CollationData * data
void appendNumericSegmentCEs(const char *digits, int32_t length, UErrorCode &errorCode)
virtual uint32_t getDataCE32(UChar32 c) const
int32_t fetchCEs(UErrorCode &errorCode)
virtual int32_t getOffset() const =0
UChar32 nextSkippedCodePoint(UErrorCode &errorCode)
virtual UBool forbidSurrogateCodePoints() const
void appendCEsFromCE32(const CollationData *d, UChar32 c, uint32_t ce32, UBool forward, UErrorCode &errorCode)
void appendNumericCEs(uint32_t ce32, UBool forward, UErrorCode &errorCode)
uint32_t getCE32FromPrefix(const CollationData *d, uint32_t ce32, UErrorCode &errorCode)
virtual uint32_t getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode)
void backwardNumSkipped(int32_t n, UErrorCode &errorCode)
uint32_t nextCE32FromDiscontiguousContraction(const CollationData *d, UCharsTrie &suffixes, uint32_t ce32, int32_t lookAhead, UChar32 c, UErrorCode &errorCode)
virtual UChar32 nextCodePoint(UErrorCode &errorCode)=0
static const uint32_t LEAD_ALL_FALLBACK
Definition: collation.h:306
static const uint32_t HANGUL_NO_SPECIAL_JAMO
Definition: collation.h:303
static int64_t ceFromLongSecondaryCE32(uint32_t ce32)
Definition: collation.h:323
static const uint32_t UNASSIGNED_CE32
Definition: collation.h:117
static int64_t latinCE0FromCE32(uint32_t ce32)
Definition: collation.h:386
static int64_t unassignedCEFromCodePoint(UChar32 c)
Definition: collation.h:489
static int32_t tagFromCE32(uint32_t ce32)
Definition: collation.h:340
static UBool isSpecialCE32(uint32_t ce32)
Definition: collation.h:336
static const uint32_t CONTRACT_NEXT_CCC
Definition: collation.h:298
static const uint32_t CONTRACT_TRAILING_CCC
Definition: collation.h:300
static const uint32_t LEAD_ALL_UNASSIGNED
Definition: collation.h:305
static const uint32_t NO_CE32
Definition: collation.h:119
static const uint32_t FALLBACK_CE32
Definition: collation.h:111
static char digitFromCE32(uint32_t ce32)
Definition: collation.h:415
static const uint32_t LEAD_TYPE_MASK
Definition: collation.h:308
static int64_t ceFromSimpleCE32(uint32_t ce32)
Definition: collation.h:420
static UBool isSimpleOrLongCE32(uint32_t ce32)
Definition: collation.h:352
static int64_t makeCE(uint32_t p)
Definition: collation.h:446
static UBool hasCE32Tag(uint32_t ce32, int32_t tag)
Definition: collation.h:344
static int32_t lengthFromCE32(uint32_t ce32)
Definition: collation.h:408
static const uint32_t FFFD_CE32
Definition: collation.h:103
static int64_t ceFromCE32(uint32_t ce32)
Definition: collation.h:427
static int64_t latinCE1FromCE32(uint32_t ce32)
Definition: collation.h:394
static const int64_t NO_CE
Definition: collation.h:124
static int64_t ceFromLongPrimaryCE32(uint32_t ce32)
Definition: collation.h:316
static int32_t indexFromCE32(uint32_t ce32)
Definition: collation.h:401
static const uint32_t NO_CE_PRIMARY
Definition: collation.h:122
@ IMPLICIT_TAG
Definition: collation.h:274
@ PREFIX_TAG
Definition: collation.h:220
@ CONTRACTION_TAG
Definition: collation.h:229
@ FALLBACK_TAG
Definition: collation.h:164
@ LONG_SECONDARY_TAG
Definition: collation.h:175
@ OFFSET_TAG
Definition: collation.h:269
@ LATIN_EXPANSION_TAG
Definition: collation.h:189
@ EXPANSION_TAG
Definition: collation.h:201
@ HANGUL_TAG
Definition: collation.h:248
@ LONG_PRIMARY_TAG
Definition: collation.h:169
@ BUILDER_DATA_TAG
Definition: collation.h:214
@ EXPANSION32_TAG
Definition: collation.h:195
@ LEAD_SURROGATE_TAG
Definition: collation.h:257
@ RESERVED_TAG_3
Definition: collation.h:182
static const uint32_t CONTRACT_SINGLE_CP_NO_MATCH
Definition: collation.h:296
UnicodeString newBuffer
UCharsTrie::State state
UBool hasNext() const
UBool isEmpty() const
void skip(UChar32 c)
void setFirstSkipped(UChar32 c)
void saveTrieState(const UCharsTrie &trie)
UnicodeString oldBuffer
void resetToTrieState(UCharsTrie &trie) const
int32_t backwardNumCodePoints(int32_t n)
void addElement(int32_t elem, UErrorCode &status)
Definition: uvectr32.h:228
int32_t size(void) const
Definition: uvectr32.h:255
void removeAllElements()
Definition: uvectr32.cpp:168
#define n
Definition: t4ht.c:1290
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
int v
Definition: dviconv.c:10
char * digit
Definition: io.c:63
#define shift
Definition: exp3.c:154
static void
Definition: fpif.c:118
#define t
Definition: afcover.h:96
#define c(n)
Definition: gpos-common.c:150
#define d(n)
Definition: gpos-common.c:151
unsigned char UChar
Definition: bzip2.c:163
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p
Definition: afcover.h:72
small capitals from c petite p scientific i
Definition: afcover.h:80
enum State_ State
unsigned short uint16_t
Definition: stdint.h:79
signed __int64 int64_t
Definition: stdint.h:89
unsigned int uint32_t
Definition: stdint.h:80
signed int int32_t
Definition: stdint.h:77
unsigned char uint8_t
Definition: stdint.h:78
const char * suffixes[16]
Definition: agl.c:236
int capacity
Definition: pdfcolor.c:1335
#define length(c)
Definition: ctangleboot.c:65
const int * pos
Definition: combiners.h:905
@ other
Definition: mtxline.h:22
constexpr T && forward(remove_reference_t< T > &t) noexcept
Definition: variant.hpp:390
union value value
Definition: obx.h:44
unsigned digits[12]
Definition: out_routines.c:255
static int offset
Definition: ppmtogif.c:642
#define uint32_t
Definition: stdint.in.h:168
#define uint8_t
Definition: stdint.in.h:154
UBool isUnsafeBackward(UChar32 c, UBool numeric) const
Definition: collationdata.h:81
uint32_t numericPrimary
const CollationData * base
uint32_t getCE32(UChar32 c) const
Definition: collationdata.h:68
static uint32_t readCE32(const UChar *p)
Definition: collationdata.h:97
Definition: utils.c:300
Definition: dvips.h:235
#define U_ASSERT(exp)
Definition: uassert.h:37
C++ API: Trie for mapping Unicode strings (or 16-bit-unit sequences) to integer values.
int32_t UChar32
Definition: umachine.h:467
int8_t UBool
Definition: umachine.h:269
#define U_SENTINEL
Definition: umachine.h:487
Definition: obx.h:51
C API: Helper definitions for dictionary trie APIs.
UStringTrieResult
Definition: ustringtrie.h:35
@ USTRINGTRIE_NO_MATCH
Definition: ustringtrie.h:43
#define USTRINGTRIE_HAS_NEXT(result)
Definition: ustringtrie.h:95
#define USTRINGTRIE_HAS_VALUE(result)
Definition: ustringtrie.h:86
#define U16_GET_SUPPLEMENTARY(lead, trail)
Definition: utf16.h:112
#define U16_IS_LEAD(c)
Definition: utf16.h:59
#define U16_LENGTH(c)
Definition: utf16.h:141
#define U16_IS_TRAIL(c)
Definition: utf16.h:67
#define U_IS_SURROGATE(c)
Definition: utf.h:193
Basic definitions for ICU, for both C and C++ APIs.
UErrorCode
Definition: utypes.h:431
@ U_MEMORY_ALLOCATION_ERROR
Definition: utypes.h:473
@ U_ZERO_ERROR
Definition: utypes.h:465
@ U_INTERNAL_PROGRAM_ERROR
Definition: utypes.h:471
#define U_FAILURE(x)
Definition: utypes.h:735
#define U_SUCCESS(x)
Definition: utypes.h:730
char prefixes[]
Definition: vlna.c:108
#define errorCode
Definition: xmlparse.c:601