1/* GENERATED SOURCE. DO NOT MODIFY. */ 2// © 2016 and later: Unicode, Inc. and others. 3// License & terms of use: http://www.unicode.org/copyright.html#License 4/* 5 ******************************************************************************* 6 * Copyright (C) 2009-2015, International Business Machines Corporation and 7 * others. All Rights Reserved. 8 ******************************************************************************* 9 */ 10 11package android.icu.impl; 12 13import java.io.DataOutputStream; 14import java.io.IOException; 15import java.io.InputStream; 16import java.nio.ByteBuffer; 17import java.nio.ByteOrder; 18import java.util.Iterator; 19import java.util.NoSuchElementException; 20 21 22/** 23 * This is the interface and common implementation of a Unicode Trie2. 24 * It is a kind of compressed table that maps from Unicode code points (0..0x10ffff) 25 * to 16- or 32-bit integer values. It works best when there are ranges of 26 * characters with the same value, which is generally the case with Unicode 27 * character properties. 28 * 29 * This is the second common version of a Unicode trie (hence the name Trie2). 30 * @hide Only a subset of ICU is exposed in Android 31 * 32 */ 33public abstract class Trie2 implements Iterable<Trie2.Range> { 34 35 36 /** 37 * Create a Trie2 from its serialized form. Inverse of utrie2_serialize(). 38 * 39 * Reads from the current position and leaves the buffer after the end of the trie. 40 * 41 * The serialized format is identical between ICU4C and ICU4J, so this function 42 * will work with serialized Trie2s from either. 43 * 44 * The actual type of the returned Trie2 will be either Trie2_16 or Trie2_32, depending 45 * on the width of the data. 46 * 47 * To obtain the width of the Trie2, check the actual class type of the returned Trie2. 48 * Or use the createFromSerialized() function of Trie2_16 or Trie2_32, which will 49 * return only Tries of their specific type/size. 50 * 51 * The serialized Trie2 on the stream may be in either little or big endian byte order. 52 * This allows using serialized Tries from ICU4C without needing to consider the 53 * byte order of the system that created them. 54 * 55 * @param bytes a byte buffer to the serialized form of a UTrie2. 56 * @return An unserialized Trie2, ready for use. 57 * @throws IllegalArgumentException if the stream does not contain a serialized Trie2. 58 * @throws IOException if a read error occurs in the buffer. 59 * 60 */ 61 public static Trie2 createFromSerialized(ByteBuffer bytes) throws IOException { 62 // From ICU4C utrie2_impl.h 63 // * Trie2 data structure in serialized form: 64 // * 65 // * UTrie2Header header; 66 // * uint16_t index[header.index2Length]; 67 // * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] 68 // * @internal 69 // */ 70 // typedef struct UTrie2Header { 71 // /** "Tri2" in big-endian US-ASCII (0x54726932) */ 72 // uint32_t signature; 73 74 // /** 75 // * options bit field: 76 // * 15.. 4 reserved (0) 77 // * 3.. 0 UTrie2ValueBits valueBits 78 // */ 79 // uint16_t options; 80 // 81 // /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */ 82 // uint16_t indexLength; 83 // 84 // /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */ 85 // uint16_t shiftedDataLength; 86 // 87 // /** Null index and data blocks, not shifted. */ 88 // uint16_t index2NullOffset, dataNullOffset; 89 // 90 // /** 91 // * First code point of the single-value range ending with U+10ffff, 92 // * rounded up and then shifted right by UTRIE2_SHIFT_1. 93 // */ 94 // uint16_t shiftedHighStart; 95 // } UTrie2Header; 96 97 ByteOrder outerByteOrder = bytes.order(); 98 try { 99 UTrie2Header header = new UTrie2Header(); 100 101 /* check the signature */ 102 header.signature = bytes.getInt(); 103 switch (header.signature) { 104 case 0x54726932: 105 // The buffer is already set to the trie data byte order. 106 break; 107 case 0x32697254: 108 // Temporarily reverse the byte order. 109 boolean isBigEndian = outerByteOrder == ByteOrder.BIG_ENDIAN; 110 bytes.order(isBigEndian ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN); 111 header.signature = 0x54726932; 112 break; 113 default: 114 throw new IllegalArgumentException("Buffer does not contain a serialized UTrie2"); 115 } 116 117 header.options = bytes.getChar(); 118 header.indexLength = bytes.getChar(); 119 header.shiftedDataLength = bytes.getChar(); 120 header.index2NullOffset = bytes.getChar(); 121 header.dataNullOffset = bytes.getChar(); 122 header.shiftedHighStart = bytes.getChar(); 123 124 // Trie2 data width - 0: 16 bits 125 // 1: 32 bits 126 if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) > 1) { 127 throw new IllegalArgumentException("UTrie2 serialized format error."); 128 } 129 ValueWidth width; 130 Trie2 This; 131 if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) == 0) { 132 width = ValueWidth.BITS_16; 133 This = new Trie2_16(); 134 } else { 135 width = ValueWidth.BITS_32; 136 This = new Trie2_32(); 137 } 138 This.header = header; 139 140 /* get the length values and offsets */ 141 This.indexLength = header.indexLength; 142 This.dataLength = header.shiftedDataLength << UTRIE2_INDEX_SHIFT; 143 This.index2NullOffset = header.index2NullOffset; 144 This.dataNullOffset = header.dataNullOffset; 145 This.highStart = header.shiftedHighStart << UTRIE2_SHIFT_1; 146 This.highValueIndex = This.dataLength - UTRIE2_DATA_GRANULARITY; 147 if (width == ValueWidth.BITS_16) { 148 This.highValueIndex += This.indexLength; 149 } 150 151 // Allocate the Trie2 index array. If the data width is 16 bits, the array also 152 // includes the space for the data. 153 154 int indexArraySize = This.indexLength; 155 if (width == ValueWidth.BITS_16) { 156 indexArraySize += This.dataLength; 157 } 158 159 /* Read in the index */ 160 This.index = ICUBinary.getChars(bytes, indexArraySize, 0); 161 162 /* Read in the data. 16 bit data goes in the same array as the index. 163 * 32 bit data goes in its own separate data array. 164 */ 165 if (width == ValueWidth.BITS_16) { 166 This.data16 = This.indexLength; 167 } else { 168 This.data32 = ICUBinary.getInts(bytes, This.dataLength, 0); 169 } 170 171 switch(width) { 172 case BITS_16: 173 This.data32 = null; 174 This.initialValue = This.index[This.dataNullOffset]; 175 This.errorValue = This.index[This.data16+UTRIE2_BAD_UTF8_DATA_OFFSET]; 176 break; 177 case BITS_32: 178 This.data16=0; 179 This.initialValue = This.data32[This.dataNullOffset]; 180 This.errorValue = This.data32[UTRIE2_BAD_UTF8_DATA_OFFSET]; 181 break; 182 default: 183 throw new IllegalArgumentException("UTrie2 serialized format error."); 184 } 185 186 return This; 187 } finally { 188 bytes.order(outerByteOrder); 189 } 190 } 191 192 /** 193 * Get the UTrie version from an InputStream containing the serialized form 194 * of either a Trie (version 1) or a Trie2 (version 2). 195 * 196 * @param is an InputStream containing the serialized form 197 * of a UTrie, version 1 or 2. The stream must support mark() and reset(). 198 * The position of the input stream will be left unchanged. 199 * @param littleEndianOk If FALSE, only big-endian (Java native) serialized forms are recognized. 200 * If TRUE, little-endian serialized forms are recognized as well. 201 * @return the Trie version of the serialized form, or 0 if it is not 202 * recognized as a serialized UTrie 203 * @throws IOException on errors in reading from the input stream. 204 */ 205 public static int getVersion(InputStream is, boolean littleEndianOk) throws IOException { 206 if (! is.markSupported()) { 207 throw new IllegalArgumentException("Input stream must support mark()."); 208 } 209 is.mark(4); 210 byte sig[] = new byte[4]; 211 int read = is.read(sig); 212 is.reset(); 213 214 if (read != sig.length) { 215 return 0; 216 } 217 218 if (sig[0]=='T' && sig[1]=='r' && sig[2]=='i' && sig[3]=='e') { 219 return 1; 220 } 221 if (sig[0]=='T' && sig[1]=='r' && sig[2]=='i' && sig[3]=='2') { 222 return 2; 223 } 224 if (littleEndianOk) { 225 if (sig[0]=='e' && sig[1]=='i' && sig[2]=='r' && sig[3]=='T') { 226 return 1; 227 } 228 if (sig[0]=='2' && sig[1]=='i' && sig[2]=='r' && sig[3]=='T') { 229 return 2; 230 } 231 } 232 return 0; 233 } 234 235 /** 236 * Get the value for a code point as stored in the Trie2. 237 * 238 * @param codePoint the code point 239 * @return the value 240 */ 241 abstract public int get(int codePoint); 242 243 244 /** 245 * Get the trie value for a UTF-16 code unit. 246 * 247 * A Trie2 stores two distinct values for input in the lead surrogate 248 * range, one for lead surrogates, which is the value that will be 249 * returned by this function, and a second value that is returned 250 * by Trie2.get(). 251 * 252 * For code units outside of the lead surrogate range, this function 253 * returns the same result as Trie2.get(). 254 * 255 * This function, together with the alternate value for lead surrogates, 256 * makes possible very efficient processing of UTF-16 strings without 257 * first converting surrogate pairs to their corresponding 32 bit code point 258 * values. 259 * 260 * At build-time, enumerate the contents of the Trie2 to see if there 261 * is non-trivial (non-initialValue) data for any of the supplementary 262 * code points associated with a lead surrogate. 263 * If so, then set a special (application-specific) value for the 264 * lead surrogate code _unit_, with Trie2Writable.setForLeadSurrogateCodeUnit(). 265 * 266 * At runtime, use Trie2.getFromU16SingleLead(). If there is non-trivial 267 * data and the code unit is a lead surrogate, then check if a trail surrogate 268 * follows. If so, assemble the supplementary code point and look up its value 269 * with Trie2.get(); otherwise reset the lead 270 * surrogate's value or do a code point lookup for it. 271 * 272 * If there is only trivial data for lead and trail surrogates, then processing 273 * can often skip them. For example, in normalization or case mapping 274 * all characters that do not have any mappings are simply copied as is. 275 * 276 * @param c the code point or lead surrogate value. 277 * @return the value 278 */ 279 abstract public int getFromU16SingleLead(char c); 280 281 282 /** 283 * Equals function. Two Tries are equal if their contents are equal. 284 * The type need not be the same, so a Trie2Writable will be equal to 285 * (read-only) Trie2_16 or Trie2_32 so long as they are storing the same values. 286 * 287 */ 288 @Override 289 public final boolean equals(Object other) { 290 if(!(other instanceof Trie2)) { 291 return false; 292 } 293 Trie2 OtherTrie = (Trie2)other; 294 Range rangeFromOther; 295 296 Iterator<Trie2.Range> otherIter = OtherTrie.iterator(); 297 for (Trie2.Range rangeFromThis: this) { 298 if (otherIter.hasNext() == false) { 299 return false; 300 } 301 rangeFromOther = otherIter.next(); 302 if (!rangeFromThis.equals(rangeFromOther)) { 303 return false; 304 } 305 } 306 if (otherIter.hasNext()) { 307 return false; 308 } 309 310 if (errorValue != OtherTrie.errorValue || 311 initialValue != OtherTrie.initialValue) { 312 return false; 313 } 314 315 return true; 316 } 317 318 319 @Override 320 public int hashCode() { 321 if (fHash == 0) { 322 int hash = initHash(); 323 for (Range r: this) { 324 hash = hashInt(hash, r.hashCode()); 325 } 326 if (hash == 0) { 327 hash = 1; 328 } 329 fHash = hash; 330 } 331 return fHash; 332 } 333 334 /** 335 * When iterating over the contents of a Trie2, Elements of this type are produced. 336 * The iterator will return one item for each contiguous range of codepoints having the same value. 337 * 338 * When iterating, the same Trie2EnumRange object will be reused and returned for each range. 339 * If you need to retain complete iteration results, clone each returned Trie2EnumRange, 340 * or save the range in some other way, before advancing to the next iteration step. 341 */ 342 public static class Range { 343 public int startCodePoint; 344 public int endCodePoint; // Inclusive. 345 public int value; 346 public boolean leadSurrogate; 347 348 @Override 349 public boolean equals(Object other) { 350 if (other == null || !(other.getClass().equals(getClass()))) { 351 return false; 352 } 353 Range tother = (Range)other; 354 return this.startCodePoint == tother.startCodePoint && 355 this.endCodePoint == tother.endCodePoint && 356 this.value == tother.value && 357 this.leadSurrogate == tother.leadSurrogate; 358 } 359 360 361 @Override 362 public int hashCode() { 363 int h = initHash(); 364 h = hashUChar32(h, startCodePoint); 365 h = hashUChar32(h, endCodePoint); 366 h = hashInt(h, value); 367 h = hashByte(h, leadSurrogate? 1: 0); 368 return h; 369 } 370 } 371 372 373 /** 374 * Create an iterator over the value ranges in this Trie2. 375 * Values from the Trie2 are not remapped or filtered, but are returned as they 376 * are stored in the Trie2. 377 * 378 * @return an Iterator 379 */ 380 @Override 381 public Iterator<Range> iterator() { 382 return iterator(defaultValueMapper); 383 } 384 385 private static ValueMapper defaultValueMapper = new ValueMapper() { 386 @Override 387 public int map(int in) { 388 return in; 389 } 390 }; 391 392 /** 393 * Create an iterator over the value ranges from this Trie2. 394 * Values from the Trie2 are passed through a caller-supplied remapping function, 395 * and it is the remapped values that determine the ranges that 396 * will be produced by the iterator. 397 * 398 * 399 * @param mapper provides a function to remap values obtained from the Trie2. 400 * @return an Iterator 401 */ 402 public Iterator<Range> iterator(ValueMapper mapper) { 403 return new Trie2Iterator(mapper); 404 } 405 406 407 /** 408 * Create an iterator over the Trie2 values for the 1024=0x400 code points 409 * corresponding to a given lead surrogate. 410 * For example, for the lead surrogate U+D87E it will enumerate the values 411 * for [U+2F800..U+2FC00[. 412 * Used by data builder code that sets special lead surrogate code unit values 413 * for optimized UTF-16 string processing. 414 * 415 * Do not modify the Trie2 during the iteration. 416 * 417 * Except for the limited code point range, this functions just like Trie2.iterator(). 418 * 419 */ 420 public Iterator<Range> iteratorForLeadSurrogate(char lead, ValueMapper mapper) { 421 return new Trie2Iterator(lead, mapper); 422 } 423 424 /** 425 * Create an iterator over the Trie2 values for the 1024=0x400 code points 426 * corresponding to a given lead surrogate. 427 * For example, for the lead surrogate U+D87E it will enumerate the values 428 * for [U+2F800..U+2FC00[. 429 * Used by data builder code that sets special lead surrogate code unit values 430 * for optimized UTF-16 string processing. 431 * 432 * Do not modify the Trie2 during the iteration. 433 * 434 * Except for the limited code point range, this functions just like Trie2.iterator(). 435 * 436 */ 437 public Iterator<Range> iteratorForLeadSurrogate(char lead) { 438 return new Trie2Iterator(lead, defaultValueMapper); 439 } 440 441 /** 442 * When iterating over the contents of a Trie2, an instance of TrieValueMapper may 443 * be used to remap the values from the Trie2. The remapped values will be used 444 * both in determining the ranges of codepoints and as the value to be returned 445 * for each range. 446 * 447 * Example of use, with an anonymous subclass of TrieValueMapper: 448 * 449 * 450 * ValueMapper m = new ValueMapper() { 451 * int map(int in) {return in & 0x1f;}; 452 * } 453 * for (Iterator<Trie2EnumRange> iter = trie.iterator(m); i.hasNext(); ) { 454 * Trie2EnumRange r = i.next(); 455 * ... // Do something with the range r. 456 * } 457 * 458 */ 459 public interface ValueMapper { 460 public int map(int originalVal); 461 } 462 463 464 /** 465 * Serialize a trie2 Header and Index onto an OutputStream. This is 466 * common code used for both the Trie2_16 and Trie2_32 serialize functions. 467 * @param dos the stream to which the serialized Trie2 data will be written. 468 * @return the number of bytes written. 469 */ 470 protected int serializeHeader(DataOutputStream dos) throws IOException { 471 // Write the header. It is already set and ready to use, having been 472 // created when the Trie2 was unserialized or when it was frozen. 473 int bytesWritten = 0; 474 475 dos.writeInt(header.signature); 476 dos.writeShort(header.options); 477 dos.writeShort(header.indexLength); 478 dos.writeShort(header.shiftedDataLength); 479 dos.writeShort(header.index2NullOffset); 480 dos.writeShort(header.dataNullOffset); 481 dos.writeShort(header.shiftedHighStart); 482 bytesWritten += 16; 483 484 // Write the index 485 int i; 486 for (i=0; i< header.indexLength; i++) { 487 dos.writeChar(index[i]); 488 } 489 bytesWritten += header.indexLength; 490 return bytesWritten; 491 } 492 493 494 /** 495 * Struct-like class for holding the results returned by a UTrie2 CharSequence iterator. 496 * The iteration walks over a CharSequence, and for each Unicode code point therein 497 * returns the character and its associated Trie2 value. 498 */ 499 public static class CharSequenceValues { 500 /** string index of the current code point. */ 501 public int index; 502 /** The code point at index. */ 503 public int codePoint; 504 /** The Trie2 value for the current code point */ 505 public int value; 506 } 507 508 509 /** 510 * Create an iterator that will produce the values from the Trie2 for 511 * the sequence of code points in an input text. 512 * 513 * @param text A text string to be iterated over. 514 * @param index The starting iteration position within the input text. 515 * @return the CharSequenceIterator 516 */ 517 public CharSequenceIterator charSequenceIterator(CharSequence text, int index) { 518 return new CharSequenceIterator(text, index); 519 } 520 521 // TODO: Survey usage of the equivalent of CharSequenceIterator in ICU4C 522 // and if there is none, remove it from here. 523 // Don't waste time testing and maintaining unused code. 524 525 /** 526 * An iterator that operates over an input CharSequence, and for each Unicode code point 527 * in the input returns the associated value from the Trie2. 528 * 529 * The iterator can move forwards or backwards, and can be reset to an arbitrary index. 530 * 531 * Note that Trie2_16 and Trie2_32 subclass Trie2.CharSequenceIterator. This is done 532 * only for performance reasons. It does require that any changes made here be propagated 533 * into the corresponding code in the subclasses. 534 */ 535 public class CharSequenceIterator implements Iterator<CharSequenceValues> { 536 /** 537 * Internal constructor. 538 */ 539 CharSequenceIterator(CharSequence t, int index) { 540 text = t; 541 textLength = text.length(); 542 set(index); 543 } 544 545 private CharSequence text; 546 private int textLength; 547 private int index; 548 private Trie2.CharSequenceValues fResults = new Trie2.CharSequenceValues(); 549 550 551 public void set(int i) { 552 if (i < 0 || i > textLength) { 553 throw new IndexOutOfBoundsException(); 554 } 555 index = i; 556 } 557 558 559 @Override 560 public final boolean hasNext() { 561 return index<textLength; 562 } 563 564 565 public final boolean hasPrevious() { 566 return index>0; 567 } 568 569 570 @Override 571 public Trie2.CharSequenceValues next() { 572 int c = Character.codePointAt(text, index); 573 int val = get(c); 574 575 fResults.index = index; 576 fResults.codePoint = c; 577 fResults.value = val; 578 index++; 579 if (c >= 0x10000) { 580 index++; 581 } 582 return fResults; 583 } 584 585 586 public Trie2.CharSequenceValues previous() { 587 int c = Character.codePointBefore(text, index); 588 int val = get(c); 589 index--; 590 if (c >= 0x10000) { 591 index--; 592 } 593 fResults.index = index; 594 fResults.codePoint = c; 595 fResults.value = val; 596 return fResults; 597 } 598 599 /** 600 * Iterator.remove() is not supported by Trie2.CharSequenceIterator. 601 * @throws UnsupportedOperationException Always thrown because this operation is not supported 602 * @see java.util.Iterator#remove() 603 */ 604 @Override 605 public void remove() { 606 throw new UnsupportedOperationException("Trie2.CharSequenceIterator does not support remove()."); 607 } 608 } 609 610 611 //-------------------------------------------------------------------------------- 612 // 613 // Below this point are internal implementation items. No further public API. 614 // 615 //-------------------------------------------------------------------------------- 616 617 618 /** 619 * Selectors for the width of a UTrie2 data value. 620 */ 621 enum ValueWidth { 622 BITS_16, 623 BITS_32 624 } 625 626 /** 627 * Trie2 data structure in serialized form: 628 * 629 * UTrie2Header header; 630 * uint16_t index[header.index2Length]; 631 * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] 632 * 633 * For Java, this is read from the stream into an instance of UTrie2Header. 634 * (The C version just places a struct over the raw serialized data.) 635 * 636 * @hide draft / provisional / internal are hidden on Android 637 */ 638 static class UTrie2Header { 639 /** "Tri2" in big-endian US-ASCII (0x54726932) */ 640 int signature; 641 642 /** 643 * options bit field (uint16_t): 644 * 15.. 4 reserved (0) 645 * 3.. 0 UTrie2ValueBits valueBits 646 */ 647 int options; 648 649 /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH (uint16_t) */ 650 int indexLength; 651 652 /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT (uint16_t) */ 653 int shiftedDataLength; 654 655 /** Null index and data blocks, not shifted. (uint16_t) */ 656 int index2NullOffset, dataNullOffset; 657 658 /** 659 * First code point of the single-value range ending with U+10ffff, 660 * rounded up and then shifted right by UTRIE2_SHIFT_1. (uint16_t) 661 */ 662 int shiftedHighStart; 663 } 664 665 // 666 // Data members of UTrie2. 667 // 668 UTrie2Header header; 669 char index[]; // Index array. Includes data for 16 bit Tries. 670 int data16; // Offset to data portion of the index array, if 16 bit data. 671 // zero if 32 bit data. 672 int data32[]; // NULL if 16b data is used via index 673 674 int indexLength; 675 int dataLength; 676 int index2NullOffset; // 0xffff if there is no dedicated index-2 null block 677 int initialValue; 678 679 /** Value returned for out-of-range code points and illegal UTF-8. */ 680 int errorValue; 681 682 /* Start of the last range which ends at U+10ffff, and its value. */ 683 int highStart; 684 int highValueIndex; 685 686 int dataNullOffset; 687 688 int fHash; // Zero if not yet computed. 689 // Shared by Trie2Writable, Trie2_16, Trie2_32. 690 // Thread safety: if two racing threads compute 691 // the same hash on a frozen Trie2, no damage is done. 692 693 694 /** 695 * Trie2 constants, defining shift widths, index array lengths, etc. 696 * 697 * These are needed for the runtime macros but users can treat these as 698 * implementation details and skip to the actual public API further below. 699 */ 700 701 static final int UTRIE2_OPTIONS_VALUE_BITS_MASK=0x000f; 702 703 704 /** Shift size for getting the index-1 table offset. */ 705 static final int UTRIE2_SHIFT_1=6+5; 706 707 /** Shift size for getting the index-2 table offset. */ 708 static final int UTRIE2_SHIFT_2=5; 709 710 /** 711 * Difference between the two shift sizes, 712 * for getting an index-1 offset from an index-2 offset. 6=11-5 713 */ 714 static final int UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2; 715 716 /** 717 * Number of index-1 entries for the BMP. 32=0x20 718 * This part of the index-1 table is omitted from the serialized form. 719 */ 720 static final int UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1; 721 722 /** Number of code points per index-1 table entry. 2048=0x800 */ 723 static final int UTRIE2_CP_PER_INDEX_1_ENTRY=1<<UTRIE2_SHIFT_1; 724 725 /** Number of entries in an index-2 block. 64=0x40 */ 726 static final int UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2; 727 728 /** Mask for getting the lower bits for the in-index-2-block offset. */ 729 static final int UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1; 730 731 /** Number of entries in a data block. 32=0x20 */ 732 static final int UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2; 733 734 /** Mask for getting the lower bits for the in-data-block offset. */ 735 static final int UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1; 736 737 /** 738 * Shift size for shifting left the index array values. 739 * Increases possible data size with 16-bit index values at the cost 740 * of compactability. 741 * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY. 742 */ 743 static final int UTRIE2_INDEX_SHIFT=2; 744 745 /** The alignment size of a data block. Also the granularity for compaction. */ 746 static final int UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT; 747 748 /* Fixed layout of the first part of the index array. ------------------- */ 749 750 /** 751 * The BMP part of the index-2 table is fixed and linear and starts at offset 0. 752 * Length=2048=0x800=0x10000>>UTRIE2_SHIFT_2. 753 */ 754 static final int UTRIE2_INDEX_2_OFFSET=0; 755 756 /** 757 * The part of the index-2 table for U+D800..U+DBFF stores values for 758 * lead surrogate code _units_ not code _points_. 759 * Values for lead surrogate code _points_ are indexed with this portion of the table. 760 * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.) 761 */ 762 static final int UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2; 763 static final int UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2; 764 765 /** Count the lengths of both BMP pieces. 2080=0x820 */ 766 static final int UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH; 767 768 /** 769 * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820. 770 * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2. 771 */ 772 static final int UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH; 773 static final int UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6; /* U+0800 is the first code point after 2-byte UTF-8 */ 774 775 /** 776 * The index-1 table, only used for supplementary code points, at offset 2112=0x840. 777 * Variable length, for code points up to highStart, where the last single-value range starts. 778 * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1. 779 * (For 0x100000 supplementary code points U+10000..U+10ffff.) 780 * 781 * The part of the index-2 table for supplementary code points starts 782 * after this index-1 table. 783 * 784 * Both the index-1 table and the following part of the index-2 table 785 * are omitted completely if there is only BMP data. 786 */ 787 static final int UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH; 788 static final int UTRIE2_MAX_INDEX_1_LENGTH=0x100000>>UTRIE2_SHIFT_1; 789 790 /* 791 * Fixed layout of the first part of the data array. ----------------------- 792 * Starts with 4 blocks (128=0x80 entries) for ASCII. 793 */ 794 795 /** 796 * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80. 797 * Used with linear access for single bytes 0..0xbf for simple error handling. 798 * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH. 799 */ 800 static final int UTRIE2_BAD_UTF8_DATA_OFFSET=0x80; 801 802 /** The start of non-linear-ASCII data blocks, at offset 192=0xc0. */ 803 static final int UTRIE2_DATA_START_OFFSET=0xc0; 804 805 /* Building a Trie2 ---------------------------------------------------------- */ 806 807 /* 808 * These definitions are mostly needed by utrie2_builder.c, but also by 809 * utrie2_get32() and utrie2_enum(). 810 */ 811 812 /* 813 * At build time, leave a gap in the index-2 table, 814 * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table 815 * and the supplementary index-1 table. 816 * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting. 817 */ 818 static final int UNEWTRIE2_INDEX_GAP_OFFSET = UTRIE2_INDEX_2_BMP_LENGTH; 819 static final int UNEWTRIE2_INDEX_GAP_LENGTH = 820 ((UTRIE2_UTF8_2B_INDEX_2_LENGTH + UTRIE2_MAX_INDEX_1_LENGTH) + UTRIE2_INDEX_2_MASK) & 821 ~UTRIE2_INDEX_2_MASK; 822 823 /** 824 * Maximum length of the build-time index-2 array. 825 * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2, 826 * plus the part of the index-2 table for lead surrogate code points, 827 * plus the build-time index gap, 828 * plus the null index-2 block. 829 */ 830 static final int UNEWTRIE2_MAX_INDEX_2_LENGTH= 831 (0x110000>>UTRIE2_SHIFT_2)+ 832 UTRIE2_LSCP_INDEX_2_LENGTH+ 833 UNEWTRIE2_INDEX_GAP_LENGTH+ 834 UTRIE2_INDEX_2_BLOCK_LENGTH; 835 836 static final int UNEWTRIE2_INDEX_1_LENGTH = 0x110000>>UTRIE2_SHIFT_1; 837 838 /** 839 * Maximum length of the build-time data array. 840 * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block, 841 * plus values for the 0x400 surrogate code units. 842 */ 843 static final int UNEWTRIE2_MAX_DATA_LENGTH = (0x110000+0x40+0x40+0x400); 844 845 846 847 /** 848 * Implementation class for an iterator over a Trie2. 849 * 850 * Iteration over a Trie2 first returns all of the ranges that are indexed by code points, 851 * then returns the special alternate values for the lead surrogates 852 * 853 * @hide draft / provisional / internal are hidden on Android 854 */ 855 class Trie2Iterator implements Iterator<Range> { 856 // The normal constructor that configures the iterator to cover the complete 857 // contents of the Trie2 858 Trie2Iterator(ValueMapper vm) { 859 mapper = vm; 860 nextStart = 0; 861 limitCP = 0x110000; 862 doLeadSurrogates = true; 863 } 864 865 // An alternate constructor that configures the iterator to cover only the 866 // code points corresponding to a particular Lead Surrogate value. 867 Trie2Iterator(char leadSurrogate, ValueMapper vm) { 868 if (leadSurrogate < 0xd800 || leadSurrogate > 0xdbff) { 869 throw new IllegalArgumentException("Bad lead surrogate value."); 870 } 871 mapper = vm; 872 nextStart = (leadSurrogate - 0xd7c0) << 10; 873 limitCP = nextStart + 0x400; 874 doLeadSurrogates = false; // Do not iterate over lead the special lead surrogate 875 // values after completing iteration over code points. 876 } 877 878 /** 879 * The main next() function for Trie2 iterators 880 * 881 */ 882 @Override 883 public Range next() { 884 if (!hasNext()) { 885 throw new NoSuchElementException(); 886 } 887 if (nextStart >= limitCP) { 888 // Switch over from iterating normal code point values to 889 // doing the alternate lead-surrogate values. 890 doingCodePoints = false; 891 nextStart = 0xd800; 892 } 893 int endOfRange = 0; 894 int val = 0; 895 int mappedVal = 0; 896 897 if (doingCodePoints) { 898 // Iteration over code point values. 899 val = get(nextStart); 900 mappedVal = mapper.map(val); 901 endOfRange = rangeEnd(nextStart, limitCP, val); 902 // Loop once for each range in the Trie2 with the same raw (unmapped) value. 903 // Loop continues so long as the mapped values are the same. 904 for (;;) { 905 if (endOfRange >= limitCP-1) { 906 break; 907 } 908 val = get(endOfRange+1); 909 if (mapper.map(val) != mappedVal) { 910 break; 911 } 912 endOfRange = rangeEnd(endOfRange+1, limitCP, val); 913 } 914 } else { 915 // Iteration over the alternate lead surrogate values. 916 val = getFromU16SingleLead((char)nextStart); 917 mappedVal = mapper.map(val); 918 endOfRange = rangeEndLS((char)nextStart); 919 // Loop once for each range in the Trie2 with the same raw (unmapped) value. 920 // Loop continues so long as the mapped values are the same. 921 for (;;) { 922 if (endOfRange >= 0xdbff) { 923 break; 924 } 925 val = getFromU16SingleLead((char)(endOfRange+1)); 926 if (mapper.map(val) != mappedVal) { 927 break; 928 } 929 endOfRange = rangeEndLS((char)(endOfRange+1)); 930 } 931 } 932 returnValue.startCodePoint = nextStart; 933 returnValue.endCodePoint = endOfRange; 934 returnValue.value = mappedVal; 935 returnValue.leadSurrogate = !doingCodePoints; 936 nextStart = endOfRange+1; 937 return returnValue; 938 } 939 940 /** 941 * 942 */ 943 @Override 944 public boolean hasNext() { 945 return doingCodePoints && (doLeadSurrogates || nextStart < limitCP) || nextStart < 0xdc00; 946 } 947 948 @Override 949 public void remove() { 950 throw new UnsupportedOperationException(); 951 } 952 953 954 /** 955 * Find the last lead surrogate in a contiguous range with the 956 * same Trie2 value as the input character. 957 * 958 * Use the alternate Lead Surrogate values from the Trie2, 959 * not the code-point values. 960 * 961 * Note: Trie2_16 and Trie2_32 override this implementation with optimized versions, 962 * meaning that the implementation here is only being used with 963 * Trie2Writable. The code here is logically correct with any type 964 * of Trie2, however. 965 * 966 * @param c The character to begin with. 967 * @return The last contiguous character with the same value. 968 */ 969 private int rangeEndLS(char startingLS) { 970 if (startingLS >= 0xdbff) { 971 return 0xdbff; 972 } 973 974 int c; 975 int val = getFromU16SingleLead(startingLS); 976 for (c = startingLS+1; c <= 0x0dbff; c++) { 977 if (getFromU16SingleLead((char)c) != val) { 978 break; 979 } 980 } 981 return c-1; 982 } 983 984 // 985 // Iteration State Variables 986 // 987 private ValueMapper mapper; 988 private Range returnValue = new Range(); 989 // The starting code point for the next range to be returned. 990 private int nextStart; 991 // The upper limit for the last normal range to be returned. Normally 0x110000, but 992 // may be lower when iterating over the code points for a single lead surrogate. 993 private int limitCP; 994 995 // True while iterating over the the Trie2 values for code points. 996 // False while iterating over the alternate values for lead surrogates. 997 private boolean doingCodePoints = true; 998 999 // True if the iterator should iterate the special values for lead surrogates in 1000 // addition to the normal values for code points. 1001 private boolean doLeadSurrogates = true; 1002 } 1003 1004 /** 1005 * Find the last character in a contiguous range of characters with the 1006 * same Trie2 value as the input character. 1007 * 1008 * @param c The character to begin with. 1009 * @return The last contiguous character with the same value. 1010 */ 1011 int rangeEnd(int start, int limitp, int val) { 1012 int c; 1013 int limit = Math.min(highStart, limitp); 1014 1015 for (c = start+1; c < limit; c++) { 1016 if (get(c) != val) { 1017 break; 1018 } 1019 } 1020 if (c >= highStart) { 1021 c = limitp; 1022 } 1023 return c - 1; 1024 } 1025 1026 1027 // 1028 // Hashing implementation functions. FNV hash. Respected public domain algorithm. 1029 // 1030 private static int initHash() { 1031 return 0x811c9DC5; // unsigned 2166136261 1032 } 1033 1034 private static int hashByte(int h, int b) { 1035 h = h * 16777619; 1036 h = h ^ b; 1037 return h; 1038 } 1039 1040 private static int hashUChar32(int h, int c) { 1041 h = Trie2.hashByte(h, c & 255); 1042 h = Trie2.hashByte(h, (c>>8) & 255); 1043 h = Trie2.hashByte(h, c>>16); 1044 return h; 1045 } 1046 1047 private static int hashInt(int h, int i) { 1048 h = Trie2.hashByte(h, i & 255); 1049 h = Trie2.hashByte(h, (i>>8) & 255); 1050 h = Trie2.hashByte(h, (i>>16) & 255); 1051 h = Trie2.hashByte(h, (i>>24) & 255); 1052 return h; 1053 } 1054 1055} 1056