| /* |
| ******************************************************************************* |
| * Copyright (C) 2009, International Business Machines Corporation and * |
| * others. All Rights Reserved. * |
| ******************************************************************************* |
| */ |
| package com.ibm.icu.impl; |
| |
| /** |
| * @author aheninger |
| * |
| * A Trie2Writable is a modifiable, or build-time Trie2. |
| * Functions for reading data from the Trie are all from class Trie2. |
| * |
| */ |
| public class Trie2Writable extends Trie2 { |
| |
| |
| /** |
| * Create a new, empty, writable Trie2. 32-bit data values are used. |
| * |
| * @param initialValueP the initial value that is set for all code points |
| * @param errorValueP the value for out-of-range code points and illegal UTF-8 |
| */ |
| public Trie2Writable(int initialValueP, int errorValueP) { |
| // This constructor corresponds to utrie2_open() in ICU4C. |
| init(initialValueP, errorValueP); |
| } |
| |
| |
| private void init(int initialValueP, int errorValueP) { |
| this.initialValue = initialValueP; |
| this.errorValue = errorValueP; |
| this.highStart = 0x110000; |
| |
| this.data = new int[UNEWTRIE2_INITIAL_DATA_LENGTH]; |
| this.dataCapacity = UNEWTRIE2_INITIAL_DATA_LENGTH; |
| this.initialValue = initialValueP; |
| this.errorValue = errorValueP; |
| this.highStart = 0x110000; |
| this.firstFreeBlock = 0; /* no free block in the list */ |
| this.isCompacted = false; |
| |
| /* |
| * preallocate and reset |
| * - ASCII |
| * - the bad-UTF-8-data block |
| * - the null data block |
| */ |
| int i, j; |
| for(i=0; i<0x80; ++i) { |
| data[i] = initialValue; |
| } |
| for(; i<0xc0; ++i) { |
| data[i] = errorValue; |
| } |
| for(i=UNEWTRIE2_DATA_NULL_OFFSET; i<UNEWTRIE2_DATA_START_OFFSET; ++i) { |
| data[i] = initialValue; |
| } |
| dataNullOffset = UNEWTRIE2_DATA_NULL_OFFSET; |
| dataLength = UNEWTRIE2_DATA_START_OFFSET; |
| |
| /* set the index-2 indexes for the 2=0x80>>UTRIE2_SHIFT_2 ASCII data blocks */ |
| for(i=0, j=0; j<0x80; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) { |
| index2[i]=j; |
| map[i]=1; |
| } |
| |
| /* reference counts for the bad-UTF-8-data block */ |
| for(; j<0xc0; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) { |
| map[i]=0; |
| } |
| |
| /* |
| * Reference counts for the null data block: all blocks except for the ASCII blocks. |
| * Plus 1 so that we don't drop this block during compaction. |
| * Plus as many as needed for lead surrogate code points. |
| */ |
| /* i==newTrie->dataNullOffset */ |
| map[i++] = |
| (0x110000>>UTRIE2_SHIFT_2) - |
| (0x80>>UTRIE2_SHIFT_2) + |
| 1 + |
| UTRIE2_LSCP_INDEX_2_LENGTH; |
| j += UTRIE2_DATA_BLOCK_LENGTH; |
| for(; j<UNEWTRIE2_DATA_START_OFFSET; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) { |
| map[i]=0; |
| } |
| |
| /* |
| * set the remaining indexes in the BMP index-2 block |
| * to the null data block |
| */ |
| for(i=0x80>>UTRIE2_SHIFT_2; i<UTRIE2_INDEX_2_BMP_LENGTH; ++i) { |
| index2[i]=UNEWTRIE2_DATA_NULL_OFFSET; |
| } |
| |
| /* |
| * Fill the index gap with impossible values so that compaction |
| * does not overlap other index-2 blocks with the gap. |
| */ |
| for(i=0; i<UNEWTRIE2_INDEX_GAP_LENGTH; ++i) { |
| index2[UNEWTRIE2_INDEX_GAP_OFFSET+i]=-1; |
| } |
| |
| /* set the indexes in the null index-2 block */ |
| for(i=0; i<UTRIE2_INDEX_2_BLOCK_LENGTH; ++i) { |
| index2[UNEWTRIE2_INDEX_2_NULL_OFFSET+i]=UNEWTRIE2_DATA_NULL_OFFSET; |
| } |
| index2NullOffset=UNEWTRIE2_INDEX_2_NULL_OFFSET; |
| index2Length=UNEWTRIE2_INDEX_2_START_OFFSET; |
| |
| /* set the index-1 indexes for the linear index-2 block */ |
| for(i=0, j=0; |
| i<UTRIE2_OMITTED_BMP_INDEX_1_LENGTH; |
| ++i, j+=UTRIE2_INDEX_2_BLOCK_LENGTH |
| ) { |
| index1[i]=j; |
| } |
| |
| /* set the remaining index-1 indexes to the null index-2 block */ |
| for(; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) { |
| index1[i]=UNEWTRIE2_INDEX_2_NULL_OFFSET; |
| } |
| |
| /* |
| * Preallocate and reset data for U+0080..U+07ff, |
| * for 2-byte UTF-8 which will be compacted in 64-blocks |
| * even if UTRIE2_DATA_BLOCK_LENGTH is smaller. |
| */ |
| for(i=0x80; i<0x800; i+=UTRIE2_DATA_BLOCK_LENGTH) { |
| set(i, initialValue); |
| } |
| |
| } |
| |
| |
| /** |
| * Create a new build time (modifiable) Trie2 whose contents are the same as the source Trie2. |
| * |
| * @param source the source Trie2. Its contents will be copied into the new Trie2. |
| */ |
| public Trie2Writable(Trie2 source) { |
| init(source.initialValue, source.errorValue); |
| |
| for (Range r: source) { |
| setRange(r, true); |
| } |
| } |
| |
| |
| private boolean isInNullBlock(int c, boolean forLSCP) { |
| int i2, block; |
| |
| if(Character.isHighSurrogate((char)c) && forLSCP) { |
| i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+ |
| (c>>UTRIE2_SHIFT_2); |
| } else { |
| i2=index1[c>>UTRIE2_SHIFT_1]+ |
| ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK); |
| } |
| block=index2[i2]; |
| return (block==dataNullOffset); |
| } |
| |
| private int allocIndex2Block() { |
| int newBlock, newTop; |
| |
| newBlock=index2Length; |
| newTop=newBlock+UTRIE2_INDEX_2_BLOCK_LENGTH; |
| if(newTop > index2.length) { |
| throw new IllegalStateException("Internal error in Trie2 creation."); |
| /* |
| * Should never occur. |
| * Either UTRIE2_MAX_BUILD_TIME_INDEX_LENGTH is incorrect, |
| * or the code writes more values than should be possible. |
| */ |
| } |
| index2Length=newTop; |
| System.arraycopy(index2, index2NullOffset, index2, newBlock, UTRIE2_INDEX_2_BLOCK_LENGTH); |
| return newBlock; |
| } |
| |
| private int getIndex2Block(int c, boolean forLSCP) { |
| int i1, i2; |
| |
| if(c>=0xd800 && c<0xdc00 && forLSCP) { |
| return UTRIE2_LSCP_INDEX_2_OFFSET; |
| } |
| |
| i1=c>>UTRIE2_SHIFT_1; |
| i2=index1[i1]; |
| if(i2==index2NullOffset) { |
| i2=allocIndex2Block(); |
| index1[i1]=i2; |
| } |
| return i2; |
| } |
| |
| private int allocDataBlock(int copyBlock) { |
| int newBlock, newTop; |
| |
| if(firstFreeBlock!=0) { |
| /* get the first free block */ |
| newBlock=firstFreeBlock; |
| firstFreeBlock=-map[newBlock>>UTRIE2_SHIFT_2]; |
| } else { |
| /* get a new block from the high end */ |
| newBlock=dataLength; |
| newTop=newBlock+UTRIE2_DATA_BLOCK_LENGTH; |
| if(newTop>dataCapacity) { |
| /* out of memory in the data array */ |
| int capacity; |
| int[] newData; |
| |
| if(dataCapacity<UNEWTRIE2_MEDIUM_DATA_LENGTH) { |
| capacity=UNEWTRIE2_MEDIUM_DATA_LENGTH; |
| } else if(dataCapacity<UNEWTRIE2_MAX_DATA_LENGTH) { |
| capacity=UNEWTRIE2_MAX_DATA_LENGTH; |
| } else { |
| /* |
| * Should never occur. |
| * Either UNEWTRIE2_MAX_DATA_LENGTH is incorrect, |
| * or the code writes more values than should be possible. |
| */ |
| throw new IllegalStateException("Internal error in Trie2 creation."); |
| } |
| newData = new int[capacity]; |
| System.arraycopy(data, 0, newData, 0, dataLength); |
| data=newData; |
| dataCapacity=capacity; |
| } |
| dataLength=newTop; |
| } |
| System.arraycopy(data, copyBlock, data, newBlock, UTRIE2_DATA_BLOCK_LENGTH); |
| map[newBlock>>UTRIE2_SHIFT_2]=0; |
| return newBlock; |
| } |
| |
| |
| /* call when the block's reference counter reaches 0 */ |
| private void releaseDataBlock(int block) { |
| /* put this block at the front of the free-block chain */ |
| map[block>>UTRIE2_SHIFT_2]=-firstFreeBlock; |
| firstFreeBlock=block; |
| } |
| |
| |
| private boolean isWritableBlock(int block) { |
| return (block!=dataNullOffset && 1==map[block>>UTRIE2_SHIFT_2]); |
| } |
| |
| private void setIndex2Entry(int i2, int block) { |
| int oldBlock; |
| ++map[block>>UTRIE2_SHIFT_2]; /* increment first, in case block==oldBlock! */ |
| oldBlock=index2[i2]; |
| if(0 == --map[oldBlock>>UTRIE2_SHIFT_2]) { |
| releaseDataBlock(oldBlock); |
| } |
| index2[i2]=block; |
| } |
| |
| |
| /** |
| * No error checking for illegal arguments. |
| * |
| * @internal |
| */ |
| private int getDataBlock(int c, boolean forLSCP) { |
| int i2, oldBlock, newBlock; |
| |
| i2=getIndex2Block(c, forLSCP); |
| |
| i2+=(c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK; |
| oldBlock=index2[i2]; |
| if(isWritableBlock(oldBlock)) { |
| return oldBlock; |
| } |
| |
| /* allocate a new data block */ |
| newBlock=allocDataBlock(oldBlock); |
| setIndex2Entry(i2, newBlock); |
| return newBlock; |
| } |
| /** |
| * Set a value for a code point. |
| * |
| * @param c the code point |
| * @param value the value |
| */ |
| public Trie2Writable set(int c, int value) { |
| if (c<0 || c>0x10ffff) { |
| throw new IllegalArgumentException("Invalid code point."); |
| } |
| set(c, true, value); |
| fHash = 0; |
| return this; |
| } |
| |
| private Trie2Writable set(int c, boolean forLSCP, int value) { |
| int block; |
| if (isCompacted) { |
| uncompact(); |
| } |
| block = getDataBlock(c, forLSCP); |
| data[block + (c&UTRIE2_DATA_MASK)] = value; |
| return this; |
| } |
| |
| |
| /* |
| * Uncompact a compacted Trie2Writable. |
| * This is needed if a the WritableTrie2 was compacted in preparation for creating a read-only |
| * Trie2, and then is subsequently altered. |
| * |
| * The structure is a bit awkward - it would be cleaner to leave the original |
| * Trie2 unaltered - but compacting in place was taken directly from the ICU4C code. |
| * |
| * The approach is to create a new (uncompacted) Trie2Writable from this one, then transfer |
| * the guts from the new to the old. |
| */ |
| private void uncompact() { |
| Trie2Writable tempTrie = new Trie2Writable(this); |
| |
| // Members from Trie2Writable |
| this.index1 = tempTrie.index1; |
| this.index2 = tempTrie.index2; |
| this.data = tempTrie.data; |
| this.index2Length = tempTrie.index2Length; |
| this.dataCapacity = tempTrie.dataCapacity; |
| this.isCompacted = tempTrie.isCompacted; |
| |
| // Members From Trie2 |
| this.header = tempTrie.header; |
| this.index = tempTrie.index; |
| this.data16 = tempTrie.data16; |
| this.data32 = tempTrie.data32; |
| this.indexLength = tempTrie.indexLength; |
| this.dataLength = tempTrie.dataLength; |
| this.index2NullOffset = tempTrie.index2NullOffset; |
| this.initialValue = tempTrie.initialValue; |
| this.errorValue = tempTrie.errorValue; |
| this.highStart = tempTrie.highStart; |
| this.highValueIndex = tempTrie.highValueIndex; |
| this.dataNullOffset = tempTrie.dataNullOffset; |
| } |
| |
| |
| private void writeBlock(int block, int value) { |
| int limit=block+UTRIE2_DATA_BLOCK_LENGTH; |
| while(block<limit) { |
| data[block++]=value; |
| } |
| } |
| |
| /** |
| * initialValue is ignored if overwrite=TRUE |
| * @internal |
| */ |
| private void fillBlock(int block, /*UChar32*/ int start, /*UChar32*/ int limit, |
| int value, int initialValue, boolean overwrite) { |
| int i; |
| int pLimit = block+limit; |
| if(overwrite) { |
| for (i=block+start; i<pLimit; i++) { |
| data[i] = value; |
| } |
| } else { |
| for (i=block+start; i<pLimit; i++) { |
| if(data[i]==initialValue) { |
| data[i]=value; |
| } |
| } |
| } |
| } |
| |
| /** |
| * Set a value in a range of code points [start..end]. |
| * All code points c with start<=c<=end will get the value if |
| * overwrite is TRUE or if the old value is the initial value. |
| * |
| * @param start the first code point to get the value |
| * @param end the last code point to get the value (inclusive) |
| * @param value the value |
| * @param overwrite flag for whether old non-initial values are to be overwritten |
| */ |
| public Trie2Writable setRange(int start, int end, |
| int value, boolean overwrite) { |
| /* |
| * repeat value in [start..end] |
| * mark index values for repeat-data blocks by setting bit 31 of the index values |
| * fill around existing values if any, if(overwrite) |
| */ |
| int block, rest, repeatBlock; |
| int /*UChar32*/ limit; |
| |
| if(start>0x10ffff || start<0 || end>0x10ffff || end<0 || start>end) { |
| throw new IllegalArgumentException("Invalid code point range."); |
| } |
| if(!overwrite && value==initialValue) { |
| return this; /* nothing to do */ |
| } |
| fHash = 0; |
| if(isCompacted) { |
| this.uncompact(); |
| } |
| |
| limit=end+1; |
| if((start&UTRIE2_DATA_MASK) != 0) { |
| int /*UChar32*/ nextStart; |
| |
| /* set partial block at [start..following block boundary[ */ |
| block=getDataBlock(start, true); |
| |
| nextStart=(start+UTRIE2_DATA_BLOCK_LENGTH)&~UTRIE2_DATA_MASK; |
| if(nextStart<=limit) { |
| fillBlock(block, start&UTRIE2_DATA_MASK, UTRIE2_DATA_BLOCK_LENGTH, |
| value, initialValue, overwrite); |
| start=nextStart; |
| } else { |
| fillBlock(block, start&UTRIE2_DATA_MASK, limit&UTRIE2_DATA_MASK, |
| value, initialValue, overwrite); |
| return this; |
| } |
| } |
| |
| /* number of positions in the last, partial block */ |
| rest=limit&UTRIE2_DATA_MASK; |
| |
| /* round down limit to a block boundary */ |
| limit&=~UTRIE2_DATA_MASK; |
| |
| /* iterate over all-value blocks */ |
| if(value==initialValue) { |
| repeatBlock=dataNullOffset; |
| } else { |
| repeatBlock=-1; |
| } |
| |
| while(start<limit) { |
| int i2; |
| boolean setRepeatBlock=false; |
| |
| if(value==initialValue && isInNullBlock(start, true)) { |
| start+=UTRIE2_DATA_BLOCK_LENGTH; /* nothing to do */ |
| continue; |
| } |
| |
| /* get index value */ |
| i2=getIndex2Block(start, true); |
| i2+=(start>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK; |
| block=index2[i2]; |
| if(isWritableBlock(block)) { |
| /* already allocated */ |
| if(overwrite && block>=UNEWTRIE2_DATA_0800_OFFSET) { |
| /* |
| * We overwrite all values, and it's not a |
| * protected (ASCII-linear or 2-byte UTF-8) block: |
| * replace with the repeatBlock. |
| */ |
| setRepeatBlock=true; |
| } else { |
| /* !overwrite, or protected block: just write the values into this block */ |
| fillBlock(block, |
| 0, UTRIE2_DATA_BLOCK_LENGTH, |
| value, initialValue, overwrite); |
| } |
| } else if(data[block]!=value && (overwrite || block==dataNullOffset)) { |
| /* |
| * Set the repeatBlock instead of the null block or previous repeat block: |
| * |
| * If !isWritableBlock() then all entries in the block have the same value |
| * because it's the null block or a range block (the repeatBlock from a previous |
| * call to utrie2_setRange32()). |
| * No other blocks are used multiple times before compacting. |
| * |
| * The null block is the only non-writable block with the initialValue because |
| * of the repeatBlock initialization above. (If value==initialValue, then |
| * the repeatBlock will be the null data block.) |
| * |
| * We set our repeatBlock if the desired value differs from the block's value, |
| * and if we overwrite any data or if the data is all initial values |
| * (which is the same as the block being the null block, see above). |
| */ |
| setRepeatBlock=true; |
| } |
| if(setRepeatBlock) { |
| if(repeatBlock>=0) { |
| setIndex2Entry(i2, repeatBlock); |
| } else { |
| /* create and set and fill the repeatBlock */ |
| repeatBlock=getDataBlock(start, true); |
| writeBlock(repeatBlock, value); |
| } |
| } |
| |
| start+=UTRIE2_DATA_BLOCK_LENGTH; |
| } |
| |
| if(rest>0) { |
| /* set partial block at [last block boundary..limit[ */ |
| block=getDataBlock(start, true); |
| fillBlock(block, 0, rest, value, initialValue, overwrite); |
| } |
| |
| return this; |
| } |
| |
| /** |
| * Set the values from a Trie2.Range. |
| * |
| * All code points within the range will get the value if |
| * overwrite is TRUE or if the old value is the initial value. |
| * |
| * Ranges with the lead surrogate flag set will set the alternate |
| * lead-surrogate values in the Trie, rather than the code point values. |
| * |
| * This function is intended to work with the ranges produced when iterating |
| * the contents of a source Trie. |
| * |
| * @param range contains the range of code points and the value to be set. |
| * @param overwrite flag for whether old non-initial values are to be overwritten |
| */ |
| public Trie2Writable setRange(Trie2.Range range, boolean overwrite) { |
| fHash = 0; |
| if (range.leadSurrogate) { |
| for (int c=range.startCodePoint; c<=range.endCodePoint; c++) { |
| if (overwrite || getFromU16SingleLead((char)c) == this.initialValue) { |
| setForLeadSurrogateCodeUnit((char)c, range.value); |
| } |
| } |
| } else { |
| setRange(range.startCodePoint, range.endCodePoint, range.value, overwrite); |
| } |
| return this; |
| } |
| |
| /** |
| * Set a value for a UTF-16 code unit. |
| * Note that a Trie2 stores separate values for |
| * supplementary code points in the lead surrogate range |
| * (accessed via the plain set() and get() interfaces) |
| * and for lead surrogate code units. |
| * |
| * The lead surrogate code unit values are set via this function and |
| * read by the function getFromU16SingleLead(). |
| * |
| * For code units outside of the lead surrogate range, this function |
| * behaves identically to set(). |
| * |
| * @param codeUnit A UTF-16 code unit. |
| * @param value the value to be stored in the Trie2. |
| */ |
| public Trie2Writable setForLeadSurrogateCodeUnit(char codeUnit, int value) { |
| fHash = 0; |
| set(codeUnit, false, value); |
| return this; |
| } |
| |
| |
| /** |
| * Get the value for a code point as stored in the Trie2. |
| * |
| * @param codePoint the code point |
| * @return the value |
| */ |
| @Override |
| public int get(int codePoint) { |
| if (codePoint<0 || codePoint>0x10ffff) { |
| return errorValue; |
| } else { |
| return get(codePoint, true); |
| } |
| } |
| |
| |
| private int get(int c, boolean fromLSCP) { |
| int i2, block; |
| |
| if(c>=highStart && (!(c>=0xd800 && c<0xdc00) || fromLSCP)) { |
| return data[dataLength-UTRIE2_DATA_GRANULARITY]; |
| } |
| |
| if((c>=0xd800 && c<0xdc00) && fromLSCP) { |
| i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+ |
| (c>>UTRIE2_SHIFT_2); |
| } else { |
| i2=index1[c>>UTRIE2_SHIFT_1]+ |
| ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK); |
| } |
| block=index2[i2]; |
| return data[block+(c&UTRIE2_DATA_MASK)]; |
| } |
| |
| /** |
| * Get a trie value for a UTF-16 code unit. |
| * |
| * This function returns the same value as get() if the input |
| * character is outside of the lead surrogate range |
| * |
| * There are two values stored in a Trie for inputs in the lead |
| * surrogate range. This function returns the alternate value, |
| * while Trie2.get() returns the main value. |
| * |
| * @param c the code point or lead surrogate value. |
| * @return the value |
| */ |
| @Override |
| public int getFromU16SingleLead(char c) { |
| return get(c, false); |
| } |
| |
| /* compaction --------------------------------------------------------------- */ |
| |
| private boolean equal_int(int[] a, int s, int t, int length) { |
| for (int i=0; i<length; i++) { |
| if (a[s+i] != a[t+i]) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| |
| private int findSameIndex2Block(int index2Length, int otherBlock) { |
| int block; |
| |
| /* ensure that we do not even partially get past index2Length */ |
| index2Length-=UTRIE2_INDEX_2_BLOCK_LENGTH; |
| |
| for(block=0; block<=index2Length; ++block) { |
| if(equal_int(index2, block, otherBlock, UTRIE2_INDEX_2_BLOCK_LENGTH)) { |
| return block; |
| } |
| } |
| return -1; |
| } |
| |
| |
| private int findSameDataBlock(int dataLength, int otherBlock, int blockLength) { |
| int block; |
| |
| /* ensure that we do not even partially get past dataLength */ |
| dataLength-=blockLength; |
| |
| for(block=0; block<=dataLength; block+=UTRIE2_DATA_GRANULARITY) { |
| if(equal_int(data, block, otherBlock, blockLength)) { |
| return block; |
| } |
| } |
| return -1; |
| } |
| |
| /* |
| * Find the start of the last range in the trie by enumerating backward. |
| * Indexes for supplementary code points higher than this will be omitted. |
| */ |
| private int findHighStart(int highValue) { |
| |
| int value; |
| int c, prev; |
| int i1, i2, j, i2Block, prevI2Block, block, prevBlock; |
| |
| |
| /* set variables for previous range */ |
| if(highValue==initialValue) { |
| prevI2Block=index2NullOffset; |
| prevBlock=dataNullOffset; |
| } else { |
| prevI2Block=-1; |
| prevBlock=-1; |
| } |
| prev=0x110000; |
| |
| /* enumerate index-2 blocks */ |
| i1=UNEWTRIE2_INDEX_1_LENGTH; |
| c=prev; |
| while(c>0) { |
| i2Block=index1[--i1]; |
| if(i2Block==prevI2Block) { |
| /* the index-2 block is the same as the previous one, and filled with highValue */ |
| c-=UTRIE2_CP_PER_INDEX_1_ENTRY; |
| continue; |
| } |
| prevI2Block=i2Block; |
| if(i2Block==index2NullOffset) { |
| /* this is the null index-2 block */ |
| if(highValue!=initialValue) { |
| return c; |
| } |
| c-=UTRIE2_CP_PER_INDEX_1_ENTRY; |
| } else { |
| /* enumerate data blocks for one index-2 block */ |
| for(i2=UTRIE2_INDEX_2_BLOCK_LENGTH; i2>0;) { |
| block=index2[i2Block+ --i2]; |
| if(block==prevBlock) { |
| /* the block is the same as the previous one, and filled with highValue */ |
| c-=UTRIE2_DATA_BLOCK_LENGTH; |
| continue; |
| } |
| prevBlock=block; |
| if(block==dataNullOffset) { |
| /* this is the null data block */ |
| if(highValue!=initialValue) { |
| return c; |
| } |
| c-=UTRIE2_DATA_BLOCK_LENGTH; |
| } else { |
| for(j=UTRIE2_DATA_BLOCK_LENGTH; j>0;) { |
| value=data[block+ --j]; |
| if(value!=highValue) { |
| return c; |
| } |
| --c; |
| } |
| } |
| } |
| } |
| } |
| |
| /* deliver last range */ |
| return 0; |
| } |
| |
| /* |
| * Compact a build-time trie. |
| * |
| * The compaction |
| * - removes blocks that are identical with earlier ones |
| * - overlaps adjacent blocks as much as possible (if overlap==TRUE) |
| * - moves blocks in steps of the data granularity |
| * - moves and overlaps blocks that overlap with multiple values in the overlap region |
| * |
| * It does not |
| * - try to move and overlap blocks that are not already adjacent |
| */ |
| private void compactData() { |
| int start, newStart, movedStart; |
| int blockLength, overlap; |
| int i, mapIndex, blockCount; |
| |
| /* do not compact linear-ASCII data */ |
| newStart=UTRIE2_DATA_START_OFFSET; |
| for(start=0, i=0; start<newStart; start+=UTRIE2_DATA_BLOCK_LENGTH, ++i) { |
| map[i]=start; |
| } |
| |
| /* |
| * Start with a block length of 64 for 2-byte UTF-8, |
| * then switch to UTRIE2_DATA_BLOCK_LENGTH. |
| */ |
| blockLength=64; |
| blockCount=blockLength>>UTRIE2_SHIFT_2; |
| for(start=newStart; start<dataLength;) { |
| /* |
| * start: index of first entry of current block |
| * newStart: index where the current block is to be moved |
| * (right after current end of already-compacted data) |
| */ |
| if(start==UNEWTRIE2_DATA_0800_OFFSET) { |
| blockLength=UTRIE2_DATA_BLOCK_LENGTH; |
| blockCount=1; |
| } |
| |
| /* skip blocks that are not used */ |
| if(map[start>>UTRIE2_SHIFT_2]<=0) { |
| /* advance start to the next block */ |
| start+=blockLength; |
| |
| /* leave newStart with the previous block! */ |
| continue; |
| } |
| |
| /* search for an identical block */ |
| movedStart=findSameDataBlock(newStart, start, blockLength); |
| if(movedStart >= 0) { |
| /* found an identical block, set the other block's index value for the current block */ |
| for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) { |
| map[mapIndex++]=movedStart; |
| movedStart+=UTRIE2_DATA_BLOCK_LENGTH; |
| } |
| |
| /* advance start to the next block */ |
| start+=blockLength; |
| |
| /* leave newStart with the previous block! */ |
| continue; |
| } |
| |
| /* see if the beginning of this block can be overlapped with the end of the previous block */ |
| /* look for maximum overlap (modulo granularity) with the previous, adjacent block */ |
| for(overlap=blockLength-UTRIE2_DATA_GRANULARITY; |
| overlap>0 && !equal_int(data, (newStart-overlap), start, overlap); |
| overlap-=UTRIE2_DATA_GRANULARITY) {} |
| |
| if(overlap>0 || newStart<start) { |
| /* some overlap, or just move the whole block */ |
| movedStart=newStart-overlap; |
| for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) { |
| map[mapIndex++]=movedStart; |
| movedStart+=UTRIE2_DATA_BLOCK_LENGTH; |
| } |
| |
| /* move the non-overlapping indexes to their new positions */ |
| start+=overlap; |
| for(i=blockLength-overlap; i>0; --i) { |
| data[newStart++]=data[start++]; |
| } |
| } else /* no overlap && newStart==start */ { |
| for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) { |
| map[mapIndex++]=start; |
| start+=UTRIE2_DATA_BLOCK_LENGTH; |
| } |
| newStart=start; |
| } |
| } |
| |
| /* now adjust the index-2 table */ |
| for(i=0; i<index2Length; ++i) { |
| if(i==UNEWTRIE2_INDEX_GAP_OFFSET) { |
| /* Gap indexes are invalid (-1). Skip over the gap. */ |
| i+=UNEWTRIE2_INDEX_GAP_LENGTH; |
| } |
| index2[i]=map[index2[i]>>UTRIE2_SHIFT_2]; |
| } |
| dataNullOffset=map[dataNullOffset>>UTRIE2_SHIFT_2]; |
| |
| /* ensure dataLength alignment */ |
| while((newStart&(UTRIE2_DATA_GRANULARITY-1))!=0) { |
| data[newStart++]=initialValue; |
| } |
| |
| if (UTRIE2_DEBUG) { |
| /* we saved some space */ |
| System.out.printf("compacting UTrie2: count of 32-bit data words %d->%d\n", |
| dataLength, newStart); |
| } |
| |
| dataLength=newStart; |
| } |
| |
| private void compactIndex2() { |
| int i, start, newStart, movedStart, overlap; |
| |
| /* do not compact linear-BMP index-2 blocks */ |
| newStart=UTRIE2_INDEX_2_BMP_LENGTH; |
| for(start=0, i=0; start<newStart; start+=UTRIE2_INDEX_2_BLOCK_LENGTH, ++i) { |
| map[i]=start; |
| } |
| |
| /* Reduce the index table gap to what will be needed at runtime. */ |
| newStart+=UTRIE2_UTF8_2B_INDEX_2_LENGTH+((highStart-0x10000)>>UTRIE2_SHIFT_1); |
| |
| for(start=UNEWTRIE2_INDEX_2_NULL_OFFSET; start<index2Length;) { |
| /* |
| * start: index of first entry of current block |
| * newStart: index where the current block is to be moved |
| * (right after current end of already-compacted data) |
| */ |
| |
| /* search for an identical block */ |
| if( (movedStart=findSameIndex2Block(newStart, start)) |
| >=0 |
| ) { |
| /* found an identical block, set the other block's index value for the current block */ |
| map[start>>UTRIE2_SHIFT_1_2]=movedStart; |
| |
| /* advance start to the next block */ |
| start+=UTRIE2_INDEX_2_BLOCK_LENGTH; |
| |
| /* leave newStart with the previous block! */ |
| continue; |
| } |
| |
| /* see if the beginning of this block can be overlapped with the end of the previous block */ |
| /* look for maximum overlap with the previous, adjacent block */ |
| for(overlap=UTRIE2_INDEX_2_BLOCK_LENGTH-1; |
| overlap>0 && !equal_int(index2, newStart-overlap, start, overlap); |
| --overlap) {} |
| |
| if(overlap>0 || newStart<start) { |
| /* some overlap, or just move the whole block */ |
| map[start>>UTRIE2_SHIFT_1_2]=newStart-overlap; |
| |
| /* move the non-overlapping indexes to their new positions */ |
| start+=overlap; |
| for(i=UTRIE2_INDEX_2_BLOCK_LENGTH-overlap; i>0; --i) { |
| index2[newStart++]=index2[start++]; |
| } |
| } else /* no overlap && newStart==start */ { |
| map[start>>UTRIE2_SHIFT_1_2]=start; |
| start+=UTRIE2_INDEX_2_BLOCK_LENGTH; |
| newStart=start; |
| } |
| } |
| |
| /* now adjust the index-1 table */ |
| for(i=0; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) { |
| index1[i]=map[index1[i]>>UTRIE2_SHIFT_1_2]; |
| } |
| index2NullOffset=map[index2NullOffset>>UTRIE2_SHIFT_1_2]; |
| |
| /* |
| * Ensure data table alignment: |
| * Needs to be granularity-aligned for 16-bit trie |
| * (so that dataMove will be down-shiftable), |
| * and 2-aligned for uint32_t data. |
| */ |
| while((newStart&((UTRIE2_DATA_GRANULARITY-1)|1))!=0) { |
| /* Arbitrary value: 0x3fffc not possible for real data. */ |
| index2[newStart++]=0x0000ffff<<UTRIE2_INDEX_SHIFT; |
| } |
| |
| if (UTRIE2_DEBUG) { |
| /* we saved some space */ |
| System.out.printf("compacting UTrie2: count of 16-bit index-2 words %d->%d\n", |
| index2Length, newStart); |
| } |
| |
| index2Length=newStart; |
| } |
| |
| private void compactTrie() { |
| int localHighStart; |
| int suppHighStart; |
| int highValue; |
| |
| /* find highStart and round it up */ |
| highValue=get(0x10ffff); |
| localHighStart=findHighStart(highValue); |
| localHighStart=(localHighStart+(UTRIE2_CP_PER_INDEX_1_ENTRY-1))&~(UTRIE2_CP_PER_INDEX_1_ENTRY-1); |
| if(localHighStart==0x110000) { |
| highValue=errorValue; |
| } |
| |
| /* |
| * Set trie->highStart only after utrie2_get32(trie, highStart). |
| * Otherwise utrie2_get32(trie, highStart) would try to read the highValue. |
| */ |
| this.highStart=localHighStart; |
| |
| if (UTRIE2_DEBUG) { |
| System.out.printf("UTrie2: highStart U+%04x highValue 0x%x initialValue 0x%x\n", |
| highStart, highValue, initialValue); |
| } |
| |
| if(highStart<0x110000) { |
| /* Blank out [highStart..10ffff] to release associated data blocks. */ |
| suppHighStart= highStart<=0x10000 ? 0x10000 : highStart; |
| setRange(suppHighStart, 0x10ffff, initialValue, true); |
| } |
| |
| compactData(); |
| if(highStart>0x10000) { |
| compactIndex2(); |
| } else { |
| if (UTRIE2_DEBUG) { |
| System.out.printf("UTrie2: highStart U+%04x count of 16-bit index-2 words %d->%d\n", |
| highStart, index2Length, UTRIE2_INDEX_1_OFFSET); |
| } |
| } |
| |
| /* |
| * Store the highValue in the data array and round up the dataLength. |
| * Must be done after compactData() because that assumes that dataLength |
| * is a multiple of UTRIE2_DATA_BLOCK_LENGTH. |
| */ |
| data[dataLength++]=highValue; |
| while((dataLength&(UTRIE2_DATA_GRANULARITY-1))!=0) { |
| data[dataLength++]=initialValue; |
| } |
| |
| isCompacted=true; |
| } |
| |
| |
| /** |
| * Produce an optimized, read-only Trie2_16 from this writable Trie. |
| * The data values outside of the range that will fit in a 16 bit |
| * unsigned value will be truncated. |
| */ |
| public Trie2_16 toTrie2_16() { |
| Trie2_16 frozenTrie = new Trie2_16(); |
| freeze(frozenTrie, ValueWidth.BITS_16); |
| return frozenTrie; |
| } |
| |
| |
| /** |
| * Produce an optimized, read-only Trie2_32 from this writable Trie. |
| * |
| */ |
| public Trie2_32 toTrie2_32() { |
| Trie2_32 frozenTrie = new Trie2_32(); |
| freeze(frozenTrie, ValueWidth.BITS_32); |
| return frozenTrie; |
| } |
| |
| |
| /** |
| * Maximum length of the runtime index array. |
| * Limited by its own 16-bit index values, and by uint16_t UTrie2Header.indexLength. |
| * (The actual maximum length is lower, |
| * (0x110000>>UTRIE2_SHIFT_2)+UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH.) |
| */ |
| private static final int UTRIE2_MAX_INDEX_LENGTH = 0xffff; |
| |
| /** |
| * Maximum length of the runtime data array. |
| * Limited by 16-bit index values that are left-shifted by UTRIE2_INDEX_SHIFT, |
| * and by uint16_t UTrie2Header.shiftedDataLength. |
| */ |
| private static final int UTRIE2_MAX_DATA_LENGTH = 0xffff<<UTRIE2_INDEX_SHIFT; |
| |
| /* Compact the data and then populate an optimized read-only Trie. */ |
| private void freeze(Trie2 dest, ValueWidth valueBits) { |
| int i; |
| int allIndexesLength; |
| int dataMove; /* >0 if the data is moved to the end of the index array */ |
| |
| |
| /* compact if necessary */ |
| if(!isCompacted) { |
| compactTrie(); |
| } |
| |
| if(highStart<=0x10000) { |
| allIndexesLength=UTRIE2_INDEX_1_OFFSET; |
| } else { |
| allIndexesLength=index2Length; |
| } |
| if(valueBits==ValueWidth.BITS_16) { |
| dataMove=allIndexesLength; |
| } else { |
| dataMove=0; |
| } |
| |
| /* are indexLength and dataLength within limits? */ |
| if( /* for unshifted indexLength */ |
| allIndexesLength>UTRIE2_MAX_INDEX_LENGTH || |
| /* for unshifted dataNullOffset */ |
| (dataMove+dataNullOffset)>0xffff || |
| /* for unshifted 2-byte UTF-8 index-2 values */ |
| (dataMove+UNEWTRIE2_DATA_0800_OFFSET)>0xffff || |
| /* for shiftedDataLength */ |
| (dataMove+dataLength)>UTRIE2_MAX_DATA_LENGTH) { |
| throw new UnsupportedOperationException("Trie2 data is too large."); |
| } |
| |
| /* calculate the sizes of, and allocate, the index and data arrays */ |
| int indexLength = allIndexesLength; |
| if (valueBits==ValueWidth.BITS_16) { |
| indexLength += dataLength; |
| } else { |
| dest.data32 = new int[dataLength]; |
| } |
| dest.index = new char[indexLength]; |
| |
| dest.indexLength = allIndexesLength; |
| dest.dataLength = dataLength; |
| if(highStart<=0x10000) { |
| dest.index2NullOffset = 0xffff; |
| } else { |
| dest.index2NullOffset = UTRIE2_INDEX_2_OFFSET + index2NullOffset; |
| } |
| dest.initialValue = initialValue; |
| dest.errorValue = errorValue; |
| dest.highStart = highStart; |
| dest.highValueIndex = dataMove + dataLength - UTRIE2_DATA_GRANULARITY; |
| dest.dataNullOffset = (dataMove+dataNullOffset); |
| |
| // Create a header and set the its fields. |
| // (This is only used in the event that we serialize the Trie, but is |
| // convenient to do here.) |
| dest.header = new Trie2.UTrie2Header(); |
| dest.header.signature = 0x54726932; /* "Tri2" */ |
| dest.header.options = valueBits==ValueWidth.BITS_16 ? 0 : 1; |
| dest.header.indexLength = dest.indexLength; |
| dest.header.shiftedDataLength = dest.dataLength>>UTRIE2_INDEX_SHIFT; |
| dest.header.index2NullOffset = dest.index2NullOffset; |
| dest.header.dataNullOffset = dest.dataNullOffset; |
| dest.header.shiftedHighStart = dest.highStart>>UTRIE2_SHIFT_1; |
| |
| |
| |
| /* write the index-2 array values shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove */ |
| int destIdx = 0; |
| for(i=0; i<UTRIE2_INDEX_2_BMP_LENGTH; i++) { |
| dest.index[destIdx++] = (char)((index2[i]+dataMove) >> UTRIE2_INDEX_SHIFT); |
| } |
| if (UTRIE2_DEBUG) { |
| System.out.println("\n\nIndex2 for BMP limit is " + Integer.toHexString(destIdx)); |
| } |
| |
| /* write UTF-8 2-byte index-2 values, not right-shifted */ |
| for(i=0; i<(0xc2-0xc0); ++i) { /* C0..C1 */ |
| dest.index[destIdx++] = (char)(dataMove+UTRIE2_BAD_UTF8_DATA_OFFSET); |
| } |
| for(; i<(0xe0-0xc0); ++i) { /* C2..DF */ |
| dest.index[destIdx++]=(char)(dataMove+index2[i<<(6-UTRIE2_SHIFT_2)]); |
| } |
| if (UTRIE2_DEBUG) { |
| System.out.println("Index2 for UTF-8 2byte values limit is " + Integer.toHexString(destIdx)); |
| } |
| |
| if(highStart>0x10000) { |
| int index1Length = (highStart-0x10000)>>UTRIE2_SHIFT_1; |
| int index2Offset = UTRIE2_INDEX_2_BMP_LENGTH + UTRIE2_UTF8_2B_INDEX_2_LENGTH + index1Length; |
| |
| /* write 16-bit index-1 values for supplementary code points */ |
| //p=(uint32_t *)newTrie->index1+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH; |
| for(i=0; i<index1Length; i++) { |
| //*dest16++=(uint16_t)(UTRIE2_INDEX_2_OFFSET + *p++); |
| dest.index[destIdx++] = (char)(UTRIE2_INDEX_2_OFFSET + index1[i+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH]); |
| } |
| if (UTRIE2_DEBUG) { |
| System.out.println("Index 1 for supplementals, limit is " + Integer.toHexString(destIdx)); |
| } |
| |
| /* |
| * write the index-2 array values for supplementary code points, |
| * shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove |
| */ |
| for(i=0; i<index2Length-index2Offset; i++) { |
| dest.index[destIdx++] = (char)((dataMove + index2[index2Offset+i])>>UTRIE2_INDEX_SHIFT); |
| } |
| if (UTRIE2_DEBUG) { |
| System.out.println("Index 2 for supplementals, limit is " + Integer.toHexString(destIdx)); |
| } |
| } |
| |
| /* write the 16/32-bit data array */ |
| switch(valueBits) { |
| case BITS_16: |
| /* write 16-bit data values */ |
| assert(destIdx == dataMove); |
| dest.data16 = destIdx; |
| for(i=0; i<dataLength; i++) { |
| dest.index[destIdx++] = (char)data[i]; |
| } |
| break; |
| case BITS_32: |
| /* write 32-bit data values */ |
| for (i=0; i<dataLength; i++) { |
| dest.data32[i] = this.data[i]; |
| } |
| break; |
| } |
| // The writable, but compressed, Trie2 stays around unless the caller drops its references to it. |
| } |
| |
| |
| /* Start with allocation of 16k data entries. */ |
| private static final int UNEWTRIE2_INITIAL_DATA_LENGTH = 1<<14; |
| |
| /* Grow about 8x each time. */ |
| private static final int UNEWTRIE2_MEDIUM_DATA_LENGTH = 1<<17; |
| |
| /** The null index-2 block, following the gap in the index-2 table. */ |
| private static final int UNEWTRIE2_INDEX_2_NULL_OFFSET = UNEWTRIE2_INDEX_GAP_OFFSET + UNEWTRIE2_INDEX_GAP_LENGTH; |
| |
| /** The start of allocated index-2 blocks. */ |
| private static final int UNEWTRIE2_INDEX_2_START_OFFSET = UNEWTRIE2_INDEX_2_NULL_OFFSET + UTRIE2_INDEX_2_BLOCK_LENGTH; |
| |
| /** |
| * The null data block. |
| * Length 64=0x40 even if UTRIE2_DATA_BLOCK_LENGTH is smaller, |
| * to work with 6-bit trail bytes from 2-byte UTF-8. |
| */ |
| private static final int UNEWTRIE2_DATA_NULL_OFFSET = UTRIE2_DATA_START_OFFSET; |
| |
| /** The start of allocated data blocks. */ |
| private static final int UNEWTRIE2_DATA_START_OFFSET = UNEWTRIE2_DATA_NULL_OFFSET+0x40; |
| |
| /** |
| * The start of data blocks for U+0800 and above. |
| * Below, compaction uses a block length of 64 for 2-byte UTF-8. |
| * From here on, compaction uses UTRIE2_DATA_BLOCK_LENGTH. |
| * Data values for 0x780 code points beyond ASCII. |
| */ |
| private static final int UNEWTRIE2_DATA_0800_OFFSET = UNEWTRIE2_DATA_START_OFFSET+0x780; |
| |
| // |
| // Private data members. From struct UNewTrie2 in ICU4C |
| // |
| private int[] index1 = new int[UNEWTRIE2_INDEX_1_LENGTH]; |
| private int[] index2 = new int[UNEWTRIE2_MAX_INDEX_2_LENGTH]; |
| private int[] data; |
| |
| private int index2Length; |
| private int dataCapacity; |
| private int firstFreeBlock; |
| private int index2NullOffset; |
| private boolean isCompacted; |
| |
| |
| /* |
| * Multi-purpose per-data-block table. |
| * |
| * Before compacting: |
| * |
| * Per-data-block reference counters/free-block list. |
| * 0: unused |
| * >0: reference counter (number of index-2 entries pointing here) |
| * <0: next free data block in free-block list |
| * |
| * While compacting: |
| * |
| * Map of adjusted indexes, used in compactData() and compactIndex2(). |
| * Maps from original indexes to new ones. |
| */ |
| private int[] map = new int[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2]; |
| |
| |
| private boolean UTRIE2_DEBUG = false; |
| |
| } |
